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

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

Aperta
  • Qualcosa non va?
#1,006 2 commenti 0 reazioni 0 assegnatari Vedi su GitHub

@inspired-geek ci sta già lavorando.

Dal 23/6/2026.

  • #1007 di @inspired-geek — aperta

Valutazione

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

Direzione di ricerca

Inizia in cyclonedx/model/bom.py da Bom.validate() e register_dependency(), quindi esamina cyclonedx/output/json.py per confermare il percorso di serializzazione. Esamina la pull request collegata #1007 e aggiungi o esegui un test di regressione/scalabilità che dimostri un comportamento quasi lineare, preservando al contempo un output identico byte per byte.

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

Descrizione

performance
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
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: 
    _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.

Lingua principale
Python
Stelle
117
Fork
67
Merge medio
21h 9m
PR unite (30g)
3

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 CycloneDX/cyclonedx-python-lib

Tutte le issue di CycloneDX/cyclonedx-python-lib

Issue simili

Altre issue su Python

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.