aboutsummaryrefslogtreecommitdiffstats
path: root/docs/design
Commit message (Collapse)AuthorAgeFilesLines
...
* 024, 126, 127: the lanes are 24 buffers (stage 2), about 200 KB a thread; ↵eunhhu2026-10-051-2/+3
| | | | 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-051-1/+1
| | | | 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-051-1/+4
| | | | 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-051-1/+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
* 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)
* 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-051-1/+2
| | | | 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-041-2/+3
| | | | and a Mac (121); 019 points at 020's view workers
* Say 020 is built and measured (121, 122)eunhhu2026-10-041-1/+1
|
* 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.
* Keep one finger a thread, as before: four cost the bank's queries ↵eunhhu2026-10-041-4/+6
| | | | 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-041-1/+18
| | | | | | | | | | | | | | | | | | | | 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.
* Say where a search's time goes and how to make it and long views fast, with ↵eunhhu2026-10-041-0/+84
| | | | criteria (020)
* Say what pushing views costs and how fresh it keeps them (019, research 120)eunhhu2026-10-041-1/+1
|
* Push a view's value to its subscribers over SSE, once per group and interval ↵eunhhu2026-10-042-1/+10
| | | | (019)
* Fix 019 before building: compare equal freshness, bound pushes per interval, ↵eunhhu2026-10-041-9/+24
| | | | carry streams across module changes
* Say how pure-serve pushes a view's value to its subscribers, and what it ↵eunhhu2026-10-041-0/+91
| | | | must show (019)
* Say what views that compute cost the writes beside them (018 stage 3, ↵eunhhu2026-10-041-1/+2
| | | | research 119)
* Say why stage 3's first isolation criterion could not hold, and what to ↵eunhhu2026-10-041-0/+21
| | | | measure instead (018)
* Let a view compute in its body, on a reader's own lists (018 stage 3)eunhhu2026-10-042-5/+16
|
* Say what computing in one event costs and finds (018 stage 2, research 118)eunhhu2026-10-041-1/+2
|
* Count in loops that nest, break, and keep an event's own lists, every event ↵eunhhu2026-10-042-10/+30
| | | | bounded (018 stage 2)
* Say what a transient state saves a write (018 stage 1, research 117)eunhhu2026-10-041-1/+2
|
* Keep transient states the app's while it runs, never stored (018 stage 1)eunhhu2026-10-042-5/+13
|
* Say how aup chooses what a state outlives, and computes in memory (018)eunhhu2026-10-041-0/+199
|
* Say what an app's tokens cost (017 3b, research 116)eunhhu2026-10-041-1/+9
| | | | | | | | 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 how an app's routes take tokens, and what it must show (017, 3b)eunhhu2026-10-041-1/+30
| | | | | | | | | An app given a tokens file (tokens=FILE, --tokens FILE) takes requests bearing a token whose SHA-256 the file lists: read for its views, queries and documents, write for all, input=NAME for one input alone; 401 without one, 403 past its grant. A delivery another node sealed needs none: its key told who sent it. A connection keeps its last token's grant; a reading swaps the tokens without stopping the app.
* Say that reading the code found stage 3's two races, and how a host changes appseunhhu2026-10-041-2/+2
| | | | | | | | | The use after free in local_done and the owner's lock made after another app's outlet used it were found reading the code, not by the check, which passed with both before it was made to change senders (115, 017). The usage now says changed lines change in place unless their store moved; and 115 names the path no check takes: a module refused while changing in place.
* Say what apps that change on a running host showed (017 stage 3, research 115)eunhhu2026-10-041-6/+24
| | | | | | | | | | 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.
* Say how apps start, stop and change on a running host, and what it must show ↵eunhhu2026-10-041-1/+76
| | | | | | | | | | | | (017, stage 3) The --apps file is the host's shape: on SIGHUP the host reads it again and starts the apps of new lines, stops those of lines gone, starts again those whose line changed (states carried by name from the store) and those stopped or uncertain. A request carries the module it was resolved with, and is not applied under another (503 stopped); link streams and local outlets look their input up again. Route authentication (3b) is designed apart.
* Say what one sending loop showed (017 2b, research 113)eunhhu2026-10-011-6/+22
| | | | | | | The loop alone slowed four links to half: woken by every record queued, it chased the owner a record at a time. Pushing once a turn made links 1.6 times as fast, with threads or the loop alike; the loop's own cost is within the noise. Twenty outputs now add two threads, not 21.
* Say how sends will share one loop, and what it must show (017, 2b)eunhhu2026-10-011-3/+18
| | | | | | | | | | | | | | | | Each link and each HTTP wire sends on a thread of its own: a host with twenty outputs runs twenty-one threads more than one without. 2b moves them into one sending loop: an epoll over the links' UDP sockets and the wires' TCP sockets with one wake, waiting until the soonest link timer or wire pause. Links (2b-1) do in the loop what their threads did each round; wires (2b-2) become a non-blocking HTTP/1.1 client state machine, with non-blocking steps added to the crypto table for TLS. A name looked up again still waits where it is, and says so. Before building: every link, wire, answer and seal check green; a host of ten links and ten wires two threads above one without; and link and wire throughput, alternated before and after, no more than 5% lower at the median (four links together: 10%).
* Say that apps of a host send to each other and to other nodes (017)eunhhu2026-10-011-2/+13
| | | | | | | | Stage 2 is built and measured: what was learned (the receiving side needed nothing new, an output goes one way only) and the numbers. The checkpoint adds sending to the many-apps row, and keeps 2b (one loop for the send threads) and stage 3 (apps added and replaced while the host runs) among what is left.
* docs: link aup and vega via clean web paths instead of raw server pathseunhhu2026-10-011-1/+1
|
* Say how apps will send to each other and to other nodes, and what it must ↵eunhhu2026-10-011-2/+41
| | | | | | | | | | | | | | | | | | | | show (017) Stage 2: each app of --apps takes its wiring (send=, seal=, reply=), its sends' source being APP.OUTPUT; one --link-port takes every app's inputs, a stream's input name APP/INPUT (012 unchanged); and send= OUTPUT=APP/INPUT hands an app's saved sends to another app of the same host with no socket, seal or packet: an outlet with the window links have, a batch of records as a link delivers them put in the receiving app's queue, applied after its last number heard, and the number heard after its save trimming the sender's outbox. Merging the send threads into one loop is split off as 2b. Before building: it goes in if the inner outlet stores at least as many sends a second as a loopback pure:// link between the same two apps, at half the host's CPU a stored send or less; checked by a host sending to an app of its own and to one of another host, exactly once and in order across a kill -9, and held back by a full receiver.
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-20 15:30:27 +0000