Say where a search's time goes and how to make it and long views fast, with criteria (020)

2 files changed, 167 insertions, 0 deletions

diff --git a/docs/design/020-computing-faster.md b/docs/design/020-computing-faster.md
new file mode 100644
index 0000000..b839e83
--- /dev/null
+++ b/docs/design/020-computing-faster.md
@@ -0,0 +1,84 @@
+# 020 — 계산을 빠르게, 긴 보기를 연결 스레드 밖에서
+
+작성일: 2026-10-04. 상태: 설계와 착수 기준(구현 전).
+[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. 키로 찾기(소속 표, 손가락).
+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%다.
diff --git a/research/experiments/036-faster-loops/bfs-run.c b/research/experiments/036-faster-loops/bfs-run.c
new file mode 100644
index 0000000..a3d9d79
--- /dev/null
+++ b/research/experiments/036-faster-loops/bfs-run.c
@@ -0,0 +1,83 @@
+/* A breadth first search in one event, on the core alone (research 121):
+ * 033's graph.aup, a random graph of NODES nodes and EDGES edges (from and
+ * to uniform, no loops, each pair once; its own generator, seeded), loaded
+ * as rows, then ROUNDS searches from fixed starts, each timed. No host, no
+ * store: what the interpreter costs.
+ *
+ * bfs-run MODULE NODES EDGES ROUNDS   a JSON line per search, then the median */
+#define _POSIX_C_SOURCE 200809L
+#include "module.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+static uint64_t state = 121;
+static uint64_t next(void) { state ^= state << 13; state ^= state >> 7; state ^= state << 17; return state; }
+
+static int compare(const void *a, const void *b) {
+    double x = *(const double *)a, y = *(const double *)b;
+    return (x > y) - (x < y);
+}
+
+static int edge_order(const void *a, const void *b) {
+    uint64_t x = *(const uint64_t *)a, y = *(const uint64_t *)b;
+    return (x > y) - (x < y);
+}
+
+int main(int argc, char **argv) {
+    if (argc != 5) { fputs("bfs-run MODULE NODES EDGES ROUNDS\n", stderr); return 2; }
+    uint32_t nodes = (uint32_t)atol(argv[2]);
+    size_t edges = (size_t)atol(argv[3]), rounds = (size_t)atol(argv[4]);
+    static PureModule module;
+    char error[160];
+    if (pure_module_read(argv[1], &module, error, sizeof(error)) != PURE_OK) { fprintf(stderr, "%s\n", error); return 1; }
+    int size = pure_module_input(&module, "size"), load = pure_module_input(&module, "load"),
+        route = pure_module_input(&module, "route"), hops = pure_module_state(&module, "hops"),
+        reached = pure_module_state(&module, "reached");
+    static PureApp app;
+    if (pure_app_start(&app, &module, (PureData){0}) != PURE_OK) return 1;
+    /* Edges as from * 2^20 + to, sorted, each once (the few drawn twice once). */
+    uint64_t *keys = malloc(edges * sizeof(*keys));
+    size_t count = 0;
+    while (count < edges) {
+        uint64_t a = next() % nodes, b = next() % nodes;
+        if (a != b) keys[count++] = a << 20 | b;
+    }
+    qsort(keys, count, sizeof(*keys), edge_order);
+    size_t unique = 0;
+    for (size_t i = 0; i < count; ++i)
+        if (!unique || keys[i] != keys[unique - 1]) keys[unique++] = keys[i];
+    unsigned char four[4] = {(unsigned char)nodes, (unsigned char)(nodes >> 8), (unsigned char)(nodes >> 16),
+                             (unsigned char)(nodes >> 24)};
+    if (pure_app_message(&app, (uint32_t)size, NULL, -1, (PureSpan){four, 4}) != PURE_OK) return 1;
+    enum { CHUNK = 65536 };
+    double *rows = malloc(CHUNK * 2 * sizeof(*rows));
+    for (size_t at = 0; at < unique; at += CHUNK) {
+        size_t n = unique - at < CHUNK ? unique - at : CHUNK;
+        for (size_t k = 0; k < n; ++k) rows[2 * k] = (double)keys[at + k], rows[2 * k + 1] = (double)(keys[at + k] & 0xFFFFF);
+        if (pure_app_message(&app, (uint32_t)load, NULL, -1, (PureSpan){(unsigned char *)rows, n * 16}) != PURE_OK) {
+            fprintf(stderr, "load failed: %s\n", pure_fault_name(app.fault));
+            return 1;
+        }
+    }
+    double *took = malloc(rounds * sizeof(*took));
+    for (size_t r = 0; r < rounds; ++r) {
+        uint32_t from = (uint32_t)(next() % nodes), to = (uint32_t)(next() % nodes);
+        if (r) next(), next(); /* each search its own pair, whatever came before */
+        unsigned char eight[8];
+        for (int i = 0; i < 4; ++i) eight[i] = (unsigned char)(from >> (8 * i)), eight[4 + i] = (unsigned char)(to >> (8 * i));
+        struct timespec a, b;
+        clock_gettime(CLOCK_MONOTONIC, &a);
+        PureResult result = pure_app_message(&app, (uint32_t)route, NULL, -1, (PureSpan){eight, 8});
+        clock_gettime(CLOCK_MONOTONIC, &b);
+        if (result != PURE_OK) { fprintf(stderr, "route failed: %s\n", pure_fault_name(app.fault)); return 1; }
+        took[r] = (double)(b.tv_sec - a.tv_sec) * 1e3 + (double)(b.tv_nsec - a.tv_nsec) / 1e6;
+        printf("{\"from\":%u,\"to\":%u,\"hops\":%g,\"reached\":%g,\"ms\":%.2f,\"work\":%llu}\n", from, to,
+               app.values[hops].num, app.values[reached].num, took[r], (unsigned long long)app.work);
+    }
+    qsort(took, rounds, sizeof(*took), compare);
+    printf("{\"nodes\":%u,\"edges\":%zu,\"median_ms\":%.2f}\n", nodes, unique, took[rounds / 2]);
+    pure_app_stop(&app);
+    return 0;
+}