perf: speed up dependency registration in Bom.validate() - #1007
perf: speed up dependency registration in Bom.validate()#1007inspired-geek wants to merge 3 commits into
Conversation
Sorry, something went wrong.
Bom.validate() ensured every component/service had a Dependency entry by calling register_dependency(), which finds existing entries via a linear scan over the dependency collection. Called once per component, this made validation -- and therefore JSON/XML serialization, which always validates -- O(n^2), stalling for minutes on BOMs with thousands of components. Resolve "already registered" through a set of refs instead, keeping the loop linear. Observable output is unchanged; a regression test covers it. Serializing an 8000-component BOM drops from ~6.7s to ~0.6s. Fixes CycloneDX#1006 Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com> Signed-off-by: Alexey Ivanov <lexa.ivanov@gmail.com>
Up to standards ✅🟢 Issues 0 issues🟢 Metrics 0 duplication
NEW Get contextual insights on your PRs based on Codacy's metrics, along with PR and Jira context, without leaving GitHub. Enable AI reviewer |
Sorry, something went wrong.
| def test_regression_issue_1006(self) -> None: | ||
| """regression test for issue #1006 | ||
|
|
||
| ``Bom.validate()`` must register a Dependency entry for the metadata |
There was a problem hiding this comment.
i dont see how the test proves the expected behavior - a speed improvement. what am i missing?
could you please elaborate?
Sorry, something went wrong.
Adds test_regression_issue_1006_scales_linearly: it counts BomRef equality comparisons performed during Bom.validate() for n and 2n components and asserts the count grows ~linearly, not quadratically -- a CI-stable complexity guard that does not rely on wall-clock timing. It fails on the previous O(n^2) scan (~22k -> ~84k comparisons, ratio ~3.9) and passes on the indexed implementation (~1.6k -> ~3.7k, ratio ~2.2). Addresses review feedback on CycloneDX#1007. Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com> Signed-off-by: Alexey Ivanov <lexa.ivanov@gmail.com>
|
@jkowalleck good question — you're right: test_regression_issue_1006 only guards correctness (that the change doesn't alter which dependencies end up registered). The speedup itself is shown by the benchmark in the PR description, and I deliberately avoided a wall-clock assertion since timing tests are flaky in CI. To actually guard the complexity, I've pushed test_regression_issue_1006_scales_linearly: it counts BomRef equality comparisons performed during validate() for n and 2n components and asserts the count grows ~linearly rather than ~quadratically — no timing involved, so it's CI-stable.
So it fails on the regression and passes on the fix. Happy to reformulate (e.g. a different counter or threshold) if you'd prefer. |
Sorry, something went wrong.
CAOShurong
left a comment
There was a problem hiding this comment.
I independently validated this exact head (caa74d7bbf0f545c31d4dc712c967a6207a09011) and did not find a correctness regression in the reviewed scope.
Verification performed:
- all 41 tests.test_model_bom tests passed;
- the full suite passed with UTF-8 mode enabled (6,961 tests); the three failures without UTF-8 mode were Windows GBK fixture-decoding errors, not failures in these two changed files;
- the new complexity guard passed under 20 fixed PYTHONHASHSEED values;
- an independent comparison-count probe measured 21,734 -> 83,852 comparisons on the base implementation for 200 -> 400 components (3.858x), versus 1,634 -> 3,652 on this head (2.235x);
- real strict-valid CycloneDX 1.6 JSON output retained matching component/dependency sets at 1,000, 2,000, and 4,000 components; observed serialization times improved from 0.145/0.451/1.941 seconds on the base to 0.072/0.182/0.360 seconds on this head;
- flake8 passed on both changed files.
The local mypy invocation reports the same two typings/sortedcontainers.pyi errors on both the base and this head, so I did not count mypy as passing or attribute those errors to this PR.
This also answers the open complexity-test question from my independent run: the deterministic comparison count distinguishes the old near-quadratic growth from the candidate's near-linear growth without relying on wall-clock assertions.
Review prepared with OpenAI Codex assistance; I verified the commands, outputs, and conclusion.
Sorry, something went wrong.
Documentation build overview4 files changed ± changelog.html ± genindex.html ± autoapi/cyclonedx/serialization/index.html ± autoapi/cyclonedx/model/component/index.html |
Sorry, something went wrong.
Reviewers
At least 0 approving reviews are required to merge this pull request.
Description
Bom.validate() ensured every component/service had a Dependency entry by calling register_dependency() once per component. register_dependency() locates an existing entry with a linear next(filter(...)) scan over the dependency collection, so the registration loop is O(n²). Because the JSON/XML outputters always call validate() during serialization, serializing large BOMs (thousands of components) stalls for minutes.
This resolves "already registered" via a set of refs, keeping the loop linear. Observable output is unchanged; test_regression_issue_1006 covers correctness.
Benchmark — serializing a BOM of N library components (output_as_string, JSON v1.6):
Scaling goes from ~quadratic (≈4× per 2×N) to linear (≈2× per 2×N).
Resolves or fixes issue: #1006
AI Tool Disclosure
Affirmation