diff options
| -rw-r--r-- | docs/design/022-arrays-and-registers.md | 151 | ||||
| -rw-r--r-- | research/experiments/038-past-c/2026-10-05-bfsfloor-alone.jsonl | 90 | ||||
| -rw-r--r-- | research/experiments/038-past-c/2026-10-05-bfsfloor-widths.jsonl | 72 | ||||
| -rw-r--r-- | research/experiments/038-past-c/2026-10-05-roundtrip.jsonl | 3 | ||||
| -rw-r--r-- | research/experiments/038-past-c/bfsfloor.c | 54 | ||||
| -rw-r--r-- | research/experiments/038-past-c/roundtrip.py | 39 | ||||
| -rw-r--r-- | research/experiments/038-past-c/runs.sh | 32 |
7 files changed, 434 insertions, 7 deletions
diff --git a/docs/design/022-arrays-and-registers.md b/docs/design/022-arrays-and-registers.md new file mode 100644 index 0000000..12f0870 --- /dev/null +++ b/docs/design/022-arrays-and-registers.md @@ -0,0 +1,151 @@ +# 022 — 배열과 레지스터로 C를 넘기 + +작성일: 2026-10-05. 상태: 설계와 착수 기준. +[021](021-past-c.md)은 BFS(노드 10만, 간선 100만) 한 번을 190 ms에서 90 ms로 줄였지만 C(9.1 ms)를 넘지 못했다 +([123](../research/123-past-c.md)). 123의 바닥은 길이 있다고 말한다: Pure의 표현대로 손으로 쓴 C가 C를 넘는 것은 저장된 리스트가 +배열이고, 열이 값만큼 좁고, 다음 노드를 미리 읽을 때뿐이다. 목표는 그대로다. 같은 aup 코드, 같은 뜻, 같은 기계에서 C보다 빠르게. + +## 산수: 재어 본 것 + +모두 Pi 5(Cortex-A76 2.4 GHz, L2 512 KB, L3 2 MB), RAM. `bfsfloor.c`는 [038](../../research/experiments/038-past-c/)에 있다. + +**C의 자리.** `bfs.c`는 탐색 하나를 21번 돌려 중앙값을 낸다(표가 데워진 채로). + +| | 그래프 | C | +|---|---|---:| +| 033의 `bfs.py` (HTTP 기준이 견주는 C) | `bfs.py`의 것(시드 118) | 9.03–9.08 ms | +| `bfsfloor c`, 한 프로세스에 한 형태 (`-alone`) | `bfs-run`의 것(시드 121) | 9.42–9.56 ms | + +**바닥.** 같은 방법(한 프로세스에 한 형태, 21번의 중앙값, 세 라운드)으로 손으로 쓴 Pure의 형태 +(`2026-10-05-bfsfloor-alone.jsonl`): + +| 형태 | 시간 | +|---|---:| +| `packed`: 저장된 리스트를 배열과 칸의 색인으로, 열은 모두 수(8바이트) | 23.1–23.3 ms | +| `narrow`: 열을 값만큼 좁게(u32, u8), 조밀한 리스트의 키 열은 두지 않음 | 12.8–13.0 ms | +| `narrow_ahead`: 그리고 큐의 앞 노드(16번 뒤의 칸, 8번 뒤의 첫 간선)를 미리 읽음 | **8.26–8.66 ms** | +| `c_ahead`: C에 같은 미리 읽기 (맥락) | 7.06–7.13 ms | + +- `narrow_ahead`는 같은 그래프의 C보다 8–12% 빠르다. 명령은 C의 2.2배(2,170만 대 990만)이고, 이기는 것은 미스를 겹쳐서다(IPC + 1.06 대 0.44). +- 이것이 이 설계가 닿을 수 있는 가장 좋은 자리로 본다. JIT이 내는 코드는 손으로 쓴 C보다 길기 쉽다. + +**칸의 폭**(`2026-10-05-bfsfloor-widths.jsonl`). 칸의 폭이 조각의 경계(`node * 2^20`)의 배수가 아니면 경계가 칸 안에 떨어지고, +찾기가 키 열(8바이트, 8 MB)을 읽는다: + +| 칸 하나의 항목 (폭) | 칸 | `narrow_ahead` | +|---|---:|---:| +| 8 (2^20) | 100,001 | 8.26–8.66 ms | +| 4 (2^19) | 200,000 | 8.99–9.10 ms | +| 16 (2^21) | 50,001 | 22.3–22.7 ms | +| 32 (2^22) | 25,001 | 28.5 ms | + +폭을 항목 수만으로 고르면(021의 디렉터리처럼) 이 그래프에서는 우연히 맞고, 노드마다 간선이 다섯이면 2^21이 되어 세 배 느려진다. +그래서 폭은 **찾은 키에 맞춘다**(아래 1). 키를 `앞 * 2^k + 뒤`로 합쳐 앞으로 조각을 찾는 것은 aup에서 인접을 쓰는 방법이다(TPC-C도 +`order * 16 + line`이다). BFS만의 모양이 아니다. + +**HTTP의 몫.** 같은 앱에 거의 일이 없는 쓰기(`POST /inputs/size`)의 왕복이 0.15 ms(읽기 0.08 ms)다. 021에서 HTTP로 잰 Pure는 +코어만 잰 것보다 0.6 ms 길었다(90.0 대 89.4, 그래프가 다르다). 그래서 HTTP 기준(Pure < 9.08 ms)에는 코어 8.48 ms 아래가 필요하다. + +**그래서:** + +- 코어의 기준(같은 프로세스의 C보다 빠르게)은 JIT의 코드가 바닥의 1.10배 안이면 선다. +- HTTP의 기준은 코어가 바닥의 중앙값(8.59 ms)보다 조금 짧아야 선다. **산수로 반반이다.** 바닥보다 짧아질 여지는 있다: 바닥은 루프의 + `i`를 수로 세고, 칸을 수로 계산하고, 미리 읽기가 같은 계산을 두 번 한다. JIT은 그것을 정수로 할 수 있다. 그래도 미달이면 미달로 + 적는다. +- 지금의 JIT은 간선 하나에 약 80 명령, BFS 하나에 3억 1,900만이다. 바닥은 2,170만이다. 15배를 줄이는 일이다. + +## 원칙 + +- **뜻은 그대로.** 키 있는 리스트는 키 순서의 리스트, 인덱스는 위치, 수는 수(−0은 −0)다. 표현과 실행의 길만 바뀐다. 어느 길로 + 가든 결과(값, 결함, 실행량, 메모리의 몫)는 바이트까지 같다. +- **벤치마크의 모양을 넣지 않는다.** 칸의 폭은 찾은 키에서, 미리 읽기는 "차례로 읽은 값으로 다른 리스트를 찾는" 일반적인 모양에서 + 온다. 코드에 그래프나 `1048576`을 아는 곳은 없다. +- **모든 길이 끝까지 간다.** 빠른 길은 가정(리스트의 표현, 열의 폭, 칸의 색인)을 루프 머리에서 확인하고, 가정이 깨지면 그 자리에서 + 일반적인 코드로 넘어간다. 일반적인 코드는 지금의 JIT과 실행기다. +- **값은 일이 쓴 만큼.** 배열과 색인은 많이 찾는 리스트에만 만든다. 바뀌면 버린다. 둘 다 그 비용을 산수로 정한다. + +## 모양 + +### 1. 저장된 키 있는 리스트를 배열로 펴기 + +- **언제.** 수로 키를 둔 저장된 리스트(항목 4,096 이상)가 한 판(version)에서 키로 찾기를 항목 수의 8분의 1번 넘게 받으면, 그 판을 + 배열로 편다: 필드마다 열 하나(이벤트의 리스트의 FLAT과 같은 모양)와 칸의 색인. 펴기는 O(n)이고 열을 한 번 베낀다(항목 하나에 + 몇 ns로 본다; 재서 적는다). 트리에서 찾기 한 번이 수백 ns이니, 펴기 전의 n/8번의 찾기(항목 하나에 수십 ns)가 펴기보다 크다. +- **바뀌면 트리로.** 편 리스트에 바뀜(넣기, 지우기, 고치기, 비우기)이 오면 먼저 트리로 돌린다(O(n), 정렬된 배열에서 아래부터 + 짓는다). 바뀌는 리스트는 판마다 찾기를 다시 세니 다시 펴지지 않는다. 그래서 TPC-C처럼 늘 바뀌는 리스트는 늘 트리다. +- **칸의 색인.** 칸마다 그 칸의 시작 키 이상인 첫 위치(u32). 칸은 2의 거듭제곱 폭이고 원점은 폭의 배수다. 폭은 펼 때까지 찾은 + 키들의 정렬(원점과의 차의 끝에 있는 0 비트 수의 가장 작은 것)과 항목 수(칸 하나에 항목 여덟)에서 작은 쪽이다. 칸은 항목 수를 + 넘지 않는다(색인이 항목 하나에 4바이트를 넘지 않는다). 찾기: 칸을 곱셈 하나로 내고, 키가 칸의 시작이면 그 칸의 첫 위치가 답이다 + (읽기 하나). 아니면 거기서 키 열을 앞으로 본다. +- **나누기.** 스냅숏의 사본은 편 배열을 함께 쓴다(참조 수). 배열은 펴진 동안 바뀌지 않는다. 트리로 돌릴 때 배열을 놓는데, 사본이 + 쥐고 있으면 참조만 줄인다. 텍스트는 지금처럼 리스트가 갖고, 놓을 때는 지금의 판(epoch)으로 늦춘다. +- **저널, 인코딩, 메모리의 몫.** 저널은 바뀜에서 나오는데 바뀜은 트리에서 일어나니 그대로다. 인코딩은 배열을 차례로 읽는다. + `bytes`(상태의 몫)는 표현과 상관없다. 배열은 트리보다 작다(잎에는 빈 자리와 머리가 있고, 안쪽 노드가 있다). +- 1단계만으로 지금의 JIT에서 BFS의 조각 찾기(노드마다 두 번)가 읽기 하나가 된다. + +### 2. 좁은 열 + +- 배열(이벤트의 리스트의 FLAT과 DENSE, 편 리스트)의 수 열마다 폭이 있다: u8, u16, u32(0 이상의 정수, −0이 아닌), 그리고 수(8바이트). + 처음 값이 들어갈 때 가장 좁은 폭에서 시작하고, 맞지 않는 값이 오면 열 전체를 그 값이 들어가는 폭으로 넓힌다(열마다 많아야 세 번). + i64와 텍스트의 열은 그대로다. +- 조밀한(DENSE) 리스트는 키 필드의 열을 두지 않는다. 그 칸은 키 그 자체다. +- 읽기는 폭을 보고 넓혀 읽는다. 이것만으로는 명령이 늘 수 있다. 2단계는 3단계와 함께 잰다. 혼자서는 시간이 그대로일 수 있다. + +### 3. 최적화하는 JIT + +지금의 JIT은 값을 메모리의 스택에 두고, 명령마다 리스트의 표현을 다시 보고, 수와 정수를 오간다. 바꿀 것: + +- **스택의 값을 레지스터에.** 블록을 옮길 때 컴파일 중의 스택(상수, 수의 레지스터, 정수의 레지스터, 조건 플래그, 메모리)을 들고 + 간다. C를 부르기 전과 분기가 모이는 곳에서만 메모리에 내린다. +- **정수로 아는 값은 정수로.** 행 번호, 좁은 열에서 읽은 값, 개수, 루프의 셈은 정수 레지스터에 둔다. `has`와 항목 읽기는 그 정수를 + 그대로 쓴다(수로 바꿨다가 되돌리지 않는다). 수가 필요한 곳에서만 바꾼다. +- **루프 머리의 가정.** `EACH`와 `LOOP`이 열릴 때, 본문이 쓰는 리스트마다 표현, 열의 주소와 폭, 키 비트의 주소와 크기, 개수와 + 자리를 레지스터에 쥐고 확인한다. 본문 안에서는 그 리스트를 바꿀 수 있는 명령(그 리스트에 넣기, 덧붙이기, 고치기, 지우기, 그리고 + 그런 C 부르기) 뒤에서만 다시 읽고 확인한다(어느 명령이 어느 리스트를 바꾸는지는 로드할 때 안다). 가정이 깨지면 스택을 내리고 + 같은 자리의 일반적인 코드로 넘어간다. +- **비교와 분기를 하나로.** 비교, `NOT`, `has` 뒤의 `JZ`는 플래그나 비트의 분기 하나다. +- **이벤트의 리스트에 쓰기를 코드로.** 조밀한 리스트에 키로 넣기(키가 자리 안이고 없을 때), 납작한 리스트에 덧붙이기(자리가 있을 + 때)는 코드로 한다. 아니면 C를 부른다. +- **값이 맞는 블록만.** 루프의 본문에 코드로 쓴 명령이 적은 블록은 컴파일하지 않는다(123: TPC-C의 루프는 명령마다 `step`을 불러 + 2.1% 느렸다). + +### 4. 미리 읽기 + +루프가 차례로 읽는 리스트(A)의 값으로 다른 리스트(B)를 키로 찾거나 조각을 걸으면(그 사이가 결함 없는 산술뿐이면), 루프 머리에서 몇 +번 뒤의 A의 값으로 같은 계산을 해 B의 칸과 첫 항목을 미리 읽는다(prefetch). A가 아직 그만큼 길지 않으면 하지 않는다. 미리 읽기는 +결과를 바꾸지 않는다. 간접 접근의 소프트웨어 미리 읽기는 컴파일러의 일반적인 기법이다(Ainsworth와 Jones, CGO 2017). + +## 단계 + +1. 저장된 리스트를 배열로 펴기와 칸의 색인. +2. 좁은 열. +3. 최적화하는 JIT. +4. 미리 읽기. + +단계마다 검사로 고정하고 재서 커밋한다. 2는 3과 함께 잰다. + +## 착수 기준 + +- **최소 확인** + - `test-module`: + - 편 리스트가 무작위 연산의 열에서 트리만의 리스트와 매 걸음 같은 답을 낸다(펴기와 트리로 돌리기, 사본, 저널, 인코딩을 지나며). + - 좁은 열의 배열이 넓은 열의 것과 같은 답을 낸다(넓히기의 모든 경계, −0, 정수의 끝). + - JIT이 있는 빌드에서 Pure의 `make check`(ASan 포함)와 aup의 검사(무작위로 만든 프로그램, 참조 모델과의 대조), Vega의 검사가 + `PURE_JIT=1`과 `PURE_JIT=0`에서 모두 초록이다. + - 기기 사이: 같은 `pure-run` 46번이 Pi(JIT), WSL2와 Mac(실행기)에서 출력, 오류, 종료 코드까지 같다. +- **통과 조건**(RAM의 Pi 5) + - 코어만 잰 BFS: `bfs-run`이 같은 그래프로 같은 프로세스에서 C의 BFS(`bfs.c`의 루프, 21번의 중앙값)를 함께 돌리고, Pure의 중앙값이 + 그보다 작다. 같은 계열에서 탐색마다 거리, 닿은 노드 수, 실행량을 `PURE_JIT=0`의 것과 견주어 모두 같다. + - HTTP로 잰 BFS(033의 `bfs.py`): Pure의 중앙값이 C(`bfs.c`, 커밋된 그대로)의 중앙값보다 작다. 산수로 반반이다(위). + - 지금의 앱: TPC-C와 은행 질의를 여섯 쌍 번갈아 잰 중앙값이 `b1b3c7b`보다 1% 넘게 느리지 않고, 021 전(`a553601`)보다 3% 넘게 느리지 + 않다(쌓인 값의 한계). 은행 질의의 명령 수가 `b1b3c7b`보다 1% 넘게 늘지 않는다. +- **밝히는 것**: 단계마다의 BFS 시간과 명령 수. 첫 탐색이 펴기에 쓰는 값. 편 `edges`와 트리의 메모리. JIT의 BFS 코드와 바닥의 + 명령 수. + +## 하지 않는 것 + +- 알고리즘을 바꾸기(방향을 바꾸는 BFS 같은), 같은 이벤트의 결과를 기억해 두기, 탐색을 여러 코어로 나누기. 같은 프로그램을 같은 + 차례로 한 코어에서 실행한다. +- `bfs.c`를 고치기. 견주는 C는 커밋된 그대로다(`c_ahead`는 맥락이다). +- macOS의 JIT, x86-64의 JIT. diff --git a/research/experiments/038-past-c/2026-10-05-bfsfloor-alone.jsonl b/research/experiments/038-past-c/2026-10-05-bfsfloor-alone.jsonl new file mode 100644 index 0000000..bb9184e --- /dev/null +++ b/research/experiments/038-past-c/2026-10-05-bfsfloor-alone.jsonl @@ -0,0 +1,90 @@ +{"round":1,"form":"c","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":9.513,"instructions":9930943,"cycles":22598532,"branch_misses":232710,"l1d_misses":1187985,"llc_misses":196358,"work":0} +{"round":1,"form":"c","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":9.565,"instructions":9930943,"cycles":22670765,"branch_misses":234181,"l1d_misses":1187951,"llc_misses":198661,"work":0} +{"round":1,"form":"c","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":9.718,"instructions":9930952,"cycles":23008498,"branch_misses":233813,"l1d_misses":1187712,"llc_misses":202749,"work":0} +{"round":1,"form":"c","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":9.554,"instructions":9930943,"cycles":22859537,"branch_misses":233719,"l1d_misses":1187927,"llc_misses":200955,"work":0} +{"round":1,"form":"c","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":9.539,"instructions":9930943,"cycles":22553554,"branch_misses":233414,"l1d_misses":1187573,"llc_misses":194217,"work":0} +{"round":1,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":8,"buckets":100001,"form":"c","repeats":21,"ms":9.554} +{"round":1,"form":"narrow_ahead","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":8.817,"instructions":21699678,"cycles":21004428,"branch_misses":199079,"l1d_misses":260581,"llc_misses":181738,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":9.733,"instructions":21699665,"cycles":23218621,"branch_misses":199749,"l1d_misses":261098,"llc_misses":228940,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":8.659,"instructions":21699677,"cycles":20732537,"branch_misses":198820,"l1d_misses":261142,"llc_misses":180357,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":8.581,"instructions":21699678,"cycles":20528115,"branch_misses":199833,"l1d_misses":261042,"llc_misses":182243,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":8.624,"instructions":21699665,"cycles":20600968,"branch_misses":198858,"l1d_misses":261003,"llc_misses":182276,"work":25997969} +{"round":1,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":8,"buckets":100001,"form":"narrow_ahead","repeats":21,"ms":8.659} +{"round":1,"form":"narrow","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":13.030,"instructions":18500082,"cycles":30950785,"branch_misses":202914,"l1d_misses":451526,"llc_misses":202269,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":12.863,"instructions":18500082,"cycles":30655768,"branch_misses":202792,"l1d_misses":451289,"llc_misses":208734,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":12.742,"instructions":18500082,"cycles":30374858,"branch_misses":203016,"l1d_misses":451339,"llc_misses":203187,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":13.044,"instructions":18500082,"cycles":31090887,"branch_misses":202424,"l1d_misses":450780,"llc_misses":214310,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":12.989,"instructions":18500082,"cycles":30974267,"branch_misses":201566,"l1d_misses":450965,"llc_misses":206665,"work":25997969} +{"round":1,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":8,"buckets":100001,"form":"narrow","repeats":21,"ms":12.989} +{"round":1,"form":"c_ahead","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":8.275,"instructions":11430806,"cycles":19794774,"branch_misses":230406,"l1d_misses":1004009,"llc_misses":208953,"work":0} +{"round":1,"form":"c_ahead","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":7.229,"instructions":11430802,"cycles":17279604,"branch_misses":229142,"l1d_misses":1004017,"llc_misses":163048,"work":0} +{"round":1,"form":"c_ahead","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":7.046,"instructions":11430805,"cycles":16841813,"branch_misses":229592,"l1d_misses":1003342,"llc_misses":161580,"work":0} +{"round":1,"form":"c_ahead","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":6.927,"instructions":11430806,"cycles":16571742,"branch_misses":229156,"l1d_misses":1004417,"llc_misses":159956,"work":0} +{"round":1,"form":"c_ahead","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":7.062,"instructions":11430802,"cycles":16893106,"branch_misses":229101,"l1d_misses":1003035,"llc_misses":162452,"work":0} +{"round":1,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":8,"buckets":100001,"form":"c_ahead","repeats":21,"ms":7.062} +{"round":1,"form":"packed","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":23.061,"instructions":29099302,"cycles":55201608,"branch_misses":197608,"l1d_misses":687725,"llc_misses":1305567,"work":25997969} +{"round":1,"form":"packed","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":23.290,"instructions":29099302,"cycles":55607437,"branch_misses":198034,"l1d_misses":689132,"llc_misses":1336320,"work":25997969} +{"round":1,"form":"packed","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":23.338,"instructions":29099302,"cycles":55872039,"branch_misses":197556,"l1d_misses":689395,"llc_misses":1332969,"work":25997969} +{"round":1,"form":"packed","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":23.121,"instructions":29099302,"cycles":55355022,"branch_misses":197373,"l1d_misses":688049,"llc_misses":1320484,"work":25997969} +{"round":1,"form":"packed","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":23.270,"instructions":29099302,"cycles":55705797,"branch_misses":197835,"l1d_misses":688876,"llc_misses":1335114,"work":25997969} +{"round":1,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":8,"buckets":100001,"form":"packed","repeats":21,"ms":23.270} +{"round":2,"form":"c","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":9.400,"instructions":9930943,"cycles":22506822,"branch_misses":233025,"l1d_misses":1188085,"llc_misses":195810,"work":0} +{"round":2,"form":"c","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":9.403,"instructions":9930943,"cycles":22528937,"branch_misses":233643,"l1d_misses":1187672,"llc_misses":194342,"work":0} +{"round":2,"form":"c","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":9.466,"instructions":9930943,"cycles":22661529,"branch_misses":232683,"l1d_misses":1187331,"llc_misses":196380,"work":0} +{"round":2,"form":"c","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":9.419,"instructions":9930943,"cycles":22559271,"branch_misses":232371,"l1d_misses":1188099,"llc_misses":197534,"work":0} +{"round":2,"form":"c","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":9.445,"instructions":9930943,"cycles":22602658,"branch_misses":232462,"l1d_misses":1187435,"llc_misses":197496,"work":0} +{"round":2,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":8,"buckets":100001,"form":"c","repeats":21,"ms":9.419} +{"round":2,"form":"narrow_ahead","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":8.377,"instructions":21699678,"cycles":20030629,"branch_misses":199233,"l1d_misses":260968,"llc_misses":212794,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":8.227,"instructions":21699665,"cycles":19695643,"branch_misses":198840,"l1d_misses":261373,"llc_misses":198694,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":8.256,"instructions":21699677,"cycles":19738860,"branch_misses":198911,"l1d_misses":261620,"llc_misses":215820,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":8.140,"instructions":21699678,"cycles":19478025,"branch_misses":199386,"l1d_misses":261655,"llc_misses":214376,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":8.415,"instructions":21699665,"cycles":20141577,"branch_misses":199145,"l1d_misses":261729,"llc_misses":193454,"work":25997969} +{"round":2,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":8,"buckets":100001,"form":"narrow_ahead","repeats":21,"ms":8.256} +{"round":2,"form":"narrow","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":12.727,"instructions":18500082,"cycles":30459303,"branch_misses":201994,"l1d_misses":449993,"llc_misses":198517,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":12.877,"instructions":18500082,"cycles":30821271,"branch_misses":202540,"l1d_misses":450914,"llc_misses":203192,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":12.835,"instructions":18500082,"cycles":30713044,"branch_misses":201373,"l1d_misses":451893,"llc_misses":211620,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":12.764,"instructions":18500082,"cycles":30566444,"branch_misses":202280,"l1d_misses":451611,"llc_misses":212361,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":12.709,"instructions":18500082,"cycles":30427138,"branch_misses":201013,"l1d_misses":450824,"llc_misses":196344,"work":25997969} +{"round":2,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":8,"buckets":100001,"form":"narrow","repeats":21,"ms":12.764} +{"round":2,"form":"c_ahead","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":7.068,"instructions":11430806,"cycles":16899365,"branch_misses":229151,"l1d_misses":1003197,"llc_misses":160489,"work":0} +{"round":2,"form":"c_ahead","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":7.076,"instructions":11430802,"cycles":16929953,"branch_misses":228509,"l1d_misses":1003466,"llc_misses":160852,"work":0} +{"round":2,"form":"c_ahead","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":7.096,"instructions":11430805,"cycles":16961974,"branch_misses":228595,"l1d_misses":1003014,"llc_misses":161011,"work":0} +{"round":2,"form":"c_ahead","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":7.015,"instructions":11430806,"cycles":16812937,"branch_misses":228759,"l1d_misses":1003284,"llc_misses":164448,"work":0} +{"round":2,"form":"c_ahead","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":7.072,"instructions":11430802,"cycles":16926924,"branch_misses":228107,"l1d_misses":1002726,"llc_misses":162025,"work":0} +{"round":2,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":8,"buckets":100001,"form":"c_ahead","repeats":21,"ms":7.072} +{"round":2,"form":"packed","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":22.935,"instructions":29099302,"cycles":54793228,"branch_misses":197473,"l1d_misses":688741,"llc_misses":1309254,"work":25997969} +{"round":2,"form":"packed","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":23.190,"instructions":29099302,"cycles":55462573,"branch_misses":197823,"l1d_misses":689011,"llc_misses":1310105,"work":25997969} +{"round":2,"form":"packed","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":23.117,"instructions":29099302,"cycles":55307475,"branch_misses":197318,"l1d_misses":689038,"llc_misses":1323771,"work":25997969} +{"round":2,"form":"packed","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":23.097,"instructions":29099302,"cycles":55243920,"branch_misses":197550,"l1d_misses":688837,"llc_misses":1328834,"work":25997969} +{"round":2,"form":"packed","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":23.070,"instructions":29099302,"cycles":55192732,"branch_misses":197511,"l1d_misses":689825,"llc_misses":1318476,"work":25997969} +{"round":2,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":8,"buckets":100001,"form":"packed","repeats":21,"ms":23.097} +{"round":3,"form":"c","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":9.561,"instructions":9930943,"cycles":22869778,"branch_misses":232056,"l1d_misses":1187795,"llc_misses":201837,"work":0} +{"round":3,"form":"c","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":9.399,"instructions":9930943,"cycles":22515873,"branch_misses":233065,"l1d_misses":1187347,"llc_misses":193257,"work":0} +{"round":3,"form":"c","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":9.478,"instructions":9930943,"cycles":22685088,"branch_misses":233836,"l1d_misses":1187285,"llc_misses":196028,"work":0} +{"round":3,"form":"c","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":10.649,"instructions":9930943,"cycles":25453339,"branch_misses":232241,"l1d_misses":1187986,"llc_misses":225063,"work":0} +{"round":3,"form":"c","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":10.434,"instructions":9930943,"cycles":24926258,"branch_misses":235525,"l1d_misses":1187296,"llc_misses":219938,"work":0} +{"round":3,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":8,"buckets":100001,"form":"c","repeats":21,"ms":9.561} +{"round":3,"form":"narrow_ahead","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":8.704,"instructions":21699678,"cycles":20826385,"branch_misses":199729,"l1d_misses":260554,"llc_misses":175494,"work":25997969} +{"round":3,"form":"narrow_ahead","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":8.587,"instructions":21699665,"cycles":20528294,"branch_misses":199793,"l1d_misses":260696,"llc_misses":166850,"work":25997969} +{"round":3,"form":"narrow_ahead","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":8.513,"instructions":21699677,"cycles":20343356,"branch_misses":199186,"l1d_misses":260809,"llc_misses":174411,"work":25997969} +{"round":3,"form":"narrow_ahead","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":8.489,"instructions":21699678,"cycles":20177155,"branch_misses":199960,"l1d_misses":261075,"llc_misses":171650,"work":25997969} +{"round":3,"form":"narrow_ahead","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":8.709,"instructions":21699665,"cycles":20834469,"branch_misses":199518,"l1d_misses":261196,"llc_misses":178564,"work":25997969} +{"round":3,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":8,"buckets":100001,"form":"narrow_ahead","repeats":21,"ms":8.587} +{"round":3,"form":"narrow","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":12.884,"instructions":18500082,"cycles":30836152,"branch_misses":202254,"l1d_misses":450594,"llc_misses":202869,"work":25997969} +{"round":3,"form":"narrow","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":12.682,"instructions":18500082,"cycles":30361751,"branch_misses":202749,"l1d_misses":450622,"llc_misses":195885,"work":25997969} +{"round":3,"form":"narrow","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":12.634,"instructions":18500082,"cycles":30238142,"branch_misses":202097,"l1d_misses":451561,"llc_misses":205780,"work":25997969} +{"round":3,"form":"narrow","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":12.818,"instructions":18500082,"cycles":30671583,"branch_misses":203287,"l1d_misses":450962,"llc_misses":215803,"work":25997969} +{"round":3,"form":"narrow","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":13.016,"instructions":18500082,"cycles":31146316,"branch_misses":202002,"l1d_misses":451624,"llc_misses":203457,"work":25997969} +{"round":3,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":8,"buckets":100001,"form":"narrow","repeats":21,"ms":12.818} +{"round":3,"form":"c_ahead","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":7.084,"instructions":11430806,"cycles":16863699,"branch_misses":229370,"l1d_misses":1003166,"llc_misses":157948,"work":0} +{"round":3,"form":"c_ahead","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":7.130,"instructions":11430802,"cycles":17055170,"branch_misses":229565,"l1d_misses":1003293,"llc_misses":160637,"work":0} +{"round":3,"form":"c_ahead","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":7.164,"instructions":11430805,"cycles":17142965,"branch_misses":229413,"l1d_misses":1002475,"llc_misses":160694,"work":0} +{"round":3,"form":"c_ahead","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":7.212,"instructions":11430806,"cycles":17243238,"branch_misses":229890,"l1d_misses":1003238,"llc_misses":168980,"work":0} +{"round":3,"form":"c_ahead","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":7.112,"instructions":11430802,"cycles":17031109,"branch_misses":231057,"l1d_misses":1002241,"llc_misses":164152,"work":0} +{"round":3,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":8,"buckets":100001,"form":"c_ahead","repeats":21,"ms":7.130} +{"round":3,"form":"packed","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":23.279,"instructions":29099302,"cycles":55675615,"branch_misses":197454,"l1d_misses":687723,"llc_misses":1307193,"work":25997969} +{"round":3,"form":"packed","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":24.655,"instructions":29099302,"cycles":58989250,"branch_misses":197757,"l1d_misses":687057,"llc_misses":1387216,"work":25997969} +{"round":3,"form":"packed","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":23.294,"instructions":29099302,"cycles":55749704,"branch_misses":197878,"l1d_misses":688298,"llc_misses":1334566,"work":25997969} +{"round":3,"form":"packed","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":23.201,"instructions":29099302,"cycles":55325156,"branch_misses":197703,"l1d_misses":687560,"llc_misses":1312181,"work":25997969} +{"round":3,"form":"packed","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":23.398,"instructions":29099302,"cycles":55967221,"branch_misses":197362,"l1d_misses":687740,"llc_misses":1319728,"work":25997969} +{"round":3,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":8,"buckets":100001,"form":"packed","repeats":21,"ms":23.294} diff --git a/research/experiments/038-past-c/2026-10-05-bfsfloor-widths.jsonl b/research/experiments/038-past-c/2026-10-05-bfsfloor-widths.jsonl new file mode 100644 index 0000000..4c9ecfd --- /dev/null +++ b/research/experiments/038-past-c/2026-10-05-bfsfloor-widths.jsonl @@ -0,0 +1,72 @@ +{"round":1,"form":"narrow_ahead","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":9.141,"instructions":21699673,"cycles":21889648,"branch_misses":199181,"l1d_misses":267372,"llc_misses":220196,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":8.989,"instructions":21699660,"cycles":21493767,"branch_misses":199654,"l1d_misses":267544,"llc_misses":206546,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":8.942,"instructions":21699672,"cycles":21405109,"branch_misses":199483,"l1d_misses":267225,"llc_misses":210997,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":8.987,"instructions":21699673,"cycles":21494691,"branch_misses":199897,"l1d_misses":267729,"llc_misses":201553,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":9.048,"instructions":21699660,"cycles":21634990,"branch_misses":199697,"l1d_misses":267686,"llc_misses":204230,"work":25997969} +{"round":1,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":4,"buckets":200000,"form":"narrow_ahead","repeats":21,"ms":8.989} +{"round":1,"form":"narrow","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":14.217,"instructions":18500077,"cycles":33909488,"branch_misses":202087,"l1d_misses":459539,"llc_misses":237253,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":14.694,"instructions":18500077,"cycles":35052529,"branch_misses":201690,"l1d_misses":459959,"llc_misses":276103,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":14.480,"instructions":18500077,"cycles":34485148,"branch_misses":201833,"l1d_misses":460120,"llc_misses":245464,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":14.107,"instructions":18500077,"cycles":33771102,"branch_misses":202409,"l1d_misses":459509,"llc_misses":250968,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":14.391,"instructions":18500077,"cycles":34293784,"branch_misses":201157,"l1d_misses":458888,"llc_misses":240061,"work":25997969} +{"round":1,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":4,"buckets":200000,"form":"narrow","repeats":21,"ms":14.391} +{"round":1,"form":"narrow_ahead","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":22.682,"instructions":29200858,"cycles":54256857,"branch_misses":353441,"l1d_misses":603484,"llc_misses":990428,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":22.681,"instructions":29200845,"cycles":54278547,"branch_misses":355841,"l1d_misses":603398,"llc_misses":976943,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":22.463,"instructions":29200857,"cycles":53613082,"branch_misses":354707,"l1d_misses":603279,"llc_misses":944855,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":22.693,"instructions":29200858,"cycles":53903702,"branch_misses":354467,"l1d_misses":604035,"llc_misses":973959,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":22.518,"instructions":29200845,"cycles":53796436,"branch_misses":354967,"l1d_misses":603733,"llc_misses":964239,"work":25997969} +{"round":1,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":16,"buckets":50001,"form":"narrow_ahead","repeats":21,"ms":22.681} +{"round":1,"form":"narrow","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":24.475,"instructions":26051261,"cycles":58191307,"branch_misses":352289,"l1d_misses":770035,"llc_misses":1369292,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":24.432,"instructions":26051261,"cycles":58186826,"branch_misses":353073,"l1d_misses":770364,"llc_misses":1377296,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":24.378,"instructions":26051261,"cycles":58052564,"branch_misses":352589,"l1d_misses":769361,"llc_misses":1367396,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":24.410,"instructions":26051261,"cycles":58172465,"branch_misses":352699,"l1d_misses":770080,"llc_misses":1383195,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":24.468,"instructions":26051270,"cycles":58150327,"branch_misses":352355,"l1d_misses":769709,"llc_misses":1370533,"work":25997969} +{"round":1,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":16,"buckets":50001,"form":"narrow","repeats":21,"ms":24.432} +{"round":1,"form":"narrow_ahead","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":28.514,"instructions":43451487,"cycles":68021901,"branch_misses":421289,"l1d_misses":738205,"llc_misses":1611386,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":28.483,"instructions":43451474,"cycles":68012352,"branch_misses":422013,"l1d_misses":738087,"llc_misses":1618587,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":28.439,"instructions":43451486,"cycles":68048135,"branch_misses":421647,"l1d_misses":738115,"llc_misses":1612382,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":28.525,"instructions":43451487,"cycles":68186305,"branch_misses":421708,"l1d_misses":738091,"llc_misses":1626742,"work":25997969} +{"round":1,"form":"narrow_ahead","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":28.527,"instructions":43451474,"cycles":68245199,"branch_misses":420687,"l1d_misses":737900,"llc_misses":1639154,"work":25997969} +{"round":1,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":32,"buckets":25001,"form":"narrow_ahead","repeats":21,"ms":28.514} +{"round":1,"form":"narrow","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":29.204,"instructions":40326890,"cycles":69848162,"branch_misses":417157,"l1d_misses":855417,"llc_misses":1641359,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":29.117,"instructions":40326890,"cycles":69599234,"branch_misses":417124,"l1d_misses":855262,"llc_misses":1641321,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":29.200,"instructions":40326890,"cycles":69839219,"branch_misses":416421,"l1d_misses":854422,"llc_misses":1636540,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":29.223,"instructions":40326890,"cycles":69809540,"branch_misses":417208,"l1d_misses":855215,"llc_misses":1644333,"work":25997969} +{"round":1,"form":"narrow","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":29.220,"instructions":40326890,"cycles":69916157,"branch_misses":416893,"l1d_misses":855647,"llc_misses":1637894,"work":25997969} +{"round":1,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":32,"buckets":25001,"form":"narrow","repeats":21,"ms":29.204} +{"round":2,"form":"narrow_ahead","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":9.098,"instructions":21699673,"cycles":21501837,"branch_misses":199083,"l1d_misses":268164,"llc_misses":205057,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":9.257,"instructions":21699660,"cycles":22120034,"branch_misses":199754,"l1d_misses":267603,"llc_misses":210308,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":8.939,"instructions":21699672,"cycles":21365285,"branch_misses":199381,"l1d_misses":268043,"llc_misses":206258,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":9.117,"instructions":21699673,"cycles":21512945,"branch_misses":199911,"l1d_misses":267651,"llc_misses":200324,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":9.035,"instructions":21699660,"cycles":21502008,"branch_misses":199438,"l1d_misses":268038,"llc_misses":201463,"work":25997969} +{"round":2,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":4,"buckets":200000,"form":"narrow_ahead","repeats":21,"ms":9.098} +{"round":2,"form":"narrow","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":14.304,"instructions":18500077,"cycles":34222206,"branch_misses":201504,"l1d_misses":459182,"llc_misses":238512,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":14.569,"instructions":18500077,"cycles":34847617,"branch_misses":202727,"l1d_misses":459735,"llc_misses":251855,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":14.279,"instructions":18500077,"cycles":34190176,"branch_misses":202471,"l1d_misses":459866,"llc_misses":243387,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":14.387,"instructions":18500077,"cycles":34427255,"branch_misses":201743,"l1d_misses":459728,"llc_misses":248537,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":14.350,"instructions":18500077,"cycles":34340800,"branch_misses":201236,"l1d_misses":459056,"llc_misses":240549,"work":25997969} +{"round":2,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":4,"buckets":200000,"form":"narrow","repeats":21,"ms":14.350} +{"round":2,"form":"narrow_ahead","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":22.226,"instructions":29200858,"cycles":53186143,"branch_misses":353023,"l1d_misses":603444,"llc_misses":960547,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":22.397,"instructions":29200845,"cycles":53517742,"branch_misses":354791,"l1d_misses":604220,"llc_misses":965447,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":22.299,"instructions":29200857,"cycles":53369938,"branch_misses":354043,"l1d_misses":602959,"llc_misses":945884,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":22.300,"instructions":29200858,"cycles":53399189,"branch_misses":355720,"l1d_misses":602978,"llc_misses":946992,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":22.262,"instructions":29200845,"cycles":53183522,"branch_misses":353366,"l1d_misses":603661,"llc_misses":951593,"work":25997969} +{"round":2,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":16,"buckets":50001,"form":"narrow_ahead","repeats":21,"ms":22.299} +{"round":2,"form":"narrow","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":24.029,"instructions":26051261,"cycles":57535579,"branch_misses":351591,"l1d_misses":769557,"llc_misses":1367134,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":24.056,"instructions":26051261,"cycles":57563063,"branch_misses":352716,"l1d_misses":770798,"llc_misses":1372321,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":24.191,"instructions":26051261,"cycles":57830356,"branch_misses":352389,"l1d_misses":770219,"llc_misses":1380059,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":24.088,"instructions":26051261,"cycles":57588541,"branch_misses":352538,"l1d_misses":769364,"llc_misses":1366742,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":24.114,"instructions":26051261,"cycles":57742013,"branch_misses":353706,"l1d_misses":770238,"llc_misses":1374648,"work":25997969} +{"round":2,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":16,"buckets":50001,"form":"narrow","repeats":21,"ms":24.088} +{"round":2,"form":"narrow_ahead","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":28.492,"instructions":43451487,"cycles":68182052,"branch_misses":421258,"l1d_misses":738346,"llc_misses":1619135,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":28.397,"instructions":43451474,"cycles":67945428,"branch_misses":421760,"l1d_misses":738141,"llc_misses":1605562,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":28.474,"instructions":43451486,"cycles":68126834,"branch_misses":420689,"l1d_misses":738043,"llc_misses":1615468,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":28.518,"instructions":43451487,"cycles":68224496,"branch_misses":421860,"l1d_misses":738253,"llc_misses":1620473,"work":25997969} +{"round":2,"form":"narrow_ahead","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":28.485,"instructions":43451474,"cycles":68139426,"branch_misses":421137,"l1d_misses":738001,"llc_misses":1618049,"work":25997969} +{"round":2,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":32,"buckets":25001,"form":"narrow_ahead","repeats":21,"ms":28.485} +{"round":2,"form":"narrow","alone":true,"from":7767,"to":34553,"hops":5,"reached":99998,"ms":29.317,"instructions":40326890,"cycles":69762016,"branch_misses":418898,"l1d_misses":854959,"llc_misses":1660842,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":18342,"to":39241,"hops":6,"reached":99998,"ms":29.242,"instructions":40326890,"cycles":69886668,"branch_misses":418494,"l1d_misses":854763,"llc_misses":1671153,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":73728,"to":40868,"hops":6,"reached":99998,"ms":29.266,"instructions":40326890,"cycles":69403555,"branch_misses":417917,"l1d_misses":854101,"llc_misses":1635658,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":75932,"to":66396,"hops":6,"reached":99998,"ms":29.173,"instructions":40326890,"cycles":69719398,"branch_misses":418633,"l1d_misses":854243,"llc_misses":1659562,"work":25997969} +{"round":2,"form":"narrow","alone":true,"from":9981,"to":23853,"hops":5,"reached":99998,"ms":29.196,"instructions":40326890,"cycles":69850365,"branch_misses":418142,"l1d_misses":854961,"llc_misses":1652789,"work":25997969} +{"round":2,"nodes":100000,"edges":999937,"far":16,"near":8,"per_bucket":32,"buckets":25001,"form":"narrow","repeats":21,"ms":29.242} diff --git a/research/experiments/038-past-c/2026-10-05-roundtrip.jsonl b/research/experiments/038-past-c/2026-10-05-roundtrip.jsonl new file mode 100644 index 0000000..7175ed7 --- /dev/null +++ b/research/experiments/038-past-c/2026-10-05-roundtrip.jsonl @@ -0,0 +1,3 @@ +{"write_us": 151.2, "read_us": 80.1} +{"write_us": 150.7, "read_us": 80.1} +{"write_us": 151.0, "read_us": 80.0} diff --git a/research/experiments/038-past-c/bfsfloor.c b/research/experiments/038-past-c/bfsfloor.c index a6258a8..a74fa82 100644 --- a/research/experiments/038-past-c/bfsfloor.c +++ b/research/experiments/038-past-c/bfsfloor.c @@ -21,9 +21,13 @@ * narrow_ahead narrow, read ahead as ahead * c_ahead bfs.c read ahead as ahead (context: what C would gain) * - * bfsfloor NODES EDGES SEARCHES [FAR NEAR]: a JSON line per search and form - * (the forms in turns; the answers must agree), with this thread's counters - * (user space), then the medians. */ + * bfsfloor NODES EDGES SEARCHES [FAR NEAR [PER_BUCKET [FORM REPEATS]]]: a + * JSON line per search and form (the forms in turns; the answers must + * agree), with this thread's counters (user space), then the medians. With + * FORM, that form alone, each search REPEATS times and its median, as bfs.c + * measures (the tables stay warm). PER_BUCKET: about how many items a bucket + * (8; the width is then 2^20 keys, a node's: other widths make a slice's + * bounds fall inside buckets). */ #define _GNU_SOURCE #include <math.h> #include <stdbool.h> @@ -255,10 +259,13 @@ static Answer search_c_ahead(uint32_t s, uint32_t t) { } int main(int argc, char **argv) { - if (argc < 4) { fputs("bfsfloor NODES EDGES SEARCHES [FAR NEAR]\n", stderr); return 2; } + if (argc < 4) { fputs("bfsfloor NODES EDGES SEARCHES [FAR NEAR [PER_BUCKET [FORM REPEATS]]]\n", stderr); return 2; } n = (uint32_t)atol(argv[1]); size_t want = (size_t)atol(argv[2]), searches = (size_t)atol(argv[3]); far_ = argc > 4 ? atoi(argv[4]) : 16, near_ = argc > 5 ? atoi(argv[5]) : 8; + size_t per_bucket = argc > 6 ? (size_t)atol(argv[6]) : 8; + const char *only = argc > 7 ? argv[7] : NULL; + size_t repeats = argc > 8 ? (size_t)atol(argv[8]) : 21; /* bfs-run's graph: from and to uniform, no loops, each pair once, sorted */ uint64_t *keys = malloc(want * sizeof(*keys)); size_t count = 0; @@ -278,7 +285,7 @@ int main(int argc, char **argv) { for (size_t k = 0; k < m; ++k) edges.key[k] = (double)keys[k], edges.to[k] = (double)(keys[k] & 0xFFFFF); double span = edges.key[m - 1] - edges.key[0]; int exponent; - frexp(span / (double)(m / 8 + 1), &exponent); + frexp(span / (double)(m / per_bucket + 1), &exponent); edges.scale = ldexp(1.0, -exponent); edges.low = floor(edges.key[0] * edges.scale) / edges.scale; edges.buckets = (size_t)floor((edges.key[m - 1] - edges.low) * edges.scale) + 2; @@ -302,6 +309,40 @@ int main(int argc, char **argv) { const char *names[] = {"c", "c_bits", "packed", "ahead", "narrow", "narrow_ahead", "c_ahead"}; Answer (*forms[])(uint32_t, uint32_t) = {search_c, search_c_bits, packed_plain, packed_ahead, narrow_plain, narrow_ahead, search_c_ahead}; + if (only) { /* one form, each search repeated: the median run's line */ + int f = 0; + while (f < FORMS && strcmp(names[f], only)) ++f; + if (f == FORMS) { fprintf(stderr, "no form %s\n", only); return 2; } + double *each = malloc(searches * sizeof(double)); + typedef struct { double ms; uint64_t c[COUNTERS]; Answer got; } Run; + Run *runs = malloc(repeats * sizeof(*runs)); + for (size_t r = 0; r < searches; ++r) { + uint32_t s = (uint32_t)(next() % n), t = (uint32_t)(next() % n); + for (size_t k = 0; k < repeats; ++k) { + uint64_t c0[COUNTERS], c1[COUNTERS]; + counters_read(c0); + double a = now(); + runs[k].got = forms[f](s, t); + runs[k].ms = now() - a; + counters_read(c1); + for (int i = 0; i < COUNTERS; ++i) runs[k].c[i] = c1[i] - c0[i]; + } + for (size_t i = 1; i < repeats; ++i) /* by time, few: insertion */ + for (size_t j = i; j > 0 && runs[j].ms < runs[j - 1].ms; --j) { Run x = runs[j]; runs[j] = runs[j - 1]; runs[j - 1] = x; } + Run *mid = &runs[repeats / 2]; + each[r] = mid->ms; + printf("{\"form\":\"%s\",\"alone\":true,\"from\":%u,\"to\":%u,\"hops\":%d,\"reached\":%u,\"ms\":%.3f," + "\"instructions\":%llu,\"cycles\":%llu,\"branch_misses\":%llu,\"l1d_misses\":%llu,\"llc_misses\":%llu," + "\"work\":%llu}\n", names[f], s, t, mid->got.hops, mid->got.reached, mid->ms, (unsigned long long)mid->c[0], + (unsigned long long)mid->c[1], (unsigned long long)mid->c[2], (unsigned long long)mid->c[3], + (unsigned long long)mid->c[4], (unsigned long long)mid->got.work); + } + qsort(each, searches, sizeof(double), by_num); + printf("{\"nodes\":%u,\"edges\":%u,\"far\":%d,\"near\":%d,\"per_bucket\":%zu,\"buckets\":%zu,\"form\":\"%s\"," + "\"repeats\":%zu,\"ms\":%.3f}\n", n, m, far_, near_, per_bucket, edges.buckets, names[f], repeats, + each[searches / 2]); + return 0; + } double *took[FORMS]; for (int f = 0; f < FORMS; ++f) took[f] = malloc(searches * sizeof(double)); for (size_t r = 0; r < searches; ++r) { @@ -324,7 +365,8 @@ int main(int argc, char **argv) { (unsigned long long)got.work); } } - printf("{\"nodes\":%u,\"edges\":%u,\"far\":%d,\"near\":%d", n, m, far_, near_); + printf("{\"nodes\":%u,\"edges\":%u,\"far\":%d,\"near\":%d,\"per_bucket\":%zu,\"buckets\":%zu", n, m, far_, near_, + per_bucket, edges.buckets); for (int f = 0; f < FORMS; ++f) { qsort(took[f], searches, sizeof(double), by_num); printf(",\"%s_ms\":%.3f", names[f], took[f][searches / 2]); diff --git a/research/experiments/038-past-c/roundtrip.py b/research/experiments/038-past-c/roundtrip.py new file mode 100644 index 0000000..53bc251 --- /dev/null +++ b/research/experiments/038-past-c/roundtrip.py @@ -0,0 +1,39 @@ +#!/usr/bin/env python3 +"""What HTTP adds to an event (docs/design/022): pure-serve (store in RAM, +cores 0-2) with a module, a write that does almost nothing (POST +/inputs/size of 033's graph.aup) and a read (GET /views/far), each 2,000 +times from one connection; the medians in microseconds. + +roundtrip.py PURE_SERVE MODULE (run the client apart: taskset -c 3)""" +import http.client +import json +import statistics +import subprocess +import sys +import tempfile +import time + +serve, module = sys.argv[1], sys.argv[2] +with tempfile.TemporaryDirectory() as work: + host = subprocess.Popen(['taskset', '-c', '0-2', serve, '--module', module, '--store', work + '/store', '--port', '0'], + stdout=subprocess.PIPE, stderr=subprocess.PIPE) + port = json.loads(host.stdout.readline())['port'] + connection = http.client.HTTPConnection('127.0.0.1', port, timeout=60) + + def request(method, path): + connection.request(method, path, b'', {'Content-Length': '0'}) + answer = connection.getresponse() + answer.read() + assert answer.status == 200, (path, answer.status) + + out = {} + for name, (method, path) in {'write_us': ('POST', '/inputs/size?nodes=100000'), 'read_us': ('GET', '/views/far')}.items(): + took = [] + for _ in range(2000): + began = time.perf_counter() + request(method, path) + took.append((time.perf_counter() - began) * 1e6) + out[name] = round(statistics.median(took), 1) + host.terminate() + host.communicate(timeout=30) + print(json.dumps(out)) diff --git a/research/experiments/038-past-c/runs.sh b/research/experiments/038-past-c/runs.sh index 3da6196..05d301e 100644 --- a/research/experiments/038-past-c/runs.sh +++ b/research/experiments/038-past-c/runs.sh @@ -13,6 +13,12 @@ # without (PURE_JIT=0), in turns # runs.sh bfs NAME 033's bfs.py on that build (100,000 nodes, # 1,000,000 edges, 5 searches, 3 rounds) +# runs.sh floor bfsfloor's forms in turns (9 searches) +# runs.sh alone bfsfloor's forms each alone, warm (5 +# searches of 21 runs, 3 rounds) +# runs.sh widths narrow and narrow_ahead alone with buckets +# of 4, 16 and 32 items (2 rounds) +# runs.sh roundtrip roundtrip.py on after (3 times) set -e here=research/experiments/038-past-c builds=$HOME/.cache/pure-038 @@ -70,6 +76,30 @@ bfs) until awk '{ exit !($1 < 1.5) }' /proc/loadavg; do sleep 10; done python3 research/guard.py --most 2048 -- python3 research/experiments/033-computing/bfs.py "$builds/$2/pure-serve" \ ../aup/build/aup 100000 1000000 5 3 > "$here/$day-bfs-$2.jsonl" ;; -*) echo "runs.sh build NAME COMMIT | core FIRST LAST | pairs FIRST LAST | jit FIRST LAST | counts | bfs NAME" >&2 +floor|alone|widths) + cc -O2 -std=gnu17 -o "$builds/bfsfloor" $here/bfsfloor.c -lm + floor() { python3 research/guard.py --most 1024 -- "$builds/bfsfloor" 100000 1000000 "$@"; } + case "$1" in + floor) floor 9 16 8 > "$here/$day-bfsfloor.jsonl" ;; + alone) + for round in 1 2 3; do + for form in c narrow_ahead narrow c_ahead packed; do + floor 5 16 8 8 $form 21 | sed "s/^{/{\"round\":$round,/" >> "$here/$day-bfsfloor-alone.jsonl" + done + done ;; + widths) + for round in 1 2; do + for per in 4 16 32; do + for form in narrow_ahead narrow; do + floor 5 16 8 $per $form 21 | sed "s/^{/{\"round\":$round,/" >> "$here/$day-bfsfloor-widths.jsonl" + done + done + done ;; + esac ;; +roundtrip) + for i in 1 2 3; do + taskset -c 3 python3 $here/roundtrip.py "$builds/after/pure-serve" "$builds/graph.pmod" >> "$here/$day-roundtrip.jsonl" + done ;; +*) echo "runs.sh build NAME COMMIT | core FIRST LAST | pairs FIRST LAST | jit FIRST LAST | counts | bfs NAME | floor | alone | widths | roundtrip" >&2 exit 2 ;; esac |