| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
