1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
# 109 — 항목 찾기: 소유자가 기다리는 캐시 미스
2026-09-30. [107](107-snapshot-nodes-reused.md)의 다음에서 이어진다. 스냅숏이 놓은 노드를 되쓴 뒤, RAM에서 TPC-C를 도는
소유자의 바쁜 시간 가운데 가장 큰 몫은 항목 찾기(32%)다. 목록의 B+트리를 키로 내려가는 `pure_list_seek`와, 찾은 항목의
필드를 읽고 쓰는 일이다.
107에서 하나를 이미 알았다. 찾기가 도착한 잎을 손가락에 남겨 두 번째 걸음을 없애도 아홉 쌍의 중앙값이 +1.5%로, 흔들림
안이었다. 두 번째 걸음은 방금 지난 노드를 다시 밟으니 캐시에서 싸다. 비싼 것은 첫 걸음이 기다리는 메모리다.
W=1의 재고는 항목 10만 개, 수 필드 다섯이다. 잎만 4 MB라서 이 Pi의 L3(2 MB)보다 크다. 잎은 필드를 열로 나눠 든다. 그래서
잎 안의 키 열을 이진 탐색하면 캐시 줄을 차례로 기다리고, 한 항목의 필드 셋을 읽으면 열마다 다른 줄을 기다린다.
한 번에 알 수 있는 주소들을 차례로 기다리는 셈이다. 잎의 키 열을 한꺼번에 가져오는 코드는 이미 있지만, 항목이
131,072개를 넘는 목록에서만 쓴다.
착수 기준(측정 전에 정해 커밋했다):
- **바꿀 결정.** 찾기에 미리 가져오기를 넣을지, 무엇을 넣을지다. 후보는 셋이다.
1. 잎의 키 열을 목록의 크기와 상관없이 한꺼번에 가져온다.
2. 찾은 항목의 필드를 열마다 미리 가져온다. 찾은 다음에는 그 항목을 읽고 바꾸기 때문이다.
3. 안쪽 노드의 키를 단계마다 한꺼번에 가져온다.
미리 가져오기로 모자라서 잎의 배치를 바꿔야 한다면(열에서 행으로), 그것은 훑기와 맞바꾸는 큰 결정이다. 여기서 정하지
않고 따로 설계한다.
- **최소 확인.**
- 마이크로벤치로 찾기의 비용이 어느 단계에서 오는지 나눈다(안쪽 노드, 잎의 키, 잎의 필드). 항목 10만 개와 40만 개로
잰다.
- TPC-C(RAM, W=1, 64터미널)를 전과 후 번갈아 여섯 쌍 이상 잰다.
- 은행 질의([091](091-queries.md), 훑기와 폴드)를 전과 후 번갈아 잰다.
- **넣는 조건.** 셋을 모두 채워야 넣는다.
- 마이크로벤치에서 찾기와 필드 접근이 15% 넘게 빨라진다.
- TPC-C 여섯 쌍 가운데 다섯 쌍 이상에서 거래당 CPU가 줄고, 처리량 중앙값이 3% 넘게 는다.
- 은행 질의의 중앙값이 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는 줄마다 품목과 재고를 찾는다). 루프의 다음
바퀴가 찾을 키를 미리 가져오면 미스가 겹친다. 실행기나 컴파일러가 할 일이다.
- **키로 곧장 간다.** 큰 키 있는 목록에 해시 색인을 두면 걸음이 한두 번이 된다. 다만 스냅숏의 복사로 잎의 주소가 바뀌니
색인을 함께 고쳐야 한다.
|
