Measure an index for a stored list's slices outside the list: three times a tree's seek, still seven times C's (021)

3 files changed, 121 insertions, 3 deletions

diff --git a/docs/design/021-past-c.md b/docs/design/021-past-c.md
index 6cfcfcc..5ff1c61 100644
--- a/docs/design/021-past-c.md
+++ b/docs/design/021-past-c.md
@@ -33,9 +33,14 @@ C의 9 ms는 Pi 5(Cortex-A76, 2.4 GHz)에서 약 2,160만 사이클이다.
   서로 기다리지 않아 미스가 겹치고, 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로 따로 적고 기준을 둔다.
+- **색인의 시제품**(`038-past-c/indexfloor.c`, 리스트 밖에서): 잎을 B+트리처럼 흩어 두고(항목 32개, 열 셋), 키의 범위를 2의
+  거듭제곱 폭의 칸으로 나눠 칸마다 첫 항목의 잎과 자리, 위치를 둔다. 칸의 원점을 폭의 배수에 맞추면(조각의 경계가 칸의 시작이
+  된다) 노드 하나에 124–134 ns, 맞추지 않으면 350–470 ns다. 같은 측정에서 C는 17–21 ns다. 둘 다 노드마다 DRAM 미스 하나인데,
+  C는 반복 하나가 명령 여덟 남짓이고 반복끼리 서로 기다리지 않아 미스 여럿을 겹친다. 색인은 B+트리보다 세 배 빠르지만, 노드마다
+  하는 일이 C만큼 짧지 않으면 C에 닿지 않는다.
+- 그래서 C를 넘으려면 색인과 함께, 노드 하나와 간선 하나에 하는 일이 C와 같은 크기여야 한다(간선마다 명령 열 남짓, 노드마다 백
+  남짓, 서로 기다리는 읽기 둘). 지금 JIT은 간선마다 약 80, 노드마다 수백이다. 그만큼 줄이는 것(값을 레지스터에, 검사를 루프
+  밖으로, 표현이 바뀌지 않는다는 가정을 루프 머리에서 한 번 확인)은 최적화 컴파일러의 일이다.
 
 ## 원칙
 
diff --git a/research/experiments/038-past-c/2026-10-05-indexfloor.jsonl b/research/experiments/038-past-c/2026-10-05-indexfloor.jsonl
new file mode 100644
index 0000000..373cd9b
--- /dev/null
+++ b/research/experiments/038-past-c/2026-10-05-indexfloor.jsonl
@@ -0,0 +1,10 @@
+{"per_bucket":8,"round":0,"index_ns_per_node":127.3,"c_ns_per_node":16.9,"same":1}
+{"per_bucket":8,"round":1,"index_ns_per_node":126.6,"c_ns_per_node":16.7,"same":1}
+{"per_bucket":8,"round":2,"index_ns_per_node":126.6,"c_ns_per_node":16.7,"same":1}
+{"per_bucket":8,"round":3,"index_ns_per_node":125.9,"c_ns_per_node":16.7,"same":1}
+{"per_bucket":8,"round":4,"index_ns_per_node":131.2,"c_ns_per_node":17.3,"same":1}
+{"per_bucket":32,"round":0,"index_ns_per_node":378.8,"c_ns_per_node":16.7,"same":1}
+{"per_bucket":32,"round":1,"index_ns_per_node":379.5,"c_ns_per_node":16.9,"same":1}
+{"per_bucket":32,"round":2,"index_ns_per_node":382.1,"c_ns_per_node":16.7,"same":1}
+{"per_bucket":32,"round":3,"index_ns_per_node":379.8,"c_ns_per_node":16.6,"same":1}
+{"per_bucket":32,"round":4,"index_ns_per_node":376.3,"c_ns_per_node":16.5,"same":1}
diff --git a/research/experiments/038-past-c/indexfloor.c b/research/experiments/038-past-c/indexfloor.c
new file mode 100644
index 0000000..7991ee3
--- /dev/null
+++ b/research/experiments/038-past-c/indexfloor.c
@@ -0,0 +1,103 @@
+/* A prototype of 022's index, before building it in the list: leaves as a
+ * B+tree keeps them (32 items, three number columns, allocated apart and
+ * not in order), a bucket table (a power of two of keys each, about eight
+ * items a bucket: the leaf and place of its first item) and the leaves'
+ * table (pointer, first position). Per node, in a random order: the slice's
+ * two bounds and its first item's second field, as seekfloor; against C's
+ * offsets. */
+#define _POSIX_C_SOURCE 200809L
+#include <math.h>
+#include <stdint.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 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); }
+typedef struct { uint64_t made; uint32_t count; uint8_t leaf; size_t items; void *first; double lead; double key[32], to[32], w[32]; } Leaf;
+typedef struct { const Leaf *leaf; uint32_t start; } LeafAt;
+int main(int argc, char **argv) {
+    unsigned per_bucket = argc > 1 ? (unsigned)atoi(argv[1]) : 8;
+    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];
+    size_t leaves = (m + 31) / 32;
+    Leaf **pool = malloc(leaves * sizeof(*pool));
+    for (size_t i = 0; i < leaves; ++i) pool[i] = malloc(sizeof(Leaf));
+    for (size_t i = leaves - 1; i > 0; --i) { size_t j = next() % (i + 1); Leaf *t = pool[i]; pool[i] = pool[j]; pool[j] = t; } /* apart, not in order */
+    LeafAt *table = malloc(leaves * sizeof(*table));
+    for (size_t i = 0; i < leaves; ++i) {
+        Leaf *l = pool[i];
+        l->count = 0;
+        for (size_t k = i * 32; k < m && k < i * 32 + 32; ++k) l->key[l->count] = (double)e[k], l->to[l->count] = (double)(e[k] & 0xFFFFF), l->w[l->count++] = 1;
+        table[i] = (LeafAt){l, (uint32_t)(i * 32)};
+    }
+    double low = (double)e[0], span = (double)e[m - 1] - low;
+    int exponent;
+    frexp(span / (double)(m / per_bucket + 1), &exponent);
+    double scale = ldexp(1.0, -exponent);
+    low = floor(low * scale) / scale; /* buckets start at multiples of their width */
+    span = (double)e[m - 1] - low;
+    size_t buckets = (size_t)floor(span * scale) + 2;
+    uint32_t *first = malloc(buckets * 4), *bucket_pos = malloc(buckets * 4);
+    size_t filled = 0;
+    for (size_t i = 0; i < leaves; ++i)
+        for (unsigned j = 0; j < table[i].leaf->count; ++j) {
+            size_t b = (size_t)floor((table[i].leaf->key[j] - low) * scale);
+            while (filled <= b) bucket_pos[filled] = (uint32_t)(i * 32 + j), first[filled++] = (uint32_t)(i << 5 | j);
+        }
+    while (filled < buckets) bucket_pos[filled] = (uint32_t)m, first[filled++] = (uint32_t)(leaves << 5);
+    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; }
+    fprintf(stderr, "buckets %zu (%zu KB) leaves table %zu KB\n", buckets, buckets * 4 / 1024, leaves * sizeof(*table) / 1024);
+    for (int round = 0; round < 5; ++round) {
+        double t0 = now();
+        size_t sum = 0;
+        for (size_t i = 0; i < N; ++i) {
+            size_t pos[2];
+            const Leaf *leaf0 = NULL;
+            unsigned place0 = 0;
+            for (int side = 0; side < 2; ++side) {
+                double key = (double)(((uint64_t)order[i] + (uint64_t)side) << 20);
+                double at = floor((key - low) * scale);
+                size_t b = !(at > 0) ? 0 : at >= (double)buckets ? buckets - 1 : (size_t)at;
+                if (side && b < buckets && low + (double)b / scale == key) { pos[1] = bucket_pos[b]; break; } /* a bucket's start: its position, no leaf read */
+                size_t li = first[b] >> 5;
+                unsigned place = first[b] & 31;
+                for (;;) {
+                    if (li >= leaves) { pos[side] = m; break; }
+                    const Leaf *l = table[li].leaf;
+                    while (place < l->count && l->key[place] < key) ++place;
+                    if (place < l->count) {
+                        pos[side] = table[li].start + place;
+                        if (!side) leaf0 = l, place0 = place;
+                        break;
+                    }
+                    ++li, place = 0;
+                }
+            }
+            sum += pos[1] - pos[0];
+            if (pos[0] < pos[1]) sum += (size_t)leaf0->to[place0];
+        }
+        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("{\"per_bucket\":%u,\"round\":%d,\"index_ns_per_node\":%.1f,\"c_ns_per_node\":%.1f,\"same\":%d}\n", per_bucket, round,
+               (t1 - t0) / N, (t2 - t1) / N, sum == csum);
+    }
+    return 0;
+}