Say that prefetching items did not pay, and why (109)

Fetching a found item's cells, a leaf's keys and each level's keys ahead
made finding and reading items 20% faster on 100,000 items in a micro
benchmark, but TPC-C's clean pairs moved 1% at most and finding alone got
48% slower, so it is not in. The owner's finding samples were the descent,
not the fields: a write right after a read copies the leaf whole anyway,
and what costs is walking structures larger than the caches at random.

1 files changed, 57 insertions, 0 deletions

diff --git a/docs/research/109-finding-items.md b/docs/research/109-finding-items.md
index 2b55ff8..ffa3c25 100644
--- a/docs/research/109-finding-items.md
+++ b/docs/research/109-finding-items.md
@@ -32,3 +32,60 @@ W=1의 재고는 항목 10만 개, 수 필드 다섯이다. 잎만 4 MB라서 �
   - 은행 질의의 중앙값이 3% 넘게 느려지지 않는다.
 - **측정의 흔들림.** 이 기계는 다른 세션과 함께 쓰인다. 쌍마다 소유자의 코어 몫을 보고, 이웃보다 뚜렷이 낮은 실행은
   방해받은 것으로 적는다(버리지 않고 밝힌다).
+
+## 쉬운 말로
+
+- **넣지 않았다.** 미리 가져오기는 마이크로벤치에서 찾고 읽기를 10만 항목에서 20% 빠르게 했다. 그러나 TPC-C에서는 깨끗한
+  쌍 셋이 +2.1%, +1.5%, −0.6%였고, 거래당 CPU가 준 것은 여섯 쌍 가운데 둘이었다. 기준(다섯 쌍, +3%)에 한참 못 미친다.
+  게다가 찾기만 하는 경우(`has`)를 48% 느리게 한다. 쓰지 않을 줄을 가져오느라 메모리의 줄을 차지하기 때문이다.
+- **가설이 틀렸다.** 필드를 열로 나눠 들어 한 항목의 필드가 여러 캐시 줄에 흩어지니 그것이 비싸리라 봤다. 마이크로벤치에서는
+  맞았다(10만 항목에서 필드 셋을 읽는 데 208 ns, 찾기의 두 배 가까이). 그러나 TPC-C의 소유자 표본에서 "찾기" 20개 가운데
+  18개는 `pure_list_seek` 안, 곧 트리를 내려가는 걸음이었고, 필드 읽기는 2개였다.
+- **까닭.** TPC-C는 필드를 읽자마자 쓴다. 저장마다 스냅숏이 있으니 첫 쓰기가 잎을 통째로 복사하고, 그때 모든 열이 캐시로
+  들어온다. 미리 가져오기가 아끼는 것은 처음 읽는 한 번뿐이다. 비싼 것은 캐시보다 큰 구조를 무작위로 찾는 걸음이다.
+  W=1에서 품목과 재고의 잎은 각각 4 MB로 L3(2 MB)보다 크고, 주문 줄 목록은 실행 중에 초당 약 15만 항목씩 자란다.
+
+## 결과
+
+원시 결과와 명령은 [024-finding-items](../../research/experiments/024-finding-items/)에 있다(`runs.sh`, 마이크로벤치
+[`bench-seek.c`](../../research/experiments/024-finding-items/bench-seek.c), 후보 [`prefetch.patch`](../../research/experiments/024-finding-items/prefetch.patch)).
+
+**마이크로벤치**(수 필드 다섯의 키 있는 목록, 무작위 키 150만 번, 다섯 번 번갈아 돈 중앙값, 부하 평균 약 3.5). 이 기계의
+메모리 지연은 109 ns다.
+
+| | 찾기만 | 찾고 필드 셋 읽기 | 셋 읽고 셋 바꾸기 | 같은 것, 30번마다 공유 |
+|---|---:|---:|---:|---:|
+| 10만 항목, 전 | 125 ns | 339 ns | 434 ns | 682 ns |
+| 10만 항목, 후 | 186 ns (+48%) | 271 ns (−20%) | 360 ns (−17%) | 597 ns (−12%) |
+| 40만 항목, 전 | 213 ns | 385 ns | 505 ns | 855 ns |
+| 40만 항목, 후 | 262 ns (+23%) | 349 ns (−9%) | 471 ns (−7%) | 802 ns (−6%) |
+
+후보는 셋을 모두 넣은 것이다. 찾은 항목의 칸을 열마다 미리 가져오고, 잎의 키 열을 크기와 상관없이 한꺼번에 가져오고, 안쪽
+노드의 키를 단계마다 가져온다. 셋을 따로 잰 것(탐색 중)에서는 셋을 모두 넣은 것이 가장 나았다.
+
+**TPC-C**(RAM, W=1, 64터미널, 20초, 전은 `2296e1e`의 pure-serve, 후는 패치를 넣은 것). 부하 평균은 4–7이었다.
+
+| 쌍 | 초당 거래(전 → 후) | 거래당 CPU(µs) | 소유자의 코어 몫 |
+|---|---:|---:|---:|
+| 1 | 43,185 → 35,582 | 43.9 → 46.4 | 0.88 → 0.77 (후가 방해받음) |
+| 2 | 44,248 → 32,144 | 42.9 → 48.7 | 0.89 → 0.74 (후가 방해받음) |
+| 3 | 43,719 → 44,626 (+2.1%) | 43.1 → 42.6 | 0.89 → 0.89 |
+| 4 | 43,895 → 44,555 (+1.5%) | 42.9 → 42.7 | 0.89 → 0.89 |
+| 5 | 37,963 → 32,643 | 45.7 → 48.7 | 0.82 → 0.75 (둘 다 방해받음) |
+| 6 | 43,848 → 43,579 (−0.6%) | 42.7 → 43.0 | 0.89 → 0.88 |
+
+방해받은 실행을 빼지 않고 적었다. 깨끗한 쌍(3, 4, 6)만 보아도 효과는 1% 안팎이다.
+
+## 판정
+
+- 기준 셋 가운데 둘(TPC-C, 그리고 40만 항목의 마이크로벤치)을 채우지 못했다. 넣지 않는다. 코드는 바뀌지 않았다.
+
+## 다음
+
+찾기의 비용은 캐시보다 큰 구조를 무작위로 찾을 때의 메모리 지연이다. 줄이려면 구조를 바꿔야 한다. 셋 다 이 연구 밖의 설계다.
+
+- **단계마다 읽는 줄을 줄인다.** 안쪽 노드의 안내 키는 binary64(8 B)라 서른두 개가 네 줄이다. 정수 키라면 더 작게 둘 수 있다.
+- **걸음을 겹친다.** 한 사건 안의 조회는 서로 기다릴 까닭이 없다(New-Order는 줄마다 품목과 재고를 찾는다). 루프의 다음
+  바퀴가 찾을 키를 미리 가져오면 미스가 겹친다. 실행기나 컴파일러가 할 일이다.
+- **키로 곧장 간다.** 큰 키 있는 목록에 해시 색인을 두면 걸음이 한두 번이 된다. 다만 스냅숏의 복사로 잎의 주소가 바뀌니
+  색인을 함께 고쳐야 한다.