aboutsummaryrefslogtreecommitdiffstats
Commit message (Collapse)AuthorAgeFilesLines
* 024: the table with operations apart and interpreted beside the hand-fused ↵eunhhu2026-10-052-35/+37
| | | | forms (geometric mean 1.58 and 1.24, the tier 1.92), the prototypes as a ceiling (124's floor 0.90x became 1.2-2.5x), division a third of the interpreted recurrence, the distance rule for equal strides only, why not copy-and-patch, matmul's miss without a fused multiply-add; CHECKPOINT says so
* 041 join ops: the recurrence interpreted and each round's rest as 11 ↵eunhhu2026-10-053-19/+172
| | | | operations apart, interpreted, 57.8 ms (C 32.6; fused by hand 48.4, the tier 2.46x); bfs: a node with more edges than the lanes runs its round alone (tested with lanes of 16, LANES_TEST); runs again
* Design 024: a batch executor, loops run 256 rounds at a time by operations ↵eunhhu2026-10-052-1/+137
| | | | the C compiler makes at build time (no code made at run time, 32 KB of lanes), checks as a batch's flag and a failed batch run again round by round; which loops batch (sums, affine keys at a nonnegative distance, filters that only grow, a count that only grows), sections run round by round interpreted, fused operations from a table, the JIT retired if it is not slower; 041's prototypes against C: roots 0.99, knapsack 0.71, matmul 0.94, BFS 1.03, join 1.59 (the tier 1.20-2.46); CHECKPOINT says so
* 041 knapsack u32_ops: the batch's operations apart and interpreted over ↵eunhhu2026-10-052-18/+70
| | | | four-byte lanes ascending in memory, 4.54 ms (C 6.38, the tier 7.5; fused 2.70): narrow lanes in memory's order are most of the gain, fusing the rest; runs again
* 041 batches: loops run a batch of rounds at a time, each operation a C loop ↵eunhhu2026-10-054-0/+707
| | | | made at build time (no code made at run time), on Pure's forms and checks, against C natural and C given the same restructuring: roots 6.79 ms (C 6.86), knapsack fused four-byte 2.70 (C 6.47, C in the batch's blocks 1.94), matmul lanes over j 6.67 (C 7.10, C swapped and vector 4.88), join 37 / 46 with its recurrence interpreted (C 30), BFS 10.3 (C 10.0, C read ahead 7.0); unfused interpreted operations 11.2 and 17.7-22.1
* 125: forms and newton runs named; BFS's time after the graph's load is the ↵eunhhu2026-10-053-4/+8
| | | | generic code's (steps 0.1%), what the tier needs for it (a list's count as a changing value); 023 cites words at e2e56dd
* Research 125: the tier's first steps against C (e2e56dd: roots 1.40, ↵eunhhu2026-10-054-1/+298
| | | | knapsack 1.19, sort 1.37, join 2.54, words 5.58, matmul 1.85, BFS 1.61; geometric mean 1.92, from 3-300x at 6b45806), what each change did, the forms measured in assembly, the apps unchanged, what is left (text in the executor, BFS's appends, spills); CHECKPOINT says so
* The tier checks a number finite in integers (its exponent's bits all ones), ↵eunhhu2026-10-053-4/+110
| | | | off the number pipes the divisions and sums wait on: roots 10.9 to 9.6 ms (1.39x C). 040 newton.c: roots' loop in the forms the tier may make it (the check as numbers 9.7 ms, in integers 8.7, none 7.7; next in r's register as gcc keeps it 7.0)
* Pointer induction (023): an inner count's access by a key affine in its ↵eunhhu2026-10-053-9/+184
| | | | | | round, in range for every round (its opening found it) and in a full list, reads its cell through a pointer, a phi at the loop's head: the column (read from the list) plus the key at round 0 times four where the loop opens, its key's step a round times four added at its latch. The key's nodes, in range, give up nowhere (no snapshot kept), so a key read by such accesses alone is not made; a list found by key alone with such an access is full where the tier begins (else the generic code runs the nest). matmul 23.0 to 14.2 ms (3.1x to 1.9x C) module_tier's programs sweep lists by keys stepping with a round (in range or not, a list full or not)
* 040 forms.c: matmul's inner loop in the forms the tier may make it (index ↵eunhhu2026-10-053-0/+100
| | | | 20.7 ms, pointer with multiply-add 13.1, apart 10.0, with checks 10.2, a bit tested before each load 13.4): the position's multiply and the pre-load branch cost, the checks hardly; 023 section 5 says so and what comes first (pointer induction, then a full list's copy)
* 040: the suite on 4bedd7f (11 rounds' medians, Pure / C): roots 1.58, ↵eunhhu2026-10-052-0/+217
| | | | knapsack 1.18, sort 1.37, join 2.62, words 5.46, matmul 3.07, BFS without reading ahead 1.58 (geometric mean 2.09; 3-300x at 6b45806)
* 040: TPC-C and the bank's queries against 6b45806 (023's criterion for the ↵eunhhu2026-10-0528-1/+136
| | | | apps there are): six pairs in turns, TPC-C's median -1.2% (the pairs -5.2 to +1.4%), the queries' medians within 1% but in_credit's (0.84 to 0.815 ms); the queries' instructions +0.3 to +1.5% on 49b6196 (2026-10-05-counts-49b6196.jsonl), -0.1 to +0.5% after the list's tree paths left HASHED's checks (2026-10-05-counts.jsonl). runs.sh serve, pairs and counts
* A text-keyed list let go at an event's end starts no key set (a number's ↵eunhhu2026-10-052-17/+20
| | | | | | bits): one that an index state then asks where an item went is inserted FLAT, whose key set an item's layout key (-1) would read past; the FLAT and tree key sets kept only for number keys. A list read by position checks for HASHED where it is not a tree alone (stored lists: none of it): the bank queries' instructions within 0.5% of 6b45806 (0.3-0.8% before) text_keys_equivalence asks where an item went in some events
* The tier's numbers' arithmetic in a run, each read by the next alone ↵eunhhu2026-10-053-15/+92
| | | | | | (constants between), checks only the last is finite, giving up at the run's first snapshot (the executor makes the run again and fails where it does); a snapshot's constants written as the constants they are, not kept in registers; the generic code's append in a loop keeping its books puts into a HASHED list as append does (its headroom kept). roots 12.2 to 10.9 ms (1.59x C), join 84 to 74 (2.5x) module_assumptions: a run of products and sums past the largest number (CHAIN_SOURCE)
* A HASHED list's table four fifths full at most (100,000 keys in 1 MB of ↵eunhhu2026-10-053-9/+73
| | | | slots, as C's table: in the L3), the generic code's APPEND into a HASHED list at its key's slot while its table need not grow, a whole number over a whole one above 0 never -0 (so MINSTD's floor(x * 48271 / p) is whole and x an integer in the tier). join 108 to 84 ms (2.8x C), sort 58 to 37 (1.4x)
* Text keys (023): a list knows the text field it is keyed by; an event's list ↵eunhhu2026-10-056-30/+264
| | | | | | keyed by a text is HASHED from its first item, its table's slots holding the texts' hashes (FNV-1a), a match the key cell's bytes too; HAS and a field by key read the table; its order made by a merge sort (the first eight bytes as a number, then all). A FIND whose index only an ITEM_SET of its list takes, the code between in a line finding by key alone, sets the item where it was found (PLAN_ROW: a HASHED list's slot, no position made). words 453 to 217 ms (5.8x C) text_keys_equivalence: adds, has, fields by key, sets where found, positions, runs, removes and clears against a tree keyed by the text
* HASHED (023): an event's list keyed by numbers that came out of order keeps ↵eunhhu2026-10-055-26/+298
| | | | | | each item's cells at its key's slot in its members' table, found by key there (the key and its cells read at one slot, as C's table); its order made by a radix sort of the slots' keys when something asks for a position (twice an event, then FLAT or a tree). The tier finds by key alone in a HASHED list (its bits' bit 1, its limit all ones: the bounds checked at a loop's opening still hold) out of the line; a list keyed by each count in order is DENSE from its first item. join 531 to 108 ms (3.5x C), sort 98 to 58 (2.1x) arrays_equivalence counts the HASHED form against a tree; module_tier's programs read a HASHED list by key
* The tier's loops tighter: a latch's way out takes the round as the next less ↵eunhhu2026-10-051-20/+72
| | | | one (the round's register the next's: no move on the way back), a way's moves only for phis something needs, a number over a power of two times its reciprocal (the same number), a constant only numbers' arithmetic reads a number made where the tier begins, the 2^53 check in three instructions. roots 14.1 to 12.2 ms (1.78x C), knapsack 8.5 to 7.8 (1.26x)
* The tier's inner loops: a count's work paid for every round as it opens (the ↵eunhhu2026-10-053-64/+253
| | | | | | rounds it does not run given back where it breaks or gives up), a comparison only a branch reads its flags, a full list's keys read without its bits (a key's position found: its key's register), an add's or sub's register its operand's where that is read last. knapsack 16.5 to 8.5 ms (1.37x C), matmul 25.7 to 22.9 Two bugs the work checks found, there since 6cd7f5a: the outermost loop's round past the work budget gave up at the loop's instruction, with nothing on the stack (the executor opened it again: LIMIT where WORK), now at its iteration; and a phi where an if's ways meet took its merge's loop (-1), so a value made of it was taken as made outside its loop and made once for all rounds. pure-run's budget and work commands; module_tier compares the work and runs four small budgets; module_assumptions keeps both programs
* The tier's keys and positions in range for every round, checked once where ↵eunhhu2026-10-053-54/+203
| | | | their loop opens (each affine in its round: both ends below the limit), the checks in the round gone; constants in the instructions (add, sub, cmp); one-byte columns widened to four where the tier begins, its loads and stores of four bytes only. roots 14.0 to 14.0 ms, knapsack 38.8 to 16.5, matmul 48.6 to 25.7
* The tier, first (023): a nest of loops as SSA, its stack, locals and states ↵eunhhu2026-10-055-8/+2297
| | | | values in registers (x20-x28 too, the frame's read again where it ends), whole numbers integers by their facts, the message's fields and lists' columns read once, invariants made before inner loops; where anything does not hold it gives up to the executor at the instruction (pure_run_rest) and the generic code goes on. roots 22.9 to 14.0 ms, knapsack 1,030 to 38.8, matmul 908 to 48.6; module_tier checks random handlers against the executor
* Keep a DENSE list's counted keys last in the list, apart from what is read ↵eunhhu2026-10-051-9/+9
| | | | often (the bank queries' instructions as before, within 0.4%)
* A keyed event list given small whole keys in order becomes DENSE too, and a ↵eunhhu2026-10-051-18/+95
| | | | DENSE list answers by position without becoming FLAT: its keys counted once per change of them (full: a key is its position; else ranks by word). knapsack 1,880 to 1,029 ms, matmul 2,284 to 908 (023 stage 1)
* 023: near C is the aim (each within 1.25x, the geometric mean within 1.1x), ↵eunhhu2026-10-051-10/+13
| | | | not past it; representation first, since a keyed list given keys in order stays FLAT and is searched by halves (knapsack's and matmul's 300x)
* Research 124: 022's BFS past C only by reading ahead (15.7 ms against 9.9 ↵eunhhu2026-10-052-1/+90
| | | | without), the suite of seven kinds of work at 3-300x C, floors at 0.90x C with the meaning's checks hoisted to 0-3%; CHECKPOINT says so
* 023: only checks the tier moved know just that they fail (those left in ↵eunhhu2026-10-051-4/+8
| | | | place fault where they are; now is the host's per-event value); value numbering of pure operations, which words' floor assumes
* Design 023, before building it: a tier that lifts every block to SSA, knows ↵eunhhu2026-10-051-0/+178
| | | | types and ranges, hoists the meaning's checks out of loops, counts work per loop, allocates registers; criteria on research 124's suite of seven kinds of work against C (each within 1.25x, the geometric mean below 1.0, the meaning's checks within 5%), from floors at 0.90x C
* Research 124's floors: each workload by hand as Pure could run it (its ↵eunhhu2026-10-055-186/+987
| | | | lists' representation, its meaning) bare, with the checks a compiler could hoist, and with every check where the meaning puts it: hoisted 0.64-1.02x C (0.90 by the geometric mean), naive up to 12x
* Research 124's suite at 6b45806: Pure against C 3.3x (roots), 300x ↵eunhhu2026-10-052-0/+217
| | | | (knapsack), 4.8x (sort), 22x (join), 12x (words), 304x (matmul), BFS 1.57x without reading ahead; only roots and BFS run as code
* Research 124's suite: seven kinds of work in one event each (roots, ↵eunhhu2026-10-059-0/+570
| | | | knapsack, sort, join, words, matmul, BFS), each against the C one would write, in one process with the same inputs and answers; PURE_AHEAD=0 to measure the code without reading ahead
* Say what finishing 022's stage 3 found: the books and the work in registers, ↵eunhhu2026-10-051-1/+40
| | | | reading ahead to the bucket's last cell, the edge loop's checks; that past C is the reading ahead (16.1 ms without it, C 9.8), and that the criteria move to 023's suite
* In the integers' code, walk only the slices it opens (the step's go to the ↵eunhhu2026-10-051-26/+72
| | | | executor), so their list's columns are there; the keys a list's bits reach none without bits, so one compare asks both; has's rare ways out of the line: a seen edge 14 to 11 instructions, BFS core 8.6 to 7.4 ms (022)
* Read ahead in integers in the integers' code, and the bucket's last cell as ↵eunhhu2026-10-051-12/+103
| | | | well as its first: a node's edges cross a line more often than not. BFS core 12.2 to 8.6 ms, 29.4M to 20.7M cycles, past C's 9.4 ms (022)
* Keep the work an event may still do in a register, x30 among what is kept, ↵eunhhu2026-10-052-64/+175
| | | | small constants and powers of two's products in the instruction; where a check may give up, make the result in x16, the operands as they were for the executor (aup's check caught a register shared with its operand): BFS core 12.5 to 12.2 ms, 46.2M to 43.0M instructions (022)
* Keep a nest's books in registers: a FLAT list's count and a DENSE one's ↵eunhhu2026-10-051-44/+265
| | | | items added as its appends make them, the event's headroom, written back before a call, at a fault and as the nest ends: BFS core 14.6 to 12.5 ms, 57.8M to 46.2M instructions (022)
* Compile each nest of loops twice, the second with whole numbers as integers ↵eunhhu2026-10-054-75/+472
| | | | (narrow columns, counts, their arithmetic within 2^53), giving up to the executor for the rest of a round when that fails: BFS core 14.9 to 13.4 ms (022)
* Compile only blocks whose loops are code throughout: a loop of steps ↵eunhhu2026-10-051-9/+39
| | | | (TPC-C's) runs in the executor, 2.7% faster there (022); PURE_JIT=all compiles every loop for the checks
* Say what 022 decided while building stages 1-4 and how stage 3 ends: ↵eunhhu2026-10-051-1/+36
| | | | integers assumed, the rest of a round in the executor when they break, the books in registers
* Read a slice's bucket and first cell some rounds ahead of the loop that ↵eunhhu2026-10-054-8/+353
| | | | opens it, read an item and find it in key bits as one, branch back once a round: BFS core 19.6 to 14.9 ms (022)
* Keep arrays' number columns as narrow as their values (u8, u32, f64; a DENSE ↵eunhhu2026-10-055-204/+735
| | | | list's keys as its slots), open a packed list's slice in code with an integer index, keep a nest of loops' values in registers of their own: BFS core 27.5 to 19.6 ms (022)
* Compile with the stack's values in registers, comparisons and bits branched ↵eunhhu2026-10-053-339/+1141
| | | | on, each loop's columns, key bits and place kept in registers, and appends to an event's list as code: BFS core 55 to 27.5 ms (022)
* Pack a stored keyed list searched often into arrays and a bucket index ↵eunhhu2026-10-054-34/+546
| | | | fitted to the keys searched, between events, and build trees from the leaves up: BFS core 89 to 55 ms (022)
* Design 022: stored lists as arrays with a bucket index fitted to the keys ↵eunhhu2026-10-057-7/+434
| | | | searched, narrow columns, a JIT with registers and loop guards, read ahead; criteria first
* Measure 021: BFS 190 to 90 ms over HTTP against C's 9.1, short of C; Pure's ↵eunhhu2026-10-0575-2/+1243
| | | | forms by hand beat C only packed, narrow and read ahead (123)
* Compile only blocks with a loop, keep no code for a module without one, set ↵eunhhu2026-10-052-11/+36
| | | | | | | | | | | | | | a frame's fields one by one, and inline group_of (021) - Compiled code paid only where blocks repeat; a block run once (a view's cell, a fold's item, most handlers) ran slower through the code's entry and its calls of step: the bank's table queries took 16-24% more instructions. Now only a block with an EACH or a LOOP is compiled, and a module with none keeps no compiled code. - run() set its whole frame each time (the compiled code's run among it); now its fields one by one. - group_of is inlined into its pass: after the executor's refactor it was a call per row (per_branch +4-5% instructions; now +1.1-1.3%).
* Measure an index for a stored list's slices outside the list: three times a ↵eunhhu2026-10-053-3/+121
| | | | tree's seek, still seven times C's (021)
* Say what a search's floor is with stored lists as trees: 373 ns a node to ↵eunhhu2026-10-054-1/+91
| | | | find a slice against C's 21 (021)
* Read a tree's items in compiled code from a run the frame keeps, start a run ↵eunhhu2026-10-055-8/+88
| | | | | | | | | | | | | | at the finger's leaf, and move indices only for a list an index refers to (021) - The frame keeps the run compiled code read a tree's item from last (the list as it was: its version); an item it holds is read from its column, else pure_run_item takes the item's run and steps. - pure_list_run starts at the leaf the finger keeps when it holds the position (a slice found by key just before): no second descent; the run after it is found from the root (PureRun.pathless). - LIST_APPEND and LIST_REMOVE move index states only for a list one refers to. - A search (core only): 89 ms compiled (answers the executor's).
* Write the hot instructions as code: constants, states, locals, rows, ↵eunhhu2026-10-054-27/+424
| | | | | | | | | | | | | | | | | arithmetic, has by bits, a DENSE field by key, a FLAT item, and loop iterations (021) - module-jit.c writes CONST, LOAD, STORE, the local and row loads, INDEX_FIRST, LIST_COUNT, INDEX_MOVE, NOT, NEG, FLOOR, the number arithmetic and comparisons (DIVIDE and NON_FINITE faults where the executor gives them), LIST_HAS by a key set's bits, a joined FIND's field of a DENSE list, a FLAT list's ITEM_GET, and a walk's and a count's iteration (work charged as the executor charges it). Anything else, or a list in another form, still calls step. - module-list.c says where a list keeps what the code reads (pure_list_layout); list_of and item_field are shared. - PURE_JIT_DUMP=file writes the code made, to read with objdump. - A search (core only): 103 ms compiled, 122 ms executed; the answers (hops, reached, work) are the executor's.
* Run a block through a frame and step, and compile blocks to AArch64 that ↵eunhhu2026-10-056-558/+1159
| | | | | | | | | | | | | | | | | | | | | | call the same steps (021) - run() keeps a block's operand stack and open loops in a Frame; step() runs one instruction (branches and loops too, one dispatch), and enter_each, enter_loop, leave_loop and iterate are their own functions. The executor is the same machine code, 7% fewer instructions. - The verifier records each instruction's stack height (from its block's start), so compiled code knows each slot's place. - module-jit.c (AArch64 Linux; elsewhere, or PURE_JIT=0, none): a module's handlers', views' and folds' blocks compiled when it loads. Branches and loops are branches; every other instruction calls the executor's own step, so both run the same meaning. A loop that is not opened lands where its iteration would have ended; an empty loop iterates in place. - test-module recompiles a module whose code a test changes after load. - A search (100,000 nodes, 1,000,000 edges, core only) is 150 ms compiled, against 122 ms executed: a call of step for every instruction costs more than the executor's switch; the hot instructions are written as code next.
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-20 16:40:24 +0000