unevaluatedItems and unevaluatedProperties are quadratic in instance size

[zhangj23]

Opening this as an issue first rather than a pull request, since CONTRIBUTING asks that larger changes be discussed ahead of time. I have a working patch and tests, but I would rather check the approach is welcome before sending it.

The problem

unevaluatedItems and unevaluatedProperties collect the evaluated indexes or keys into a list, then run a membership test against that list once per instance element. Each test is an O(n) scan, so validating an n-element array or object is O(n^2). Both the 2020-12 and 2019-09 code paths do this.

Timings with time.process_time, alternating base and patched subprocesses, min of 5, validating a list of n integers against {"items": {"type": "integer"}, "unevaluatedItems": false}:

n	current	patched	speedup	current growth	patched growth
200	0.437 ms	0.403 ms	1.1x	-	-
400	1.022 ms	0.784 ms	1.3x	x2.34	x1.95
800	2.562 ms	1.583 ms	1.6x	x2.51	x2.02
1600	7.428 ms	3.215 ms	2.3x	x2.90	x2.03

The growth columns are the real finding: the current code grows about 2.8x per doubling and trending up, the patch grows 2x flat. So the quadratic term is what is being removed, and the gap keeps widening with instance size.

I want to frame this honestly as a pathological-input fix rather than a general throughput win, and it is not free at the small end.

A realistic API-request shape, where unevaluatedProperties sits on each of many small records of two properties, measures about 1.00x. The win needs many keys or items at a single node, such as a 4000-element array or a wide config object.

An empty array or object is about 0.96x, roughly 4 percent slower. I first assumed that was the cost of building the set and gated it on size, but the regression did not move. Measuring directly, it is the extra function call: the membership test now goes through a wrapper that does not exist today, at roughly 47ns per call. So the trade is about 4 percent on tiny instances for the quadratic term on large ones. The set construction is gated regardless, on the length of the internal index list rather than on len(instance), so no new requirement is placed on a custom array type.

The approach I have

For unevaluatedItems the indexes are always integers, so they go straight into a set.

For unevaluatedProperties the keys cannot be hashed unconditionally, because a caller's key only ever needed to support == for the current code to work. So the keys are wrapped in a small helper that keeps the exact str keys in a set and answers a str probe from it, while anything else still scans the list. Only exact str is treated as hashable, via type(key) is str, so a str subclass with a custom __eq__ or __hash__ keeps its existing semantics. Below roughly 20 keys the list scan wins, so the set is only built above that.

What I have verified

Suite is 8280 passed, 232 skipped, exit code 0, identical to main. ruff check . is clean.

Differential testing against main across both drafts, three schema shapes and eight instance shapes, comparing not just pass or fail but the error message, absolute_path and absolute_schema_path. 0 mismatches.

I also checked the cases where the str-only guard matters: a str subclass whose __eq__ returns True for everything, an unhashable key reached through a custom type checker, keys whose __hash__ raises or counts calls, non-str probes that compare equal to a str, bool and int key aliasing, and the gate boundary at 19 through 22 keys.

One correction I would make to my own write-up before any PR: cProfile attributes about 66% of runtime to the keyword frame, which would imply a ceiling near 3x and make the larger numbers look impossible. That figure is a profiler artifact, since per-call overhead inflates the denominator. Measuring the ceiling empirically instead, by deleting the membership loop outright, gives about 8.4x at n=8000, and the patch lands at essentially that ceiling. Happy to include that reasoning or leave it out.

Would you like this as a PR? And if so, do you have a preference between the wrapper approach above and something simpler, for instance always building the set and accepting the change for exotic key types?