From 4a7e780278df740e5e37c3307fe687405df72448 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 19 Oct 2026 08:05:53 +0100 Subject: 140: LIST_VALUE's copy reviewed before building (measured by spec: UAX #14 about 10% of its time, JSON tree 6%, HTTP 2%, inflate 0.06%, the rest none; the cost a tree built item by item, 64 ns an item and 250 ns a copy): lend and detach (CoW) noted as the decision point (a branch on every event list's change for 10/6/2/0/0/0), a compile-time move ruled out (it changes LIST_VALUE's contract), the arrays copied whole built (UAX #14 -6.8%, its share to about 3%); 041's five works within 0.03% (b49, b50), the bank's queries within 0.3% (s49, s50), noise between builds larger --- docs/research/140-spec-suite.md | 63 ++++++++++++++++++++++ .../040-against-c/2026-10-19-counts.jsonl | 4 ++ .../041-batches/2026-10-19-counts.jsonl | 20 +++++++ .../044-specs/2026-10-19-list-value.jsonl | 8 +++ 4 files changed, 95 insertions(+) create mode 100644 research/experiments/040-against-c/2026-10-19-counts.jsonl create mode 100644 research/experiments/044-specs/2026-10-19-list-value.jsonl diff --git a/docs/research/140-spec-suite.md b/docs/research/140-spec-suite.md index 9cbe5c2..da1f562 100644 --- a/docs/research/140-spec-suite.md +++ b/docs/research/140-spec-suite.md @@ -959,6 +959,69 @@ min과 max가 남는다. Flexbox의 어려운 반은 크기가 아래에서 위 - aup에 두는 것: 축을 필드 번호로 고르기(배치의 마찰 3), `number`나 `send` 같은 이름. 이름은 타입과 말의 자리를 지키려고 그대로 둔다. - 원본: `2026-10-19-frictions.jsonl`(검사, 전과 뒤의 명령과 시간, 줄). aup의 설계 002 "140의 마찰을 걷어 냄". +## LIST_VALUE의 복사를 다시 봄 (2026-10-19) + +리스트 값(let의 리스트를 fn에 넘기거나 레코드에 담기)은 항목을 복사한다. 여러 명세에서 그 값이 보였다. 새 명령 없이 줄일 수 있는지 +설계부터 보고, 실익이 분명한 것만 만들었다. + +**잰 것.** 계측한 빌드(연구용, 커밋하지 않음)로 명세마다 LIST_VALUE의 시간 몫을 쟀다(시계의 값은 대략 뺐다). + +| 명세 | 한 번 돌 때의 LIST_VALUE | 원본의 꼴 | 시간 몫 | +|---|---|---|---| +| UAX #14 | 168,048번(줄마다 9번, 평균 3.3항목) | FLAT 배열 | 약 10% | +| JSON 트리 | 4,001번 | 트리(리스트를 담은 레코드) | 약 6% | +| HTTP/1.1 | 596번 | 트리(바이트를 담은 레코드) | 약 2% | +| inflate | 9번 | FLAT 배열 | 0.06% | +| DNS, JSON 검사기, 상자 배치 | 0 | — | 0 | + +- **원인.** `nest()`가 원본의 꼴과 상관없이 새 리스트를 트리로, 항목을 하나씩 넣어 지었다. 항목당 약 64 ns였고, 한 번에 약 250 ns의 + 고정 비용(새 리스트의 할당과 초기화)이 더 들었다. 수 8바이트를 베끼는 값이 아니라 트리에 넣는 값이다. + +**검토한 셋.** +1. **빌려주고 뗀다(CoW).** 리스트 값이 원본의 리스트를 그대로 가리키고, 원본이 바뀌기 전에 떼어 낸다. 복사가 없어질 수 있는 유일한 + 길이다. 다만 비용이 넓다. + - 실행기에서 이벤트 리스트를 바꾸는 모든 자리에 갈래가 하나씩 는다. LIST_APPEND는 어디서나 뜨겁다. + - `drop_nested`가 누구의 리스트를 놓을지 가려야 한다. + - `nested.shared`를 세서, APPEND_IN이 빌린 값을 통해 let의 리스트에 쓰지 않게 해야 한다. + - 블록 안의 let 리스트가 반복마다 도는 비우기 고리가 떼어 내기를 부른다. + - 그 값으로 얻는 것은 10%, 6%, 2%, 0, 0, 0이다. 지금은 만들지 않고 결정점으로 남긴다. +2. **컴파일 때 옮긴다.** aup가 let 리스트의 마지막 쓰임을 알아 LIST_VALUE를 "옮기기"로 낸다. LIST_VALUE의 뜻(명령의 계약)을 바꾸므로 + 이번의 규칙(새 명령도 계약의 변경도 없이) 밖이다. 적어만 둔다. +3. **배열을 통째로 복사한다(만들었다).** 원본이 FLAT 배열이고 키가 없고 칸이 수, bool, i64뿐이면, 열마다 memcpy로 새 리스트를 + 짓는다(`pure_list_copied`). 내부 표현일 뿐이라 명령도 모듈의 꼴도 검증기도 그대로다. 리스트 값을 쓰지 않는 일에는 닿지 않는다. + +**결과.** + +| 복사 하나 | 전 | 뒤 | +|---|---|---| +| 3항목 | 540 ns | 320 ns | +| 60항목 | 3,926 ns | 324 ns | +| 600항목 | 38,268 ns | 985 ns | + +(계측한 빌드의 값이다. 시계 값으로 한 번에 100–150 ns가 더 들어 있다.) + +| 명세 | 코드 포인트·바이트당 ns 전 → 뒤 | 명령 | +|---|---|---| +| UAX #14 | 6,917 → 6,445(**−6.8%**) | 같다(1,774.3) | +| JSON 트리 | 606.0 → 607.4 | 같다 | +| HTTP/1.1 | 270.6 → 270.5 | 같다 | +| inflate | 895.0 → 895.2 | 같다 | + +- UAX #14의 LIST_VALUE 몫은 약 10%에서 약 3%로 줄었다. 남은 것은 한 번의 고정 비용(할당)이다. +- JSON 트리와 HTTP는 그대로다. 원본이 트리이고(레코드에 리스트나 바이트가 들었다), 리스트를 담은 레코드는 칸마다 공유 수를 센다. +- **남은 결정점.** 셋이 있다. 모두 지금은 만들지 않는다(얻는 것이 3% 이하, 6% 이하). + - 리스트 값의 리스트를 사건마다 새로 할당하지 않고 다시 쓰기(UAX #14의 남은 약 3%). + - 트리의 잎을 통째로 복사하기(JSON 트리, HTTP). + - 빌려주고 떼기. +- **검사.** `test-module`의 `copied_lists`가 무작위 리스트(좁고 넓은 수, bool, i64)를 복제해 하나씩 넣은 것과 같은지 보고, 복제본과 + 원본을 따로 바꿔 서로 닿지 않는지 본다. 트리, 키, 텍스트는 그렇게 복사하지 않는다. ASan에서도 지난다. aup의 `make check`(리스트 + 값, 블록 안의 리스트, 저장되는 중첩)와 Pure의 `make check`가 지난다. +- **다른 일에 닿지 않는다.** 041의 다섯 일(b49 대 b50, 3라운드의 사용자 모드 명령)은 묶음과 라운드 두 길 모두 ±0.03% 안이다. + 가장 큰 것이 묶음의 knapsack +0.023%다. 은행 질의(s49 대 s50, 025의 count.py, 둘씩 번갈아)는 모두 0.3% 안이다(in_credit + +0.26%, per_branch +0.15%). 같은 빌드끼리의 흔들림(per_branch 0.47%)보다 작다. 리스트 값을 쓰지 않는 일이므로 바뀌지 않는 것이 + 맞다. +- 원본: `2026-10-19-list-value.jsonl`, 041의 `2026-10-19-counts.jsonl`(b49, b50), 040의 `2026-10-19-counts.jsonl`. + ## 착수 기준 (다음 일) - **바꿀 결정.** 계산의 핵을 설계한다(027). 위 표의 여덟 후보 가운데 무엇을 어떤 모양으로 받을지 정한다. diff --git a/research/experiments/040-against-c/2026-10-19-counts.jsonl b/research/experiments/040-against-c/2026-10-19-counts.jsonl new file mode 100644 index 0000000..659baa7 --- /dev/null +++ b/research/experiments/040-against-c/2026-10-19-counts.jsonl @@ -0,0 +1,4 @@ +{"serve": "pure-serve", "per_branch": {"instructions": 27019462, "cycles": 12164303}, "in_credit": {"instructions": 3545634, "cycles": 1607652}, "large": {"instructions": 1410326, "cycles": 594546}, "ranks": {"instructions": 24533365, "cycles": 14922645}, "none": {"instructions": 617346, "cycles": 189029}, "field": {"instructions": 8887355, "cycles": 3098576}, "found": {"instructions": 14037788, "cycles": 10311844}} +{"serve": "pure-serve", "per_branch": {"instructions": 26879511, "cycles": 12039119}, "in_credit": {"instructions": 3514348, "cycles": 1560109}, "large": {"instructions": 1410334, "cycles": 610860}, "ranks": {"instructions": 24456349, "cycles": 14897979}, "none": {"instructions": 617346, "cycles": 196117}, "field": {"instructions": 8887355, "cycles": 3172331}, "found": {"instructions": 14039644, "cycles": 10406373}} +{"serve": "pure-serve", "per_branch": {"instructions": 26892569, "cycles": 12080612}, "in_credit": {"instructions": 3516951, "cycles": 1597121}, "large": {"instructions": 1410200, "cycles": 597235}, "ranks": {"instructions": 24460737, "cycles": 15160955}, "none": {"instructions": 617348, "cycles": 287537}, "field": {"instructions": 8887357, "cycles": 3491839}, "found": {"instructions": 14039278, "cycles": 13686055}} +{"serve": "pure-serve", "per_branch": {"instructions": 27114295, "cycles": 12138057}, "in_credit": {"instructions": 3566857, "cycles": 1635326}, "large": {"instructions": 1410230, "cycles": 587500}, "ranks": {"instructions": 24585094, "cycles": 15147011}, "none": {"instructions": 617346, "cycles": 190446}, "field": {"instructions": 8887355, "cycles": 3105449}, "found": {"instructions": 14039323, "cycles": 10384001}} diff --git a/research/experiments/041-batches/2026-10-19-counts.jsonl b/research/experiments/041-batches/2026-10-19-counts.jsonl index 1308b8f..4d64572 100644 --- a/research/experiments/041-batches/2026-10-19-counts.jsonl +++ b/research/experiments/041-batches/2026-10-19-counts.jsonl @@ -78,3 +78,23 @@ {"version":"b48","way":"rounds","work":"matmul","instructions":21188570506,"cycles":7080362595} {"version":"b48","way":"batches","work":"bfs","instructions":3341462445,"cycles":1651383358} {"version":"b48","way":"rounds","work":"bfs","instructions":4708847452,"cycles":2089960576} +{"version":"b49","way":"batches","work":"bfs","instructions":3341464590,"cycles":1646561645} +{"version":"b49","way":"rounds","work":"bfs","instructions":4704847479,"cycles":2168041736} +{"version":"b49","way":"batches","work":"join","instructions":1783721471,"cycles":1034914133} +{"version":"b49","way":"rounds","work":"join","instructions":7711078090,"cycles":3500677823} +{"version":"b49","way":"batches","work":"knapsack","instructions":348032921,"cycles":105296183} +{"version":"b49","way":"rounds","work":"knapsack","instructions":22068882218,"cycles":8072864143} +{"version":"b49","way":"batches","work":"matmul","instructions":702231807,"cycles":226743470} +{"version":"b49","way":"rounds","work":"matmul","instructions":21188570525,"cycles":7082508169} +{"version":"b49","way":"batches","work":"roots","instructions":157246650,"cycles":109490715} +{"version":"b49","way":"rounds","work":"roots","instructions":2715504255,"cycles":1049396169} +{"version":"b50","way":"batches","work":"bfs","instructions":3341464219,"cycles":1654281878} +{"version":"b50","way":"rounds","work":"bfs","instructions":4704848617,"cycles":2112423475} +{"version":"b50","way":"batches","work":"join","instructions":1783747800,"cycles":1077705689} +{"version":"b50","way":"rounds","work":"join","instructions":7711078484,"cycles":3427071171} +{"version":"b50","way":"batches","work":"knapsack","instructions":348113595,"cycles":104567697} +{"version":"b50","way":"rounds","work":"knapsack","instructions":22068882244,"cycles":8077777633} +{"version":"b50","way":"batches","work":"matmul","instructions":702235577,"cycles":227645850} +{"version":"b50","way":"rounds","work":"matmul","instructions":21188570749,"cycles":7091541167} +{"version":"b50","way":"batches","work":"roots","instructions":157246595,"cycles":109502177} +{"version":"b50","way":"rounds","work":"roots","instructions":2715504257,"cycles":1048646803} diff --git a/research/experiments/044-specs/2026-10-19-list-value.jsonl b/research/experiments/044-specs/2026-10-19-list-value.jsonl new file mode 100644 index 0000000..c5058c2 --- /dev/null +++ b/research/experiments/044-specs/2026-10-19-list-value.jsonl @@ -0,0 +1,8 @@ +{"what": "list values by spec, before (an instrumented build, not committed: nest() timed; ROUNDS 1, 8 passes)", "pure_jit": "0", "linebreak": {"list_values": 1344384, "items": 4412520, "ns": 485793268, "passes": 8, "source_form": "FLAT"}, "json_tree": {"list_values": 32008, "items": 96000, "ns": 35799925, "passes": 8, "source_form": "tree"}, "http": {"list_values": 4768, "items": 16536, "ns": 4182491, "passes": 8, "source_form": "tree"}, "inflate": {"list_values": 72, "items": 4312, "ns": 302150, "passes": 8}, "dns": {"list_values": 0}, "json": {"list_values": 0}, "layout": {"list_values": 0}} +{"what": "a list value of numbers, ns a copy (instrumented, its clock in it: 100-150 ns)", "items": [3, 60, 600], "before": [540, 3926, 38268], "after": [320, 324, 985]} +{"what": "linebreak nest() a pass, ns (instrumented)", "before": 48646023, "after": 17293018, "copies": 168048} +{"what": "time, base (f1bb9de) and new (1c1133c) libpure, three pairs in turns, medians", "spec": "linebreak", "pure_jit": "0", "base": {"ns": 6916.7, "runs": [6956.2, 6914.4, 6916.7], "instructions": 1774.3}, "new": {"ns": 6444.7, "runs": [6445.9, 6437.0, 6444.7], "instructions": 1774.3}} +{"what": "time, base (f1bb9de) and new (1c1133c) libpure, three pairs in turns, medians", "spec": "json_tree", "pure_jit": "0", "base": {"ns": 606.014, "runs": [606.014, 605.443, 606.019], "instructions": 248.0}, "new": {"ns": 607.423, "runs": [608.203, 607.423, 606.024], "instructions": 248.0}} +{"what": "time, base (f1bb9de) and new (1c1133c) libpure, three pairs in turns, medians", "spec": "http", "pure_jit": "0", "base": {"ns": 270.569, "runs": [270.569, 270.789, 270.399], "instructions": 61.6}, "new": {"ns": 270.517, "runs": [270.613, 270.517, 270.509], "instructions": 61.6}} +{"what": "time, base (f1bb9de) and new (1c1133c) libpure, three pairs in turns, medians", "spec": "inflate", "pure_jit": "0", "base": {"ns": 894.96, "runs": [894.96, 894.952, 894.965], "instructions": 151.2}, "new": {"ns": 895.166, "runs": [895.166, 895.338, 894.811], "instructions": 151.2}} +{"what": "041's five works, user-mode instructions of 3 rounds (041-batches/2026-10-19-counts.jsonl)", "b49 batches bfs": 3341464590, "b49 rounds bfs": 4704847479, "b49 batches join": 1783721471, "b49 rounds join": 7711078090, "b49 batches knapsack": 348032921, "b49 rounds knapsack": 22068882218, "b49 batches matmul": 702231807, "b49 rounds matmul": 21188570525, "b49 batches roots": 157246650, "b49 rounds roots": 2715504255, "b50 batches bfs": 3341464219, "b50 rounds bfs": 4704848617, "b50 batches join": 1783747800, "b50 rounds join": 7711078484, "b50 batches knapsack": 348113595, "b50 rounds knapsack": 22068882244, "b50 batches matmul": 702235577, "b50 rounds matmul": 21188570749, "b50 batches roots": 157246595, "b50 rounds roots": 2715504257} -- cgit v1.2.3