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%)