Generate validators without dispatching

[Stranger6667]

Even though compiling validators gives pretty good results, it is not the fastest way to perform validation in all circumstances. If we know the schema during the build time, then we can generate code that will be more efficient, than the current approach.

For example if we have this schema:

{"type": "string", "maxLength": 5}

then our current approach will basically iterate over a vector of trait objects and call their validate / is_valid methods.

The idea is to generate code like this:

fn is_valid(instance: &Value) -> bool {
    match instance {
        Value::String(value) => value.len() <= 5,
        _ => false
    }
}

https://github.com/horejsek/python-fastjsonschema does this.

[macisamuele]

@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).

[Stranger6667]

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

[Stranger6667]

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

[macisamuele]

@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).

[Stranger6667]

@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?

[macisamuele]

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)