Measure an index for a stored list's slices outside the list: three times a tree's seek, still seven times C's (021)

1 files changed, 8 insertions, 3 deletions

diff --git a/docs/design/021-past-c.md b/docs/design/021-past-c.md
index 6cfcfcc..5ff1c61 100644
--- a/docs/design/021-past-c.md
+++ b/docs/design/021-past-c.md
@@ -33,9 +33,14 @@ C의 9 ms는 Pi 5(Cortex-A76, 2.4 GHz)에서 약 2,160만 사이클이다.
   서로 기다리지 않아 미스가 겹치고, 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로 따로 적고 기준을 둔다.
+- **색인의 시제품**(`038-past-c/indexfloor.c`, 리스트 밖에서): 잎을 B+트리처럼 흩어 두고(항목 32개, 열 셋), 키의 범위를 2의
+  거듭제곱 폭의 칸으로 나눠 칸마다 첫 항목의 잎과 자리, 위치를 둔다. 칸의 원점을 폭의 배수에 맞추면(조각의 경계가 칸의 시작이
+  된다) 노드 하나에 124–134 ns, 맞추지 않으면 350–470 ns다. 같은 측정에서 C는 17–21 ns다. 둘 다 노드마다 DRAM 미스 하나인데,
+  C는 반복 하나가 명령 여덟 남짓이고 반복끼리 서로 기다리지 않아 미스 여럿을 겹친다. 색인은 B+트리보다 세 배 빠르지만, 노드마다
+  하는 일이 C만큼 짧지 않으면 C에 닿지 않는다.
+- 그래서 C를 넘으려면 색인과 함께, 노드 하나와 간선 하나에 하는 일이 C와 같은 크기여야 한다(간선마다 명령 열 남짓, 노드마다 백
+  남짓, 서로 기다리는 읽기 둘). 지금 JIT은 간선마다 약 80, 노드마다 수백이다. 그만큼 줄이는 것(값을 레지스터에, 검사를 루프
+  밖으로, 표현이 바뀌지 않는다는 가정을 루프 머리에서 한 번 확인)은 최적화 컴파일러의 일이다.
 
 ## 원칙