diff options
| -rw-r--r-- | docs/design/021-past-c.md | 17 | ||||
| -rw-r--r-- | research/experiments/038-past-c/2026-10-05-bfs-f3e3fe6.jsonl | 16 | ||||
| -rw-r--r-- | research/experiments/038-past-c/2026-10-05-seekfloor.jsonl | 5 | ||||
| -rw-r--r-- | research/experiments/038-past-c/seekfloor.c | 54 |
4 files changed, 91 insertions, 1 deletions
diff --git a/docs/design/021-past-c.md b/docs/design/021-past-c.md index ec0df36..6cfcfcc 100644 --- a/docs/design/021-past-c.md +++ b/docs/design/021-past-c.md @@ -1,6 +1,6 @@ # 021 — C보다 빠르게 -작성일: 2026-10-05. 상태: 설계와 착수 기준(구현 전). +작성일: 2026-10-05. 상태: 1–4단계를 구현해 쟀다. 아래 "바로잡음"이 처음의 산수를 고친다. [020](020-computing-faster.md)이 BFS(노드 10만, 간선 100만) 한 번을 397 ms에서 187 ms로 줄였다([121](../research/121-computing-faster.md)). 같은 탐색을 C(033의 `bfs.c`: 인접을 오프셋 배열로, 깊이는 `int32_t` 배열)는 9 ms에 한다. 목표는 그 C보다 빠른 것이다. 같은 aup 코드, 같은 뜻(키 있는 리스트, 인덱스는 위치, 결정적인 결과), 같은 기계에서. @@ -22,6 +22,21 @@ C의 9 ms는 Pi 5(Cortex-A76, 2.4 GHz)에서 약 2,160만 사이클이다. 키 집합을 비트로 고른다). - **그래서 기대하는 것은 1.3–1.8배다**(5–7 ms), 10배가 아니다. 10 ms에 머물면 그렇게 적는다. +## 바로잡음 (2026-10-05, 1–4단계를 해 보고) + +위의 산수는 명령의 수만 셌다. 잰 것은 다르다. + +- **저장된 리스트의 디렉터리**(3)는 만들어 쟀고 넣지 않았다: 탐색 하나의 명령은 3.6% 줄었지만 사이클은 6% 늘었다. 칸의 표(760 KB)와 + 잎의 표(500 KB)가 L2(512 KB)에 들지 않아, B+트리 위쪽 단(캐시에 있다)을 내려가는 것보다 미스가 많았다. "필수"라는 판단은 틀렸다. +- **바닥은 메모리 지연이다.** `038-past-c/seekfloor.c`: 간선 100만 개의 리스트에서 노드마다 조각의 두 경계를 찾고 첫 간선을 읽는 데, + BFS처럼 무작위 차례로 노드 하나에 373 ns가 든다. 같은 일을 C의 오프셋 배열(`start[v]`, `to[start]`)은 21 ns에 한다. C의 반복끼리는 + 서로 기다리지 않아 미스가 겹치고, B+트리는 뿌리에서 잎까지 서로 기다리는 읽기를 넷 한다. 이것만으로 10만 노드에 18–37 ms다. +- 그래서 **저장된 키 있는 리스트가 B+트리뿐인 한, JIT만으로는 C(9 ms)를 넘지 못한다.** 바닥은 25–35 ms 근처로 본다. "1.3–1.8배 + 앞선다"는 예측은 틀렸다. +- C를 넘으려면 둘 다 있어야 한다: 저장된 키 있는 리스트의 조각을 L2에 드는 색인으로 찾는 형태(잎 하나에 칸 하나, 칸에서 잎으로 + 바로: C의 `start[v]` → `to[k]`와 같은 사슬)와, 검사를 루프 밖으로 빼고 값을 레지스터에 두는 JIT. 앞의 것은 저장 형태의 일이라 + 설계 022로 따로 적고 기준을 둔다. + ## 원칙 - **뜻은 그대로.** 키 있는 리스트는 키 순서의 리스트이고 인덱스는 위치다. 바뀌는 것은 표현과 실행의 길이다. 어느 길로 가든 diff --git a/research/experiments/038-past-c/2026-10-05-bfs-f3e3fe6.jsonl b/research/experiments/038-past-c/2026-10-05-bfs-f3e3fe6.jsonl new file mode 100644 index 0000000..72d0665 --- /dev/null +++ b/research/experiments/038-past-c/2026-10-05-bfs-f3e3fe6.jsonl @@ -0,0 +1,16 @@ +{"system": "c", "from": 42224, "to": 57393, "hops": 6, "reached": 99996, "us": 8938.2} +{"system": "c", "from": 5153, "to": 48368, "hops": 6, "reached": 99996, "us": 8946.3} +{"system": "c", "from": 73314, "to": 58793, "hops": 5, "reached": 99996, "us": 8992.0} +{"system": "c", "from": 47063, "to": 90963, "hops": 5, "reached": 99996, "us": 9011.5} +{"system": "c", "from": 67811, "to": 96464, "hops": 5, "reached": 99996, "us": 9002.6} +{"system": "python", "from": 42224, "to": 57393, "us": 439204.9} +{"system": "python", "from": 5153, "to": 48368, "us": 450209.7} +{"system": "python", "from": 73314, "to": 58793, "us": 441184.5} +{"system": "python", "from": 47063, "to": 90963, "us": 451578.7} +{"system": "python", "from": 67811, "to": 96464, "us": 443178.3} +{"system": "pure", "from": 42224, "to": 57393, "hops": 6, "reached": 99996, "us": 89278.4} +{"system": "pure", "from": 5153, "to": 48368, "hops": 6, "reached": 99996, "us": 88753.7} +{"system": "pure", "from": 73314, "to": 58793, "hops": 5, "reached": 99996, "us": 89680.4} +{"system": "pure", "from": 47063, "to": 90963, "hops": 5, "reached": 99996, "us": 90632.1} +{"system": "pure", "from": 67811, "to": 96464, "hops": 5, "reached": 99996, "us": 88629.1} +{"nodes": 100000, "edges": 1000000, "median_us": {"c": 8992.0, "python": 443178.3, "pure": 89278.4}, "pure_over_c": 9.9, "pure_over_python": 0.2} diff --git a/research/experiments/038-past-c/2026-10-05-seekfloor.jsonl b/research/experiments/038-past-c/2026-10-05-seekfloor.jsonl new file mode 100644 index 0000000..b106f44 --- /dev/null +++ b/research/experiments/038-past-c/2026-10-05-seekfloor.jsonl @@ -0,0 +1,5 @@ +{"round":0,"pure_ns_per_node":441.2,"c_ns_per_node":23.6,"same":1} +{"round":1,"pure_ns_per_node":378.4,"c_ns_per_node":21.4,"same":1} +{"round":2,"pure_ns_per_node":380.1,"c_ns_per_node":21.1,"same":1} +{"round":3,"pure_ns_per_node":380.5,"c_ns_per_node":21.2,"same":1} +{"round":4,"pure_ns_per_node":388.1,"c_ns_per_node":28.8,"same":1} diff --git a/research/experiments/038-past-c/seekfloor.c b/research/experiments/038-past-c/seekfloor.c new file mode 100644 index 0000000..23fcdc8 --- /dev/null +++ b/research/experiments/038-past-c/seekfloor.c @@ -0,0 +1,54 @@ +/* The floor a stored keyed list sets for a search (021): per node, the two + * seeks of its slice (as slice_of does), in a random order of nodes, against + * C's offsets: start[v], start[v+1] and the first to[] of the node. */ +#define _POSIX_C_SOURCE 200809L +#include "module-list.h" +#include <stdio.h> +#include <stdlib.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 double now(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec * 1e9 + t.tv_nsec; } +static int cmp64(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(void) { + enum { N = 100000, M = 1000000 }; + uint64_t *e = malloc(M * sizeof(*e)); + for (size_t k = 0; k < M; ++k) { uint64_t a = next() % N, b = next() % N; e[k] = a << 20 | b; } + qsort(e, M, sizeof(*e), cmp64); + size_t m = 0; + for (size_t k = 0; k < M; ++k) if (!m || e[k] != e[m - 1]) e[m++] = e[k]; + static const uint8_t kinds[3] = {PURE_CELL_NUMBER, PURE_CELL_NUMBER, PURE_CELL_NUMBER}; + PureList *list = pure_list_new(3, kinds); + pure_list_keyed(list, 0); + for (size_t k = 0; k < m; ++k) { + PureCell cells[3] = {{.num = (double)e[k]}, {.num = (double)(e[k] & 0xFFFFF)}, {.num = 1}}; + pure_list_insert(list, k, cells, NULL); + } + uint32_t *start = calloc(N + 1, 4), *to = malloc(m * 4); + for (size_t k = 0; k < m; ++k) { ++start[(e[k] >> 20) + 1]; to[k] = (uint32_t)(e[k] & 0xFFFFF); } + for (size_t v = 0; v < N; ++v) start[v + 1] += start[v]; + uint32_t *order = malloc(N * 4); + for (uint32_t v = 0; v < N; ++v) order[v] = v; + for (uint32_t v = N - 1; v > 0; --v) { uint32_t w = (uint32_t)(next() % (v + 1)), t = order[v]; order[v] = order[w]; order[w] = t; } + for (int round = 0; round < 5; ++round) { + double t0 = now(); + size_t sum = 0; + for (size_t i = 0; i < N; ++i) { + double low = (double)((uint64_t)order[i] << 20), high = (double)(((uint64_t)order[i] + 1) << 20); + bool found; + size_t a = pure_list_seek(list, 0, (PureCell){.num = low}, &found), b = pure_list_seek(list, 0, (PureCell){.num = high}, &found); + sum += b - a; + if (a < b) sum += (size_t)pure_list_get(list, a, 1).num; /* the slice's first item read, as the walk does */ + } + double t1 = now(); + size_t csum = 0; + for (size_t i = 0; i < N; ++i) { + uint32_t v = order[i], s = start[v], f = start[v + 1]; + csum += f - s; + if (s < f) csum += to[s]; + } + double t2 = now(); + printf("{\"round\":%d,\"pure_ns_per_node\":%.1f,\"c_ns_per_node\":%.1f,\"same\":%d}\n", round, (t1 - t0) / N, (t2 - t1) / N, sum == csum); + } + return 0; +} |