Hacktoberfest 2026：维护者为十月标记出来的 issue，仍然开放、适合新手。 浏览 Hacktoberfest issue

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

未关闭
  • 哪里不对？
#1,006 2 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看

@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 分钟
30 天内合并 PR
3

环境准备

从这里开始

  1. 先读完整个 Issue，再读项目的贡献指南。
  2. 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
  3. Fork 仓库，在一个分支上完成修改。
  4. 提交 Pull Request，并在描述里引用这个 Issue 编号。

CycloneDX/cyclonedx-python-lib 的其他 Issue

查看 CycloneDX/cyclonedx-python-lib 的全部 Issue

相似的 Issue

更多 Python Issue

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。