aboutsummaryrefslogtreecommitdiffstats
path: root/core
Commit message (Collapse)AuthorAgeFilesLines
...
* Batch: a recurrence's steps each an operation of two numbers a round keeps ↵eunhhu2026-10-061-39/+60
| | | | (a step's result, a recurrence's value, the loop's value, a number that stays) rather than a stack's pushes and pops, an operation computed twice in its statement once (x the same until it is done): 1,000,000 rounds of MINSTD 44.4 to 25.7 ms (the compiled code 18.5, the executor alone 73.0); costs/recur.aup
* Batch: a batch's appends made at once (pure_list_add_many, a call a chunk of ↵eunhhu2026-10-063-14/+291
| | | | 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)
* Batch: a walk (EACH) whose block has batch forms runs a batch of its items ↵eunhhu2026-10-062-27/+55
| | | | 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
* Batch: a sum into a cell, L[k].f = L[k].f + e (k computed twice the same and ↵eunhhu2026-10-061-12/+166
| | | | 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
* Batch executor stage 5 (024): a recurrence (a local a round reads before it ↵eunhhu2026-10-063-14/+206
| | | | 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
* JIT: books written back only for lists their nest keeps books of: a nest ↵eunhhu2026-10-061-0/+1
| | | | 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)
* Batch executor stage 4, first part (024): an item of numbers and bools ↵eunhhu2026-10-063-17/+89
| | | | 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)
* JIT: an append to a HASHED list in a nest whose books keep DENSE appends' ↵eunhhu2026-10-061-10/+14
| | | | 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
* Batch: numbers' results checked finite as they are made (in integers, in the ↵eunhhu2026-10-051-39/+117
| | | | 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
* Batch executor stage 2 (024): a loop in the batch's block runs its rounds ↵eunhhu2026-10-053-42/+339
| | | | 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
* Batch executor stage 1 (024): a count's loop whose block has batch forms ↵eunhhu2026-10-056-56/+1227
| | | | (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
* The tier checks a number finite in integers (its exponent's bits all ones), ↵eunhhu2026-10-051-4/+6
| | | | 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-051-4/+156
| | | | | | 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)
* 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-051-11/+64
| | | | | | (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-052-7/+71
| | | | 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-055-29/+256
| | | | | | 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-053-18/+279
| | | | | | 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-051-60/+158
| | | | | | 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-054-8/+2173
| | | | 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)
* Research 124's suite: seven kinds of work in one event each (roots, ↵eunhhu2026-10-051-0/+2
| | | | 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
* 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-051-54/+132
| | | | 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-053-75/+410
| | | | (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
* Read a slice's bucket and first cell some rounds ahead of the loop that ↵eunhhu2026-10-053-7/+347
| | | | 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)
* 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%).
* 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-055-557/+1158
| | | | | | | | | | | | | | | | | | | | | | 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.
* Share an event's empty list as it is: a snapshot made every event's lists ↵eunhhu2026-10-052-1/+20
| | | | trees for the next event (021)
* Keep an event's lists in arrays, flat or at their keys, and read a field by ↵eunhhu2026-10-055-18/+620
| | | | | | | | | | | | | | | | | | | | key as one (021) - pure_list_arrays: an event's list (never shared, journaled or undone) keeps its items in arrays: FLAT in order, or DENSE at their keys when keyed by small whole numbers. A position asked of a DENSE list makes it FLAT; moves past a few times its items, arrays past 64 MiB, or a third change of form make it a tree. Answers are the tree's; the stored bytes stand for its items in the memory budget whatever it keeps them in. - pure_list_add need not say where an item went: a list no index state refers to is not asked. - A LIST_FIND whose index the next ITEM_GET of its list takes at once is joined to it at load (PLAN_JOINED): pure_list_lookup reads the field by key, at the key in a DENSE list. - test-module arrays_equivalence: beside a tree, every step of a random run (adds, inserts, removes, changes, finds, reads, runs, clears) gives the same answers through every form and change of form. - A search (100,000 nodes, 1,000,000 edges, core only): 187 to 126 ms.
* End a loop's iteration at the block's end check, not a second one per ↵eunhhu2026-10-041-12/+12
| | | | instruction (020)
* Keep one finger a thread, as before: four cost the bank's queries ↵eunhhu2026-10-042-33/+22
| | | | instructions and a search no time (020)
* Search an event's keyed lists by a key set and lists by fingers, add by key ↵eunhhu2026-10-045-96/+738
| | | | | | | | | | | | | | | | | | | | in one descent, and loop without recursion (020) - An event's list keyed by a number keeps its keys beside its tree: bits while they are small whole numbers, else an open-addressing table; has() reads only that, and inserts, removes, key changes, their undoing and clears keep it. - Each thread keeps fingers on the last four leaves it read (list id and version must match): reads by position and searches by key that land in them do not descend. - pure_list_add finds a key's place and inserts there in one descent; a stored keyed list's appends take it too, journaled as inserts. - Child searches count over the whole guide; item fields know at load whether they are text; loops run on a stack of loop records, not by recursion; module-list.c builds at -O3. - test-module: the key set and fingers answer as a model at every step (bits to table, removes inside runs, undone changes, clears, shares), and a stored keyed list's adds replay from its journal.
* Let a view compute in its body, on a reader's own lists (018 stage 3)eunhhu2026-10-043-29/+201
|
* Count in loops that nest, break, and keep an event's own lists, every event ↵eunhhu2026-10-045-41/+321
| | | | bounded (018 stage 2)
* Keep transient states the app's while it runs, never stored (018 stage 1)eunhhu2026-10-044-20/+162
|
* Build with clang, and the core and store on macOS, againeunhhu2026-10-012-5/+10
| | | | | | | | | | | | | | Apple clang 21 (an M3) and clang 19 refused what gcc let pass (research 029): - PURE_FIELD_REST was an enum of UINT32_MAX, past an int (C17): a macro. - a store's publish copied an entry rebuild left unset when the record was not found (the copy was never used): copied when it was made. - the log's image writer kept a count only Linux's sync_file_range uses. - ",{" + (row == from) read as adding an int to a string: said plainly. - the tests: mkdtemp, hidden by _POSIX_C_SOURCE on macOS, needs _DARWIN_C_SOURCE; a string split so that \x80 and a stay apart is bracketed; a count left over and a malloc measure only glibc has. The core's and the store's tests pass on the Mac.
* Read a list cell's place after finding its leaf, not beside iteunhhu2026-10-011-1/+2
| | | | | | | | pure_list_get passed leaf_of(list, at, &within) and within to cell_at in one call: C leaves the order of a call's arguments open, so within could be read before leaf_of set it. gcc 14 on AArch64 called leaf_of first; gcc 13 on x86_64 says within is used uninitialized (found building Pure there, research 029).
* Count work only under a budget, and say why a view failed only then (017)eunhhu2026-10-013-21/+32
| | | | | | | | | | | | | | The work budget added about 26 instructions to every row of a table a host shows (bank, a table of 10,000 rows: +3.0% instructions an ask), which 017's one-app criterion allows at 1%. A sample put most of it in show_given asking every cell why it failed, and the rest in evaluate and the row lookup writing that reason and the count for every cell. Now nothing is counted without a budget (PureApp.work stays), the reason is written only when a view, a cell or a row has no value, and pure-serve asks it only of a cell without one. The table: +0.94%; the other bank queries within 0.4%. The tests that read the count set a budget that is never reached.
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-20 11:24:11 +0000