Say what a search's floor is with stored lists as trees: 373 ns a node to find a slice against C's 21 (021)

1 files changed, 16 insertions, 1 deletions

diff --git a/docs/design/021-past-c.md b/docs/design/021-past-c.md
index ec0df36..6cfcfcc 100644
--- a/docs/design/021-past-c.md
+++ b/docs/design/021-past-c.md
@@ -1,6 +1,6 @@
 # 021 — C보다 빠르게
 
-작성일: 2026-10-05. 상태: 설계와 착수 기준(구현 전).
+작성일: 2026-10-05. 상태: 1–4단계를 구현해 쟀다. 아래 "바로잡음"이 처음의 산수를 고친다.
 [020](020-computing-faster.md)이 BFS(노드 10만, 간선 100만) 한 번을 397 ms에서 187 ms로 줄였다([121](../research/121-computing-faster.md)).
 같은 탐색을 C(033의 `bfs.c`: 인접을 오프셋 배열로, 깊이는 `int32_t` 배열)는 9 ms에 한다. 목표는 그 C보다 빠른 것이다. 같은
 aup 코드, 같은 뜻(키 있는 리스트, 인덱스는 위치, 결정적인 결과), 같은 기계에서.
@@ -22,6 +22,21 @@ C의 9 ms는 Pi 5(Cortex-A76, 2.4 GHz)에서 약 2,160만 사이클이다.
   키 집합을 비트로 고른다).
 - **그래서 기대하는 것은 1.3–1.8배다**(5–7 ms), 10배가 아니다. 10 ms에 머물면 그렇게 적는다.
 
+## 바로잡음 (2026-10-05, 1–4단계를 해 보고)
+
+위의 산수는 명령의 수만 셌다. 잰 것은 다르다.
+
+- **저장된 리스트의 디렉터리**(3)는 만들어 쟀고 넣지 않았다: 탐색 하나의 명령은 3.6% 줄었지만 사이클은 6% 늘었다. 칸의 표(760 KB)와
+  잎의 표(500 KB)가 L2(512 KB)에 들지 않아, B+트리 위쪽 단(캐시에 있다)을 내려가는 것보다 미스가 많았다. "필수"라는 판단은 틀렸다.
+- **바닥은 메모리 지연이다.** `038-past-c/seekfloor.c`: 간선 100만 개의 리스트에서 노드마다 조각의 두 경계를 찾고 첫 간선을 읽는 데,
+  BFS처럼 무작위 차례로 노드 하나에 373 ns가 든다. 같은 일을 C의 오프셋 배열(`start[v]`, `to[start]`)은 21 ns에 한다. C의 반복끼리는
+  서로 기다리지 않아 미스가 겹치고, B+트리는 뿌리에서 잎까지 서로 기다리는 읽기를 넷 한다. 이것만으로 10만 노드에 18–37 ms다.
+- 그래서 **저장된 키 있는 리스트가 B+트리뿐인 한, JIT만으로는 C(9 ms)를 넘지 못한다.** 바닥은 25–35 ms 근처로 본다. "1.3–1.8배
+  앞선다"는 예측은 틀렸다.
+- C를 넘으려면 둘 다 있어야 한다: 저장된 키 있는 리스트의 조각을 L2에 드는 색인으로 찾는 형태(잎 하나에 칸 하나, 칸에서 잎으로
+  바로: C의 `start[v]` → `to[k]`와 같은 사슬)와, 검사를 루프 밖으로 빼고 값을 레지스터에 두는 JIT. 앞의 것은 저장 형태의 일이라
+  설계 022로 따로 적고 기준을 둔다.
+
 ## 원칙
 
 - **뜻은 그대로.** 키 있는 리스트는 키 순서의 리스트이고 인덱스는 위치다. 바뀌는 것은 표현과 실행의 길이다. 어느 길로 가든