| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
| |
128) when every list takes its items so (an event's list, no index into it, one append to it: FLAT not keyed at its end, DENSE by keys it holds at its count, HASHED by number; never past its arrays' limit) and the memory budget takes them all (each item only grows what it counts): columns grown and widened once, the first key there already the executor's EXISTS at its round; else round by round as before, tried at once again after a round that changed a list's form. 50,000 DENSE adds 5.18 to 0.65 ms (the compiled code 0.28). APPEND_SOURCE: keys there already at rounds q and p, keys past a DENSE list's from round p, two appends to one list, widened columns, under memory budgets (seeds 1, 2, 3, 5, 23 alike: 31,402 batches at once in seed 23's, 292 by the budget round by round)
|
| |
|
|
| |
(lane forms, locals set before read in every round, ifs, numbers set in items) runs, in the executor, up to 1024 rounds at a time: values uniform, affine or lanes (numbers, or whole numbers in four bytes), branches as masks, cells read by affine rows as strided columns, sets kept to the batch's end and made only when no round reads an earlier round's; a fault, a form it lacks or such a read gives the rounds back to the executor one by one, work counted as written. Planned at load (PURE_BATCH=0: none); the executor of a module without such loops is the same code (run aligned to 64: as many instructions and cycles), with one its own copy. knapsack with PURE_JIT=0: 1,056 to 13.7 ms. module_tier compares batches with the executor alone and makes loops of rounds apart; BATCH_SOURCE: widened columns, -0, a fault mid-batch, rounds reading the last's sets
|
| |
|
|
|
|
| |
bits): one that an index state then asks where an item went is inserted FLAT, whose key set an item's layout key (-1) would read past; the FLAT and tree key sets kept only for number keys. A list read by position checks for HASHED where it is not a tree alone (stored lists: none of it): the bank queries' instructions within 0.5% of 6b45806 (0.3-0.8% before)
text_keys_equivalence asks where an item went in some events
|
| |
|
|
| |
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)
|
| |
|
|
|
|
| |
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
|
| |
|
|
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
often (the bank queries' instructions as before, within 0.4%)
|
| |
|
|
| |
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)
|
| |
|
|
| |
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)
|
| |
|
|
| |
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)
|
| |
|
|
| |
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)
|
| |
|
|
| |
fitted to the keys searched, between events, and build trees from the leaves up: BFS core 89 to 55 ms (022)
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
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).
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
| |
trees for the next event (021)
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
| |
instructions and a search no time (020)
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
| |
bounded (018 stage 2)
|
| |
|
|
|
|
|
|
| |
pure_list_get passed leaf_of(list, at, &within) and within to cell_at
in one call: C leaves the order of a call's arguments open, so within
could be read before leaf_of set it. gcc 14 on AArch64 called leaf_of
first; gcc 13 on x86_64 says within is used uninitialized (found
building Pure there, research 029).
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Counting user-mode instructions per query (bank, 100,000 accounts)
against ee21aec found what i64 had added to the number paths, and an
instruction sampler found where:
- fold_in took a union and asked whether the fold was of i64s for every
item, in the group and leaf-at-a-time passes too, where a fold of
i64s never runs (it is never planned). Those passes now call
fold_number, which takes a double; fold_in keeps the i64 branch for
folds run item by item. per_branch: 27.83M instructions an ask back
to 27.05M (26.72M before i64).
- cell_at's third kind made it too big to inline into pure_list_get,
so every item read became a call. A number's, bool's or integer's
cell is 8 bytes read as they are (memcpy, so no aliasing rule is
bent), one branch as before, and it inlines again. A table of 10,000
rows: 8.78M instructions an ask to 8.70M (8.58M before i64).
Behaviour is unchanged; every check passes.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
An i64 is an int64_t in a value's 8 bytes, its own stack type: CONST and
NUM_TEXT take argument 2 for one, eleven opcodes are appended (ADD, SUB
and MUL fail as overflow past its range, DIV and MOD floor and fail as
divide by zero, NEG, COMPARE with a relation, MIN, MAX, and I64_FROM and
NUM_FROM, which convert only where the value fits and else fail as
limit), and moves (LOAD, STORE, locals, items, FIELD, SEND) copy it as
they copy a number. Type codes: state 6, record field 3, message field 7
(8 bytes), view 4, local 3. v6 stays: all of it is added.
- Folds with PURE_FOLD_INTEGER sum (overflow fails), keep the most or
least of, or count the different i64s; distinct's set keeps an i64's
-1 apart from its free mark. Blocks with an i64 run item by item.
- A list's kinds are its stored header's (number, text, bytes, bool,
integer): integer columns are int64_t, ordered as integers as keys
(found without guide keys for now), stored in 8 bytes and logged as
zigzag varints of any size. Records name their fields' type in one
array (record_field_type) in place of text and bool flags.
- A number, a bool and an i64 carry over each other by one rule,
pure_cell_as, wherever one becomes another: a module replaced, a stored
value or item read by another module, a waiting send recast. A u32
field delivers to an i64 one.
- The host reads i64 fields from JSON, rows and queries as integer digits
in range and nothing else, and shows every digit in views, tables,
deliveries and pure-run. Faults are named by one function,
pure_fault_name, in place of three tables; overflow is new.
test-module: 28 arithmetic cases at the range's ends, relations,
conversions both ways, 14 refusals, a keyed i64 list app (order, a sum
that overflows, a failed add undone, messages and sends of 8 bytes, every
digit as text), recasts, replacement between numbers, bools and i64s, and
three stored runs against memory with restarts (46 images written).
|
| |
|
|
|
|
|
|
|
| |
Before i64 (016 stage 2): a state's value, a record field's default, a
list cell's number, the interpreter's stack slot and an instruction's
constant become unions of a double and an int64_t (PureValue, anonymous
unions in PureCell, Slot and PureOp). LOAD and STORE, and a list cell
made from the stack, copy the bits; everything else reads .num as before.
No behaviour changes: every check passes as it did.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
Each node a list copies once a snapshot shares it went, once the last
snapshot that could read it was released, back to the system: a leaf of
TPC-C's (1.3 KB) past glibc's thread cache, often freed by a connection
thread into the owner's arena, while the owner allocated the next. That
was 70% of what snapshots cost the owner. Now what no snapshot reads
comes back to the app under the register's lock, and each snapshot the
owner makes hands it to the lists of its size as spares, as many as each
made lately; retired entries carry what the pass and the reuse ask of a
node, so neither reads it again. TPC-C in RAM, W=1, 64 terminals: 10-14%
more a second at 7% less CPU a transaction, resident 1.97x the state
bytes where it was 2.18x (docs/research/107).
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
An app's snapshots formed a chain, each holding the next, and what the
app's lists let go while a snapshot was the newest went with it. So one
snapshot held for long held every later one and every node and text let
go since: a surface holding the snapshot of 20,000 items while their
notes were set again grew the node from 6.5 MB to 696 MB in 30 s, 3.4 KB
an update, without end.
A snapshot reads only what was made before it. Snapshots are now
numbered (their epoch, given to the lists' copies and so to each node
and text made after), and the ones held are linked under a register
they share. What the app lets go while a snapshot is its newest goes
with it, as before; when that one goes, what the newest older one still
held may read (made before its epoch) goes to it, and the rest back to
the system at once. The links move under a spin the register keeps; what
is freed is freed outside it. The same held snapshot now costs its
states once: 6.6 MB to 10.6 MB, flat after the notes diverge.
test-module's snapshot_held holds a snapshot through 40,000 events and
snapshots: none of the second 20,000's allocations stays (0 B; with the
chain's keeping, it fails). The kept-snapshots tests read eight held in
random order, and the module tests pass under AddressSanitizer too.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
The sends not yet trimmed were written whole into the links value at
every save, as the numbers heard were: a sender whose receiver is away
or slow saved all its waiting sends again with each new one. They are
now a runtime list {output (its name), seq, payload}, in the order sent,
stored as a list state is (image "0sent" and its changes in the log). A
send is a change of the list with its event; a trim lets the sends go at
once and a failed save brings them back; the host sees the saved ones
(sent_saved). Outputs are named in the items, so a module replaced keeps
them without moving anything; one that lacks or changed an output with
sends left is refused as before. Links stored before (PLK1, PLK2) move
their sends to the list at a start and are stored again without them
(PLK3).
A list field may now hold any bytes (kind 2), unchecked, besides a number
and a UTF-8 text.
Saving 5,000 sends of 16 KB one by one took 84.8 s and left a store of
400 MB; now 0.91 s and 144 MB. 20,000 of 61 bytes: 8.4 s, now 2.9 s.
|
| | |
|
| | |
|
| |
|
|
| |
searched without branches
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
EACH runs the block that follows in a handler once for every item its list
has when it begins, in order, with ROW the item: the block may change
states, the list's items (a field, or removing one) and other lists, but
may not insert into the list it walks, hold another walk or reply, so a
walk runs at most its items times its block. Removing the walked item, or
one before it, moves the walk with it, so no item is skipped. A fold in
the block reads the walked item as OUTER_ROW, as a fold in a column reads
its row. SQL's UPDATE ... WHERE and DELETE ... WHERE are a walk.
A message field may now be rows (type 5, naming a list state): records
laid out as the list's stored form, filling that list, whose flags hold
PURE_LIST_ROWS and whose name is the field's path (order.lines), when the
message arrives; rows that are not whole fail it (limit). A list of rows
is emptied when every event ends, is never saved, and its changes are not
logged for undoing, so a handler walks, folds and counts a message's rows
as any list, and may use one as a scratch table within its event. An
output has no rows. pure_list_clear lets a list's items go.
walks checks a shop against a model over 3,000 random events: orders
whose rows each take stock and are logged, all or nothing (997 applied,
1,322 failed and undone, by an item not stocked or not enough of it), and
a clean that walks the stock removing items (83 while walking, 32 of them
before the walked item). Nine refusals are checked, and 20,000 damaged
walk modules run safely with no rows left after any event; all under
ASan and UBSan too.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
A fold in a table's column runs once per row, over its whole list each
time: per branch, the sum of its accounts read all 100,000 accounts for
every branch, and per rich account, how many are richer read them all for
each of 404 accounts. At load, a planned fold in a column whose test
compares a field of its item with a key the row gives, the rest of it
reading only its list, its item and constants, gets a shape: a group (the
field equals the key) or a rank (a count of items whose field orders
against the key, and nothing else). The app then keeps one pass over the
list per fold and list version: a group pass runs the block a leaf at a
time with the comparison taken as true and the key left out, folding each
item into its field's group; a rank pass radix-sorts the field's values.
A row runs its key alone and looks it up. The pass is made at the second
row that asks, so a fold asked once scans once.
Answers are the fold's own: items join their group in order, so a sum
adds as it would; a key that faults leaves that row to run the fold as
written, and an item that would fault in the pass leaves every row to.
lane_folds now also makes shaped folds (185 groups, 127 ranks, 98 passes
made) and checks them against the same module run item by item.
On the bank of 100,000 accounts: per-branch totals 4.8 ms (16 ms before,
SQLite 46 ms, 14 ms with the index a DBA would add on branch and balance)
and each rich account's rank 6.7 ms (268 ms before, SQLite 2.84 s, 7.6 ms
with an index on balance), HTTP and JSON included on Pure's side. Pure is
given no index.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
A fold ran its block once per item through the interpreter, a call and a
lookup of the item each: counting 100,000 accounts took 4.7 ms and a
per-account rank over them 5.3 s. When every instruction of a fold's
block (or a table's filter) has a lane form, as numbers and indexes with
no branch and no text do, the module marks it at load, and the block
then runs for a leaf's items at once: a value is one per item (a leaf's
column read in place, or computed into a row per stack depth), the
items' positions, or one value for all. Lookups by a value for all items
are made once per fold, not per leaf. Leaves are walked with an iterator
that keeps its path (pure_list_next) and fetches the next leaf ahead.
The lanes only take what the interpreter would compute. Where an item
would fault (division by zero, a non-finite result, a key not found, an
index past the end, a clamp the wrong way round, a fractional move), the
whole leaf runs again item by item, so a fold faults, and a filter leaves
the item out, exactly as before; items join the fold in order, so a sum
adds as it did. lane_folds checks it: 300 rounds of random well-typed
folds in views, in a table's columns reading their row and in a handler
storing them, with a random filter, over random lists, answer bit for bit
as the same module run item by item, 920 faults included by kind and
instruction. list_trees now walks runs too.
On the bank of 100,000 accounts (benchmarks/bank/queries.py), against
the same SQL on SQLite 3.46.1: per-branch totals 16 ms (SQLite 46 ms),
accounts in credit 1.1 ms (6.2 ms), large transfers with their accounts
and tellers 0.77 ms (2.1 ms), each rich account's rank 268 ms (2.85 s),
HTTP and JSON included on Pure's side.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
An item was its own allocation (a share stamp and a cell per field) that
a leaf pointed to, so reading a field of items one after another chased a
pointer to wherever each was made: a count over 100,000 accounts built by
HTTP took 14.5 ms, against 4.6 ms after a restart laid them out in order.
A leaf now holds its items' cells field by field, numbers as binary64
arrays and texts as spans, and pure_list_run gives a leaf's columns to
read item after item.
Copy on write moves to the leaf: a change copies the path including its
leaf, whose texts stay shared; texts carry the share stamp items had, so
one a snapshot may read is retired, not freed. An event's log keeps a
removed item's cells until the event is kept or undone. A node split at
the end of the list leaves the full node full, so lists that grow at
their end (histories, keyed lists filled in key order) fill their leaves.
An account of three numbers and a text now takes 41 bytes in a leaf, not
some 130 across its allocation and the leaf's pointer.
The same count now takes 4.7 ms however the list was built, below
SQLite's 6.1 ms on the same rows. list_trees passes unchanged, and the
app model's tests under ASan and UBSan.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
A list was one array of item pointers: an item's place in the stored form
was found by adding up the sizes of every item before it, so each change
and each appended row cost O(n); a snapshot copied a changed list's whole
array at each save; and a list held at most 65,536 items. A bank of
30,000 accounts ran transfers at 299 us of CPU each, and set up in time
growing with the square of its rows.
Items now live in a B+tree of fanout 32 whose nodes know the items below
them, their stored bytes and the first of them: positions, keys (keyed
lists) and stored offsets are found in O(log n). Nodes carry the list's
share count when made, as items do: one a snapshot may read never changes,
so a change copies the path to it and retires the nodes it replaced, and
a share is a root and a count. Reads in order go through a finger, each
thread's last leaf. A list may hold 2^24 items.
list_trees checks it against a model array: 6,000 events of inserts,
removals and field changes, 1,195 of them undone, up to 8,983 items (three
levels), the stored form equal byte for byte, four shares kept whole while
the list changes on, and 13,959 keyed items found by key as a binary
search finds them. The app model's tests pass under ASan and UBSan too.
|
|
|
The app model, the tree store and the HTTP host lived in
prototypes/connections among the earlier document runtime, the store was
known only by its format's name, and Vega compiled six Pure sources by path.
Now, as the README's principle has it:
core/ runtime, flow and the app model (module*.c), with what the core
asks of storage (state.h, store.h)
store/ the tree store (PURETRE3, PUREREC1)
serve/ pure-serve: HTTP host, outbound delivery, JSON in place
cli/ pure-run, pure-edit-module
A top-level make builds libpure.a (app model and store, for hosts to link)
and the hosts; make check runs the store's and the app model's tests. The
earlier runtime still builds from prototypes/connections against core/ and
store/ (check, check-tree and check-core pass). Design 009 records the rule:
parts by role behind libraries; git repositories split by coupling, so the
store stays here while its contract moves with the core, and Vega stays apart.
|
