article-linked-lists

CC0-1.0 License

Stars
6

Blazingly Fast Linked Lists

This repository contains a toy validation library built in the Blazingly Fast Linked Lists article.

Usage

use serde_json::json;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    jsonschema::validate(
      // JSON instance to validate
      &json!({
          "name": "John",
          "location": {
               "country": 404
          }
      }),
      // JSON schema
      &json!({
          "properties": {
              "name": {
                  "type": "string"
              },
              "location": {
                  "properties": {
                      "country": {
                          "type": "string"
                      }
                  }
              }
          }
      }),
    ).expect_err("Should fail");
    Ok(())
}
// 404 is not of type string at /location/country

NOTE: To keep the article focused on path tracking, this library uses a single hardcoded schema.

Run benchmarks:

cargo bench

Build flame graph for the "valid/10 levels" benchmark:

cargo flamegraph --bench jsonschema -o valid-10.svg -- --bench "valid/10 levels"

Benchmarks

Here is the performance progression described in the article:

Iteration Commit valid 0 valid 5 valid 10 invalid 0 invalid 5 invalid 10
No tracking a030dcb 36.3 s 553.8 s 1.11 ms 475.2 s 914.8 s 1.48 ms
Naive 9ef7b4c 40.9 s (+12.0%) 2.61 ms (+369.4%) 6.69 ms (+499.6%) 961.2 s (+100.8%) 4.11 ms (+346.8%) 9.07 ms (+502.7%)
&mut Vec 7c94736 40.2 s (-13.1%) 1.24 ms (-46.0%) 2.46 ms (-62.3%) 951.7 s (+3.0%) 2.39 ms (-42.2%) 4.16 ms (-57.8%)
Linked list 91ec92c 35.0 s (-14.8%) 663.5 s (-46.4%) 1.32 ms (-46.6%) 958.9 s (+1.8%) 2.54 ms (+5.1%) 4.58 ms (+9.9%)
Tune capacity 10ae4f1 39.1 s (+11.2%) 667.9 s (+0.5%) 1.30 ms (-1.7%) 899.7 s (-7.5%) 1.96 ms (-23.3%) 3.49 ms (-24.3%)
Single Vec d3d2182 39.3 s (-0.2%) 652.3 s (-2.7%) 1.35 ms (+2.2%) 765.1 s (-14.2%) 1.83 ms (-6.9%) 3.33 ms (-5.9%)