diff options
Diffstat (limited to 'docs/design')
| -rw-r--r-- | docs/design/020-computing-faster.md | 19 |
1 files changed, 18 insertions, 1 deletions
diff --git a/docs/design/020-computing-faster.md b/docs/design/020-computing-faster.md index b839e83..35cc071 100644 --- a/docs/design/020-computing-faster.md +++ b/docs/design/020-computing-faster.md @@ -1,6 +1,6 @@ # 020 — 계산을 빠르게, 긴 보기를 연결 스레드 밖에서 -작성일: 2026-10-04. 상태: 설계와 착수 기준(구현 전). +작성일: 2026-10-04. 상태: 설계와 착수 기준. 1단계 구현(아래 "1단계에서 달라진 것"), 검사로 고정했다. [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)). @@ -50,6 +50,23 @@ - 본문이 없는 보기(식 하나)는 지금처럼 연결 스레드가 계산한다(가장 흔하고 짧은 길을 그대로 둔다). - 넘긴 일이 `--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`의 것과 같다. +- **손가락은 스레드마다 넷이다**(리스트 하나가 아니라: 걷기와 큐와 `seen`이 번갈아 읽는다). 리스트의 번호와 판이 맞을 때만 쓴다. + 스냅숏의 사본은 리스트와 번호가 같고 판이 다르다. 키로 찾기도 손가락의 잎에서 먼저 본다. +- 설계에 없던 넷: 항목의 필드가 text인지를 로드할 때 명령에 적기(실행할 때마다 찾지 않게), 각 단에서 자식 찾기를 이분 탐색이 + 아니라 세기로(가지 32개를 모두 비교해 센다, 벡터가 된다), 실행기의 루프를 재귀 없이(루프 기록의 스택), `module-list.c`를 + `-O3`로(`Makefile`의 `LIST_OPTIMIZE`). 넷의 몫은 204 ms에서 186 ms이고 거의 다 `-O3`다. +- 해 보고 뺀 것: 잎의 울타리(키로 찾은 잎의 다음 잎의 첫 키, 손가락이 키 범위를 더 넓게 알게) — 185.5 대 185.5 ms. 손가락의 + 앞으로 옮기기는 남겼지만 차이는 재지 못했다(206 대 204 ms). + ## 단계 1. 키로 찾기(소속 표, 손가락). |