aboutsummaryrefslogtreecommitdiffstats
path: root/research
Commit message (Collapse)AuthorAgeFilesLines
* Research 135: batch plans' stage 2 measured (b11 = 7959885 against b10, ↵eunhhu12 days2-0/+100
| | | | 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)
* Research 134: batch plans' stage 1 measured (b10 = a6fabf0 against b9, ↵eunhhu12 days4-1/+152
| | | | 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
* Design 025: batch programs (132's A), the block's facts once at load and ↵eunhhu12 days2-1/+90
| | | | 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
* 042 tiles: knapsack's two passes with the lanes numbered the batch ↵eunhhu12 days2-3/+32
| | | | executor's way (memory's order, ascending): clang -O2 1.87 ms, gcc -O3 2.11, gcc -O2 9.02 (C 6.2, the compiled code 7.9)
* 042 tiles (research 133): a register-tile interpreter in two forms, computed ↵eunhhu12 days3-0/+794
| | | | goto in one function (make.py: GCC spills every slot across the indirect branch) and threaded tail calls with the slots as vector arguments (make2.py: an operation its vector instructions, a load and a branch; clang's musttail, GCC's sibling calls); knapsack's inner loop, BFS's frontier and roots' Newton steps against tight passes and C: roots 5.8 ms (C 6.9, the compiled code 9.57), knapsack 29.4 (passes 2.9 with clang, 9.6 gcc; C 6.2; compiled 7.9), BFS 18.1 (passes 9.8; C 8.6; compiled 7.7); NEON gathers lane by lane cost the tiles what they gain in registers
* Research 132 (no code): where the batch executor's cost sits (an element's ↵eunhhu12 days2-0/+28
| | | | 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
* 041 runs of b8 = d0558a3 and b9 = 33e9908 (the suite three ways and counts: ↵eunhhu12 days4-0/+618
| | | | batches BFS 24.0 ms, the compiled code 7.7, alone 92.7; knapsack 11.45 and matmul 40.0, up from b7's 10.3 and 36.5; the executor alone as before) and the search counts on b9 (BFS 112 instructions an edge, 57 cycles; the frontier sum 56 and 20; the compiled code 38.5 and 19, 35 and 15)
* 041 runs of b7 = 1f8faac (the suite three ways and counts: batches BFS 41.0 ↵eunhhu12 days7-0/+549
| | | | ms, the compiled code 7.66, alone 93.4; the others and the executor alone as b6's) and search/: the suite's graph loaded and one handler run again and again (frontier-run: each node's edges' to summed, 70 instructions an edge batched, 35 compiled; search-run: the BFS, 211 and 38.5), counted with icount (2026-10-08-search-counts.jsonl)
* 041 runs of b5 = bdfc4d7 and b6 = de9efad: batches knapsack 10.84 ms (the ↵eunhhu2026-10-067-54/+800
| | | | compiled code 7.93), matmul 36.41 (14.20), join 118.3 (78.7), sort 55.5 (35.6), roots 8.87 (9.57); the executor alone as many instructions as b4's; costs three ways on b5 and b6 (tagged by version, b4's too: adds 0.65, ops 4.00, recur 21.8, recur4 36.0); frontier.c: the suite's BFS as frontier batches (105,232 of 999,913 edges asked again in order, 99,997 added; walking a batch's edges together 2.17x the edges)
* Batch: a recurrence's steps each an operation of two numbers a round keeps ↵eunhhu2026-10-061-0/+11
| | | | (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
* 041 runs of stages 4 and 5, sums into cells and walks (b3 = 06c2978, b4 = ↵eunhhu2026-10-0614-0/+853
| | | | 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)
* 041 runs of stage 2 (b2 = 76b4e3d): batches roots 9.13 ms (the compiled code ↵eunhhu2026-10-053-0/+301
| | | | 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
* 041 runs.sh: the suite three ways (the compiled code, the executor with ↵eunhhu2026-10-055-0/+384
| | | | 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
* 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
* 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-051-0/+2
| | | | 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-052-0/+217
| | | | 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-052-0/+104
| | | | 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)
* 040 forms.c: matmul's inner loop in the forms the tier may make it (index ↵eunhhu2026-10-052-0/+93
| | | | 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
* 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-058-0/+568
| | | | 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
* Read a slice's bucket and first cell some rounds ahead of the loop that ↵eunhhu2026-10-051-1/+6
| | | | 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)
* Design 022: stored lists as arrays with a bucket index fitted to the keys ↵eunhhu2026-10-056-7/+283
| | | | 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-0572-0/+1024
| | | | 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-052-0/+113
| | | | 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-053-0/+75
| | | | find a slice against C's 21 (021)
* The same answers on the final build and the same pure-runs on the Pi, WSL2 ↵eunhhu2026-10-044-0/+145
| | | | and a Mac (121); 019 points at 020's view workers
* Measure views off the connection threads: writes' tail as with the CPU ↵eunhhu2026-10-049-3/+71
| | | | 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-0466-0/+399
| | | | fingers found and undone (121)
* 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
* Wait for a counter before searching in bfs-run, and the runs of research 121eunhhu2026-10-042-0/+67
|
* Say where a search's time goes and how to make it and long views fast, with ↵eunhhu2026-10-041-0/+83
| | | | criteria (020)
* Wake each thread at most once a push, end streams only of stopped apps, and ↵eunhhu2026-10-043-0/+93
| | | | show a subscriber costs writes nothing (019)
* Say what pushing views costs and how fresh it keeps them (019, research 120)eunhhu2026-10-0451-0/+365
|
* Say what views that compute cost the writes beside them (018 stage 3, ↵eunhhu2026-10-046-0/+299
| | | | research 119)
* Say what computing in one event costs and finds (018 stage 2, research 118)eunhhu2026-10-043-3/+95
|
* Measure 018 stage 2: a graph search in one event, the pairs, and runs to ↵eunhhu2026-10-0434-0/+511
| | | | compare across machines (033)
* Say what a transient state saves a write (018 stage 1, research 117)eunhhu2026-10-043-0/+87
|
* Say what an app's tokens cost (017 3b, research 116)eunhhu2026-10-042-0/+109
| | | | | | | | Requests to an app that checks tokens go 2.92% slower than to an open one on 64 keep-alive connections, 2.2% of it the head the token makes longer (an open app sent the same head is as slow); hashing every request on a new connection costs 0.91%. 031 measures the three in turns.
* Say what apps that change on a running host showed (017 stage 3, research 115)eunhhu2026-10-0443-14/+605
| | | | | | | | | | Changing an app in place keeps a million items' app answering but for 1.12 ms (a host restart: 150 ms; stopping and starting it again from its store, as first built, 150.4 ms), 171.5 ms when its records change shape (332 ms). Another app's p99 stays 0.97 times as it was while one changes every 0.2 s; a host of one app is as it was (TPC-C +0.7%, instructions at most +0.02%); each module change leaves 19 KB. 030 holds the windows of both builds, the isolation, the pairs, the counts and the memory.
* Measure how long an app changing module cannot answer, against a host ↵eunhhu2026-10-046-0/+293
| | | | | | | | | | | | restart (030) An app of a million items (a list grown by doubling) or of a thousand, in a host of apps, its store in RAM: the longest gap between two answered writes while it changes module on SIGHUP (stopped and started again from its store, 71e319b), and while the host is restarted. A thousand items: 1.59 ms against 3.05 (median of 20 and 10). A million: 150.64 ms against 149.73 (10 and 5): both are the store read again (pure_app_start, 142 ms), so changing does not answer sooner than restarting.
* Trade stores with the WSL2 too: its bytes are the Pi's (029, research 114)eunhhu2026-10-044-0/+27
| | | | | | The same events make byte-identical stores on the x86_64 WSL2 (4 KiB pages) as on the Pi and the Mac, and a store made on either of the Pi and the WSL2 opens on the other and goes on the same.
* Run Pure and aup on an x86_64 WSL2 and an M3 Mac against the Pi (029)eunhhu2026-10-0226-0/+3806
| | | | | | | | | | Every pure-run of aup's check (1,053 runs of 667 modules) gives the same output, errors and exit on the Pi, the WSL2 (x86_64, 4 KiB pages, gcc 13) and the Mac (Apple clang 21); the same events make byte-identical stores on the Pi and the Mac, and either opens the other's and goes on the same. Pure's checks pass one at a time in WSL (each_check.py); its wall clock is set back about 2 s every 32 s (clock.py). stores.py streams pure-run's output, whose size grows with the square of the events.
* Run experiments under a memory guard, so they cannot freeze the Pieunhhu2026-10-021-0/+110
| | | | | | | | | | | The Pi has 8 GiB, zram swap and no OOM daemon, and the user's systemd holds no memory controller: a run that outgrows its memory has every program's code evicted before the kernel kills anything, and the machine stops answering. It was reset twice so (a run held 13 GiB of output it should have streamed). guard.py runs a command in a session of its own and kills the session when it holds more than --most MiB (3072) or the machine has less than --floor MiB available (1024, a tmpfs filled counts), and stops what it leaves running.
* Measure wires on the sending loop, and a host's threads (028)eunhhu2026-10-016-7/+211
| | | | | | | | | Five rounds of 1,000 bursts by one wire, four wires, one link and four links: a thread each (966b82f), links on the loop (94e7bb8), wires on it too (5f5603c). Medians: one wire 774k, 782k, 779k sends/s; four wires 629k, 625k, 615k (the same CPU a send); one link 581k to 948k; four links 485k to 811k. A host whose app sends to ten links and ten wires has 24 threads before and 5 after (3 with no output).
* Measure one sending loop against a thread a link, with and without push (028)eunhhu2026-10-017-0/+338
| | | | | | | | Five rounds of 1,000 bursts by one link, four links and one wire, four builds in turns: a thread a link (966b82f), those threads with push (threads-push.patch), the loop (99b2219), the loop with push (94e7bb8). Medians: one link 597k, 923k, 525k, 897k sends/s; four links 506k, 799k, 268k, 800k; the wire as it was, 789k to 794k.
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-20 15:38:21 +0000