aboutsummaryrefslogtreecommitdiffstats
path: root/docs
Commit message (Collapse)AuthorAgeFilesLines
* 043 programs (research 139, in progress): a batch loop's body as the program ↵eunhhu11 days1-0/+52
| | | | a load would make, interpreted a step at a time (scalar steps by the executor's rules, kernel steps over four-byte lane registers fixed at load with two buffers each, a list's cells once a batch, a deferred set after its distance check), against the same kernels called straight and natural.h's C: matmul 10.36 ms (straight 7.17; the executor's 25.8 with 3.6 of making), knapsack 4.16 (straight 3.76; the executor's 8.19); 139's question, bars and b20's split (matmul's 11.1 ms of interpretation, knapsack's 1.9)
* Research 138: the batch executor's stage 5, design 025 made: sums into cells ↵eunhhu11 days3-4/+86
| | | | at once in integers (join 116.0 to 110.5 ms, short of 108: what is left is the same cells' memory, read, add and write again), decide's bit found once (BFS 23.2, short of 21.5: the tail's time was its loads more than its instructions), and the batch executor's loops aligned to 64-byte lines (the hot loops' placement had swung knapsack 6% at the same instructions; the lists' loops aligned too cost the bank's queries 1-2% more instructions, so not they); against b9 matmul -36%, knapsack -28%, roots -7.6%, join -6.2%, BFS -3.9%, the executor alone, the bank queries and TPC-C (+0.7%) as they were; 025's bars and what each stage measured; 024 and CHECKPOINT say so
* Design 025: stage 5's bars measured again on b16: BFS's candidate tail about ↵eunhhu11 days1-2/+8
| | | | 5.7 ms of 24.1 (decide, keep_filtered, apply_filters and the list side), halved 21.5 ms; join's sums into cells about 17 ns a round, a chain through the same cells, in four-byte integers with the width once a batch about 5 ns, 108 ms; neither moves BFS from about 2.7x the compiled code, and join's recurrence (about 40 ms) stays outside
* Design 024: its header says stages 1-4 of 025 are made (134-137)eunhhu12 days1-1/+1
|
* Research 137: the batch executor's stage 4 (columns read in place, ↵eunhhu12 days2-1/+70
| | | | comparisons counting their lanes): knapsack 10.07 to 8.25 ms (bar 8.6; b9 11.46, the compiled code 7.9), its instructions 12.2% below b9's; what is left of knapsack's gap is the per-batch interpretation (about 3 ms), not the kernels (ADD 1.7, GT 1.7, the masked set 0.55 ms); the others the same by instructions; make check's server_view_workers timed out once (the known flake), passed 3/3 alone and in a full rerun; bank queries' instructions within 0.1% of b9's, TPC-C -0.3%; the two large gaps left (matmul's nested rounds, BFS's candidate tail) the user's to choose
* Design 025: stage 4's knapsack bar by arithmetic (8.6 ms: two 4 KB copies ↵eunhhu12 days1-2/+5
| | | | and the branch's counting pass a batch, about 0.35 us), and the general way's floor at 1024 lanes (about 8.3 ms, ADD and GT apart) against the compiled code's 7.9
* Research 136: the batch executor's stage 3 (four-byte MUL, reductions with ↵eunhhu12 days2-1/+69
| | | | no lanes while every lane's e is the same, a list's cells once a batch): against b9, interleaved, matmul 40.01 to 25.97 ms, knapsack 11.47 to 10.07, roots 8.97 to 8.29, join 117.2 to 115.8, BFS and sort the same; sum0 8.69 to 1.01 (bar 1.5); matmul short of its bar (21): the nested rounds' interpretation (about 14 ms) and the matrices' making (4-5) were left out of the arithmetic; the executor alone and the bank queries' instructions as b9 (0.08%), TPC-C +0.7%; stage 4 next (knapsack's six passes to three)
* Design 025: stage 3's matmul bar against what the four-byte MUL gave (26.57 ↵eunhhu12 days1-2/+3
| | | | ms against 21): the arithmetic left out the nested rounds' interpretation (about 15 ms) and the matrices' making (4-5 ms)
* Research 135: batch plans' stage 2 measured (b11 = 7959885 against b10, ↵eunhhu12 days2-1/+71
| | | | interleaved): matmul 38.18 to 36.10 ms with 4.5% fewer instructions (segments in its nested rounds), knapsack's per-batch cost 0.68 to 0.63 us but knapsack 10.35 to 10.51 ms with 1% fewer instructions (its per-element loops placed elsewhere), sum0 1,743 instructions a batch: short of 025's stage-2 bars (9.2 ms, 0.45 us, 33 ms): 025 priced a segment's instruction at 50 cycles, the counts show about 25 instructions, and a batch's cost sits in finds, bounds, read records, lane setup, masks and the deferred store's check; a list's cells once a batch measured at 3% and not made; next, per element: stage 3's four-byte MUL (matmul 21 ms)
* Design 025: stage 2 reshaped after stage 1 (134): scalar segments planned at ↵eunhhu12 days1-10/+22
| | | | load, run by the same rules with the per-instruction pass as fallback, and a list's cells once a batch; bars by arithmetic: knapsack's inner block has 10-12 of 24 instructions in segments, so 0.45 us a batch and 9.2 ms (the compiled code's 7.9 needs stage 4's passes), matmul 33 ms, sum0 1,300 instructions a batch
* Research 134: batch plans' stage 1 measured (b10 = a6fabf0 against b9, ↵eunhhu12 days2-1/+74
| | | | interleaved): knapsack's per-batch cost 0.90 to 0.68 us and knapsack 11.48 to 10.34 ms, short of 025's bars (0.60 us, 10.3 ms): 025 counted the pass's per-instruction head as lookups; sum0 2,330 to 1,822 instructions a batch (bar 1,550); matmul 40.0 to 38.2 ms with the same instructions and BFS 24.04 to 24.31 with 0.2% fewer (placement); sum0's 8.69 to 6.13 ms mostly the compiler now vectorizing the reductions' first loop; the executor alone the same instructions; what is left a batch is the pass's Val handling (stage 2); 041 runs.sh pairs, pairs and counts data
* Research 132 and 133 corrected: the per-batch cost was icount's three rounds ↵eunhhu12 days2-10/+14
| | | | over one round's batches, 3x too high; about 2,300 instructions (0.33 us) in a small block, 0.90 us in knapsack's (38% of its time, not 20%)
* Design 025: batch programs (132's A), the block's facts once at load and ↵eunhhu12 days2-1/+180
| | | | only values each batch: knapsack's per-batch cost measured at 0.90 us, 38% of its 11.5 ms (BATCH 1024 against 256 under a sampled profile: re-reading the block about 39%, value kinds 26%, list facts and dependence 22%, dispatch 14%), sum0's 0.33 us, matmul's inner-round dispatch about 13 ms and float-checked arithmetic about 22; five stages (facts at load, static kinds and list facts once a batch, typed kernels, fewer passes, the tails) with bars from those shares; 041 batch-costs data
* Research 133: register tiles measured (132's deciding experiment): past the ↵eunhhu12 days3-2/+90
| | | | bar on roots (0.71x the compiled code's cycles a step), not on knapsack (4x) or BFS (2.4x), as NEON has no gather and a tile's lanes go out and in one by one; tight passes of the batch executor's own shape in the same run at 1.2x (BFS) and 0.4x (knapsack, clang): the shape is right and the 3x is implementation, so 132's A (a batch program made once at load, loops tight by type, width and stride, fewer passes) is the way; tiles kept aside for chains of arithmetic; 132, 024 and CHECKPOINT say so
* Research 132 (no code): where the batch executor's cost sits (an element's ↵eunhhu12 days1-0/+166
| | | | passes through memory; a batch's fixed cost about 6,500 instructions, 1 us, measured by 1024 against 256 lanes: fewer lanes are slower, so 024's L1 sizing was the wrong lever; a candidate's tail about 250), what the database literature measured of the same shape (X100, Kersten 2018's cycles and instructions a tuple, Sompolski 2011, Gubner 2017's in-register aggregation, Photon, Ertl and Gregg), the ways judged by the philosophy (a batch program made once at load; register tiles with threaded dispatch as the one general way past the floor; a table of fused operations and AOT C out), and the deciding experiment with its bar first (three bodies in tiles of 4, 8, 16: within 1.3x the compiled code's cycles an element, or it is not the answer); 041 lanes data
* Research 131: the batch executor's general cuts, by the user's choice of the ↵eunhhu12 days2-1/+96
| | | | general way over a table of fused operations: values computed by the same code taken from the first, if !c one branch, selections (an arm's few lanes alone), keys as bits asked in one loop, L.first + i affine, a slice's bounds at once: the suite's BFS 211 to 112 instructions an edge, 41 to 24 ms (the compiled code 38.5, 7.7); where the rest goes and the floor of the general way (about twice the compiled code); knapsack and matmul 10% slower, cause not fully told; 024 and CHECKPOINT say so
* Research 130: the batch executor's frontiers (a count's guard, walks in a ↵eunhhu12 days2-1/+115
| | | | batch's rounds together or spread into lanes, filters asked as a batch opens and again at its end): the suite's BFS batched, 93 to 41 ms (the compiled code 7.7, C 10); where it goes (211 instructions an edge against 38.5: a filter's code over every lane the most); the floor of operations each a pass over the lanes (about 50 an edge, 1.3x the compiled code) and what would pass it (fused operations from a table, 024's); the choice left: a table of them, or the compiled code kept for such work; 024 and CHECKPOINT say so
* Research 129: the batch executor's costs cut (appends at once 5.18 to 0.65 ↵eunhhu2026-10-062-1/+125
| | | | ms, a recurrence's steps as numbered values and one loop of actions 44.4 to 21.8, reductions' ends in any order where it cannot tell 9.80 to 4.00): knapsack 10.8, matmul 36.4, join 118, sort 55.5 ms without machine code; where each work's time goes now; BFS's arithmetic (a tail of about a tenth of the edges, done batch-side; edges spread into lanes, not walked together) and the three pieces it needs; the view-workers check's flake; 024 and CHECKPOINT say so
* Research 128: the batch executor's appends, recurrences, sums into cells and ↵eunhhu2026-10-063-1/+152
| | | | 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
* 024, 126, 127: the lanes are 24 buffers (stage 2), about 200 KB a thread; ↵eunhhu2026-10-053-4/+7
| | | | stage 2 under ASan and UBSan (139 programs, the executor's output)
* Research 127: the batch executor's stage 2 (nested loops' rounds run ↵eunhhu2026-10-052-1/+66
| | | | 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
* Research 126: the batch executor's first stage (024) as built and measured: ↵eunhhu2026-10-052-1/+104
| | | | 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
* 024: the table with operations apart and interpreted beside the hand-fused ↵eunhhu2026-10-051-34/+36
| | | | 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
* Design 024: a batch executor, loops run 256 rounds at a time by operations ↵eunhhu2026-10-051-0/+136
| | | | 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
* 125: forms and newton runs named; BFS's time after the graph's load is the ↵eunhhu2026-10-052-4/+6
| | | | 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-051-0/+80
| | | | 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
* Pointer induction (023): an inner count's access by a key affine in its ↵eunhhu2026-10-051-0/+8
| | | | | | 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-051-0/+7
| | | | 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)
* The tier's numbers' arithmetic in a run, each read by the next alone ↵eunhhu2026-10-051-2/+5
| | | | | | (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-051-2/+2
| | | | 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-051-1/+8
| | | | | | 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-051-3/+6
| | | | | | 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
* 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-051-0/+89
| | | | 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
* 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
* 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
* Design 022: stored lists as arrays with a bucket index fitted to the keys ↵eunhhu2026-10-051-0/+151
| | | | 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-052-1/+218
| | | | forms by hand beat C only packed, narrow and read ahead (123)
* Measure an index for a stored list's slices outside the list: three times a ↵eunhhu2026-10-051-3/+8
| | | | 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-051-1/+16
| | | | find a slice against C's 21 (021)
* 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-042-3/+8
| | | | 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-041-0/+3
| | | | 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-041-0/+84
| | | | 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-041-0/+160
| | | | 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)
* Compute views with a body on view workers, off the connection threads, asked ↵eunhhu2026-10-041-0/+11
| | | | | | | | | | | | | | | | | | | | 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.
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-20 16:24:48 +0000