From 2634e067cd2411078d61c7f737dcd7b06121d5df Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 19 Oct 2026 13:05:34 +0100 Subject: 045: UAX #14's whole app emitted by hand, the chain (app.c, app-way.h: on line, decide and its fns written once against a rung's macros; every rung answers all 18,672 lines as the test and exactly as exact; with LB18 made wrong every rung is refused): machine instructions a code point, the handler: exact 8,785 (registers and plain calls; doubles, fmod, whole and bounds checks twice, the event's lists FLAT PureLists with list_held and grows at each append, Text's lists copied, ranges the stored tree, the budget), integers 7,979, ranges' columns flat 6,561, the event's lists typed buffers 696, Text sharing them 564, no bounds checks 502, no charges 362 (the same algorithm in C), Vega's C 225; the executor 40,189 and stitched 28,089 hold the event's own 1,566 besides (an empty handler: decoding the points into a list, clearing and freeing the event's lists, malloc, the breaks state through the store tree) --- .../045-proof-compiler/2026-10-19-app.jsonl | 18 + .../045-proof-compiler/2026-10-19-where-v0.txt | 75 ++++ research/experiments/045-proof-compiler/app-way.h | 193 ++++++++++ research/experiments/045-proof-compiler/app.c | 417 +++++++++++++++++++++ 4 files changed, 703 insertions(+) create mode 100644 research/experiments/045-proof-compiler/2026-10-19-app.jsonl create mode 100644 research/experiments/045-proof-compiler/2026-10-19-where-v0.txt create mode 100644 research/experiments/045-proof-compiler/app-way.h create mode 100644 research/experiments/045-proof-compiler/app.c (limited to 'research/experiments') diff --git a/research/experiments/045-proof-compiler/2026-10-19-app.jsonl b/research/experiments/045-proof-compiler/2026-10-19-app.jsonl new file mode 100644 index 0000000..c8886cc --- /dev/null +++ b/research/experiments/045-proof-compiler/2026-10-19-app.jsonl @@ -0,0 +1,18 @@ +{"what": "the executor and the stitched build on the app (cost.c, 2026-10-19-break.jsonl), and the empty handler (v0: the event itself, the same in both)", "executor": {"instructions_per_point": 40189.2, "cycles_per_point": 15416}, "stitched": {"instructions_per_point": 28088.7, "cycles_per_point": 11704}, "event_v0": {"instructions_per_point": 1565.6, "cycles_per_point": 625}, "event_v0_by_file": {"module-list.c": 674, "libc (malloc, free)": 389, "module.c": 386, "store-tree.c": 113}} +{"rung": "exact", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 8784.6, "cycles_per_point": 3996.8, "answers": "the test's, and exact's", "run": 1} +{"rung": "integer", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 7979.0, "cycles_per_point": 3539.1, "answers": "the test's, and exact's", "run": 1} +{"rung": "stored_flat", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 6560.8, "cycles_per_point": 2800.3, "answers": "the test's, and exact's", "run": 1} +{"rung": "local_flat", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 696.4, "cycles_per_point": 364.4, "answers": "the test's, and exact's", "run": 1} +{"rung": "shared", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 564.3, "cycles_per_point": 319.4, "answers": "the test's, and exact's", "run": 1} +{"rung": "unbounded", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 501.9, "cycles_per_point": 300.3, "answers": "the test's, and exact's", "run": 1} +{"rung": "plain", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 361.7, "cycles_per_point": 260.1, "answers": "the test's, and exact's", "run": 1} +{"rung": "vega", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 224.7, "cycles_per_point": 87.7, "answers": "the test's, and exact's", "run": 1} +{"rung": "exact", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 8784.6, "cycles_per_point": 4007.0, "answers": "the test's, and exact's", "run": 2} +{"rung": "integer", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 7979.0, "cycles_per_point": 3554.2, "answers": "the test's, and exact's", "run": 2} +{"rung": "stored_flat", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 6560.8, "cycles_per_point": 2799.8, "answers": "the test's, and exact's", "run": 2} +{"rung": "local_flat", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 696.4, "cycles_per_point": 362.9, "answers": "the test's, and exact's", "run": 2} +{"rung": "shared", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 564.3, "cycles_per_point": 314.7, "answers": "the test's, and exact's", "run": 2} +{"rung": "unbounded", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 501.9, "cycles_per_point": 295.5, "answers": "the test's, and exact's", "run": 2} +{"rung": "plain", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 361.7, "cycles_per_point": 255.1, "answers": "the test's, and exact's", "run": 2} +{"rung": "vega", "lines": 18672, "code_points": 61285, "rounds": 5, "instructions_per_point": 224.7, "cycles_per_point": 87.2, "answers": "the test's, and exact's", "run": 2} +{"what": "built with -DBREAK_ONE_RULE (LB18 wrong): every hand rung refused, 6,233 of 18,672 lines wrong each"} diff --git a/research/experiments/045-proof-compiler/2026-10-19-where-v0.txt b/research/experiments/045-proof-compiler/2026-10-19-where-v0.txt new file mode 100644 index 0000000..47850cb --- /dev/null +++ b/research/experiments/045-proof-compiler/2026-10-19-where-v0.txt @@ -0,0 +1,75 @@ +1,577 machine instructions a code point, 48,284 samples + +by mechanism: + 660 41.9% unknown + 375 23.8% list build + 249 15.8% memory + 178 11.3% event + 45 2.9% dispatch + 44 2.8% compute + 18 1.2% list read + 4 0.2% moves + 2 0.1% loop + +in step(), by the case its line is in (code the compiler shares between cases goes to one of them): + 47 LIST_APPEND + 45 (fetch, decode) + 39 TEXT_INSERT + 13 BYTES_OF + 5 TEXT_REMOVE + 4 CONST + 1 FLOORDIV + +outside step(), by function as linked: + 127 ?? + 121 arrays_free + 96 free + 88 place + 79 decode_cell + 79 pure_list_insert + 77 message + 57 malloc + 52 __default_morecore + 49 pure_list_read + 47 prepare_extras + 37 __xpg_strerror_r + 35 clear_rows + 34 open_burst + 30 pure_list_clear + 25 pure_list_settle + 23 chunk_bytes + 23 own + 22 sum + 20 mark_event + 20 run_batches + 19 collect + 19 pure_list_changes + 19 sum_path + 18 close_burst + 14 put_cells + 14 descend + 14 add_node + 13 let_go_tree + 12 timer_settime + +no mechanism: + 67 ?? (where:0) < ?? + 61 ?? (??:0) < ?? + 50 decode_cell (module-list.c:2132) < decode_cell + 45 prepare_extras (module-list.c:625) < prepare_extras + 26 decode_item (module-list.c:2344) < pure_list_read + 13 move_items (module-list.c:337) < place + 13 decode_cell (module-list.c:2130) < decode_cell + 12 place (module-list.c:729) < place + 12 sum_path (module-list.c:591) < sum_path + 11 place (module-list.c:689) < place + 9 own (module-list.c:563) < own + 9 own (module-list.c:552) < own + 8 pure_list_read (module-list.c:2358) < pure_list_read + 8 run_batches (module.c:4968) < run_batches + 8 release_extras (module-list.c:673) < place + 8 pure_draft_size (store-tree.c:1530) < pure_draft_size + 8 pure_draft_version (store-tree.c:1584) < pure_draft_version + 8 place (module-list.c:682) < place + 8 chunk_bytes (store-tree.c:615) < chunk_bytes + 7 sum (module-list.c:511) < sum diff --git a/research/experiments/045-proof-compiler/app-way.h b/research/experiments/045-proof-compiler/app-way.h new file mode 100644 index 0000000..44e3d98 --- /dev/null +++ b/research/experiments/045-proof-compiler/app-way.h @@ -0,0 +1,193 @@ +/* Research 045: UAX #14's app (aup's examples/linebreak.aup: on line, decide and the fns it calls), written once by hand + * as an emitter would write it, against the macros a way (app.c) defines first: how numbers that are whole are held + * (IDX) and computed, how an index is checked, how the event's lists, the message's points and the stored ranges are + * held and read (LIST_N numbers, LIST_I whole numbers, LIST_B bools), what a record of lists takes (CAPTURE), and what + * the budget charges. Included once a way, with WAY + * the suffix of its names. Locals are C's (registers) and each aup fn a C function in every way. + * + * C's && and || go no further than they must; where the executor evaluates both sides, this does less (so the first + * way is cheaper than the module's code would be, never dearer). */ +#define JOIN2(a, b) a##_##b +#define JOIN(a, b) JOIN2(a, b) +#define FN(name) JOIN(name, WAY) + +/* -1 aside, every value the app keeps of a code point's position: the result of a call that faulted is 0 and x->fault set. */ +#define FAIL do { x->fault = true; x->fault_line = __LINE__; return 0; } while (0) +#define CALLED(e) ({ __typeof__(e) called_ = (e); if (x->fault) return 0; called_; }) + +typedef struct { LIST_N codes, cls, eff; LIST_I start, nonspace, ri, at; LIST_B joined, numeric; } FN(Text); + +static double FN(range)(CONTEXT *x, double c) { + CHARGE(CALL_COST); + IDX low = 0, high = R_COUNT; + while (GT(SUB(high, low), 1)) { + CHARGE(ROUND_COST); + IDX middle = DIV2(ADD(low, high)); + if (R_START(middle) <= c) low = middle; + else high = middle; + } + return (double)low; +} + +static IDX FN(next_unit)(CONTEXT *x, const FN(Text) *t, IDX i) { + CHARGE(CALL_COST); + IDX j = ADD(i, 1); + while (j < NCOUNT(t->codes) && GETB(t->joined, j)) { + CHARGE(ROUND_COST); + j = ADD(j, 1); + } + return j; +} + +static bool FN(aksara)(CONTEXT *x, const FN(Text) *t, IDX u) { + CHARGE(CALL_COST); + return GETN(t->eff, u) == AK || GETN(t->eff, u) == AS || GETN(t->codes, u) == 0x25CC; +} +static bool FN(pi)(CONTEXT *x, const FN(Text) *t, IDX k) { CHARGE(CALL_COST); return R_PI(GETI(t->at, k)); } +static bool FN(pf)(CONTEXT *x, const FN(Text) *t, IDX k) { CHARGE(CALL_COST); return R_PF(GETI(t->at, k)); } +static bool FN(east)(CONTEXT *x, const FN(Text) *t, IDX k) { CHARGE(CALL_COST); return R_EAST(GETI(t->at, k)); } + +#define END(c) ((c) == BK || (c) == CR || (c) == LF || (c) == NL) +#define NEXT_UNIT(i) CALLED(FN(next_unit)(x, t, (i))) +#define AKSARA(u) CALLED(FN(aksara)(x, t, (u))) +#define PI(k) CALLED(FN(pi)(x, t, (k))) +#define PF(k) CALLED(FN(pf)(x, t, (k))) +#define EAST(k) CALLED(FN(east)(x, t, (k))) + +static int FN(decide)(CONTEXT *x, const FN(Text) *t, IDX i) { + CHARGE(CALL_COST); + IDX n = NCOUNT(t->codes); + double a = GETN(t->cls, SUB(i, 1)), b = GETN(t->cls, i), A = GETN(t->eff, SUB(i, 1)), B = GETN(t->eff, i); + IDX unit = GETI(t->start, SUB(i, 1)), before = GETI(t->nonspace, SUB(i, 1)); + double base = GETN(t->codes, unit); + if (a == BK) return MANDATORY; /* LB4 */ + if (a == CR && b == LF) return NONE; /* LB5 */ + if (a == CR || a == LF || a == NL) return MANDATORY; + if (END(b)) return NONE; /* LB6 */ + if (b == SP || b == ZW) return NONE; /* LB7 */ + if (before >= 0 && GETN(t->eff, before) == ZW) return ALLOWED; /* LB8 */ + if (a == ZWJ) return NONE; /* LB8a */ + if (GETB(t->joined, i)) return NONE; /* LB9 */ + if (A == WJ || B == WJ) return NONE; /* LB11 */ + if (A == GL) return NONE; /* LB12 */ + if (B == GL && A != SP && A != BA && A != HY) return NONE; /* LB12a */ + if (B == CL || B == CP || B == EX || B == SY) return NONE; /* LB13 */ + if (before >= 0 && GETN(t->eff, before) == OP) return NONE; /* LB14 */ + if (before >= 0 && GETN(t->eff, before) == QU && PI(before)) { /* LB15a */ + if (before == 0) return NONE; + double q = GETN(t->eff, SUB(before, 1)); + if (END(q) || q == OP || q == QU || q == GL || q == SP || q == ZW) return NONE; + } + if (B == QU && PF(i)) { /* LB15b */ + IDX j = NEXT_UNIT(i); + if (j == n) return NONE; + double e = GETN(t->eff, j); + if (e == SP || e == GL || e == WJ || e == CL || e == QU || e == CP || e == EX || e == IS || e == SY || END(e) || e == ZW) + return NONE; + } + if (A == SP && B == IS) { /* LB15c */ + IDX j = NEXT_UNIT(i); + if (j < n && GETN(t->eff, j) == NU) return ALLOWED; + } + if (B == IS) return NONE; /* LB15d */ + if (B == NS && before >= 0 && (GETN(t->eff, before) == CL || GETN(t->eff, before) == CP)) return NONE; /* LB16 */ + if (B == B2 && before >= 0 && GETN(t->eff, before) == B2) return NONE; /* LB17 */ +#ifdef BREAK_ONE_RULE + if (A == SP) return NONE; /* a rule made wrong: the check must refuse the way */ +#else + if (A == SP) return ALLOWED; /* LB18 */ +#endif + if (B == QU && !PI(i)) return NONE; /* LB19 */ + if (A == QU && !PF(unit)) return NONE; + if (B == QU) { /* LB19a */ + IDX j = NEXT_UNIT(i); + if (!EAST(unit) || j == n || !EAST(j)) return NONE; + } + if (A == QU && (!EAST(i) || unit == 0 || !EAST(GETI(t->start, SUB(unit, 1))))) return NONE; + if (B == CB || A == CB) return ALLOWED; /* LB20 */ + if ((A == HY || base == 0x2010) && B == AL) { /* LB20a */ + double w = unit > 0 ? GETN(t->eff, SUB(unit, 1)) : SP; + if (END(w) || w == SP || w == ZW || w == CB || w == GL) return NONE; + } + if (B == BA || B == HY || B == NS || A == BB) return NONE; /* LB21 */ + if ((A == HY || (A == BA && !EAST(unit))) && unit > 0 && GETN(t->eff, SUB(unit, 1)) == HL && B != HL) return NONE; /* LB21a */ + if (A == SY && B == HL) return NONE; /* LB21b */ + if (B == IN) return NONE; /* LB22 */ + if (((A == AL || A == HL) && B == NU) || (A == NU && (B == AL || B == HL))) return NONE; /* LB23 */ + if ((A == PR && (B == ID || B == EB || B == EM)) || ((A == ID || A == EB || A == EM) && B == PO)) return NONE; /* LB23a */ + if (((A == PR || A == PO) && (B == AL || B == HL)) || ((A == AL || A == HL) && (B == PR || B == PO))) return NONE; /* LB24 */ + if ((B == PO || B == PR) && + (GETB(t->numeric, SUB(i, 1)) || ((A == CL || A == CP) && unit > 0 && GETB(t->numeric, SUB(unit, 1))))) + return NONE; /* LB25 */ + if (A == PO || A == PR) { + if (B == NU) return NONE; + if (B == OP) { + IDX j = NEXT_UNIT(i); + if (j < n && GETN(t->eff, j) == IS) j = NEXT_UNIT(j); + if (j < n && GETN(t->eff, j) == NU) return NONE; + } + } + if ((A == HY || A == IS || GETB(t->numeric, SUB(i, 1))) && B == NU) return NONE; + if (A == JL && (B == JL || B == JV || B == H2 || B == H3)) return NONE; /* LB26 */ + if (((A == JV || A == H2) && (B == JV || B == JT)) || ((A == JT || A == H3) && B == JT)) return NONE; + bool jamo = A == JL || A == JV || A == JT || A == H2 || A == H3; /* LB27 */ + if ((jamo && B == PO) || (A == PR && (B == JL || B == JV || B == JT || B == H2 || B == H3))) return NONE; + if ((A == AL || A == HL) && (B == AL || B == HL)) return NONE; /* LB28 */ + if (A == AP && AKSARA(i)) return NONE; /* LB28a */ + if (AKSARA(unit) && (B == VF || B == VI)) return NONE; + if (A == VI && unit > 0 && AKSARA(GETI(t->start, SUB(unit, 1))) && (B == AK || GETN(t->codes, i) == 0x25CC)) return NONE; + if (AKSARA(unit) && AKSARA(i)) { + IDX j = NEXT_UNIT(i); + if (j < n && GETN(t->eff, j) == VF) return NONE; + } + if (A == IS && (B == AL || B == HL)) return NONE; /* LB29 */ + if ((A == AL || A == HL || A == NU) && B == OP && !EAST(i)) return NONE; /* LB30 */ + if (A == CP && !EAST(unit) && (B == AL || B == HL || B == NU)) return NONE; + if (A == RI && B == RI && MOD2(GETI(t->ri, SUB(i, 1))) == 1) return NONE; /* LB30a */ + if (B == EM && (A == EB || R_PICT(GETI(t->at, unit)))) return NONE; /* LB30b */ + return ALLOWED; /* LB31 */ +} + +/* on line: the boundaries of the line's points into got (0 none, 1 allowed, 2 mandatory), count + 1 of them; false on a fault. */ +static bool FN(on_line)(CONTEXT *x, const POINTS *points, uint8_t *got) { + LINE_BEGIN; + for (IDX k = 0; k < P_COUNT(points); k = k + 1) { + CHARGE(ROUND_COST); + double code = P_CODE(points, k); + IDX i = NCOUNT(L(codes)); + IDX r = (IDX)CALLED(FN(range)(x, code)); + double c = R_CLASS(r); + bool mark = c == CM || c == ZWJ; + double previous = i > 0 ? GETN(L(eff), SUB(i, 1)) : SP; + bool joins = mark && i > 0 && !END(previous) && previous != SP && previous != ZW; /* LB9, LB10 */ + double e = joins ? previous : mark ? AL : c; + APPN(L(codes), code); + APPN(L(cls), c); + APPI(L(at), r); + APPB(L(joined), joins); + APPN(L(eff), e); + APPI(L(start), joins ? GETI(L(start), SUB(i, 1)) : i); + APPI(L(nonspace), e != SP ? GETI(L(start), i) : i > 0 ? GETI(L(nonspace), SUB(i, 1)) : (IDX)-1); + APPB(L(numeric), joins ? GETB(L(numeric), SUB(i, 1)) : e == NU || ((e == SY || e == IS) && i > 0 && GETB(L(numeric), SUB(i, 1)))); + APPI(L(ri), joins ? GETI(L(ri), SUB(i, 1)) : e == RI ? ADD(i > 0 ? GETI(L(ri), SUB(i, 1)) : (IDX)0, 1) : (IDX)0); + } + FN(Text) t; + CAPTURE(t.codes, codes); CAPTURE(t.cls, cls); CAPTURE(t.eff, eff); CAPTURE(t.joined, joined); CAPTURE(t.start, start); + CAPTURE(t.nonspace, nonspace); CAPTURE(t.numeric, numeric); CAPTURE(t.ri, ri); CAPTURE(t.at, at); + OUT_APPEND(0); /* LB2 */ + for (IDX i = 1; i < NCOUNT(L(codes)); i = i + 1) { + CHARGE(ROUND_COST); + OUT_APPEND(CALLED(FN(decide)(x, &t, i))); + } + if (NCOUNT(L(codes)) > 0) OUT_APPEND(2); /* LB3 */ + OUT_EMIT(got); + LINE_END; + return true; +} + +#undef END +#undef NEXT_UNIT +#undef AKSARA +#undef PI +#undef PF +#undef EAST diff --git a/research/experiments/045-proof-compiler/app.c b/research/experiments/045-proof-compiler/app.c new file mode 100644 index 0000000..2c54a8e --- /dev/null +++ b/research/experiments/045-proof-compiler/app.c @@ -0,0 +1,417 @@ +/* Research 045: UAX #14's whole app emitted by hand (app-way.h), a rung at a time, each dropping one more thing the + * runtime holds that a fact of the proof could let go. Cumulative: + * + * exact Pure's meaning and the runtime's forms: numbers doubles, each sum and difference checked finite, // + * floor_divide and % Pure's (fmod); every index checked whole and in bounds (INDEX_AT) and again + * (ITEM_GET); the event's lists PureLists in FLAT arrays as the runtime keeps them (021: columns of + * the narrowest width that holds what they hold; cleared each line, appended with pure_list_insert and + * the memory a change holds counted as list_held and grows count it), the points the message's list, + * ranges the stored tree (pure_list_get); a Text's lists copied (pure_list_copied, LIST_VALUE) and let + * go at the line's end; the work budget charged each round and call. Locals in registers, plain calls. + * integer + whole numbers as integers (positions, counts, ranges, start, nonspace, ri, at): one bounds check. + * stored_flat + ranges' columns flat (unchanged in the event). + * local_flat + the event's lists, the points and out as flat buffers (a memory charge an append kept). + * shared + a Text's lists the buffers themselves (no copy). + * unbounded - the bounds checks (the budget and memory still charged). + * plain - every charge too: the same algorithm in C. + * vega Vega's C (text/linebreak.c; its classes from a two-stage table, no halving). + * + * Every rung's boundaries are compared first with the test's for all lines (and exactly with exact's); built with + * -DBREAK_ONE_RULE (LB18 made wrong) every rung must be refused. Then machine instructions and cycles a code point + * (perf_event_open, user mode), ROUNDS passes a rung, the rungs interleaved. + * + * cc -O2 -std=gnu17 -I../../../core -I../../../../vega/text app.c ../../../../vega/text/linebreak.c \ + * ../../../../vega/text/unicode-data.c ../../../build/libpure.a -lm -pthread -o app + * ./app linebreak.pmod RANGES LINES ROUNDS one JSON line a rung */ +#define _GNU_SOURCE +#include "module.h" +#include "module-list.h" +#include "text.h" +#include +#include +#include +#include +#include +#include +#include +#include + +enum { + BK = 0, CR = 1, LF = 2, NL = 3, SP = 4, ZW = 5, ZWJ = 6, CM = 7, WJ = 8, GL = 9, BA = 10, BB = 11, B2 = 12, HY = 13, CB = 14, + CL = 15, CP = 16, EX = 17, IN = 18, NS = 19, OP = 20, QU = 21, IS = 22, NU = 23, PO = 24, PR = 25, SY = 26, AK = 27, AL = 28, + AP = 29, AS = 30, EB = 31, EM = 32, H2 = 33, H3 = 34, HL = 35, ID = 36, JL = 37, JV = 38, JT = 39, RI = 40, VF = 41, VI = 42 +}; +enum { NONE = 0, ALLOWED = 1, MANDATORY = 2 }; +enum { ROUND_COST = 24, CALL_COST = 8 }; /* what a round and a call charge (constants: what is charged, not how much) */ +enum { START = 0, CLASS = 1, PI_FIELD = 2, PF_FIELD = 3, EAST_FIELD = 4, PICT_FIELD = 5 }; /* Range's fields */ + +typedef struct { double *v; size_t n, cap; } BufN; +typedef struct { int64_t *v; size_t n, cap; } BufI; +typedef struct { unsigned char *v; size_t n, cap; } BufB; +typedef struct { size_t stored, kept; } Held; +typedef PureList *ListP; /* a list's handle as one name, so a declaration of several declares each a handle */ +typedef BufN *BufNP; +typedef BufI *BufIP; +typedef BufB *BufBP; + +typedef struct { + bool fault; + int fault_line; /* where the last fault was (a macro's use) */ + uint64_t work, budget; + int64_t grown, spent, room; /* the memory the event's changes hold (module.c's grows) */ + PureUndo undo; /* empty: the event's lists keep none (undo_for), list_held still asks its size */ + const PureList *ranges; + size_t ranges_count; + const double *r_start, *r_class; + const unsigned char *r_pi, *r_pf, *r_east, *r_pict; + PureList *codes, *cls, *eff, *start, *nonspace, *ri, *at, *joined, *numeric, *out; /* the event's lists */ + PureList *copies[9]; + unsigned copied; + BufN b_codes, b_cls, b_eff, k_codes, k_cls, k_eff; /* the event's lists as buffers, and a Text's copies of them */ + BufI b_start, b_nonspace, b_ri, b_at, b_out, k_start, k_nonspace, k_ri, k_at; + BufB b_joined, b_numeric, k_joined, k_numeric; +} Context; +typedef Context CONTEXT; + +typedef struct { const PureList *list; const double *codes; size_t count; } Points; +typedef Points POINTS; + +/* core/module.c's, as they are. */ +static double floor_divide(double a, double b) { + double mod = fmod(a, b), quotient = (a - mod) / b; + if (mod != 0 && (b < 0) != (mod < 0)) quotient -= 1.0; + if (quotient == 0) return copysign(0.0, a / b); + double whole = floor(quotient); + return quotient - whole > 0.5 ? whole + 1.0 : whole; +} +static double pure_mod(double a, double b) { + double value = fmod(a, b); + if (value != 0 && (value < 0) != (b < 0)) value += b; + else if (value == 0) value = copysign(0.0, b); + return value; +} +static inline Held held(const Context *x, const PureList *l) { + return (Held){pure_list_size(l), pure_list_changes(l).size + pure_undo_size(&x->undo) + pure_list_extra(l)}; +} +static inline bool grows(Context *x, Held before, Held after) { + x->grown += (int64_t)after.stored - (int64_t)before.stored; + x->spent += (int64_t)(after.stored + after.kept) - (int64_t)(before.stored + before.kept); + return x->spent <= x->room; +} +static __attribute__((noinline)) bool grow(void **v, size_t *cap, size_t size) { + size_t more = *cap ? *cap * 2 : 64; + void *p = realloc(*v, more * size); + if (!p) return false; + *v = p, *cap = more; + return true; +} + +#define CHARGES_ON(n) do { if ((uint64_t)(n) > x->budget - x->work) FAIL; x->work += (uint64_t)(n); } while (0) + +/* ======== exact ======== */ +#define WAY exact +#define IDX double +#define ADD(a, b) ({ double v_ = (double)(a) + (double)(b); if (!isfinite(v_)) FAIL; v_; }) +#define SUB(a, b) ({ double v_ = (double)(a) - (double)(b); if (!isfinite(v_)) FAIL; v_; }) +#define GT(a, b) ((a) > (b)) +#define DIV2(a) ({ double q_ = floor_divide((a), 2); if (!isfinite(q_)) FAIL; q_; }) +#define MOD2(a) ({ double m_ = pure_mod((a), 2); if (!isfinite(m_)) FAIL; m_; }) +#define CHECK_AT(count, i) do { size_t c_ = (count); double i_ = (i); /* INDEX_AT, then ITEM_GET */ \ + if (i_ != floor(i_) || i_ < 0 || i_ >= (double)c_) FAIL; if ((size_t)i_ >= c_) FAIL; } while (0) +#define CHARGE(n) CHARGES_ON(n) +#define LIST_N ListP +#define LIST_I ListP +#define LIST_B ListP +#define L(name) (x->name) +#define NCOUNT(l) ((IDX)pure_list_count(l)) +#define GET_CELL(l, i) ({ const PureList *l_ = (l); IDX at_ = (i); CHECK_AT(pure_list_count(l_), at_); pure_list_get(l_, (size_t)at_, 0); }) +#define GETN(l, i) (GET_CELL(l, i).num) +#define GETI(l, i) ((IDX)GET_CELL(l, i).num) +#define GETB(l, i) (GET_CELL(l, i).num != 0) +#define APP_LIST(l, cell) do { PureList *l_ = (l); Held b_ = held(x, l_); PureCell c_ = cell; \ + if (pure_list_insert(l_, pure_list_count(l_), &c_, NULL) != PURE_OK) FAIL; if (!grows(x, b_, held(x, l_))) FAIL; } while (0) +#define APPN(l, v) APP_LIST(l, ((PureCell){.num = (v)})) +#define APPI(l, v) APP_LIST(l, ((PureCell){.num = (double)(v)})) +#define APPB(l, v) APP_LIST(l, ((PureCell){.num = (v) ? 1.0 : 0.0})) +#define R_COUNT ((IDX)pure_list_count(x->ranges)) +#define R_CELL(f, k) ({ IDX k_ = (k); CHECK_AT(pure_list_count(x->ranges), k_); pure_list_get(x->ranges, (size_t)k_, f); }) +#define R_START(k) (R_CELL(START, k).num) +#define R_CLASS(k) (R_CELL(CLASS, k).num) +#define R_PI(k) (R_CELL(PI_FIELD, k).num != 0) +#define R_PF(k) (R_CELL(PF_FIELD, k).num != 0) +#define R_EAST(k) (R_CELL(EAST_FIELD, k).num != 0) +#define R_PICT(k) (R_CELL(PICT_FIELD, k).num != 0) +#define P_COUNT(p) ((IDX)pure_list_count((p)->list)) +#define P_CODE(p, k) ({ IDX k_ = (k); CHECK_AT(pure_list_count((p)->list), k_); pure_list_get((p)->list, (size_t)k_, 0).num; }) +#define CAPTURE(dst, name) do { PureList *s_ = L(name); /* LIST_VALUE: nest's copy, an empty list none */ \ + if (pure_list_count(s_)) { PureList *c_ = pure_list_copied(s_); if (!c_) FAIL; \ + if (!grows(x, (Held){0, 0}, (Held){0, pure_list_size(c_)})) FAIL; x->copies[x->copied++] = c_; s_ = c_; } \ + dst = s_; } while (0) +#define OUT_APPEND(v) APP_LIST(x->out, ((PureCell){.i64 = (int64_t)(v)})) +#define OUT_EMIT(got) do { size_t n_ = pure_list_count(x->out); for (size_t k_ = 0; k_ < n_; ++k_) { \ + int64_t v_ = pure_list_get(x->out, k_, 0).i64; if ((uint64_t)v_ > 255) FAIL; (got)[k_] = (uint8_t)v_; } } while (0) +#define LINE_BEGIN do { PureList *all_[] = {x->codes, x->cls, x->eff, x->start, x->nonspace, x->ri, x->at, x->joined, \ + x->numeric, x->out}; for (unsigned l_ = 0; l_ < 10; ++l_) pure_list_clear(all_[l_]); x->copied = 0; } while (0) +#define LINE_END do { for (unsigned c_ = 0; c_ < x->copied; ++c_) pure_list_free(x->copies[c_]); x->copied = 0; } while (0) +#include "app-way.h" +#undef WAY +#undef IDX +#undef ADD +#undef SUB +#undef DIV2 +#undef MOD2 +#undef CHECK_AT +#undef GETI + +/* ======== integer: whole numbers as integers ======== */ +#define WAY integer +#define IDX int64_t +#define ADD(a, b) ((a) + (b)) +#define SUB(a, b) ((a) - (b)) +#define DIV2(a) ((a) / 2) /* whole and at or above 0 */ +#define MOD2(a) ((a) % 2) /* ri: whole and at or above 0 */ +#define CHECK_AT(count, i) do { if ((uint64_t)(i) >= (uint64_t)(count)) FAIL; } while (0) +#define GETI(l, i) ((IDX)GET_CELL(l, i).num) +#include "app-way.h" +#undef WAY + +/* ======== stored_flat: ranges' columns flat ======== */ +#define WAY stored_flat +#undef R_COUNT +#undef R_START +#undef R_CLASS +#undef R_PI +#undef R_PF +#undef R_EAST +#undef R_PICT +#define R_COUNT ((IDX)x->ranges_count) +#define R_AT(column, k) ({ IDX k_ = (k); CHECK_AT(x->ranges_count, k_); (column)[k_]; }) +#define R_START(k) R_AT(x->r_start, k) +#define R_CLASS(k) R_AT(x->r_class, k) +#define R_PI(k) (R_AT(x->r_pi, k) != 0) +#define R_PF(k) (R_AT(x->r_pf, k) != 0) +#define R_EAST(k) (R_AT(x->r_east, k) != 0) +#define R_PICT(k) (R_AT(x->r_pict, k) != 0) +#include "app-way.h" +#undef WAY + +/* ======== local_flat: the event's lists, the points and out as buffers ======== */ +#define WAY local_flat +#undef LIST_N +#undef LIST_I +#undef LIST_B +#undef L +#undef NCOUNT +#undef GETN +#undef GETI +#undef GETB +#undef APPN +#undef APPI +#undef APPB +#undef P_COUNT +#undef P_CODE +#undef CAPTURE +#undef OUT_APPEND +#undef OUT_EMIT +#undef LINE_BEGIN +#undef LINE_END +#define LIST_N BufNP +#define LIST_I BufIP +#define LIST_B BufBP +#define L(name) (&x->b_##name) +#define NCOUNT(l) ((IDX)(l)->n) +#define GET_BUF(l, i) ({ __typeof__(l) l_ = (l); IDX at_ = (i); CHECK_AT(l_->n, at_); l_->v[at_]; }) +#define GETN(l, i) GET_BUF(l, i) +#define GETI(l, i) GET_BUF(l, i) +#define GETB(l, i) (GET_BUF(l, i) != 0) +#define MEMORY(bytes) do { if ((x->spent += (bytes)) > x->room) FAIL; } while (0) +#define APP_BUF(l, value) do { __typeof__(l) l_ = (l); \ + if (l_->n == l_->cap && !grow((void **)&l_->v, &l_->cap, sizeof(*l_->v))) FAIL; \ + MEMORY(sizeof(*l_->v)); l_->v[l_->n++] = (value); } while (0) +#define APPN(l, v) APP_BUF(l, (v)) +#define APPI(l, v) APP_BUF(l, (v)) +#define APPB(l, v) APP_BUF(l, (unsigned char)((v) ? 1 : 0)) +#define P_COUNT(p) ((IDX)(p)->count) +#define P_CODE(p, k) ({ IDX k_ = (k); CHECK_AT((p)->count, k_); (p)->codes[k_]; }) +#define CAPTURE(dst, name) do { __typeof__(L(name)) s_ = L(name), c_ = &x->k_##name; /* LIST_VALUE: the items copied */ \ + while (c_->cap < s_->n) if (!grow((void **)&c_->v, &c_->cap, sizeof(*c_->v))) FAIL; \ + MEMORY(s_->n * sizeof(*s_->v)); memcpy(c_->v, s_->v, s_->n * sizeof(*s_->v)); c_->n = s_->n; dst = c_; } while (0) +#define OUT_APPEND(v) APP_BUF(&x->b_out, (int64_t)(v)) +#define OUT_EMIT(got) do { for (size_t k_ = 0; k_ < x->b_out.n; ++k_) { int64_t v_ = x->b_out.v[k_]; \ + if ((uint64_t)v_ > 255) FAIL; (got)[k_] = (uint8_t)v_; } } while (0) +#define LINE_BEGIN do { x->b_codes.n = x->b_cls.n = x->b_eff.n = x->b_start.n = x->b_nonspace.n = x->b_ri.n = x->b_at.n = \ + x->b_joined.n = x->b_numeric.n = x->b_out.n = 0; } while (0) +#define LINE_END do { } while (0) +#include "app-way.h" +#undef WAY + +/* ======== shared: a Text's lists the buffers ======== */ +#define WAY shared +#undef CAPTURE +#define CAPTURE(dst, name) ((dst) = L(name)) +#include "app-way.h" +#undef WAY + +/* ======== unbounded: shared, no bounds checks (the budget and memory charged) ======== */ +#define WAY unbounded +#undef CHECK_AT +#define CHECK_AT(count, i) do { (void)(count); } while (0) +#include "app-way.h" +#undef WAY + +/* ======== plain: no check, no charge ======== */ +#define WAY plain +#undef CHARGE +#undef MEMORY +#define CHARGE(n) do { (void)x; } while (0) +#define MEMORY(bytes) do { } while (0) +#undef OUT_EMIT +#define OUT_EMIT(got) do { for (size_t k_ = 0; k_ < x->b_out.n; ++k_) (got)[k_] = (uint8_t)x->b_out.v[k_]; } while (0) +#include "app-way.h" +#undef WAY + +static bool on_line_vega(Context *x, const Points *p, const uint32_t *codes, uint8_t *got) { + (void)x, (void)p; + return vega_line_breaks(codes, p->count, got); +} + +/* ---- the harness ---- */ +static unsigned char *whole(const char *path, size_t *size) { + FILE *f = fopen(path, "rb"); + if (!f) return NULL; + fseek(f, 0, SEEK_END); + *size = (size_t)ftell(f); + rewind(f); + unsigned char *bytes = malloc(*size ? *size : 1); + if (fread(bytes, 1, *size, f) != *size) { free(bytes); bytes = NULL; } + fclose(f); + return bytes; +} + +static int counter(uint64_t config) { + struct perf_event_attr a; + memset(&a, 0, sizeof(a)); + a.size = sizeof(a), a.type = PERF_TYPE_HARDWARE, a.config = config, a.disabled = 1, a.exclude_kernel = 1, a.exclude_hv = 1; + return (int)syscall(SYS_perf_event_open, &a, 0, -1, -1, 0); +} + +static uint64_t read_counter(int fd) { + uint64_t v = 0; + if (read(fd, &v, sizeof(v)) != sizeof(v)) return 0; + return v; +} + +typedef struct { Points points; const uint32_t *codes; const unsigned char *want; } Line; +enum { RUNGS = 8 }; +static const char *const names[RUNGS] = {"exact", "integer", "stored_flat", "local_flat", "shared", "unbounded", "plain", "vega"}; + +static bool run(int rung, Context *x, const Line *l, uint8_t *got) { + switch (rung) { + case 0: return on_line_exact(x, &l->points, got); + case 1: return on_line_integer(x, &l->points, got); + case 2: return on_line_stored_flat(x, &l->points, got); + case 3: return on_line_local_flat(x, &l->points, got); + case 4: return on_line_shared(x, &l->points, got); + case 5: return on_line_unbounded(x, &l->points, got); + case 6: return on_line_plain(x, &l->points, got); + default: return on_line_vega(x, &l->points, l->codes, got); + } +} + +int main(int argc, char **argv) { + if (argc != 5) { fprintf(stderr, "usage: %s linebreak.pmod RANGES LINES ROUNDS\n", argv[0]); return 2; } + size_t ranges_size, lines_size; + unsigned char *ranges = whole(argv[2], &ranges_size), *bytes = whole(argv[3], &lines_size); + int rounds = atoi(argv[4]); + if (!ranges || !bytes) return 1; + PureModule module = {0}; + char error[160]; + if (pure_module_read(argv[1], &module, error, sizeof(error)) != PURE_OK) { fprintf(stderr, "%s\n", error); return 1; } + PureApp app; + if (pure_app_start(&app, &module, (PureData){0}) != PURE_OK) return 1; + int load = pure_module_input(&module, "load"), state = pure_module_state(&module, "ranges"); + if (load < 0 || state < 0 || pure_app_message(&app, (uint32_t)load, (PureSpan){ranges, ranges_size}) != PURE_OK) return 1; + static Context x; + x.budget = UINT64_MAX, x.room = INT64_MAX; + x.ranges = app.lists[state], x.ranges_count = pure_list_count(x.ranges); + double *r_start = malloc(x.ranges_count * sizeof(double)), *r_class = malloc(x.ranges_count * sizeof(double)); + unsigned char *flags = malloc(4 * x.ranges_count); + for (size_t i = 0; i < x.ranges_count; ++i) { + r_start[i] = pure_list_get(x.ranges, i, START).num, r_class[i] = pure_list_get(x.ranges, i, CLASS).num; + for (unsigned f = 0; f < 4; ++f) flags[f * x.ranges_count + i] = pure_list_get(x.ranges, i, PI_FIELD + f).num != 0; + } + x.r_start = r_start, x.r_class = r_class; + x.r_pi = flags, x.r_pf = flags + x.ranges_count, x.r_east = flags + 2 * x.ranges_count, x.r_pict = flags + 3 * x.ranges_count; + const uint8_t number[] = {PURE_CELL_NUMBER}, boolean[] = {PURE_CELL_BOOL}, integer[] = {PURE_CELL_INTEGER}; + PureList **numbers[] = {&x.codes, &x.cls, &x.eff, &x.start, &x.nonspace, &x.ri, &x.at}; + for (unsigned k = 0; k < 7; ++k) *numbers[k] = pure_list_new(1, number); + x.joined = pure_list_new(1, boolean), x.numeric = pure_list_new(1, boolean), x.out = pure_list_new(1, integer); + PureList *events[] = {x.codes, x.cls, x.eff, x.start, x.nonspace, x.ri, x.at, x.joined, x.numeric, x.out}; + for (unsigned k = 0; k < 10; ++k) /* an event's list in FLAT arrays, as the runtime starts one (021) */ + if (!pure_list_arrays(events[k])) return 1; + /* The lines: each its points as the message's list (the event's form) and as the message's numbers. */ + static Line lines[1 << 16]; + size_t count = 0, points = 0; + for (size_t at = 0; at + 4 <= lines_size && count < sizeof(lines) / sizeof(*lines); ++count) { + Line *l = &lines[count]; + uint32_t n; + memcpy(&n, bytes + at, 4); + l->codes = (const uint32_t *)(bytes + at + 4); + l->want = bytes + at + 4 + 4 * (size_t)n; + at += 4 + 4 * (size_t)n + n + 1; + double *codes = malloc(((size_t)n + 1) * sizeof(double)); + PureList *list = pure_list_new(1, number); + if (!pure_list_arrays(list)) return 1; + for (uint32_t i = 0; i < n; ++i) { + codes[i] = l->codes[i]; + PureCell cell = {.num = codes[i]}; + if (pure_list_insert(list, i, &cell, NULL) != PURE_OK) return 1; + } + l->points = (Points){list, codes, n}; + points += n; + } + /* Checked first: each rung's boundaries are the test's, and exactly exact's. */ + static uint8_t got[4096], first[4096]; + size_t wrong[RUNGS] = {0}; + for (size_t k = 0; k < count; ++k) { + const Line *l = &lines[k]; + if (l->points.count + 1 > sizeof(got)) return 1; + for (int r = 0; r < RUNGS; ++r) { + x.fault = false; + bool same = run(r, &x, l, got) && !x.fault; + for (size_t i = 0; same && i <= l->points.count; ++i) same = (got[i] != NONE) == l->want[i]; + if (r == 0) memcpy(first, got, l->points.count + 1); + else if (r < RUNGS - 1) same = same && !memcmp(first, got, l->points.count + 1); + if (!same && getenv("APP_DEBUG") && !wrong[r]) { + fprintf(stderr, "%s line %zu fault %d at %d:", names[r], k, x.fault, x.fault_line); + for (size_t i = 0; i <= l->points.count; ++i) fprintf(stderr, " %u/%u", got[i], l->want[i]); + fprintf(stderr, "\n"); + } + wrong[r] += !same; + } + } + bool refused = false; + for (int r = 0; r < RUNGS; ++r) + if (wrong[r]) fprintf(stderr, "%s: %zu of %zu lines wrong\n", names[r], wrong[r], count), refused = true; + if (refused) return 1; + int ins = counter(PERF_COUNT_HW_INSTRUCTIONS), cyc = counter(PERF_COUNT_HW_CPU_CYCLES); + if (ins < 0 || cyc < 0) { perror("perf_event_open"); return 1; } + uint64_t total_ins[RUNGS] = {0}, total_cyc[RUNGS] = {0}; + for (int round = 0; round < rounds; ++round) + for (int r = 0; r < RUNGS; ++r) { + x.work = 0, x.spent = 0, x.grown = 0; + ioctl(ins, PERF_EVENT_IOC_RESET, 0), ioctl(cyc, PERF_EVENT_IOC_RESET, 0); + ioctl(ins, PERF_EVENT_IOC_ENABLE, 0), ioctl(cyc, PERF_EVENT_IOC_ENABLE, 0); + for (size_t k = 0; k < count; ++k) run(r, &x, &lines[k], got); + ioctl(ins, PERF_EVENT_IOC_DISABLE, 0), ioctl(cyc, PERF_EVENT_IOC_DISABLE, 0); + total_ins[r] += read_counter(ins), total_cyc[r] += read_counter(cyc); + x.spent = 0; + } + double n = (double)points * rounds; + for (int r = 0; r < RUNGS; ++r) + printf("{\"rung\":\"%s\",\"lines\":%zu,\"code_points\":%zu,\"rounds\":%d,\"instructions_per_point\":%.1f," + "\"cycles_per_point\":%.1f,\"answers\":\"the test's, and exact's\"}\n", + names[r], count, points, rounds, total_ins[r] / n, total_cyc[r] / n); + pure_app_stop(&app); + return 0; +} -- cgit v1.2.3