Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

unevaluatedItems and unevaluatedProperties are quadratic in instance size

Aperta
  • Qualcosa non va?
#1,536 1 commento 0 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
4/5
Tempo stimato
3-5 giorni
Idoneità per principianti
45/100
Tipo di issue
Bug
Chiarezza
Abbastanza chiara
Stato di attività
Attiva
Stack tecnologico
json, python
Ambito
performance

Direzione di ricerca

Inizia dai punti di ingresso di unevaluatedItems e unevaluatedProperties in entrambi i percorsi del codice, 2020-12 e 2019-09, quindi confronta i controlli correnti di appartenenza alle liste con l’approccio proposto basato su set e wrapper. Esegui l’intera suite di test e ruff check; il lavoro è completato quando non ci sono discrepanze differenziali nei risultati di validazione o nei percorsi di errore, con una crescita migliorata per array e oggetti di grandi dimensioni.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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?

Lingua principale
Python
Stelle
5k
Fork
694
Merge medio
1g 20h
PR unite (30g)
6

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di python-jsonschema/jsonschema

Tutte le issue di python-jsonschema/jsonschema

Issue simili

Altre issue su Python

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.