aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authoreunhhu <[email protected]>2026-10-19 08:05:53 +0100
committereunhhu <[email protected]>2026-10-19 08:05:53 +0100
commit4a7e780278df740e5e37c3307fe687405df72448 (patch)
treeab56d72029970669416705cd5ea7c50f9caffbf3
parent1c1133ce8258dad367aad3b7c8eee0083aecf772 (diff)
downloadpure-4a7e780278df740e5e37c3307fe687405df72448.tar.gz
pure-4a7e780278df740e5e37c3307fe687405df72448.zip
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
-rw-r--r--docs/research/140-spec-suite.md63
-rw-r--r--research/experiments/040-against-c/2026-10-19-counts.jsonl4
-rw-r--r--research/experiments/041-batches/2026-10-19-counts.jsonl20
-rw-r--r--research/experiments/044-specs/2026-10-19-list-value.jsonl8
4 files changed, 95 insertions, 0 deletions
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}