[RFC] More efficient ValidationVisitor implementation

[jhgg]

For the ValidationVisitor, in graphql-core I had implemented it in a slightly different way. Running each ValidationVisitor as it walks the AST, instead of walking the AST 22 times.

https://github.com/graphql-python/graphql-core/blob/master/graphql/core/validation/visitor.py

So far, it's been working perfectly. All tests pass without issue, and it looks like running validation runs quite a bit faster too. I didn't do any perf benchmarks comparing them, but the unit tests ran like 30% faster with the new implementation. :O

I could open a PR porting this to graphql-js if interested.

[leebyron]

One thing to consider (which is currently not very well tested in graphql-js now) is that validation should find all issues in a document. I actually had a version which ran each validation visitor during a single walkthrough but found it cumbersome to maintain which of those validations where skipping analysis of subtrees and in a mistake was accidentally omitting entire subtrees for other validators when one validator encountered an error which hid errors.

From a theoretical point of view, walking the AST 22 times with 1 validator each should be operationally equivalent to walking the AST 1 time with 22 validators, so I'm curious if your 30% savings is coming from omitting potential document validation errors, or if this is actually an example of devil-in-the-details performance tweaking.

I would definitely be happy to entertain PRs which prove equivalence and have dramatic performance improvements.

[jhgg]

This does do the proper tracking of omitted sub-trees. So far it's doing good. The performance overhead in the Python implementation was actually the tracking of TypeInfo as it walked the tree. Having to only do that tracking once meant 1/22th of the time spent tracking TypeInfo! Which I think is what led to the speedups.

Also, when I was doing this I didn't properly have the optimization of the actual visitor done yet. So that could have led to more performance gain than there actually was!

[leebyron]

Thanks for prodding me on this, it ended up being a real 4-5x time improvement on an internal stress test. I managed to implement it in a way that composed nicely as well to not disrupt the existing usage of the visitor.

[jhgg]

Cheers! I really liked the way you implemented it as well.