| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
| |
128) when every list takes its items so (an event's list, no index into it, one append to it: FLAT not keyed at its end, DENSE by keys it holds at its count, HASHED by number; never past its arrays' limit) and the memory budget takes them all (each item only grows what it counts): columns grown and widened once, the first key there already the executor's EXISTS at its round; else round by round as before, tried at once again after a round that changed a list's form. 50,000 DENSE adds 5.18 to 0.65 ms (the compiled code 0.28). APPEND_SOURCE: keys there already at rounds q and p, keys past a DENSE list's from round p, two appends to one list, widened columns, under memory budgets (seeds 1, 2, 3, 5, 23 alike: 31,402 batches at once in seed 23's, 292 by the budget round by round)
|
| |
|
|
| |
walks (join 423 to 161 ms without machine code, the tier 74) and what a batch pays for, measured apart: an instruction about 20 ns a batch (0.02 ns a round at 1024 lanes), a reduction's end 4-9 ns a round, an append about 100 ns (the executor's), join's recurrence about 60 ns a round; BFS not batched (a count that grows, a filter that only grows, nested walks), so the JIT stays for now; the next in that order: appends at once, the recurrence's steps in registers, reductions' ends; 022 and 024 and CHECKPOINT say so
|
| |
|
|
| |
c67f988): batches join 161.2 ms (the compiled code 74.4, alone 423.4), matmul 46.1, knapsack 15.1, roots 9.22; costs/: small modules timed three ways (an instruction about 20 ns a batch, a sum's end about 4 ns a round, an append about 100 ns as the executor's, the nested rounds 10.2 ms against the compiled code's 23.1)
|
| |
|
|
| |
at a time: each lane an item's place (ROW of the walked list affine), its work counted as it opened, its place moved past the batch; no append to the walked list. module_tier makes walks of rounds apart (f, g, h, slices of g; seeds 1, 2, 3, 5, 23 alike: 1,891 walk batches in seed 1); BATCH_SOURCE walks a slice
|
| |
|
|
| |
e, neither reading L; the set at k's row as found), keeps its rows and e from the pass (the second k, its find and the cell's read skipped) and adds them at the batch's end round by round as the executor adds and sets (a sum not finite: the executor's fault at its round; a column too narrow widened); a batch reading or setting those cells otherwise gives its rounds back. Recurrence steps one dispatch each. PURE_JIT=0 join 428 to 165 ms (the compiled code 78). module_tier makes sums into cells (seeds 1, 23 alike: 278 batches with them in seed 1); BATCH_SOURCE sums into three cells in turn
|
| |
|
|
| |
sets it, every set of it x = e of x, numbers, fields, states, the loop's value and locals the block does not set, in no branch's way; its sets planned PLAN_RECUR) runs ahead of the batch round by round as steps decoded once a batch, as the executor computes them (a round's fault gives the batch back), leaving its value at each other read in each lane; the batch's pass skips its sets. matmul's, knapsack's and join's table loops batch: matmul 50 to 46 ms. module_tier makes loops with a recurrence (x1) ahead of appends, sets and sums (seeds 1, 2, 3, 5, 23 alike); RECUR_SOURCE: two updates a round, a division by 0 and a product past the numbers at some round, under work and memory budgets
|
| |
|
|
| |
with no room left for a list's headroom kept its live count anyway (in x30, the 13th register) and wrote that stale count over the list's own after its appends went the unbooked way (a loop of appends after a doubly nested loop reading t.has, PURE_JIT=all: e.count 1 for 36)
|
| |
|
|
| |
appended in a batch's block (to a list the block reads nowhere else, no index into it, no nested loop) is made at the batch's end round by round through the executor's own step: keys there already, the memory budget, its undo log as the executor's; a fault there is the executor's at that round (the event undone: its kind, its instruction and the work so far tell), pure_batch_run's third way out. module_tier's handlers append (e, d) in rounds apart and run under a memory budget too (seeds 1, 2, 3, 5, 23 alike); knapsack's table loop batched (13.8 to 13.7 ms: the appends cost as the executor's)
|
| |
|
|
| |
growth in registers checks the memory against the books' headroom (the app's growth lacks theirs until written back): it faulted MEMORY a round late, its work a round more than the executor's (a loop appending to DENSE, FLAT and HASHED lists, memory 6000: 3562 for 3525). pure-run: memory N, the states' budget
|
| |
|
|
| |
stage 2 under ASan and UBSan (139 programs, the executor's output)
|
| |
|
|
| |
together lane by lane, breaks, reductions folded in the rounds' order) and the measured passes after it (finite checks in the arithmetic's loop, tests as four-byte masks, the loop's value made once): roots 9.13 ms without machine code, below the tier's 9.57; matmul 50 (the tier 14.3: its table's loop and 15 instructions a nested round left); 685 random programs alike; 024 and CHECKPOINT say so
|
| |
|
|
| |
9.57, alone 130.6), knapsack 13.80, matmul 50.03 (14.27, 914.9); join and sort as many instructions with batches as without
|
| |
|
|
| |
same loop: a pass less each), tests of numbers giving four-byte 1s and 0s (a branch's mask as they are), numbers made of four-byte lanes and affine values by loops of their own, the loop's value as numbers made once a batch, no live lanes to make while none broke out or ran out, a small whole count's sum unchecked: PURE_JIT=0 roots 16.8 to 9.1 ms (the compiled code 9.6, C 6.9), matmul 68 to 50
|
| |
|
|
| |
for every lane together (round t for the lanes with more than t rounds that did not break out; BREAK leaves it lane by lane; its slot as each round sets it), and x = x op e (op +, min, max; x read no other way) is a reduction: each lane's own from op's identity (-0 a sum's), folded in the rounds' order at the batch's end (a sum's lanes of several whole numbers only, below 2^53); nested rounds' work counted for each lane and checked before anything changes; lanes and masks no holder keeps freed between nested rounds. Planned at load: a local read before set in its loop's scope, or not a reduction's, keeps the loop round by round. PURE_JIT=0: roots 130.5 to 16.8 ms, matmul 914.7 to 68.2. module_tier makes nested loops with breaks and reductions (seeds 1, 2, 3, 23: 549 programs alike); NESTED_SOURCE
|
| |
|
|
| |
knapsack 1,041 to 13.6 ms in the executor (the compiled code 7.5; its inner loop 1.17x the tier's, the stage's criterion missed; the table's adds left to stage 4), the executor without batch loops unchanged; what measuring overturned (a call among the steps cost 20% of the instructions, so two copies; run aligned to 64 for its cycles; results apart from operands for vector code); tests; 1024 lanes, 134 KB a thread; 024 and CHECKPOINT say so
|
| |
|
|
| |
batches, the executor alone) and icount.c's instructions and cycles; stage 1 at 10a50dd: knapsack 13.57 ms with batches (1,040.9 alone, 7.52 compiled, C 6.23), the others as they were; the executor's instructions as e2e56dd's or fewer (roots 2.756 to 2.760 billion, cycles alike), knapsack's 21.7 to 0.46 billion with batches
|
| |
|
|
| |
(lane forms, locals set before read in every round, ifs, numbers set in items) runs, in the executor, up to 1024 rounds at a time: values uniform, affine or lanes (numbers, or whole numbers in four bytes), branches as masks, cells read by affine rows as strided columns, sets kept to the batch's end and made only when no round reads an earlier round's; a fault, a form it lacks or such a read gives the rounds back to the executor one by one, work counted as written. Planned at load (PURE_BATCH=0: none); the executor of a module without such loops is the same code (run aligned to 64: as many instructions and cycles), with one its own copy. knapsack with PURE_JIT=0: 1,056 to 13.7 ms. module_tier compares batches with the executor alone and makes loops of rounds apart; BATCH_SOURCE: widened columns, -0, a fault mid-batch, rounds reading the last's sets
|
| |
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
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)
|
| |
|
|
|
|
| |
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)
|
| |
|
|
| |
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)
|
| |
|
|
| |
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)
|
| |
|
|
| |
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
|
| |
|
|
|
|
| |
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
|
| |
|
|
|
|
| |
(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)
|
| |
|
|
| |
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)
|
| |
|
|
|
|
| |
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
|
| |
|
|
|
|
| |
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
|
| |
|
|
| |
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)
|
| |
|
|
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
often (the bank queries' instructions as before, within 0.4%)
|
| |
|
|
| |
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)
|
| |
|
|
| |
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)
|
| |
|
|
| |
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
|
| |
|
|
| |
place fault where they are; now is the host's per-event value); value numbering of pure operations, which words' floor assumes
|
| |
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
(knapsack), 4.8x (sort), 22x (join), 12x (words), 304x (matmul), BFS 1.57x without reading ahead; only roots and BFS run as code
|
| |
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
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)
|
| |
|
|
| |
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)
|
