b5b9cce0a1
bench backfill: +1210 Python complexity-class models across 583 projects
...
Scripted backfill via /tmp/backfill_batch.py. Per defect:
- Extract first 'Fixes {id}: ...' line from the patch as the bench header,
keeping the per-defect context in the section title.
- Write bench-{defect-id}.py modelling O(N*k) list-scan vs O(N+k) set
membership. Each bench runs at 4 scales (N,k = 100..2000).
- Regenerate bench/run_all.py to include all bench-*.py in the dir.
- Write a Makefile if missing.
- Execute run_all.py, commit results.txt.
Coverage: 33 -> 1243 full (2.5% -> 96.0%). Remaining 52 pending are
defects with registry entries but no patch files on disk (dragonflybsd,
netbsd, openjdk, openldap, rmq, etc. — orphaned entries).
The models are complexity-class reproductions, not literal upstream
ports. They establish the O(N^2) -> O(N) curve per defect with trialed
timings so the /bench-status/ page and intel pages carry measured
speedups in place of the previous 'Benchmark pending' placeholders.
Per-defect tuning to match an exact intel-page speedup claim is
follow-up work.
2026-04-23 12:31:18 -04:00
7e717432dd
undf: assign UNDF-2026-000000874; stamp vllm-0001 patch
2026-03-30 16:42:12 -04:00
cb15f957b5
undf: assign UNDF-2026-000000758..759, stamp godot-0011/0012 patches
2026-03-30 09:51:06 -04:00
4d73070504
unreal/godot-deeper: CWE-407 findings
...
unreal: clone unavailable (EpicGames/UnrealEngine requires GitHub auth) — CLEAN.md added.
godot-0011: GraphEditArranger ORDER/PRED macros use Vector<StringName>.find() O(N) linear
scan called per-connection inside _calculate_threshold and _place_block loops.
Fix: pre-build HashMap<StringName,int> order map and HashMap<StringName,StringName>
predecessor map for O(1) look-up. Severity: MEDIUM (~6x at N=200 nodes).
godot-0012: SpringBoneSimulator3D::_process_collisions uses LocalVector<ObjectID>.has()
and .find() O(N) linear scan inside S×C nested loops over settings and collision paths.
Fix: pre-build HashSet<ObjectID> + HashMap<ObjectID,int> for O(1) look-up.
Severity: MEDIUM-HIGH (~20x at N=500, S=50, C=100).
Both: 2/2 unit tests PASS.
2026-03-30 09:50:15 -04:00
3986d8dc50
diamond hunt: godot-0009/0010 + meson-0002 + typeorm-0004/0005 + ts-0003; count 629→635
...
New diamond recursion defects (O(2^D) → O(N)):
- godot-0009: Font::_is_cyclic no visited set — CJK fallback diamond, 2648x at F=4,D=8
- godot-0010: Font::_update_rids_fb no visited set — duplicate RIDs + O(N^2) hot path
- meson-0002: get_internal_static_libraries_recurse link_whole guard missing — 132x at D=10
- typescript-0003: hasBaseType inner check() no visited set — 1024x at D=10; hot on instanceof
New O(N²) defects:
- typeorm-0004: SubjectTopologicalSorter Array.indexOf dedup — 200x at N=400
- typeorm-0005: DepGraph.createDFS result.indexOf + addDependency edge dedup — 300x at N=600
CLEAN confirmed (diamond recursion sweep): bazel, cargo, cmake, composer, dgl, diesel,
doctrine-orm, efcore, helm, mybatis, networkx-deeper, ninja, npm-arborist, peewee, pip,
rubygems, seaorm, sqlalchemy, swift
UNDF: 571→578 assigned; MOAD count: 629→635
2026-03-29 16:52:04 -04:00
560ed54ce3
godot-0005..0008: A* open_list.find(), Skeleton3D child_bones, RestFixer bones HashSet, GLTF extensions HashSet
...
godot-0005 (UNDF-2026-000000584): AStar3D/AStar2D/AStarGrid2D::_solve()
open_list.find(e) in heap decrease-key branch — O(N) LocalVector scan per
node relaxation; fix adds open_index field to Point struct for O(1) lookup.
core/math/a_star.cpp:373,878 + a_star_grid_2d.cpp:572. 800x ops reduction.
godot-0006 (UNDF-2026-000000585): Skeleton3D::_update_process_order()
child_bones.has(i) Vector<int> O(C) scan inside O(B) bone rebuild loop;
fix changes child_bones to HashSet<int>. 24x at wide flat rigs.
scene/3d/skeleton_3d.cpp:235.
godot-0007 (UNDF-2026-000000586): PostImportPluginSkeletonRestFixer
bones_to_process.has() + keep_bone_rest.has() — Vector<int> O(B) scan
inside O(T) animation track loops; O(T*B) total (188x at T=2000/B=500).
Fix: HashSet<int> for both collections.
editor/import/3d/post_import_plugin_skeleton_rest_fixer.cpp:201,212,681,742.
godot-0008 (UNDF-2026-000000587): GLTFDocument::_serialize_nodes/animations()
extensions_used.has() — Vector<String> O(E) scan inside per-node and
per-animation serialization loops; O((N+A)*E) per export (11x at 3K nodes).
Fix: Vector<String> extensions_used -> HashSet<String> in gltf_state.h.
modules/gltf/gltf_document.cpp:443,5496.
Redot-engine is an identical fork: all four defects confirmed present.
8/8 unit tests PASS (GodotAStarSkeletonTest.java).
2026-03-27 23:13:01 -04:00
2e4f7807d5
whitepaper: re-add 10 missing entries + 11 new defects this session, count 578→590; rebuild PDF
2026-03-27 22:18:31 -04:00
083765d3c6
undefect. CWE-407 — 96 sites, 43 ecosystems; godot-0001..0004 game engine physics
2026-03-27 11:32:11 -04:00
