From 5db97c60b953205e68d273b9b56424d346fa750d Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 19 Oct 2026 11:51:58 +0100 Subject: 045: 029's principle 1 broken on UAX #14 before any emitter, the tools and the numbers: (a) the executor runs 549.9 instructions a code point (the budget's 1,774 counts blocks as written), moves 205.5, constants 76.7 and reads of the same list, version, field and place in an event 16.4, so merging leaves 251.3: 2.19x, the bar 4x (ops-count.patch); (b) the executor's own steps stitched on constant instructions, a function a basic block (stitch.c, native-hook.patch), answers checked: 40,703 to 28,601 machine instructions a point, 15,566 to 11,850 cycles: 1.31x, the bar 3x (cost.c); Vega's C 220 and 82; where it goes: dispatch 22 machine instructions an instruction of 74, an empty handler 1,583 a point, the lists built 22,651 more, the Text record 2,951, decide 12,988 (events.c, variants); a stored list's read 331, a block fn's call 1,375, an arithmetic step 248 in the executor and 35 in batches (unit.c, units) --- .../045-proof-compiler/2026-10-19-break.jsonl | 10 ++ research/experiments/045-proof-compiler/cost.c | 132 +++++++++++++++++++++ research/experiments/045-proof-compiler/events.c | 103 ++++++++++++++++ .../045-proof-compiler/native-hook.patch | 25 ++++ .../experiments/045-proof-compiler/ops-count.patch | 62 ++++++++++ research/experiments/045-proof-compiler/stitch.c | 108 +++++++++++++++++ research/experiments/045-proof-compiler/unit.c | 47 ++++++++ .../045-proof-compiler/units/append.aup | 7 ++ .../experiments/045-proof-compiler/units/arith.aup | 7 ++ .../experiments/045-proof-compiler/units/call.aup | 11 ++ .../experiments/045-proof-compiler/units/mod.aup | 7 ++ .../045-proof-compiler/units/read-direct.aup | 14 +++ .../experiments/045-proof-compiler/units/read.aup | 14 +++ .../045-proof-compiler/variants/v0-empty.patch | 34 ++++++ .../045-proof-compiler/variants/v1-lists.patch | 14 +++ .../045-proof-compiler/variants/v2-text.patch | 12 ++ 16 files changed, 607 insertions(+) create mode 100644 research/experiments/045-proof-compiler/2026-10-19-break.jsonl create mode 100644 research/experiments/045-proof-compiler/cost.c create mode 100644 research/experiments/045-proof-compiler/events.c create mode 100644 research/experiments/045-proof-compiler/native-hook.patch create mode 100644 research/experiments/045-proof-compiler/ops-count.patch create mode 100644 research/experiments/045-proof-compiler/stitch.c create mode 100644 research/experiments/045-proof-compiler/unit.c create mode 100644 research/experiments/045-proof-compiler/units/append.aup create mode 100644 research/experiments/045-proof-compiler/units/arith.aup create mode 100644 research/experiments/045-proof-compiler/units/call.aup create mode 100644 research/experiments/045-proof-compiler/units/mod.aup create mode 100644 research/experiments/045-proof-compiler/units/read-direct.aup create mode 100644 research/experiments/045-proof-compiler/units/read.aup create mode 100644 research/experiments/045-proof-compiler/variants/v0-empty.patch create mode 100644 research/experiments/045-proof-compiler/variants/v1-lists.patch create mode 100644 research/experiments/045-proof-compiler/variants/v2-text.patch (limited to 'research/experiments') diff --git a/research/experiments/045-proof-compiler/2026-10-19-break.jsonl b/research/experiments/045-proof-compiler/2026-10-19-break.jsonl new file mode 100644 index 0000000..07aef0d --- /dev/null +++ b/research/experiments/045-proof-compiler/2026-10-19-break.jsonl @@ -0,0 +1,10 @@ +{"what": "(a) instructions the executor runs, UAX #14 (ops-count.patch: by opcode, and reads of the same list, version, field and place within an event)", "code_points": 61285, "executed_per_point": 549.9, "moves_per_point": 205.5, "constants_per_point": 76.7, "same_reads_per_point": 16.4, "left_per_point": 251.3, "factor": 2.19, "bar": 4, "passed": false, "note": "the budget counts blocks as written: 1,774 a point; executed 549.9"} +{"what": "(b) the executor stitched (stitch.c, native-hook.patch: step() on each constant instruction, a function a basic block), cost.c (answers checked first)", "interpreted": {"instructions_per_point": 40702.7, "cycles_per_point": 15565.8}, "stitched": {"instructions_per_point": 28601.5, "cycles_per_point": 11849.9}, "instruction_factor": 1.42, "cycle_factor": 1.31, "bar": 3, "passed": false} +{"what": "Vega C (text/linebreak.c) on the same lines", "instructions_per_point": 220.2, "cycles_per_point": 82.4} +{"what": "machine instructions an executed instruction", "interpreted": 74.0, "stitched": 52.0, "dispatch_and_decode": 22.0} +{"what": "variants of the app (events.c, executor): machine instructions a code point", "empty_handler": 1583.2, "lists_built": 24233.7, "and_text_record": 27184.8, "whole": 40172.9} +{"what": "units (unit.c, units/*.aup): machine instructions an operation, PURE_JIT=0", "arith_loop_batches": 34.7, "arith_loop_executor": 248.0, "append_let_list_batches": 35.7, "stored_list_read_with_mod": 435.8, "stored_list_read": 330.8, "mod": 75.4, "block_fn_call": 1375.1} +{"mode":"interp","lines":18672,"code_points":61285,"rounds":3,"jit":"0","c_instructions_per_point":220.2,"c_cycles_per_point":81.9,"pure_instructions_per_point":40702.7,"pure_cycles_per_point":15591.7} +{"mode":"native","lines":18672,"code_points":61285,"rounds":3,"jit":"0","c_instructions_per_point":220.2,"c_cycles_per_point":82.7,"pure_instructions_per_point":28600.9,"pure_cycles_per_point":11868.1} +{"mode":"interp","lines":18672,"code_points":61285,"rounds":3,"jit":"0","c_instructions_per_point":220.2,"c_cycles_per_point":82.2,"pure_instructions_per_point":40702.7,"pure_cycles_per_point":15539.8} +{"mode":"native","lines":18672,"code_points":61285,"rounds":3,"jit":"0","c_instructions_per_point":220.2,"c_cycles_per_point":83.5,"pure_instructions_per_point":28602.1,"pure_cycles_per_point":11831.7} diff --git a/research/experiments/045-proof-compiler/cost.c b/research/experiments/045-proof-compiler/cost.c new file mode 100644 index 0000000..2b300a4 --- /dev/null +++ b/research/experiments/045-proof-compiler/cost.c @@ -0,0 +1,132 @@ +/* Research 045 (029's principle 1, its breaking experiment): what UAX #14 costs in machine instructions and cycles a + * code point, Vega's C (text/linebreak.c) and Pure's executor (aup's examples/linebreak.aup), on the lines + * 044's linebreak_check.py writes; user-mode counters (perf_event_open) around each, ROUNDS passes after one checked. + * + * cc -O2 -std=c17 -I../../../core -I../../../../vega/text cost.c ../../../../vega/text/linebreak.c \ + * ../../../../vega/text/unicode-data.c ../../../build/libpure.a -lm -pthread -o cost + * ./cost linebreak.pmod RANGES LINES ROUNDS + * + * One JSON line. */ +#define _GNU_SOURCE +#include "module.h" +#include "text.h" +#include +#include +#include +#include +#include +#include +#include +#include + +static double now_ns(void) { + struct timespec t; + clock_gettime(CLOCK_MONOTONIC, &t); + return (double)t.tv_sec * 1e9 + (double)t.tv_nsec; +} + +static int by_value(const void *a, const void *b) { + double x = *(const double *)a, y = *(const double *)b; + return (x > y) - (x < y); +} + +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; +} + +typedef struct { uint32_t count; const uint32_t *codes; const unsigned char *want; unsigned char *payload; } Line; + +/* A line's boundaries from Pure: the bytes state "breaks", compared as breaks or not with want. */ +typedef struct { const unsigned char *want; size_t at; bool same; } Compare; +static bool compare(void *context, PureSpan span) { + Compare *c = context; + for (size_t i = 0; i < span.size; ++i, ++c->at) c->same = c->same && (span.data[i] != 0) == c->want[c->at]; + return true; +} + + +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; +} + +int main(int argc, char **argv) { + if (argc != 5) { fprintf(stderr, "usage: %s MODULE 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; + 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]; + memcpy(&l->count, bytes + at, 4); + l->codes = (const uint32_t *)(bytes + at + 4); + l->want = bytes + at + 4 + 4 * (size_t)l->count; + at += 4 + 4 * (size_t)l->count + l->count + 1; + l->payload = malloc(8 * (size_t)l->count + 1); + for (uint32_t i = 0; i < l->count; ++i) { + double c = l->codes[i]; + memcpy(l->payload + 8 * i, &c, 8); + } + points += l->count; + } + 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"), line = pure_module_input(&module, "line"); + if (pure_app_message(&app, (uint32_t)load, (PureSpan){ranges, ranges_size}) != PURE_OK) return 1; + static uint8_t got[4096]; + size_t right = 0; + for (size_t k = 0; k < count; ++k) { /* checked first: both give the test's boundaries */ + bool same = pure_app_message(&app, (uint32_t)line, (PureSpan){lines[k].payload, 8 * (size_t)lines[k].count}) == PURE_OK && + lines[k].count < sizeof(got) && vega_line_breaks(lines[k].codes, lines[k].count, got); + for (uint32_t i = 0; same && i <= lines[k].count; ++i) same = (got[i] != VEGA_BREAK_NONE) == lines[k].want[i]; + right += same; + } + if (right != count) { fprintf(stderr, "right %zu of %zu\n", right, count); 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; } + volatile unsigned sink = 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 (int r = 0; r < rounds; ++r) + for (size_t k = 0; k < count; ++k) { + vega_line_breaks(lines[k].codes, lines[k].count, got); + sink += got[0]; + } + ioctl(ins, PERF_EVENT_IOC_DISABLE, 0), ioctl(cyc, PERF_EVENT_IOC_DISABLE, 0); + uint64_t c_ins = read_counter(ins), c_cyc = read_counter(cyc); + 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 (int r = 0; r < rounds; ++r) + for (size_t k = 0; k < count; ++k) + if (pure_app_message(&app, (uint32_t)line, (PureSpan){lines[k].payload, 8 * (size_t)lines[k].count}) != PURE_OK) return 1; + ioctl(ins, PERF_EVENT_IOC_DISABLE, 0), ioctl(cyc, PERF_EVENT_IOC_DISABLE, 0); + uint64_t p_ins = read_counter(ins), p_cyc = read_counter(cyc); + double n = (double)points * rounds; + const char *jit = getenv("PURE_JIT"); + printf("{\"lines\":%zu,\"code_points\":%zu,\"rounds\":%d,\"jit\":\"%s\",\"c_instructions_per_point\":%.1f,\"c_cycles_per_point\":%.1f," + "\"pure_instructions_per_point\":%.1f,\"pure_cycles_per_point\":%.1f}\n", + count, points, rounds, jit ? jit : "", c_ins / n, c_cyc / n, p_ins / n, p_cyc / n); + pure_app_stop(&app); + return 0; +} diff --git a/research/experiments/045-proof-compiler/events.c b/research/experiments/045-proof-compiler/events.c new file mode 100644 index 0000000..58dd0f1 --- /dev/null +++ b/research/experiments/045-proof-compiler/events.c @@ -0,0 +1,103 @@ +/* Research 045: where UAX #14's machine instructions go in Pure's executor. A variant of aup's examples/linebreak.aup + * (the patches in variants: v0 an empty handler, v1 the lists built, v2 and the Text record, the app itself all of it) on the + * lines 044's linebreak_check.py writes; machine instructions and cycles a code point (perf_event_open, user mode), + * Vega's C beside it. No answer checked (the variants answer nothing); cost.c checks the app itself. + * + * cc -O2 -std=c17 -I../../../core -I../../../../vega/text events.c ../../../../vega/text/linebreak.c \ + * ../../../../vega/text/unicode-data.c ../../../build/libpure.a -lm -pthread -o events + * ./events VARIANT.pmod RANGES LINES ROUNDS one JSON line */ +#define _GNU_SOURCE +#include "module.h" +#include "text.h" +#include +#include +#include +#include +#include +#include +#include + +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; +} + +typedef struct { uint32_t count; const uint32_t *codes; const unsigned char *want; unsigned char *payload; } Line; + +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; +} + +int main(int argc, char **argv) { + if (argc != 5) { fprintf(stderr, "usage: %s MODULE 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; + 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]; + memcpy(&l->count, bytes + at, 4); + l->codes = (const uint32_t *)(bytes + at + 4); + l->want = bytes + at + 4 + 4 * (size_t)l->count; + at += 4 + 4 * (size_t)l->count + l->count + 1; + l->payload = malloc(8 * (size_t)l->count + 1); + for (uint32_t i = 0; i < l->count; ++i) { + double c = l->codes[i]; + memcpy(l->payload + 8 * i, &c, 8); + } + points += l->count; + } + 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"), line = pure_module_input(&module, "line"); + if (pure_app_message(&app, (uint32_t)load, (PureSpan){ranges, ranges_size}) != PURE_OK) return 1; + static uint8_t got[4096]; + 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; } + volatile unsigned sink = 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 (int r = 0; r < rounds; ++r) + for (size_t k = 0; k < count; ++k) { + vega_line_breaks(lines[k].codes, lines[k].count, got); + sink += got[0]; + } + (void)got; + ioctl(ins, PERF_EVENT_IOC_DISABLE, 0), ioctl(cyc, PERF_EVENT_IOC_DISABLE, 0); + uint64_t c_ins = read_counter(ins), c_cyc = read_counter(cyc); + 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 (int r = 0; r < rounds; ++r) + for (size_t k = 0; k < count; ++k) + if (pure_app_message(&app, (uint32_t)line, (PureSpan){lines[k].payload, 8 * (size_t)lines[k].count}) != PURE_OK) return 1; + ioctl(ins, PERF_EVENT_IOC_DISABLE, 0), ioctl(cyc, PERF_EVENT_IOC_DISABLE, 0); + uint64_t p_ins = read_counter(ins), p_cyc = read_counter(cyc); + double n = (double)points * rounds; + const char *jit = getenv("PURE_JIT"); + printf("{\"lines\":%zu,\"code_points\":%zu,\"rounds\":%d,\"jit\":\"%s\",\"c_instructions_per_point\":%.1f,\"c_cycles_per_point\":%.1f," + "\"pure_instructions_per_point\":%.1f,\"pure_cycles_per_point\":%.1f}\n", + count, points, rounds, jit ? jit : "", c_ins / n, c_cyc / n, p_ins / n, p_cyc / n); + pure_app_stop(&app); + return 0; +} diff --git a/research/experiments/045-proof-compiler/native-hook.patch b/research/experiments/045-proof-compiler/native-hook.patch new file mode 100644 index 0000000..a791e86 --- /dev/null +++ b/research/experiments/045-proof-compiler/native-hook.patch @@ -0,0 +1,25 @@ +diff --git a/core/module.c b/core/module.c +index 4b20e25..fd953e8 100644 +--- a/core/module.c ++++ b/core/module.c +@@ -4967,10 +4967,20 @@ static __attribute__((noinline, aligned(64))) PureResult run_batches(const PureM + return finish(&frame, how, result); + } + ++#ifdef PURE_NATIVE_INC /* research 045: the executor's steps stitched for one module */ ++#include PURE_NATIVE_INC ++#endif ++ + /* At a cache line's start: the steps' branches land where they would (research 126: else 10% more cycles, as many instructions). */ + static __attribute__((aligned(64))) PureResult run(const PureModule *m, PureValue *values, PureBlock block, Event *ev, Slot *result) { + PureCompiled code = m->jit ? pure_jit_code(m->jit, block) : NULL; + if (code) return run_compiled(code, m, values, block, ev, result); ++#ifdef PURE_NATIVE_INC ++ static const PureModule *native_seen; ++ static bool native_ok; ++ if (m != native_seen) native_seen = m, native_ok = native_matches(m) && getenv("PURE_NATIVE"); ++ if (native_ok && m->runner == 2) return run_native(m, values, block, ev, result); ++#endif + if (m->runner) return m->runner == 2 ? run_calls(m, values, block, ev, result) : run_batches(m, values, block, ev, result); + Slot stack[PURE_MODULE_STACK]; + Loop loops[PURE_MODULE_NESTING]; diff --git a/research/experiments/045-proof-compiler/ops-count.patch b/research/experiments/045-proof-compiler/ops-count.patch new file mode 100644 index 0000000..616ad09 --- /dev/null +++ b/research/experiments/045-proof-compiler/ops-count.patch @@ -0,0 +1,62 @@ +diff --git a/core/module.c b/core/module.c +index 4b20e25..2205f77 100644 +--- a/core/module.c ++++ b/core/module.c +@@ -3902,7 +3902,57 @@ static __attribute__((noinline, cold)) int open_batches(Frame *frame, uint32_t p + #define STOPPED(why) do { frame->status = (why); return STEP_RETURN; } while (0) + + /* The instruction op at pc; *next the one to run after it. */ ++/* Research only (029's breaking experiment): the instructions the executor runs, by opcode. */ ++#include ++static uint64_t research_ops[256], research_same[256]; ++static const char *const research_names[] = {"CONST", "LOAD", "ADD", "SUB", "MUL", "DIV", "NEG", "LT", "LE", "GT", "GE", "EQ", "NE", "AND", "OR", "NOT", "MIN", "MAX", "CLAMP", "STORE", "JZ", "JMP", "FIELD", "LEN", "REPLY", "REQUIRE", "TEXT_CONST", "TEXT_LOAD", "NUM_TEXT", "CONCAT", "CHARS", "LINES", "TEXT_BYTES", "ANCHOR_LOAD", "ANCHOR_START", "ANCHOR_END", "ANCHOR_MOVE", "ANCHOR_STORE", "TEXT_INSERT", "TEXT_REMOVE", "TEXT_LINE", "TEXT_SET", "TEXT_FROM", "BYTES_FROM", "ANCHOR_COUNT", "LIST_COUNT", "LIST_APPEND", "LIST_INSERT", "LIST_REMOVE", "ITEM_GET", "ITEM_SET", "ROW", "PICK", "SLIDE", "FOLD", "TEXT_COMPARE", "LIST_FIND", "LIST_HAS", "NOW", "FLOOR", "MOD", "SEND", "OUTER_ROW", "EACH", "LOCAL_LOAD", "LOCAL_STORE", "I64_ADD", "I64_SUB", "I64_MUL", "I64_DIV", "I64_MOD", "I64_NEG", "I64_COMPARE", "I64_MIN", "I64_MAX", "I64_FROM", "NUM_FROM", "LOOP", "BREAK", "I64_BITS", "BYTE_AT", "BYTES_OF", "ANCHOR_AT", "BYTES_SLICE", "BYTE", "BYTES_LOAD", "BYTES_STORE", "LIST_VALUE", "LIST_BIND", "APPEND_IN", "NUM_PARSE", "CALL", "RETURN", "CHAR_AT", "CHAR", "FLOORDIV", "CUR_LOAD", "CUR_START", "CUR_END", "CUR_MOVE", "CUR_STORE", "CUR_COUNT", "CUR_AT", "INDEX_LOAD", "INDEX_STORE", "INDEX_MOVE", "INDEX_FIRST", "INDEX_LAST", "INDEX_NUM", "INDEX_AT", "KEPT_GET", "KEPT_SET", "KEPT_APPEND", "KEPT_INSERT", "KEPT_APPEND_IN"}; ++static void research_reads(const Frame *frame, const PureOp *op); ++static void research_dump(void) { ++ const char *out = getenv("PURE_OPS_OUT"); ++ FILE *f = out ? fopen(out, "w") : stderr; ++ for (unsigned i = 0; i < 256; ++i) ++ if (research_ops[i]) fprintf(f, "%s %llu %llu\n", i < sizeof(research_names) / sizeof(*research_names) ? research_names[i] : "?", ++ (unsigned long long)research_ops[i], (unsigned long long)research_same[i]); ++ if (out) fclose(f); ++} ++/* Reads the proof makes the same: the same list (its address and version: a change makes another), field and place ++ * read again within an event (the event's work starts again at 0). Counted by opcode. */ ++static uint64_t research_last_work, research_keys[1 << 16]; ++static uint32_t research_key_count; ++static void research_reads(const Frame *frame, const PureOp *op) { ++ if (frame->app->work < research_last_work) memset(research_keys, 0, sizeof(research_keys)), research_key_count = 0; ++ research_last_work = frame->app->work; ++ uint64_t list = 0, version = 0, place = 0, id = 0; ++ switch (op->op) { ++ case PURE_OP_ITEM_GET: case PURE_OP_INDEX_AT: case PURE_OP_LIST_COUNT: { ++ uint32_t state = op->op == PURE_OP_ITEM_GET ? (op->arg & 0xFFFF) : op->arg; ++ if (state >= frame->app->laid && state < PURE_LIST_HEARD) return; ++ const PureList *l = frame->app->lists[state]; ++ if (!l) return; ++ pure_list_stamp(l, &id, &version); ++ list = (uint64_t)(uintptr_t)l; ++ if (op->op != PURE_OP_LIST_COUNT) memcpy(&place, &frame->stack[frame->sp - 1], sizeof(place)); ++ break; ++ } ++ case PURE_OP_LIST_BIND: { ++ list = 0x51ull << 56 | op->arg; ++ memcpy(&place, &frame->stack[frame->sp - 1], sizeof(place)); ++ version = 0; ++ break; ++ } ++ default: return; ++ } ++ uint64_t key = ((list * 0x9E3779B97F4A7C15ull) ^ (version * 0xC2B2AE3D27D4EB4Full) ^ (place * 0x165667B19E3779F9ull) ^ ++ ((uint64_t)op->op << 32 | op->arg)) | 1; ++ for (uint32_t i = (uint32_t)(key >> 40) & 0xFFFF, k = 0; k < 1 << 16; ++k, i = (i + 1) & 0xFFFF) { ++ if (research_keys[i] == key) { ++research_same[op->op]; return; } ++ if (!research_keys[i]) { if (research_key_count < (1 << 15)) research_keys[i] = key, ++research_key_count; return; } ++ } ++} ++__attribute__((constructor)) static void research_start(void) { atexit(research_dump); } + static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp *op, uint32_t pc, uint32_t *next, bool batches) { ++ ++research_ops[op->op]; ++ research_reads(frame, op); + const PureModule *m = frame->m; + PureValue *values = frame->values; + Event *ev = frame->ev; diff --git a/research/experiments/045-proof-compiler/stitch.c b/research/experiments/045-proof-compiler/stitch.c new file mode 100644 index 0000000..8d690e0 --- /dev/null +++ b/research/experiments/045-proof-compiler/stitch.c @@ -0,0 +1,108 @@ +/* Research 045 (029's principle 1, experiment (b)): the executor's own instruction bodies stitched without dispatch. + * Reads a module as Pure loads it and writes C for Pure's core to include (native.inc): the module's code as a + * constant array; a function for each basic block calling the executor's step() on each of its constant instructions, + * so the C compiler specializes each body to its instruction alone (no fetch, no decode, no dispatch within a block); + * and run_native, run_calls's loop dispatching once a block. Calls, returns and the ends of loops go through + * run_calls's own code. The semantics are the executor's source, unchanged. + * + * cc -O2 -std=c17 -I../../../core stitch.c ../../../build/libpure.a -lm -pthread -o stitch + * ./stitch MODULE > native.inc (then core/module.c built with -DPURE_NATIVE_INC='"native.inc"') */ +#include "module.h" +#include +#include + +int main(int argc, char **argv) { + if (argc != 2) { fprintf(stderr, "usage: %s MODULE\n", argv[0]); return 2; } + PureModule m = {0}; + char error[160]; + if (pure_module_read(argv[1], &m, error, sizeof(error)) != PURE_OK) { fprintf(stderr, "%s\n", error); return 1; } + uint32_t n = m.code_count; + printf("/* Stitched from %s: %u instructions (research 045). */\n", argv[1], n); + printf("enum { NATIVE_COUNT = %u, STEP_ENDED = 9 }; /* STEP_ENDED: a block reached its end (frame.end) */\n", n); + printf("static const PureOp native_code[NATIVE_COUNT] = {\n"); + for (uint32_t pc = 0; pc < n; ++pc) { + const PureOp *o = &m.code[pc]; + printf(" {.integer = INT64_C(%" PRId64 "), .arg = %" PRIu32 "u, .op = %u, .plan = %u, .shape = %u, .range = %u},\n", + o->integer, o->arg, o->op, o->plan, o->shape, o->range); + } + printf("};\n\n"); + printf("static bool native_matches(const PureModule *m) {\n" + " if (m->code_count != NATIVE_COUNT) return false;\n" + " for (uint32_t pc = 0; pc < NATIVE_COUNT; ++pc)\n" + " if (m->code[pc].op != native_code[pc].op || m->code[pc].arg != native_code[pc].arg ||\n" + " m->code[pc].integer != native_code[pc].integer || m->code[pc].plan != native_code[pc].plan)\n" + " return false;\n" + " return true;\n" + "}\n\n"); + /* Basic blocks: a leader at each block's and function's start, each jump's target, past each instruction that may + * go elsewhere (a branch, a loop's, a call, a return), and every 16 instructions. Each is a function of its own (one + * enormous function took the compiler past 3 GiB): stitched within, dispatched once a block. */ + static bool leader[1 << 16]; + for (uint32_t h = 0; h < m.handlers; ++h) leader[m.handler[h].code.start] = true; + for (uint32_t f = 0; f < m.functions; ++f) leader[m.function[f].code.start] = true; + for (uint32_t pc = 0; pc < n; ++pc) { + uint8_t op = m.code[pc].op; + bool control = op == PURE_OP_JZ || op == PURE_OP_JMP || op == PURE_OP_LOOP || op == PURE_OP_EACH || op == PURE_OP_BREAK || + op == PURE_OP_CALL || op == PURE_OP_RETURN || op == PURE_OP_FOLD; + if ((op == PURE_OP_JZ || op == PURE_OP_JMP) && m.code[pc].arg < n) leader[m.code[pc].arg] = true; + if (control && pc + 1 < n) leader[pc + 1] = true; + } + leader[0] = true; + for (uint32_t pc = 0, run = 0; pc < n; ++pc, ++run) { + if (leader[pc]) run = 0; + else if (run == 16) leader[pc] = true, run = 0; + } + for (uint32_t pc = 0; pc < n;) { + uint32_t end = pc + 1; + while (end < n && !leader[end]) ++end; + printf("static __attribute__((noinline)) int native_%u(Frame *frame, uint32_t *pc) {\n int how;\n", pc); + for (uint32_t k = pc; k < end; ++k) { + printf(" if (%uu >= frame->end) { *pc = %uu; return STEP_ENDED; }\n", k, k); + printf(" if ((how = step(frame, &native_code[%u], %uu, pc, true)) != STEP_NEXT || *pc != %uu) return how;\n", k, k, k + 1); + } + printf(" return STEP_NEXT;\n}\n"); + pc = end; + } + printf("typedef int (*NativeBlock)(Frame *, uint32_t *);\n"); + printf("static const NativeBlock native_blocks[NATIVE_COUNT] = {\n"); + for (uint32_t pc = 0; pc < n; ++pc) if (leader[pc]) printf(" [%u] = native_%u,\n", pc, pc); + printf("};\n\n"); + printf("static __attribute__((noinline)) PureResult run_native(const PureModule *m, PureValue *values, PureBlock block, Event *ev,\n" + " Slot *result) {\n" + " Slot stack[PURE_MODULE_STACK];\n" + " Loop few[PURE_MODULE_NESTING], *loops = m->nesting > PURE_MODULE_NESTING ? deep_loops(ev->app, m->nesting) : few;\n" + " if (!loops) return PURE_ALLOCATION;\n" + " Frame frame;\n" + " open_frame(&frame, m, values, block, ev, stack, loops);\n" + " Call *top = NULL;\n" + " int how = STEP_NEXT;\n" + " for (uint32_t pc = block.start;;) {\n" + " if (pc >= frame.end) {\n" + " if (!frame.depth || (how = iterate(&frame, &pc)) != STEP_NEXT) break;\n" + " continue;\n" + " }\n" + " NativeBlock b = pc < NATIVE_COUNT ? native_blocks[pc] : NULL;\n" + " how = b ? b(&frame, &pc) : step(&frame, &m->code[pc], pc, &pc, true);\n" + " if (how == STEP_NEXT || how == STEP_ENDED) continue;\n" + " if (how != STEP_CALL && how != STEP_BACK && how != STEP_BATCH) break;\n" + " Frame apart = frame;\n" + " if (how == STEP_CALL) how = enter_call(&apart, &top, &pc);\n" + " else if (how == STEP_BACK) how = leave_call(&apart, &top, &pc);\n" + " else {\n" + " uint32_t past = 0;\n" + " how = open_batches(&apart, pc - 1, &past);\n" + " pc = past;\n" + " }\n" + " frame = apart;\n" + " if (how != STEP_NEXT) break;\n" + " }\n" + " if (top) {\n" + " Frame apart = frame;\n" + " unwind_calls(&apart, top);\n" + " frame = apart;\n" + " }\n" + " return finish(&frame, how, result);\n" + "}\n"); + pure_module_release(&m); + return 0; +} diff --git a/research/experiments/045-proof-compiler/unit.c b/research/experiments/045-proof-compiler/unit.c new file mode 100644 index 0000000..f85a4d9 --- /dev/null +++ b/research/experiments/045-proof-compiler/unit.c @@ -0,0 +1,47 @@ +/* Research 045: an operation's cost in machine instructions and cycles, from small apps (the apps in units): each takes + * message go { n: u32 } and does its operation n times; MESSAGES messages, counted (perf_event_open, user mode). + * + * cc -O2 -std=c17 -I../../../core unit.c ../../../build/libpure.a -lm -pthread -o unit + * ./unit MODULE N MESSAGES one JSON line: instructions and cycles an operation */ +#define _GNU_SOURCE +#include "module.h" +#include +#include +#include +#include +#include +#include +#include + +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); +} + +int main(int argc, char **argv) { + if (argc != 4) { fprintf(stderr, "usage: %s MODULE N MESSAGES\n", argv[0]); return 2; } + uint32_t n = (uint32_t)atoi(argv[2]); + int messages = atoi(argv[3]); + 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 go = pure_module_input(&module, "go"); + unsigned char payload[4]; + memcpy(payload, &n, 4); + if (pure_app_message(&app, (uint32_t)go, (PureSpan){payload, 4}) != PURE_OK) { fprintf(stderr, "failed\n"); return 1; } + int ins = counter(PERF_COUNT_HW_INSTRUCTIONS), cyc = counter(PERF_COUNT_HW_CPU_CYCLES); + ioctl(ins, PERF_EVENT_IOC_ENABLE, 0), ioctl(cyc, PERF_EVENT_IOC_ENABLE, 0); + for (int k = 0; k < messages; ++k) + if (pure_app_message(&app, (uint32_t)go, (PureSpan){payload, 4}) != PURE_OK) return 1; + ioctl(ins, PERF_EVENT_IOC_DISABLE, 0), ioctl(cyc, PERF_EVENT_IOC_DISABLE, 0); + uint64_t i = 0, c = 0; + if (read(ins, &i, 8) != 8 || read(cyc, &c, 8) != 8) return 1; + double ops = (double)n * messages; + printf("{\"n\":%u,\"messages\":%d,\"instructions_per_op\":%.1f,\"cycles_per_op\":%.1f}\n", n, messages, i / ops, c / ops); + pure_app_stop(&app); + return 0; +} diff --git a/research/experiments/045-proof-compiler/units/append.aup b/research/experiments/045-proof-compiler/units/append.aup new file mode 100644 index 0000000..def7fa5 --- /dev/null +++ b/research/experiments/045-proof-compiler/units/append.aup @@ -0,0 +1,7 @@ +state t = 0 +input go = message { n: u32 } +on go { + let xs: list of number + for i in 0 .. go.n { xs.append(i) } + t = xs.count +} diff --git a/research/experiments/045-proof-compiler/units/arith.aup b/research/experiments/045-proof-compiler/units/arith.aup new file mode 100644 index 0000000..76f48dc --- /dev/null +++ b/research/experiments/045-proof-compiler/units/arith.aup @@ -0,0 +1,7 @@ +state t = 0 +input go = message { n: u32 } +on go { + let s = 0 + for i in 0 .. go.n { s = s + i * 2 } + t = s +} diff --git a/research/experiments/045-proof-compiler/units/call.aup b/research/experiments/045-proof-compiler/units/call.aup new file mode 100644 index 0000000..ef31ef6 --- /dev/null +++ b/research/experiments/045-proof-compiler/units/call.aup @@ -0,0 +1,11 @@ +state t = 0 +input go = message { n: u32 } +fn f(x) { + if x > 1000000 { return 0 } + return x + 1 +} +on go { + let s = 0 + for i in 0 .. go.n { s = s + f(i) } + t = s +} diff --git a/research/experiments/045-proof-compiler/units/mod.aup b/research/experiments/045-proof-compiler/units/mod.aup new file mode 100644 index 0000000..dfb0f98 --- /dev/null +++ b/research/experiments/045-proof-compiler/units/mod.aup @@ -0,0 +1,7 @@ +state t = 0 +input go = message { n: u32 } +on go { + let s = 0 + for i in 0 .. go.n { s = s + i % 1000 } + t = s +} diff --git a/research/experiments/045-proof-compiler/units/read-direct.aup b/research/experiments/045-proof-compiler/units/read-direct.aup new file mode 100644 index 0000000..8609a5e --- /dev/null +++ b/research/experiments/045-proof-compiler/units/read-direct.aup @@ -0,0 +1,14 @@ +record R { + start = 0 +} +state ranges: list of R +state t = 0 +input go = message { n: u32 } +on go { + if ranges.count == 0 { + for i in 0 .. 1000 { ranges.append(R { start: i }) } + } + let s = 0 + for i in 0 .. go.n { s = s + ranges[i].start } + t = s +} diff --git a/research/experiments/045-proof-compiler/units/read.aup b/research/experiments/045-proof-compiler/units/read.aup new file mode 100644 index 0000000..34828e7 --- /dev/null +++ b/research/experiments/045-proof-compiler/units/read.aup @@ -0,0 +1,14 @@ +record R { + start = 0 +} +state ranges: list of R +state t = 0 +input go = message { n: u32 } +on go { + if ranges.count == 0 { + for i in 0 .. 1000 { ranges.append(R { start: i }) } + } + let s = 0 + for i in 0 .. go.n { s = s + ranges[i % 1000].start } + t = s +} diff --git a/research/experiments/045-proof-compiler/variants/v0-empty.patch b/research/experiments/045-proof-compiler/variants/v0-empty.patch new file mode 100644 index 0000000..de5b3fc --- /dev/null +++ b/research/experiments/045-proof-compiler/variants/v0-empty.patch @@ -0,0 +1,34 @@ +--- linebreak.aup ++++ v0-empty.aup +@@ -153,30 +153,6 @@ + } + + on line { +- let codes, cls, eff, start, nonspace, ri, at: list of number +- let joined, numeric: list of bool +- for p in line.points { +- let i = codes.count +- let r = range(p.code) +- let c = ranges[r].class +- let mark = c == CM || c == ZWJ +- let previous = if i > 0 { eff[i - 1] } else { SP } +- let joins = mark && i > 0 && !end(previous) && previous != SP && previous != ZW # LB9, LB10 +- let e = if joins { previous } else if mark { AL } else { c } +- codes.append(p.code) +- cls.append(c) +- at.append(r) +- joined.append(joins) +- eff.append(e) +- start.append(if joins { start[i - 1] } else { i }) +- nonspace.append(if e != SP { start[i] } else if i > 0 { nonspace[i - 1] } else { -1 }) +- numeric.append(if joins { numeric[i - 1] } else { e == NU || ((e == SY || e == IS) && i > 0 && numeric[i - 1]) }) +- ri.append(if joins { ri[i - 1] } else if e == RI { (if i > 0 { ri[i - 1] } else { 0 }) + 1 } else { 0 }) +- } +- let t = Text { codes: codes, cls: cls, eff: eff, joined: joined, start: start, nonspace: nonspace, numeric: numeric, ri: ri, +- at: at } +- let out: list of i64 = [0] # LB2 +- for i in 1 .. codes.count { out.append(i64(decide(t, i))) } +- if codes.count > 0 { out.append(2) } # LB3 ++ let out: list of i64 = [0] + breaks = bytes(out) + } diff --git a/research/experiments/045-proof-compiler/variants/v1-lists.patch b/research/experiments/045-proof-compiler/variants/v1-lists.patch new file mode 100644 index 0000000..6b73004 --- /dev/null +++ b/research/experiments/045-proof-compiler/variants/v1-lists.patch @@ -0,0 +1,14 @@ +--- linebreak.aup ++++ v1-lists.aup +@@ -173,10 +173,6 @@ + numeric.append(if joins { numeric[i - 1] } else { e == NU || ((e == SY || e == IS) && i > 0 && numeric[i - 1]) }) + ri.append(if joins { ri[i - 1] } else if e == RI { (if i > 0 { ri[i - 1] } else { 0 }) + 1 } else { 0 }) + } +- let t = Text { codes: codes, cls: cls, eff: eff, joined: joined, start: start, nonspace: nonspace, numeric: numeric, ri: ri, +- at: at } +- let out: list of i64 = [0] # LB2 +- for i in 1 .. codes.count { out.append(i64(decide(t, i))) } +- if codes.count > 0 { out.append(2) } # LB3 ++ let out: list of i64 = [0] + breaks = bytes(out) + } diff --git a/research/experiments/045-proof-compiler/variants/v2-text.patch b/research/experiments/045-proof-compiler/variants/v2-text.patch new file mode 100644 index 0000000..2539f0c --- /dev/null +++ b/research/experiments/045-proof-compiler/variants/v2-text.patch @@ -0,0 +1,12 @@ +--- linebreak.aup ++++ v2-text.aup +@@ -175,8 +175,6 @@ + } + let t = Text { codes: codes, cls: cls, eff: eff, joined: joined, start: start, nonspace: nonspace, numeric: numeric, ri: ri, + at: at } +- let out: list of i64 = [0] # LB2 +- for i in 1 .. codes.count { out.append(i64(decide(t, i))) } +- if codes.count > 0 { out.append(2) } # LB3 ++ let out: list of i64 = [0] + breaks = bytes(out) + } -- cgit v1.2.3