| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
| |
byte the same, the executor alone moved matmul +0.43% and BFS -0.34% (knapsack, roots, join within 0.03%; the bar of 0.1% missed, mixed signs: four cases more in step), the bank's queries -0.22% to 0.00% (bar 1%); the four cases out of line in a noinline function (b23) cost 6-15% of the executor's instructions (a call taking frame from step: the register cliff) and were taken back; CHECKPOINT's direction row through 027's stage 1
|
| |
|
|
| |
examples/sha256.aup) right for FIPS 180-2's examples and 138 more messages on every path, in make check against hashlib; 52 lines against Python's 28 (the bar missed: no formatting, no bytes joined or sliced, no lists as values, moved into stage 2), 176 times C's time and 0.43 of plain Python's (1,591 ns a byte; a block's 19,129 instructions, 39% of them the inlined fn's literals not folded); 044's check, time.c against the same algorithm in C (digests compared first) and the Python reference
|
| |
|
|
| |
xor, a left shift as a times 2^b failing as overflow past the range, a right shift as floor(a / 2^b), a count outside 0-63 failing as limit: integers in two's complement without end), BYTE_AT (the byte of any bytes value at a whole position, a number or an i64, else limit), BYTES_OF (a list of one i64 field as bytes, a value outside 0-255 failing as limit) and INDEX_AT (a list's item at a position, not_found where there is none); the fold-shape and batch analyses count their arity and the lists they read; unit tests of the ends (27 bit cases, 11 reads of a constant's and a text state's bytes, 7 refused)
|
| |
|
|
| |
typed value built of bool, i64, number, bytes (text the UTF-8 ones), records, variants and lists of anything (an unkeyed list keyed by position), anchors for cursors and indexes; functions that may recur and while, ending by the budget as EVM's gas (the module the unit of determinism); bit operations on integers as infinite two's complement within i64; folds left folds in meaning, reordered by the implementation only for the same answer; meaning apart from representation; answers to 026's suspects; five stages (bytes, bits and lists of numbers for SHA-256; nesting, variants, recursion and characters for JSON; nested state stored; patterns gathered; the number model) with bars
|
| |
|
|
| |
inflate, JSON, UTF-8 and line breaking, relational queries and graphs, text editing, box layout, HTTP/1.1 by packets, retries and timeouts, constant-time crypto) with five criteria (written in aup and Pure alone, no workaround, lines against a Python reference, time against C, the spec's own vectors passing in Pure's checks on three machines); ten probes (044) show today's aup stops at a byte by position, bit operations, nesting, recursion, variants and reading a character; the core's minimal candidates and the rule against piling up (only what two specs need); SHA-256 and JSON first
|
| |
|
|
| |
1.0: an event a total, atomic, deterministic function step(S, E) -> (S, Out*) or a fault (budgets in instructions and bytes), time an input, views pure functions of the committed snapshot, the history seen a prefix of commits, delivery in order and once with the transport's state in the store, values the same on every path, replacement joined by names; the layers it removes; its own suspects (input and view kinds, cursors and indexes, keyed documents, the number model, the budget's unit, fixed limits); the computation language rebuilt before 1.0, no compatibility kept before it (the user's word)
|
| |
|
|
| |
spare_count they moved its large arrays and knapsack ran 7% slower at the same instructions (8.79 against 8.29 ms), at its end about 2% (8.45); research 139's afterword: 026 not taken heavily (the user's word), the one light cut made (a nested count loop's rounds sweeping only when few lanes are left: matmul 25.85 to 24.3 ms), the walk loops kept sweeping each round (held, BFS's batches ran out), and the stop; 041 runs of b21
|
| |
|
|
| |
back only when fewer are left than the most a round has taken and one (fresh and new_mask keep the fewest left; nested rounds' marks given back to the rounds around), else once after the loop as the last round did; matmul 3.6% fewer instructions, 4.5% fewer cycles (a sweep a k-round); a walk's rounds and a spread walk's chunks still sweep each: so held, BFS's batches ran out of lanes and went back to the executor (36.9 ms, the answers the same), what their filters and selections take not told by a round's fewest left; seeds 1 2 3 5 23 (default and PURE_SELECT=all), the fixed sources (also sanitized), the unit tests and ASan's pass
|
| | |
|
| |
|
|
| |
deciding prototype 043): the executor's extra over 041 is interpretation, not semantics (matmul 11.1 ms of it, checks 0.2); the program interpreted a step at a time, with the executor's checks, ran matmul's loop in 10.36 ms and knapsack's in 4.16 (straight kernels 7.17 and 3.76; the executor about 22.2 and 7.3), about 14 and 5.4 ms with the making (bars 15 and 6.5; the compiled code 14.2 and 7.9); the buffer rule it found (registers at load, two buffers each so a result never lands on its operand, 24 lanes apart); the suite's five bodies sorted (matmul, knapsack, join's order loop straight-line; roots and BFS not); 026's scope as straight-line programs with the pass for the rest, and its risk
|
| |
|
|
| |
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)
|
| |
|
|
| |
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
|
| |
|
|
| |
lists' loops so aligned cost the bank's queries 0.8-2.0% more instructions (the padding) with their cycles mixed
|
| |
|
|
| |
line (-falign-loops=64 in LIST_OPTIMIZE): a change anywhere in module-batch.c moved knapsack's hot loops and it ran 8.26, 8.74 and 8.20 ms with the same instructions; aligned, every batched work's cycles fell (knapsack 6%, matmul 1.8%, BFS 1.1%) and the executor alone stayed within its noise, at 0.7-2.3% more instructions (the padding)
|
| |
|
|
| |
(an add of the key it asked, as a filter's is, takes the place found) and clears only the words of the bits it set (their places kept as it sets them): BFS 0.4% fewer instructions; seeds 1 2 3 5 23 (default and PURE_SELECT=all), the fixed sources (GRAPH's exists, memory and work faults where they were) and the unit tests pass
|
| |
|
|
| |
round 0 (sums_in_words): the rows and e's in four bytes first (vector code) up to the first round whose e is not a whole number below 2^32, then each round's sums in turn in integers for a one- or four-byte cell while it stays in its bytes, as a number for an eight-byte cell while finite; where one is not so the executor's way goes on from that round and sum (nothing faulted or widened before it); join 4.9% fewer cycles; SUMS_SOURCE in check.py (sixteen rows met again and again, a one-byte column widened mid-batch, a four-byte one past 2^32, a masked fraction), 7,912 rounds at once and 3,228 the other way, the same three ways; seeds 1 2 3 5 23 (default and PURE_SELECT=all), the fixed sources (also sanitized) and the unit tests pass
|
| |
|
|
| |
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
|
| | |
|
| |
|
|
| |
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
|
| |
|
|
| |
in its own loop (TEST, a vector add in the same loop) and its value carries the count (ones), so the branch after it in every running lane needs not count them; seeds 1 2 3 5 23 (default and PURE_SELECT=all), the fixed sources and the unit tests pass
|
| |
|
|
| |
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
|
| |
|
|
| |
memory's order in four or eight bytes is a view of the column itself (cells_at), no copy, read only while the pass runs; what outlives the pass (a local, a set's rows and value, an append's cells, a sum's rows and e, a filter's key, a read's rows) copies it (own); knapsack 4.0% fewer instructions, 6.6% fewer cycles; VIEW_SOURCE in check.py (a local holding a field the batch sets, a set from the same column in the order that overwrites what it reads, a set widening the column under a view), which differs and trips ASan's memcpy overlap when the copies are left out; seeds 1 2 3 5 23 (default and PURE_SELECT=all), the fixed sources (also sanitized) and the unit tests pass
|
| |
|
|
| |
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)
|
| |
|
|
| |
its pass reads): no list changes while the pass runs (sets, appends and filters wait for its end, which reads its own); find and item_get read them there; matmul 2.3% fewer instructions (two finds a nested round), knapsack and BFS 0.4%; seeds 1 2 3 5 23 (default and PURE_SELECT=all), the fixed sources and the unit tests pass
|
| |
|
|
| |
uniform max and min, a fraction, a sum past 2^53, a count in a nested loop, the same e then a masked or a lane's own and the other way), against the rounds one by one and the compiled code; it makes lanes from the one number 56 times and folds the one number 77 times
|
| |
|
|
| |
no lanes while every lane's e is the same), interleaved with b11 and b12, and their counts: matmul 36.10 to 26.56 ms (instructions -20%), roots 8.82 to 8.31 (-6.1%), the executor alone as b9 on all five
|
| |
|
|
| |
while every step adds (or takes the least or most of) the same e in every lane, every lane's partial is one number and its count one count, made as each lane would make them; the first step that differs makes the lanes from them; fold takes n times the one number (whole numbers below 2^53, as the lanes' sums) or folds it in the rounds' order; sum0 6.09 to 1.01 ms; seeds 1 2 3 5 23 (default and PURE_SELECT=all), the fixed sources and the unit tests pass
|
| |
|
|
| |
ms against 21): the arithmetic left out the nested rounds' interpretation (about 15 ms) and the matrices' making (4-5 ms)
|
| |
|
|
| |
(POSIX's select in a build without -std=c17 refused the file)
|
| |
|
|
| |
below 2^32 of whole numbers below it in four-byte lanes, past it the product's high half sends the lanes back to numbers as ADD's sum does (umull and umull2 over four lanes); matmul's products and sums stay in four bytes; seeds 1 2 3 5 23 (default and PURE_SELECT=all), the fixed sources and the unit tests pass
|
| |
|
|
| |
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)
|
| |
|
|
| |
unit tests in three modes and under ASan (executor mode too), the sanitized pure-run's fixed sources and seed 23 (both modes), make check and aup's checks in both modes pass
|
| |
|
|
| |
instructions that make one uniform or affine value (constants, fields, LOADs, a walk's item, locals the block does not set, the loop's value, a nested count loop's, a local a segment set once before; a field at a uniform row; arithmetic and comparisons) and their LOCAL_STORE, planned at load and run at once in scalars by the pass's rules when the batch runs plainly, the pass's own way when a value is not as planned; the check (PURE_BATCH_CHECK) runs each dry and compares with the pass's own: seeds 1 2 3 5 23 (default and PURE_SELECT=all), the fixed sources and the unit tests pass, seed 23's programs checking 312,249 segments in 213 of 650 runs
|
| |
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
the unit tests in three modes and under ASan (executor mode too), the sanitized pure-run's fixed sources and seed 23 (both modes), make check and aup's checks in both modes pass
|
| |
|
|
| |
their locals, updates and steps, records and a round's actions in the plan, a number that stays planned by its source (a constant, field, LOAD or local the block does not set: the same source one number, two sources of the same value two) and filled in as a batch opens, the pass finding an update or a record by its instruction's role; the check compares updates, records and whether the batch holds them with the block read again each batch: seeds 1 2 3 5 23 (default and PURE_SELECT=all), the fixed sources and the unit tests pass
|
| |
|
|
| |
load (pure_batch_plans, after its instructions' plans are final): the locals it sets and whether it sets items, its sums into cells, and at each instruction a role (a sum's again, add or set) and how far on a LOCAL_LOAD's x = x op e is; batch_run, pass and local_load read the plan instead of scanning the block each batch; PURE_BATCH_LANES to build other lane counts; PURE_BATCH_CHECK (a build flag, while the stage is made) reads the block again each batch and stops if the plan differs; seeds 1 2 3 5 23 (default and PURE_SELECT=all), the fixed sources and the unit tests pass with it
|
| |
|
|
| |
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%)
|
| |
|
|
| |
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
|
| |
|
|
| |
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)
|
| |
|
|
| |
clang -Wpedantic refuses
|
| |
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
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)
|
| |
|
|
| |
are (a loop's value gathered: the end's checks know them, where lanes of rows gave the batch back: knapsack 48 to 11.5 ms); a module with no value planned for reuse spares the batch the looks (reuses); local_load inlined again
|
| |
|
|
| |
as an earlier one in a line of the block (nothing between setting what it reads: planned at load, reuse_from and reuse_length) is taken from the earlier, kept for it; if !c { ... } one branch the other way, no NOT; an arm whose lanes are a quarter or fewer runs in those lanes alone (a selection: outer values gathered by sel, reductions into their lanes around, locals set given back masked at its end, stores and sums expanded, appends and a filter's kept rounds by sel; PURE_SELECT=all every straight arm, 0 none); a list whose keys are bits asked by them in one loop of lanes, a filter decided by its bits and bits of our own (no hash set; a key with no bit is not there); L.first + i affine while within the list; a slice's two bounds in one call (pure_list_slice); a filter's kept rounds copied from numbers made once. The suite's BFS 211 to 112 instructions an edge (the compiled code 38.5), 41.0 to 23.5 ms; the frontier sum 70 to 56 (35). Seeds 1, 2, 3, 5, 23 alike by default and with every arm selected
|
| |
|
|
| |
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
|
