Hacktoberfest 2026：メンテナが10月に向けて印を付けた、オープンで初心者向けの issue。 Hacktoberfest の issue を見る

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

オープン
  • 何か問題がありますか？
#1,006 コメント 2 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

@inspired-geek がすでに取り組んでいます。

2026年6月23日 から。

  • #1007 @inspired-geek による — オープン

評価

難易度
3/5
見積もり時間
1〜2日
初心者へのやさしさ
36/100
issue の種類
バグ
明瞭さ
明確に書かれている
活発さ
停滞
技術スタック
python
領域
performance

調査の方向性

cyclonedx/model/bom.py の Bom.validate() と register_dependency() から始め、次に cyclonedx/output/json.py を調べてシリアライズの経路を確認します。リンクされている pull request #1007 をレビューし、バイト単位で同一の出力を維持しながら、ほぼ線形の挙動を示すリグレッション／スケーリングテストを追加または実行します。

索引モデルが issue の本文から書いたものです。

説明

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.

主要言語
Python
スター
117
フォーク
67
平均マージ
21時間 9分
マージ済み PR（30日）
3

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

CycloneDX/cyclonedx-python-lib のほかの issue

CycloneDX/cyclonedx-python-lib の issue をすべて見る

似ている issue

Python の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。