everit-org / json-schema / 586

92%

push

travis-ci

schema loading performance improvement - fixes #348

Context: properly handle references by $id values, whenever we encounter a $ref, after resolving the root schema json,
we have to check if the fragment part of the $ref identifies a subschema by $id. (We have to do it even in cases when
the fragment part is a valid json pointer, because nothing stops a schema author to set $id to be a json pointer string
 - see `ReferenceLookupTest#idAsJsonPointerWorks()` covering this case). To perform this $id check, until now, we always
deep-traversed the entire root schema json for each encountered $ref, looking for a matching $id.

This repeated deep-traversal caused crazy performance problems with extremely big schemas, utilizing a lot of $refs.

This change fixes this problem by deep-traversing each involved json document at most once, at least for document-local
references. `LoadingState` gains a <rootSchema, SubschemaRegistry> map, where SubschemaRegistry is essentially a map of
<$id, subschemaJson> pairs. The registry for a root json is initialized at the first time when it is necessary to look up
a $ref in the json. The registry eagerly deep-traverses the whole root json, and collects the $id -> subschemaJson pairs.
Later the lookup-by-$id part of the $ref lookup process is just an O(1) hashmap lookup.

API changes: no, all affected and newly introduced classes are package-private.

Performance improvements based on local testing: ran a validation with ECV-JsonSchema-tNoBOM.json schema and empty json
instance ({}),
 * with 1.12.0: loading didn't complete (killed the process after 20 minutes)
 * with HEAD: schema loaded & validation passed in ~30 seconds.

34 of 34 new or added lines in 5 files covered. (100.0%)

3152 of 3445 relevant lines covered (91.49%)

0.91 hits per line