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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
# 020 — 계산을 빠르게, 긴 보기를 연결 스레드 밖에서
작성일: 2026-10-04. 상태: 설계와 착수 기준. 두 단계 모두 구현해 검사로 고정하고 쟀다(1단계 [121](../research/121-computing-faster.md), 2단계 [122](../research/122-views-off-the-connection-threads.md)). 만들며 달라진 것과 정한 것은 아래에 적었다.
[018](018-lifetimes-and-computation.md)이 계산을 들였지만 그 값이 컸다: BFS(노드 10만, 간선 100만) 한 이벤트가 396 ms로 CPython과
비슷하고 C의 44배였다([118](../research/118-computing-in-one-event.md)). 계산하는 보기는 연결 스레드에서 돌아 그동안 그 스레드의 다른
연결을 기다리게 했다([119](../research/119-views-that-compute.md)).
## 문제: 재어 본 것
**어디에 가는가.** 코어만으로 BFS를 돌려(`036-faster-loops/bfs-run.c`, 호스트 없이, 394 ms) gprof로 본 몫:
| 함수 | 몫 | 무엇 |
|---|---:|---|
| `pure_list_seek` | 61% | 키로 찾기: 간선마다 `seen.has`, 노드마다 `seen.add`, `seen[q.node]`, 간선 조각의 두 경계. BFS 한 번에 약 140만 번, 한 번에 약 183 ns |
| `run` | 13% | 실행기 자신 |
| `pure_list_get` + `descend` | 17% | 위치로 항목 읽기: 걷는 항목의 필드(`e.to`), 찾은 항목(`seen[…]`)마다 뿌리부터 다시 내려간다 |
키로 찾기 한 번이 183 ns인 것은 명령이 아니라 메모리다. 리스트는 영속 B+트리(가지 32)라 10만 항목이면 3–4단을 내려가고, 단마다
캐시에 없는 노드를 읽는다. C의 BFS는 노드 번호로 배열을 바로 읽는다(간선 하나에 미스 하나).
**긴 보기.** 연결 스레드를 코어보다 많이(8) 두면 보기가 나란히 돌지만(초당 46번, 스레드 셋에서는 연결이 같은 스레드에 떨어지면 22번),
쓰기의 최대 지연은 그대로 100–130 ms다. 보기를 계산하는 스레드에 붙은 쓰기 연결은 계산이 끝날 때까지 기다린다. 스레드 수로는 꼬리가
풀리지 않는다.
## 원칙
- **뜻은 그대로, 길만 빠르게.** 키 있는 리스트는 여전히 키 순서의 리스트이고 인덱스는 위치다. 바꾸는 것은 같은 답에 이르는 길이다.
- **잰 것을 고친다.** 위의 표가 순서를 정한다.
- **연결 스레드는 연결을 읽고 쓴다.** 오래 걸릴 수 있는 계산(본문이 있는 보기)은 보기의 스레드가 한다.
## 모양
### 1. 키로 찾기를 싸게
- **이벤트의 리스트의 소속 표.** 수로 키를 둔 이벤트의 리스트(018: `let seen: list of Seen by node`, 메시지의 행은 키가 없다)는 B+트리
옆에 키의 해시 집합을 가진다(열린 주소, 선형 탐사, 지우면 뒤를 당긴다). `has`는 그것만 본다(미스 하나). 넣기와 지우기와 비우기가
함께 고친다. 이벤트의 리스트는 되돌리기도 저장도 스냅숏의 나눔도 없으니(018) 그 셋을 따라 고칠 일이 없다. 그 바이트는 이벤트가
쥔 것으로 센다(018의 몫).
- **손가락.** 리스트는 마지막으로 내려간 잎과 그 잎의 첫 위치, 그때의 판을 기억한다. 위치로 읽는 것(`pure_list_get`)이 그 잎 안이면
내려가지 않는다. 키로 찾은 뒤 그 항목을 읽는 것(`seen[x].depth`), 걷기가 다음 항목을 읽는 것, 큐를 차례로 읽는 것(`queue.first +
i`)이 그렇다. 판이 바뀌면(넣기, 지우기, 바꾸기) 잊는다. 저장되는 리스트와 스냅숏의 사본도 같이 쓴다(읽는 쪽마다 제 사본이다).
### 2. 긴 보기를 연결 스레드 밖에서
- `pure-serve`는 보기의 스레드를 둔다(`--view-workers N`, 기본은 CPU 수). 본문이 있는 보기(018: 로드할 때 적힌다)의 `GET`은 연결
스레드가 보기의 스레드에 넘기고, 보기의 스레드가 자기 읽는 쪽에서 최신 스냅숏으로 계산해 답을 연결 스레드에 돌려준다(소유자가 답을
돌려주는 길과 같다: eventfd). 연결 스레드는 그동안 다른 연결을 읽고 쓴다.
- 미는 보기(019)도 같다: 본문이 있는 보기의 무리는 미는 일에서 계산을 넘기고, 값이 돌아오면 보낸다. 그동안 무리의 구독자가 다
떠나도 무리는 값이 돌아올 때까지 남는다.
- 본문이 없는 보기(식 하나)는 지금처럼 연결 스레드가 계산한다(가장 흔하고 짧은 길을 그대로 둔다).
- 넘긴 일이 `--queue`만큼 쌓이면 503 `busy`다.
### 1단계에서 달라진 것
재면서 만들었고, 잰 것이 모양을 바꿨다(코어만의 BFS, 중앙값).
- **소속 표는 비트와 표 둘이다.** 키가 2^22 아래의 0 이상 정수인 동안은 비트(노드 번호 10만이면 12.5 KB, 캐시에 든다)이고, 그 밖의
키가 처음 오면 열린 주소의 표(선형 탐사, 반 넘게 차지 않게, 지우면 뒤를 당긴다)로 바뀐다. 표만으로는 286 ms였고 비트로 207 ms다.
비우면 64 KiB까지의 비트는 지우고 남긴다(다음 이벤트가 다시 쓴다). `-0`과 `+0`은 한 키다.
- **키로 넣기는 한 번 내려간다**(`pure_list_add`). 찾고 나서 넣으면 두 번이다. 저장되는 키 있는 리스트의 덧붙이기도 이 길로 가고,
기록과 되돌리기는 `pure_list_insert`의 것과 같다.
- **손가락은 스레드마다 하나다.** 리스트 하나에 하나가 아니라 스레드가 마지막으로 읽은 잎이다(이미 있던 것). 넷(리스트마다 하나,
앞으로 옮기기)으로 늘려 봤지만 BFS는 빨라지지 않았고(183 대 185 ms) 은행 질의의 명령 수는 늘었다(`field` +2.9%, 하나로는
−0.3%): 되돌렸다. 리스트의 번호와 판이 맞을 때만 쓴다. 스냅숏의 사본은 리스트와 번호가 같고 판이 다르다. 새로 더한 것은 키로
찾기도 손가락의 잎에서 먼저 보는 것이다.
- 설계에 없던 넷: 항목의 필드가 text인지를 로드할 때 명령에 적기(실행할 때마다 찾지 않게), 각 단에서 자식 찾기를 이분 탐색이
아니라 세기로(가지 32개를 모두 비교해 센다, 벡터가 된다), 실행기의 루프를 재귀 없이(루프 기록의 스택), `module-list.c`를
`-O3`로(`Makefile`의 `LIST_OPTIMIZE`). 넷의 몫은 204 ms에서 186 ms이고 거의 다 `-O3`다.
- 해 보고 뺀 것: 잎의 울타리(키로 찾은 잎의 다음 잎의 첫 키, 손가락이 키 범위를 더 넓게 알게) — 185.5 대 185.5 ms. 손가락 넷
(위).
### 2단계에서 정한 것
- 보기의 스레드는 넘겨받은 일을 할 때 그 앱의 **가장 새 스냅숏을 스스로 읽는다**(연결 스레드가 그 라운드에 읽은 것을 쥐고 넘기지
않는다). 답은 그 라운드의 것보다 새것이거나 같으니, 쓰기의 답을 받은 뒤의 `GET`이 그 쓰기를 본다는 것은 그대로다. 스냅숏의
모듈이 요청이 풀린 모듈과 다르면(앱이 모듈을 바꿨다) 계산하지 않고 503 `stopped`다. 앱이 멈춰 스냅숏이 없어도 그렇다.
- 넘긴 일의 한도는 앱의 `queue=N`(`--apps`의 줄)이다. 그 앱의 보기 가운데 보기의 스레드에 있는 것이 N이면 503 `busy`. 한 앱의
호스트처럼 `queue`가 없으면 한도는 연결 수다(연결 하나에 요청 하나가 답을 기다린다). 미는 무리는 한 번에 계산 하나만 넘긴다.
- 표는 그 열 가운데 하나라도 본문이 있으면 넘긴다. 식 하나의 보기는 연결 스레드가 계산한다(지금처럼).
- 스레드의 이름은 `pure-view`, 멈출 때의 통계에 `view_workers`와 `views_by_workers`가 있다. `--view-workers 0`이면 전처럼 연결
스레드가 계산한다(견주는 쪽).
## 단계
1. 키로 찾기(소속 표, 손가락).
2. 긴 보기를 보기의 스레드로(요청과 미는 일).
## 1단계의 착수 기준
- **바꿀 결정:** 이벤트의 리스트에 소속 표를, 모든 리스트에 손가락을 둘지.
- **최소 확인:** test-module에서 소속 표와 손가락을 가진 리스트가, 같은 무작위 넣기·지우기·찾기·읽기·비우기 열에서 그것 없는 리스트와
매 단계 같은 답을 낸다(지우기가 탐사의 사슬 가운데를 빼는 경우 포함, 스냅숏의 사본 포함). aup의 `computing`(BFS, DFS, 다익스트라,
배낭)과 Pure, aup, Vega의 모든 검사가 초록이다.
- **통과 조건**(RAM의 Pi 5):
- BFS(노드 10만, 간선 100만, `bfs-run`) 한 번의 중앙값이 200 ms 이하다(394 ms의 절반 남짓). HTTP로 잰 033의 `bfs.py`도 밝힌다.
- 지금의 앱: TPC-C와 은행 질의를 전과 후 번갈아 여섯 쌍 재서 중앙값이 3% 넘게 느려지지 않는다. 손가락은 모든 리스트의 읽기를
바꾸므로 은행 질의의 명령 수를 밝힌다(늘면 1% 안이어야 한다).
## 2단계의 착수 기준
- **바꿀 결정:** 본문이 있는 보기를 보기의 스레드에서 계산할지.
- **최소 확인:** 019와 018의 검사(`server_view_bodies`, `server_push`)가 그대로 초록이다. 64연결이 동시에 묻는 `distance`가 모두 모델과
같다. 보기의 스레드에서 계산하는 동안 앱의 모듈을 바꾸거나 앱을 멈춰도 답이 섞이지 않는다(옛 모듈의 답이거나 503).
- **통과 조건**(RAM의 Pi 5, 034의 `views.py`):
- 꼬리: 연결 둘이 BFS 보기를 쉬지 않고 묻는 동안 쓰기의 최대 지연 중앙값이, 같은 코어에서 다른 프로세스가 그 보기를 계산할 때
(apart)의 2배 이하다(지금 100–190 ms 대 6–9 ms).
- 나란히: 연결 스레드 하나(`--threads 1`)에서도 연결 둘이 묻는 BFS 보기의 처리량이 연결 하나일 때의 1.8배 이상이다(지금 1.0배).
- 짧은 보기: 본문 없는 보기(`total`)의 읽기 처리량(64연결)이 전과 후 번갈아 여섯 쌍에서 3% 넘게 줄지 않는다.
## 하지 않는 것
- 키 있는 리스트를 해시 맵으로 바꾸기. 키 순서의 걷기와 위치로서의 인덱스가 언어의 뜻이다.
- 저장되는 리스트의 소속 표. 되돌리기, 저장, 스냅숏의 나눔을 함께 고쳐야 한다. 이벤트의 리스트로 효과를 본 뒤에 잰다.
- JIT. 실행기 자신은 13%다.
|
