aboutsummaryrefslogtreecommitdiffstats
Commit message (Collapse)AuthorAgeFilesLines
* 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.
* 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.
* Say how a search gets past C: event lists as arrays, a directory for stored ↵eunhhu2026-10-051-0/+112
| | | | keys, then a JIT, with criteria (021)
* The same answers on the final build and the same pure-runs on the Pi, WSL2 ↵eunhhu2026-10-046-3/+153
| | | | and a Mac (121); 019 points at 020's view workers
* Check a pushed view that computes gets the newest value of writes made ↵eunhhu2026-10-042-9/+44
| | | | meanwhile, and queue=N's busy and its places coming back (020)
* Say 020 is built and measured (121, 122)eunhhu2026-10-041-1/+1
|
* Measure views off the connection threads: writes' tail as with the CPU ↵eunhhu2026-10-0411-6/+158
| | | | shared, two askers 1.95 times one (122)
* Measure computing faster: a search 2.1 times as fast, TPC-C 4.1%, four ↵eunhhu2026-10-0467-0/+559
| | | | fingers found and undone (121)
* Say why the dashboard's push-to-poll CPU sits at a tenth: an event costs ↵eunhhu2026-10-041-0/+4
| | | | what a request does (120)
* The runs of research 122: writes beside views that compute, one asker and ↵eunhhu2026-10-043-0/+283
| | | | two, and a plain view's reads
* Compute views with a body on view workers, off the connection threads, asked ↵eunhhu2026-10-043-81/+393
| | | | | | | | | | | | | | | | | | | | and pushed (020) - pure-serve --view-workers N (a CPU each; 0: on the connection threads): a GET of a view with a body (or a table with such a column) goes to the workers, which show it from the app's newest snapshot on readers of their own and give the answer back as an owner does (eventfd). The connection thread reads and writes its other connections meanwhile. - A snapshot of another module than the request was resolved with, or none (the app stopped), answers 503 stopped. Past an app's queue=N of them, 503 busy. - A push group of such a view hands one evaluation at a time; a newer snapshot meanwhile is evaluated after it; a group whose subscribers all left stays until its evaluation is back. - check.py server_view_workers: 8 askers of a long view while its app changes module (another view in its place) and then goes: every answer the old module's, the new one's, 503 or 404; streams closed at once leave nothing; --view-workers 0 as before.
* 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-043-37/+28
| | | | instructions and a search no time (020)
* Wait for a counter before searching in bfs-run, and the runs of research 121eunhhu2026-10-042-0/+67
|
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-20 16:12:21 +0000