Git Product home page Git Product logo

article-linked-lists's Introduction

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

performance-comparison

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

article-linked-lists's People

Contributors

stranger6667 avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar

Forkers

mqudsi

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.