aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authoreunhhu <[email protected]>2026-10-19 01:31:39 +0100
committereunhhu <[email protected]>2026-10-19 01:31:39 +0100
commit809a83a5764ec0f0c84b96c43a20cfb906eee031 (patch)
treefe255be70914400060d810ec9ecd68c0edf1305e
parentb79f627af433a63f8f42869b124f5ef344a49352 (diff)
downloadpure-809a83a5764ec0f0c84b96c43a20cfb906eee031.tar.gz
pure-809a83a5764ec0f0c84b96c43a20cfb906eee031.zip
027's 5b: an i64 sum exact: its items gathered in a 128-bit integer and only the result checked against the range (overflow past it), so a sum past the range midway and back in it at the end is the answer and an i64 sum's order is none of its business; the batch executor's folds are numbers' lanes alone, summed in the items' order, as before; 008's FOLD says so; counts: b44 against b43 within 0.04% (BFS without batches -0.03%); the bank's queries (s43 and s44 in turns, six each) per_branch -1.32% (all six below s43's lowest: a larger Fold lays the number sum's loop otherwise), in_credit -0.72%, ranks -0.26%, the rest within 0.01%, the seven queries' answers the same bytes on both; 008 and 027
-rw-r--r--core/module.c21
-rw-r--r--docs/design/008-module-format.md2
-rw-r--r--docs/design/027-computation-core.md9
-rw-r--r--research/experiments/040-against-c/2026-10-19-counts-s44.jsonl12
-rw-r--r--research/experiments/041-batches/2026-10-19-counts.jsonl10
5 files changed, 44 insertions, 10 deletions
diff --git a/core/module.c b/core/module.c
index 052528c..ca5b0e2 100644
--- a/core/module.c
+++ b/core/module.c
@@ -3283,9 +3283,11 @@ static bool run_lanes(const PureModule *m, const PureValue *values, PureBlock bl
typedef struct { uint64_t *keys; size_t capacity, count; bool marked; } Seen;
/* A fold's running value: what count, sum, max, min, first or distinct has
- * so far, over numbers (total) or i64s (whole; a sum past the range
- * overflows and ends the fold). */
-typedef struct { unsigned how; bool integer, overflow; double total; int64_t whole; bool any, done; Seen seen; } Fold;
+ * so far, over numbers (total) or i64s (whole; an i64 sum exactly, in sum:
+ * only the result past the range overflows, so its items' order is none of
+ * its business: 027's stage 5). */
+__extension__ typedef __int128 Wide;
+typedef struct { unsigned how; bool integer; double total; int64_t whole; Wide sum; bool any, done; Seen seen; } Fold;
static size_t seen_slot(uint64_t bits, size_t capacity) {
bits ^= bits >> 33, bits *= 0xff51afd7ed558ccdu, bits ^= bits >> 33;
@@ -3353,8 +3355,7 @@ static bool fold_number(Fold *fold, size_t row, double value, double counts) {
return true;
}
-/* One item run as written: a number's, or an i64's (a sum past the range
- * overflows and ends the fold; count and first take no i64). */
+/* One item run as written: a number's, or an i64's (count and first take no i64). */
static bool fold_in(Fold *fold, size_t row, PureValue value, double counts) {
if (!fold->integer) return fold_number(fold, row, value.num, counts);
if (counts == 0) return true;
@@ -3365,9 +3366,8 @@ static bool fold_in(Fold *fold, size_t row, PureValue value, double counts) {
fold->any = true;
return !full;
}
- if (fold->how == PURE_FOLD_SUM) {
- if (__builtin_add_overflow(fold->whole, v, &fold->whole)) fold->overflow = fold->done = true;
- } else if (!fold->any || (fold->how == PURE_FOLD_MAX ? v > fold->whole : v < fold->whole))
+ if (fold->how == PURE_FOLD_SUM) fold->sum += v; /* (a Wide holds 2^64 items' worth) */
+ else if (!fold->any || (fold->how == PURE_FOLD_MAX ? v > fold->whole : v < fold->whole))
fold->whole = v;
fold->any = true;
return true;
@@ -4202,7 +4202,10 @@ static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp
free(fold.seen.keys);
if (status != PURE_OK) STOPPED(status);
}
- if (fold.overflow) { kind = PURE_FAULT_OVERFLOW; FAILED; }
+ if (fold.integer && fold.how == PURE_FOLD_SUM) { /* the exact sum, if an i64 holds it */
+ if (fold.sum > INT64_MAX || fold.sum < INT64_MIN) { kind = PURE_FAULT_OVERFLOW; FAILED; }
+ fold.whole = (int64_t)fold.sum;
+ }
if (!fold.any && (fold.how == PURE_FOLD_MAX || fold.how == PURE_FOLD_MIN || fold.how == PURE_FOLD_FIRST)) {
kind = PURE_FAULT_NOT_FOUND;
FAILED;
diff --git a/docs/design/008-module-format.md b/docs/design/008-module-format.md
index 201baf9..0ef9bf8 100644
--- a/docs/design/008-module-format.md
+++ b/docs/design/008-module-format.md
@@ -185,7 +185,7 @@ v7은 027의 4단계(패턴 모으기)의 판이다. 4b로 **키별 문서**를
bool은 실행 중에 수의 칸에 든 0이나 1이고, i64는 같은 8바이트의 정수다. CONST의 인자 2는 i64 상수(값의 8바이트), NUM_TEXT의
인자 2는 i64의 10진 글자다. LOAD·STORE·지역 칸·항목·FIELD·SEND는 i64를 수처럼 옮긴다. FOLD의 종류에 64(PURE_FOLD_INTEGER)를
-더하면 sum·max·min·distinct가 i64 값을 받는다(sum이 범위를 넘으면 `overflow`). i64 키 목록은 정수로 비교한다. `f`는 레코드 필드의 타입(수, text, bool 또는 i64)이고, `k`는 그 리스트의 키 필드 타입이다. 수 연산 결과가 유한하지 않으면 실패한다. 실패하면 그 이벤트의 모든
+더하면 sum·max·min·distinct가 i64 값을 받는다(sum은 정확하게 셈하고 결과가 범위를 넘을 때만 `overflow`: 중간이 넘쳐도 끝이 i64 안이면 답이라 항목의 차례에 매이지 않는다). i64 키 목록은 정수로 비교한다. `f`는 레코드 필드의 타입(수, text, bool 또는 i64)이고, `k`는 그 리스트의 키 필드 타입이다. 수 연산 결과가 유한하지 않으면 실패한다. 실패하면 그 이벤트의 모든
핸들러가 한 일이 취소된다.
## 로드할 때 검증하는 것
diff --git a/docs/design/027-computation-core.md b/docs/design/027-computation-core.md
index 4c7fb60..0813958 100644
--- a/docs/design/027-computation-core.md
+++ b/docs/design/027-computation-core.md
@@ -539,6 +539,15 @@
200쌍의 `a // b`와 `a % b`를 파이썬과 비트까지(−0의 부호까지) 견준다. 진단 하나(305).
- 명령 수(b43 대 b42): 실행기만의 BFS −0.09%, 나머지 ±0.001% 안이다. 은행 질의(s42와 s43을 한 번에 번갈아 여섯 번)는 −0.20%에서
0.00% 사이다.
+ - **5b 만듦(2026-10-19).**
+ - Pure: i64의 sum을 128비트 정수(`__int128`)에 정확하게 모으고, 접기가 끝날 때 결과만 범위를 본다(넘으면 `overflow`). 중간의
+ 넘침이 사라져 i64 합은 항목의 차례에 매이지 않는다. 128비트는 i64 2^64개의 합을 담는다. 묶음 실행기의 접기는 number의 레인뿐이고
+ 항목의 차례대로 더하므로 그대로다(i64의 접기는 항목마다 돈다).
+ - 시험: aup의 시험이 i64 리스트에 가장 큰 i64, 1, −2, 2를 차례로 더하며 합의 보기를 본다: 가장 큰 i64, `overflow`(보기가 빈다),
+ 가장 큰 i64 − 1(중간이 넘쳤어도 답이다), `overflow`. 008의 FOLD에 그 뜻을 적었다.
+ - 명령 수(b44 대 b43): ±0.04% 안이다(실행기만의 BFS −0.03%). 은행 질의(s43과 s44를 한 번에 번갈아 여섯 번의 중앙값)는 per_branch
+ −1.32%(여섯 번 모두 s43의 가장 낮은 것 아래: Fold가 커져 number 합의 고리가 달리 놓였다), in_credit −0.72%, ranks −0.26%, 나머지
+ ±0.01% 안이다. 일곱 질의의 답은 두 빌드에서 바이트까지 같다.
**순서의 까닭.**
- 1과 2가 묶음의 명세 대부분을 연다. 가장 값이 크다.
diff --git a/research/experiments/040-against-c/2026-10-19-counts-s44.jsonl b/research/experiments/040-against-c/2026-10-19-counts-s44.jsonl
new file mode 100644
index 0000000..0317a5d
--- /dev/null
+++ b/research/experiments/040-against-c/2026-10-19-counts-s44.jsonl
@@ -0,0 +1,12 @@
+{"serve": "pure-serve", "per_branch": {"instructions": 27085607, "cycles": 12001170}, "in_credit": {"instructions": 3505582, "cycles": 1625979}, "large": {"instructions": 1412830, "cycles": 586912}, "ranks": {"instructions": 24436679, "cycles": 14818761}, "none": {"instructions": 617346, "cycles": 190613}, "field": {"instructions": 8917574, "cycles": 3098994}, "found": {"instructions": 14070911, "cycles": 10603885}}
+{"serve": "pure-serve", "per_branch": {"instructions": 26889165, "cycles": 11969954}, "in_credit": {"instructions": 3516405, "cycles": 1588634}, "large": {"instructions": 1412854, "cycles": 589521}, "ranks": {"instructions": 24464801, "cycles": 14765295}, "none": {"instructions": 617346, "cycles": 191278}, "field": {"instructions": 8917574, "cycles": 3107257}, "found": {"instructions": 14070767, "cycles": 10535250}}
+{"serve": "pure-serve", "per_branch": {"instructions": 27297383, "cycles": 11823551}, "in_credit": {"instructions": 3553087, "cycles": 1641957}, "large": {"instructions": 1412782, "cycles": 594487}, "ranks": {"instructions": 24553578, "cycles": 14850715}, "none": {"instructions": 617346, "cycles": 193168}, "field": {"instructions": 8917574, "cycles": 3097810}, "found": {"instructions": 14067894, "cycles": 10611655}}
+{"serve": "pure-serve", "per_branch": {"instructions": 26928829, "cycles": 12160940}, "in_credit": {"instructions": 3525135, "cycles": 1605826}, "large": {"instructions": 1412790, "cycles": 586239}, "ranks": {"instructions": 24484976, "cycles": 16087485}, "none": {"instructions": 617346, "cycles": 215727}, "field": {"instructions": 8917574, "cycles": 3178320}, "found": {"instructions": 14068430, "cycles": 10172471}}
+{"serve": "pure-serve", "per_branch": {"instructions": 27303273, "cycles": 12329450}, "in_credit": {"instructions": 3554393, "cycles": 1720535}, "large": {"instructions": 1412766, "cycles": 779344}, "ranks": {"instructions": 24557459, "cycles": 15102204}, "none": {"instructions": 617346, "cycles": 195274}, "field": {"instructions": 8917574, "cycles": 3117935}, "found": {"instructions": 14068823, "cycles": 10325207}}
+{"serve": "pure-serve", "per_branch": {"instructions": 26840722, "cycles": 11902778}, "in_credit": {"instructions": 3505565, "cycles": 1582785}, "large": {"instructions": 1412878, "cycles": 615649}, "ranks": {"instructions": 24437680, "cycles": 14896302}, "none": {"instructions": 617346, "cycles": 191445}, "field": {"instructions": 8917575, "cycles": 3097807}, "found": {"instructions": 14069831, "cycles": 10511346}}
+{"serve": "pure-serve", "per_branch": {"instructions": 27276793, "cycles": 11945931}, "in_credit": {"instructions": 3548439, "cycles": 1613872}, "large": {"instructions": 1412830, "cycles": 596596}, "ranks": {"instructions": 24541453, "cycles": 14849958}, "none": {"instructions": 617346, "cycles": 191203}, "field": {"instructions": 8917574, "cycles": 3107698}, "found": {"instructions": 14068679, "cycles": 10580306}}
+{"serve": "pure-serve", "per_branch": {"instructions": 27109584, "cycles": 12814964}, "in_credit": {"instructions": 3565922, "cycles": 1639444}, "large": {"instructions": 1412806, "cycles": 597538}, "ranks": {"instructions": 24585462, "cycles": 15067404}, "none": {"instructions": 617346, "cycles": 193021}, "field": {"instructions": 8917575, "cycles": 3105280}, "found": {"instructions": 14069327, "cycles": 11116570}}
+{"serve": "pure-serve", "per_branch": {"instructions": 27253267, "cycles": 11780440}, "in_credit": {"instructions": 3543390, "cycles": 1612778}, "large": {"instructions": 1412798, "cycles": 600064}, "ranks": {"instructions": 24531189, "cycles": 14932089}, "none": {"instructions": 617346, "cycles": 190750}, "field": {"instructions": 8917677, "cycles": 3099309}, "found": {"instructions": 14068303, "cycles": 10243530}}
+{"serve": "pure-serve", "per_branch": {"instructions": 26813264, "cycles": 11775255}, "in_credit": {"instructions": 3499393, "cycles": 1558388}, "large": {"instructions": 1412870, "cycles": 598217}, "ranks": {"instructions": 24422351, "cycles": 14707787}, "none": {"instructions": 617346, "cycles": 190575}, "field": {"instructions": 8917574, "cycles": 3106960}, "found": {"instructions": 14070502, "cycles": 10362872}}
+{"serve": "pure-serve", "per_branch": {"instructions": 27002801, "cycles": 11774783}, "in_credit": {"instructions": 3487045, "cycles": 1643142}, "large": {"instructions": 1412862, "cycles": 601615}, "ranks": {"instructions": 24391326, "cycles": 14666502}, "none": {"instructions": 617346, "cycles": 190604}, "field": {"instructions": 8917574, "cycles": 3095604}, "found": {"instructions": 14072087, "cycles": 10181850}}
+{"serve": "pure-serve", "per_branch": {"instructions": 26922980, "cycles": 11994325}, "in_credit": {"instructions": 3524030, "cycles": 1628818}, "large": {"instructions": 1412822, "cycles": 591557}, "ranks": {"instructions": 24482691, "cycles": 14816251}, "none": {"instructions": 617346, "cycles": 192759}, "field": {"instructions": 8917574, "cycles": 3104001}, "found": {"instructions": 14070087, "cycles": 10401503}}
diff --git a/research/experiments/041-batches/2026-10-19-counts.jsonl b/research/experiments/041-batches/2026-10-19-counts.jsonl
index 3746b9e..958d9d2 100644
--- a/research/experiments/041-batches/2026-10-19-counts.jsonl
+++ b/research/experiments/041-batches/2026-10-19-counts.jsonl
@@ -28,3 +28,13 @@
{"version":"b43","way":"rounds","work":"matmul","instructions":21186409838,"cycles":6817006402}
{"version":"b43","way":"batches","work":"bfs","instructions":3341463903,"cycles":1640907916}
{"version":"b43","way":"rounds","work":"bfs","instructions":4705147005,"cycles":2086468365}
+{"version":"b44","way":"batches","work":"roots","instructions":157246372,"cycles":110236606}
+{"version":"b44","way":"rounds","work":"roots","instructions":2715504098,"cycles":1000646542}
+{"version":"b44","way":"batches","work":"knapsack","instructions":348031933,"cycles":105343305}
+{"version":"b44","way":"rounds","work":"knapsack","instructions":22162412282,"cycles":7769116952}
+{"version":"b44","way":"batches","work":"join","instructions":1783720568,"cycles":1020867745}
+{"version":"b44","way":"rounds","work":"join","instructions":7723077450,"cycles":3523189145}
+{"version":"b44","way":"batches","work":"matmul","instructions":702231628,"cycles":227521152}
+{"version":"b44","way":"rounds","work":"matmul","instructions":21186170497,"cycles":6763916506}
+{"version":"b44","way":"batches","work":"bfs","instructions":3341455171,"cycles":1657087395}
+{"version":"b44","way":"rounds","work":"bfs","instructions":4703547672,"cycles":2087752517}