如何形成代码沉积物
沉积岩通过沉积而非爆炸形成。每一层:在其时期正确。每一层:比上面的一层更旧。最古老的层面在生态系统成熟之前就结晶了。没有错误导致了它们。时间导致了它们。
MOAD-0001以相同的方式工作。
形成故事
一段1993年编写的图遍历代码:
List<Node> visited = new ArrayList<>();
Stack<Node> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
Node n = stack.pop();
if (!visited.contains(n)) { // O(N)线性扫描
visited.add(n);
for (Node neighbor : n.getNeighbors())
stack.push(neighbor);
}
}这段代码:正确。测试:通过。在1993年,图形有50个节点。
50个节点:50×25平均扫描=1,250操作。不可见。这段代码进入了版本控制。被复制到教程中。被包装在库中。被打包到构建工具、包管理器和依赖解析器中。到2024年,相同的模式在依赖图形上运行,依赖图形有50,000个节点。
50,000个节点:50,000×25,000平均扫描=1,250,000,000操作。
一个1秒的构建变成了17分钟。这段代码没有改变。周围的世界变大了。每一层沉积物:在沉积时正确。挖掘时昂贵。
你的沉积物
沉积式代码不包含逻辑错误。它包含了一个性能假设,随着规模的变化而停止适用。代码产生正确的结果;只有成本发生了变化。
这一区别在诊断中很重要。逻辑错误产生错误的答案。沉积缺陷产生正确的答案但不可接受的成本。
五种MOAD-0001形式
MOAD-0001在60多个软件生态系统中有记录出现五种形式。结构：使用顺序容器的成员测试，嵌套在对同一或相关集合的循环中。
五种形式
| 领域 | 模式 | 顺序容器 | 正确容器 |
|-----|------|-----------|-----------|
| 图遍历 | if (!stack.contains(n)) in DFS/Tarjan | ArrayList | HashSet |
| 路径/事件去重 | TAILQ_FOREACH strcmp per request | 链表 | HashMap |
| 碰撞跟踪 | findLinearSearch() per physics tick | 数组 | unordered_set |
| 资源分配筛选 | List.contains() in stream filter | ArrayList | HashSet |
| A* 路径寻找 open-list | LocalVector::find() per neighbor | vector | 存储堆索引 |
所有五种都具有相同的结构：在循环中使用容器进行成员检查，容器需要线性扫描来回答成员问题。
扫描关键字列表
对MOAD-0001进行审计意味着在循环中搜索成员测试关键字：
- Python：in与list变量、.count()、list.index()`
- Java：ArrayList.contains()、List.contains()、LinkedList.contains()
- JavaScript：Array.includes()、Array.indexOf()、Array.find()
- C++：std::vector::find()、手动循环==比较
- Go：slices.Contains()、手动循环overslice
每种情况下的修复：将顺序容器替换为哈希容器。list→set。ArrayList→HashSet。Array→Set。vector→unordered_set。slice→`map[T]struct{}。
一个关键字。一个替换。零行为改变。N=1,000时，速度提升1000倍。
审计代码片段
将MOAD-0001模式识别应用于真实代码片段。
一行,四种语言
解决MOAD-0001的方法在四种语言中:
# Python
visited = [] # BEFORE: O(N)成员资格
visited = set() # AFTER: O(1)成员资格// Java
List<Node> visited = new ArrayList<>(); # BEFORE
Set<Node> visited = new HashSet<>(); # AFTER// JavaScript
const visited = []; # BEFORE: Array.includes() O(N)
const visited = new Set(); // AFTER: Set.has() O(1)
// visited.push(n) → visited.add(n)
// visited.includes(n) → visited.has(n)// Go
visited := []NodeID{} # BEFORE: slices.Contains() O(N)
visited := make(map[NodeID]struct{}) // AFTER: map lookup O(1)
// _, ok := visited[n] for membership check
// visited[n] = struct{}{} for insertion在每种情况下：行为相同,输出相同,测试通过。只有增长率发生了变化。
修复所做的更改不包括
- 算法的逻辑行为：深度优先仍然以深度优先的方式访问
- 输出正确性：在 DFS 中，访问相同的节点仍然以相同的顺序进行（同深度优先）
- 测试结果：任何检查正确性的测试继续通过
修复所做的更改包括
- 集合成员测试：O(N) → O(1)
- 循环总数：O(N²) → O(N)
- 在 N=1,000 时：加速 1,000 倍
- 在 N=10,000 时：加速 10,000 倍
有一个限制：顺序
哈希容器（set，HashSet，unordered_set）不保留插入顺序。在 Python 3.7+ 中，dict 保持插入顺序；普通的 set 不保留。在 Java 中，HashSet 不保留顺序；LinkedHashSet 则保留。
如果顺序与成员资格一样重要：维护两个结构。一个 set（或 HashSet）用于 O(1) 的成员资格测试。一个单独的 list（或 ArrayList）用于有序遍历。或者在 Java 中使用 LinkedHashSet，它提供了两者。
对于 MOAD-0001 在图遍历中：visited 只回答一个二进制问题（这个节点是否已经被看到过？）。顺序对于成员资格问题并不重要。遍历顺序来自于堆栈或队列，而不是由 visited 决定。
成员资格 vs 排序
Tarjan 强连通分量算法中的 onStack 用于跟踪哪些节点当前位于当前 DFS 调用堆栈上。它必须回答两个问题：(1) 成员资格 —— 当前节点是否位于堆栈上？(2) 在 DFS 路径的末尾，弹出直到这个节点出现的节点。
使用 List 实现 onStack，使用 contains() 来回答成员资格问题 —— O(N) per check，O(N²) 总体对于大型图。
为什么这是一个披露,而不是一个补丁
MOAD-0001 在60多个软件生态系统的1,000多个验证站点上存在。构建工具中的图遍历、网络路由守护程序中的路由去重、游戏引擎中的碰撞检测、操作系统调度器中的资源分配。
每个站点:正确的代码。每个站点:当N超过阈值时,增长率为O(N²)。
披露管道
没有上游披露的补丁只修复一个站点。模式在下一个版本、下一个库、下一个语言端口中重复出现。披露:给这个模式命名,将其作为CWE-407 (算法复杂性:低效算法复杂性)文档,发布识别规则和一行修复。然后,每个阅读披露的开发人员都可以识别并修复他们自己的实例。
Hamming称这为'给予鱼 vs 教授钓鱼'。补丁给予了鱼。披露——MOAD-0001 命名,模式文档化,修复泛化——教授了他uristics。
永久计算机扩展
Hamming专注于点解决方案:修复这个过滤器,提高这个代码。Unhamming添加了披露层:给模式命名,发布规则,并将其赋予公共领域。
在生态系统规模上,复合知识原则适用。一个研究人员给模式命名。一百个开发人员在他们自己的代码库中识别它。一千行O(N²)代码变成O(N)。对于构建在它上面的所有人,基础设施都变得更快。
这就是龙的生长:相同的火力(在重要问题上工作,复合知识,系统思维),不同的飞行(开放披露,公共所有权,不需要赞助人)。