코드 퇴적물이 형성되는 방식
퇴적암은 폭발이 아니라 퇴적에 의해 형성된다. 각 층: 그 시대에는 올바른 것이었다. 각 층: 위의 층보다 오래되었다. 가장 오래된 층은 생태계가 그 주변으로 성숙하기 전에 이미 굳어 있었다. 오류가 원인이 아니었다. 시간이 원인이었다.
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 nodes: 50 × 25 avg scanned = 1,250 operations. Invisible.코드가 버전 관리에 들어갔다. 튜토리얼에 복사되었다. 라이브러리에 감싸졌다. 빌드 도구, 패키지 매니저, 의존성 해결자에 포함되어 배포되었다. 2024년이 되자 같은 패턴이 50,000개의 노드를 가진 의존성 그래프에서 실행되었다.
50,000 nodes: 50,000 × 25,000 avg scanned = 1,250,000,000 operations.
1초짜리 빌드가 17분이 된다.코드는 바뀌지 않았다. 주변 세상이 커졌다. 퇴적물의 모든 층: 퇴적 당시에는 올바랐지만, 발굴할 때는 비용이 많이 든다.
당신의 침전물
침전물 코드는 논리 오류를 포함하지 않습니다. 규모가 커지면서 더 이상 성립하지 않게 된 성능 가정을 포함하고 있습니다. 코드는 올바른 결과를 생성합니다. 단지 비용만이 변했을 뿐입니다.
이 구분은 진단에 중요합니다. 논리 오류는 잘못된 답을 생성합니다. 침전물 결함은 올바른 답을 생성하지만 수용할 수 없는 비용이 발생합니다.
MOAD-0001의 다섯 가지 형태
MOAD-0001은 60개 이상의 소프트웨어 생태계에서 다섯 가지 문서화된 형태로 나타납니다. 구조는 순차 컨테이너를 사용한 멤버십 테스트이며, 동일하거나 관련된 컬렉션을 순회하는 루프 안에 중첩되어 있습니다.
다섯 가지 형태
| 도메인 | 패턴 | 순차 컨테이너 | 올바른 컨테이너 |
|---|---|---|---|
| 그래프 순회 | DFS/Tarjan에서 if (!stack.contains(n)) | ArrayList | HashSet |
| 경로/이벤트 중복 제거 | 요청당 TAILQ_FOREACH strcmp | 연결 리스트 | HashMap |
| 충돌 추적 | 물리 틱당 findLinearSearch() | 배열 | unordered_set |
| Resource allocation filter | List.contains() in stream filter | ArrayList | HashSet |
| A* pathfinding open-list | LocalVector::find() per neighbor | vector | stored heap index |
다섯 가지 모두 동일한 구조를 공유합니다: 멤버십 검사가 루프 안에 중첩되어 있으며, 멤버십 여부를 확인하기 위해 선형 스캔이 필요한 컨테이너를 사용합니다.
스캔 키워드 목록
MOAD-0001 감사를 위해서는 루프 내부에서 멤버십 테스트 키워드를 grep으로 검색해야 합니다:
- Python: list 변수와 함께 사용하는 in, .count(), list.index()
- Java: ArrayList.contains(), List.contains(), LinkedList.contains()
- JavaScript: Array.includes(), Array.indexOf(), Array.find()
- C++: std::vector::find(), == 비교를 사용하는 수동 루프
- Go: slices.Contains(), 슬라이스에 대한 수동 루프
모든 경우의 해결책: 순차 컨테이너를 해시 컨테이너로 교체. list → set. ArrayList → HashSet. Array → Set. vector → unordered_set. slice → map[T]struct{}.
키워드 하나. 치환 하나. 동작 변화는 0. N=1,000에서 1,000배 속도 향상.
코드 조각 감사
실제 코드 조각에 MOAD-0001 패턴 인식을 적용합니다.
한 줄, 네 가지 언어
네 가지 언어로 표현한 MOAD-0001 수정 방법:
# Python
visited = [] # BEFORE: O(N) membership
visited = set() # AFTER: O(1) membership// 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이 순서를 보존합니다.
멤버십 검사와 함께 순서가 중요한 경우: 두 개의 자료구조를 유지하세요. O(1) 멤버십 검사를 위한 set(또는 HashSet)과 순서 있는 순회를 위한 별도의 list(또는 ArrayList)를 사용합니다. 또는 Java에서는 두 기능을 모두 제공하는 LinkedHashSet을 사용합니다.
그래프 순회에서 MOAD-0001의 경우: visited는 이진 질문(이 노드를 이미 방문했는가?)에 답합니다. 멤버십 질문에서는 순서가 중요하지 않습니다. 순회 순서는 visited가 아니라 스택이나 큐에서 결정됩니다.
멤버십 vs 순서
Tarjan의 강연결 요소 알고리즘에서 onStack은 현재 DFS 호출 스택에 남아 있는 노드를 추적합니다. 두 가지 질문에 답해야 합니다: (1) 멤버십 — 이 노드가 현재 스택에 있는가? (2) DFS 경로의 끝에서 이 노드가 나타날 때까지 노드를 순서대로 팝합니다.
단순한 구현에서는 onStack에 List를 사용하여 contains()로 멤버십을 확인합니다. 이는 검사당 O(N), 대형 그래프에서는 전체 O(N²)이 됩니다.
이것이 패치가 아니라 공개(Disclosure)인 이유
MOAD-0001은 60개 이상의 소프트웨어 생태계에 걸쳐 1,000개 이상의 검증된 사이트에 존재한다. 빌드 도구의 그래프 순회, 네트워크 라우팅 데몬의 경로 중복 제거, 게임 엔진의 충돌 감지, 운영체제 스케줄러의 자원 할당 등.
각 사이트: 올바른 코드. 각 사이트: N이 임계값을 넘을 때까지 기다리는 O(N²) 성장.
공개 파이프라인
업스트림 공개 없이 패치하는 것은 하나의 사이트만 수정한다. 이 패턴은 다음 버전, 다음 라이브러리, 다음 언어 포트에서 반복된다. 공개: 패턴에 이름을 붙이고, CWE-407(알고리즘 복잡도: 비효율적인 알고리즘 복잡도)로 문서화하며, 인식 휴리스틱과 한 줄 수정 방법을 공개한다. 그러면 공개를 읽는 모든 개발자가 자신의 인스턴스를 인식하고 수정할 수 있다.
해밍은 이를 '물고기를 주는 것 vs 낚시를 가르치는 것'이라고 불렀다. 패치는 물고기를 준다. 공개 — MOAD-0001을 명명하고, 패턴을 문서화하며, 수정을 일반화한 것 — 은 휴리스틱을 가르친다.
퍼마컴퓨터 확장
해밍은 점 단위 해결책에 집중했다: 이 필터를 고치고, 이 코드를 개선하라. 언해밍은 공개 계층을 추가한다: 패턴에 이름을 붙이고, 휴리스틱을 공개하며, 이를 커먼즈에 기여한다.
복합 지식 원리는 여기서 생태계 규모로 적용된다. 한 연구자가 패턴에 이름을 붙이면, 백 명의 개발자가 자신의 코드베이스에서 그 패턴을 인식한다. 그 결과 천 줄의 O(N²) 코드가 O(N)으로 바뀐다. 인프라는 이를 기반으로 구축하는 모든 사람에게 더 빨라진다.
이것이 용이 성장하는 모습이다: 같은 불(중요한 문제에 집중하고, 지식을 복합하며, 시스템 사고를 하라), 다른 비행(공개 공개, 커먼즈 소유권, 후원자 불필요).