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
Bom.validate()#1007Conversation
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
|
| Metric | Results |
|---|---|
| Duplication | 0 |
NEW Get contextual insights on your PRs based on Codacy's metrics, along with PR and Jira context, without leaving GitHub. Enable AI reviewer
TIP This summary will be updated as you push new changes.
| 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?
Bom.validate()
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: To actually guard the complexity, I've pushed
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. |
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_bomtests 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
PYTHONHASHSEEDvalues; - 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.
Documentation build overview
|
Description
Bom.validate()ensured every component/service had aDependencyentry by callingregister_dependency()once per component.register_dependency()locates an existing entry with a linearnext(filter(...))scan over the dependency collection, so the registration loop is O(n²). Because the JSON/XML outputters always callvalidate()during serialization, serializing large BOMs (thousands of components) stalls for minutes.This resolves "already registered" via a
setof refs, keeping the loop linear. Observable output is unchanged;test_regression_issue_1006covers 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
validate()→register_dependencylinear scan) and the set-based fix were produced with assistance; I reviewed the change and ran the benchmarks, regression test, and linters (isort/flake8/mypy) to verify it.Affirmation