diff options
Diffstat (limited to 'research/experiments/045-proof-compiler')
4 files changed, 703 insertions, 0 deletions
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 <math.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <linux/perf_event.h> +#include <sys/ioctl.h> +#include <sys/syscall.h> +#include <unistd.h> + +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; +} |