Hacktoberfest 2026 : les issues que les mainteneurs ont marquées pour octobre, ouvertes et accessibles aux débutants. Parcourir les issues Hacktoberfest

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

Ouverte
  • Quelque chose ne va pas ?
#1,006 2 commentaires 0 réactions 0 personnes assignées Voir sur GitHub

@inspired-geek y travaille déjà.

Depuis le 23/6/2026.

  • #1007 par @inspired-geek — ouverte

Évaluation

Difficulté
3/5
Temps estimé
1-2 jours
Accessibilité débutants
36/100
Type d'issue
Bug
Clarté
Clairement spécifiée
Activité
À l'abandon
Stack technique
python
Domaine
performance

Piste de recherche

Commencez dans cyclonedx/model/bom.py, au niveau de Bom.validate() et register_dependency(), puis examinez cyclonedx/output/json.py pour confirmer le chemin de sérialisation. Examinez la pull request liée #1007 et ajoutez ou exécutez un test de régression/mise à l’échelle démontrant un comportement quasi linéaire tout en préservant une sortie identique octet par octet.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

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.

Langage dominant
Python
Étoiles
117
Forks
67
Merge moyen
3 j 9 h
PR mergées (30 j)
4

Préparer son environnement

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de CycloneDX/cyclonedx-python-lib

Toutes les issues de CycloneDX/cyclonedx-python-lib

Issues similaires

Plus d'issues Python

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.