Even though compiling validators gives pretty good results, it is not the fastest way

<a class="user-mention notranslate" data-hovercard-type="user" data-hovercard-url="/us

Generate validators without dispatching about jsonschema-rs HOT 6 OPEN

stranger6667 commented on June 6, 2024 1

Generate validators without dispatching

from jsonschema-rs.

Comments (6)

macisamuele commented on June 6, 2024 1

I’ll read it carefully in a bit ... but looks very similar to what I eventually had in mind (in order to pay the Value::as_* once and not once per validator)

from jsonschema-rs.

macisamuele commented on June 6, 2024

@Stranger6667 this approach would make the definition of the keywords more involved and dependent on multiple keywords, still it might provide noticeable improvements.

Have you considered the possibility of running all the validators in parallel (via rayon)? On a multicore machine it might provide comparable performances.
Mentioning this because on python working on multiple threads (especially on CPython) is not very effective for CPU-bound operations (GIL contention).

from jsonschema-rs.

Stranger6667 commented on June 6, 2024

Yes, my attempts gave me worse results than a single thread implementation :( But, I believe the problem was that I didn't use any heuristic about when to run validation in parallel and when not. At the moment only items keyword uses it with a somehow estimated condition, which provided a significant performance boost on the test dataset & schema, but still is suboptimal and won't work in other cases (probably it can give performance decline).
I think that it can be properly estimated indeed and we need to consider multiple factors:

The input size. Overhead on spawning threads might be more than the benefit.
The nesting level where threads are started. It is again connected to the input size, i.e. the bigger chunk we can offload to a thread the better. The deeper we are in the validation the smaller these chunks are. However with $ref it can be opposite and we don't know upfront
Available CPUs

I believe that it can be significant speedup, indeed, but implementing a balanced approach (that will be beneficial for most of the cases) will require more investigation & experiments that I was able to do :)

I'll try to organize my thoughts on this matter and will post it here :)

from jsonschema-rs.

Stranger6667 commented on June 6, 2024

I tried to compose a validator manually and compare the results with the current approach. Example schema:

{
    "$schema": "http://json-schema.org/draft-07/schema#",
    "type": "array",
    "items": [
        {
            "type": "number",
            "exclusiveMaximum": 10
        },
        {
            "type": "string",
            "enum": ["hello", "world"]
        },
        {
            "type": "array",
            "minItems": 1,
            "maxItems": 3,
            "items": [
                {"type": "number"},
                {"type": "string"},
                {"type": "boolean"}
            ]
        },
        {
            "type": "object",
            "required": ["a", "b"],
            "minProperties": 3,
            "properties": {
                "a": {"type": ["null", "string"]},
                "b": {"type": ["null", "string"]},
                "c": {"type": ["null", "string"], "default": "abc"}
            },
            "additionalProperties": {"type": "string"}
        },
        {"not": {"type": ["null"]}}
    ]
}

Input data: [9, "hello", [1, "a", true], {"a": "a", "b": "b", "d": "d"}, 42]

Validator code (which is probably incomplete, misses some checks & optimizations):

fn optimal_small_is_valid(instance: &Value) -> bool {
    match instance {
        Value::Array(items) => {
            if let Value::Number(value) = &items[0] {
                if value.as_f64().unwrap() >= 10f64 {
                    return false;
                }
            } else {
                return false;
            }
            if let Value::String(value) = &items[1] {
                if !["hello", "world"].iter().any(|item| item == value) {
                    return false;
                }
            } else {
                return false;
            }
            if let Value::Array(sub_items) = &items[2] {
                let length = sub_items.len();
                if length < 1 {
                    return false;
                }
                if length > 3 {
                    return false;
                }
                if let Value::Number(_) = sub_items[0] {
                } else {
                    return false;
                }
                if let Value::String(_) = sub_items[1] {
                } else {
                    return false;
                }
                if let Value::Bool(_) = sub_items[2] {
                } else {
                    return false;
                }
            } else {
                return false;
            }
            if let Value::Object(map) = &items[3] {
                if map.len() < 3 {
                    return false;
                }
                if !map.contains_key("a") || !map.contains_key("b") {
                    return false;
                }
                for (key, value) in map {
                    match key.as_str() {
                        "a" => match value {
                            Value::Null | Value::String(_) => (),
                            _ => return false,
                        },
                        "b" => match value {
                            Value::Null | Value::String(_) => (),
                            _ => return false,
                        },
                        "c" => match value {
                            Value::Null | Value::String(_) => (),
                            _ => return false,
                        },
                        _ => match value {
                            Value::String(_) => (),
                            _ => return false,
                        },
                    }
                }
            }
            match &items[4] {
                Value::Null => return false,
                _ => (),
            }
            true
        }
        _ => false,
    }
}

Benchmark for a compiled validator: 129.64 ns
Benchmark for the validator above: 36.184 ns

Which is ~x3.58 faster. I think that in general on big input data the benefit will be more significant and even if the validator above is incomplete I think that we can expect a really significant boost

from jsonschema-rs.

macisamuele commented on June 6, 2024

@Stranger6667 : something that might also be worth to mention is that certain keywords have some intrinsic dependencies on others (ie. maxItems is meaningless if type is not array) and so combining them at compile phase would reduce the memory footprint but also contribute to a smaller runtime (so better performances).

from jsonschema-rs.

Stranger6667 commented on June 6, 2024

@macisamuele

I wasn't completely sure what do you mean, but having your message as a start I added some more thoughts here - #63
Could you, please, check it, and let me know if it correlates with what you meant?

from jsonschema-rs.

Generate validators without dispatching about jsonschema-rs HOT 6 OPEN

Comments (6)

Related Issues (20)

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent