CycloneDX / CycloneDX/cyclonedx-python-lib

[PERF] Quadratic (O(N^2)) serialization time for large BOMs — `Bom.validate()` → `register_dependency()` linear scan

Aperta
#1,006 2 commenti 0 reazioni 0 assegnatari Rivendicata da @inspired-geek Vedi su GitHub
performance
Lingua principale
Python
Stelle
116
Fork
67
Merge medio
8g 2h
PR unite (30g)
2

Descrizione

### Environment

- `cyclonedx-python-lib` **9.1.0** (the offending code path is unchanged on `main` / 11.x)
- Python 3.10, Linux

### Description

Serializing a BOM with many components scales **quadratically** with the number of components, not linearly. For a container SBOM with several thousand components, `output_as_string()` stalls for minutes, almost entirely inside `Bom.validate()`.

### Steps to reproduce

```python
import time
from cyclonedx.model.bom import Bom
from cyclonedx.model.component import Component, ComponentType
from cyclonedx.output import make_outputter
from cyclonedx.schema import OutputFormat, SchemaVersion

for N in (1000, 2000, 4000, 8000):
bom = Bom()
bom.metadata.component = Component(name="root", type=ComponentType.CONTAINER, bom_ref="root")
for i in range(N):
bom.components.add(Component(name=f"c{i}", version="1.0",
type=ComponentType.LIBRARY, bom_ref=f"ref-{i}"))
out = make_outputter(bom=bom, output_format=OutputFormat.JSON,
schema_version=SchemaVersion.V1_6)
t = time.perf_counter(); out.output_as_string()
print(f"N={N}: {time.perf_counter()-t:.2f}s")
```

### Expected vs actual

Expected: time grows roughly **linearly** with N.
Actual: time grows roughly **4x per 2x N** (quadratic):

```
N=1000: 0.14s
N=2000: 0.48s (x3.4)
N=4000: 1.75s (x3.6)
N=8000: 6.70s (x3.8)
```

A `cProfile` run at N=15000 shows ~112M calls to the lambda at `cyclonedx/model/bom.py:653`.

### Root cause

- `cyclonedx/output/json.py` — `generate()` unconditionally calls `bom.validate()` during serialization (there is no opt-out).
- `cyclonedx/model/bom.py` — `Bom.validate()` calls `self.register_dependency(target=...)` once per component (and per service).
- `cyclonedx/model/bom.py` — `register_dependency()` locates the existing entry with a **linear** scan:
```python
_d = next(filter(lambda _d: _d.ref == target.bom_ref, self.dependencies), None)
```
Called once per component over the growing dependency collection, this is **O(N²)** overall.

### Proposed fix

Replace the linear lookup with an indexed (`dict[ref -> Dependency]`) lookup. In a local benchmark an indexed variant produces byte-identical output and gives ~8x speedup at N=6000 (the gap widens with N). I'm happy to open a PR with the fix and a regression/scaling test.

Guida per i contributori

Apri la guida per i contributori

Direzione di ricerca

Start in cyclonedx/model/bom.py at Bom.validate() and register_dependency(), then inspect cyclonedx/output/json.py to confirm the serialization path. Review linked pull request #1007 and add or run a regression/scaling test demonstrating near-linear behavior while preserving byte-identical output.

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

Valutazione

Stack tecnologico
python
Ambito
performance
Tipo di issue
Bug
Difficoltà
3/5
Tempo stimato
1-2 giorni
Stato di attività
Ferma
Chiarezza
Specificata chiaramente
Idoneità per principianti
36/100

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.