| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
| |
5): held as a text is but for UTF-8, its default a constant; a function's bytes in a signature this type too (PURE_SIGNATURE_BYTES gone); no list keyed by bytes; replaced, a text field becomes a bytes field keeping its value (pure_cell_as, kinds_carry); images' headers take its kind; the JSON edge reads it from a string; pure-run shows it as hex; an append asks a record's fields held as bytes from a mask the load makes (record_held) instead of each field's type twice, so b32 runs fewer instructions than b30 (BFS without batches -1.05%, join -0.25%, BFS with batches -0.36%, the rest within 0.04%; the bank's queries s30 against s32 -0.01% to +0.30%); unit test bytes_fields (bytes not UTF-8, a text field replaced by a bytes field, three refused); server_trees with a bytes field; 008 and 027
|
| |
|
|
| |
3): the load gives ITEM_GET and ITEM_SET of a kept list's list field, and LIST_APPEND, LIST_INSERT and APPEND_IN of a kept list whose record holds lists, numbers past the module's (OP_KEPT_*, after verifying and planning: no module holds them, the JIT leaves their blocks to the executor), so the instructions' own steps are as before stage 3; the list module holds a list field's value as bytes (PURE_CELL_LIST only in images' headers and layouts) and text_field is a text's alone again: the stage 3 commit had cost BFS 1.4% of its instructions with batches and 1.7% without (its millions of appends asking each field twice), the five works now within 0.04% of before it
|
| |
|
|
| |
a transient list's records may hold lists (a message's rows not, nor as a key); such a list's cell holds the value in its items' stored form (PURE_CELL_LIST, held as bytes are: each item's fields in order, 8 bytes a number, bool or i64, a u32le length and bytes a text or a list, a list's in this form again), read into one of the event's lists by ITEM_GET (counted in the event's room) and written from one by LIST_APPEND, LIST_INSERT and ITEM_SET, APPEND_IN reading, appending and writing back (undone with the event): images, the log, undoing, readers' shares and commits hold it as a text's bytes, so nothing new is stored or recovered; a list image's header names its record graph (a list field's items' record by its number, the graph's other records after the fields: a record holds itself through a list), and starting or replacing moves the items of the lists in fields by field name down the graph (PureLayout, pure_list_migrate); an event's lists keep the event's lists' numbers; a view lets go the lists a view before it read in; no FIND joined to a list field's read; pure-run shows a kept list's lists; unit tests (an event changing a number and a stored item's list, the process dying at the tree's four stages and the log's two, failed commits changing nothing; a replacement moving a stored and a transient list's lists, their items' record gaining a field and the board's fields changing places; under ASan and UBSan too)
|
| |
|
|
| |
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
|
| |
|
|
| |
walk's spread items (PLAN_FILTER; L only grown there, one filter a list, none in a nested LOOP): each round asked as the batch opens, its code run in the rounds it said no to, those rounds kept (k and the appends' cells) and asked again at the end in the rounds' order (L as it is and what the kept rounds before add), the rest added at once (pure_list_add_many) once the lists take them and the memory budget all of them (else, or a key added there already, the batch gives its rounds back); a list such a filter grows read in the block only as no earlier round's item would change (its count in the guard, its first, a place when it has no key, a field by key). Keys kept as bits (pure_list_bits) asked by a loop of lanes, fields of a DENSE list found at their keys (pure_list_dense); an outer lane's affine value in four bytes. The suite's BFS batched: PURE_JIT=0 93 to 39.6 ms (the compiled code 7.7, C 10). module_tier's walks filter d (seeds 1, 2, 3, 5, 23 alike: 5,806 filters decided in seed 23's); GRAPH_SOURCE: a graph built by a filter, searched twice, marks whose filter adds another key (EXISTS), under work and memory budgets
|
| |
|
|
| |
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
|
| |
|
|
|
|
| |
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
|
| |
|
|
| |
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
|
| |
|
|
| |
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)
|
| |
|
|
| |
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).
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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)
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
