russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
1.3 KiB
| id | repo | severity | status | created | patched | patch |
|---|---|---|---|---|---|---|
| gcc-0001 | gcc | MEDIUM | PATCHED | 2026-03-23 | 2026-03-23 | defects/gcc/patch/gcc-0001-gcov-blocked-map.patch |
Defect
File: gcc/gcov.cc:980
Pattern: std::find(vector.begin,end,w) in Johnson's algorithm for coverage analysis
Complexity: O(V²)
Language: C++
Description
GCC's coverage analysis (gcov) uses Johnson's algorithm to find all simple cycles in the control flow graph. At line 980, the algorithm checks whether a vertex is blocked using std::find over a std::vector. This linear membership check is performed for every vertex examined during the cycle-finding DFS, causing the blocked-set lookup to dominate runtime and degrading the algorithm from near-linear to O(V²) for dense CFGs.
Fix
Replace: std::find(blocked.begin(), blocked.end(), w) != blocked.end()
With: blockedSet.count(w) > 0
Data structure change: std::vector<vertex_t> blocked → std::unordered_set<vertex_t> blockedSet
Work required
- Patch in
defects/gcc/patch/ - Unit test — asserts exact operation counts before/after (in
defects/gcc/unit/) - Integration test (in
defects/gcc/integration/) - Benchmark — before/after on V=100,200,400,800 (in
defects/gcc/bench/) - White paper section