| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
The work budget added about 26 instructions to every row of a table a
host shows (bank, a table of 10,000 rows: +3.0% instructions an ask),
which 017's one-app criterion allows at 1%. A sample put most of it in
show_given asking every cell why it failed, and the rest in evaluate
and the row lookup writing that reason and the count for every cell.
Now nothing is counted without a budget (PureApp.work stays), the
reason is written only when a view, a cell or a row has no value, and
pure-serve asks it only of a cell without one. The table: +0.94%; the
other bank queries within 0.4%. The tests that read the count set a
budget that is never reached.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
An event's run was bounded only by its lists: a walk or a fold is its
block's length for each item, and a list holds up to 16 million. One
event could hold the owner for seconds, one view a connection thread.
pure_app_work(app, n) budgets one unit of work: an event, or one
evaluation of a view, a cell or a table's filter. It is counted as
written, as each part begins: a block's length, and a fold's or walk's
block length for every item of its list (or slice), whatever the plan
runs (lanes, a group or rank pass, a range). Nothing is counted inside
the interpreter's loop. Past the budget an event fails with the new
fault work and changes nothing (PURE_LIMIT, so 422 work over HTTP); a
view, a cell or a table's rows have no value and pure_app_view_fault
says work, which pure-serve answers 422 work, for a whole table when
a cell of it ran past. pure-serve --work N sets it (0: none).
test-module counts exact amounts on the shop's walk, the tasks' fold
view and a filtered table, and lane_folds now checks that a planned
fold counts what the same fold run item by item counts (3,600 folds,
every view, cell, filter and handler). server_work grows a list over
HTTP until the walk, the table and the fold each pass a budget of 400.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
A condition was a number, non-zero being true: a flag was a number field,
a view showed 1 for true, and nothing kept a number from standing for a
bool or a bool from being added to. Now the verifier has a bool among its
stack types, and a verified module never mixes the two. No opcode is new:
- CONST with argument 1 is a bool (+0 or 1), NUM_TEXT with argument 1
writes one as true or false; LOAD and STORE take a number or a bool
state, locals may hold a bool (2).
- Comparisons (LT to NE, TEXT_COMPARE) and LIST_HAS give a bool; AND, OR
and NOT take and give them; JZ, REQUIRE, filters and folds' tests take
one (count and first leave a bool, sum, max, min and distinct a number
and a bool); EQ and NE compare two bools too.
- Type codes: state 5, record field 2, message field 6 (one byte in the
prefix, 0 or 1, or the message fails as limit), view 3. A bool's
constant, initial value and default are +0 or 1; a list is not keyed by
one. PUREMOD6: v5 modules are built again.
At run time a bool is a number's 0 or 1, so leaf-at-a-time folds run as
before. A number that becomes a bool (a module replaced, a stored state
or item read again, a waiting send recast) keeps 0 (either sign) and 1
and takes the default otherwise; a bool that becomes a number is 0 or 1.
The host carries bools on every boundary: JSON true and false only (a
row's field too), a query's true and false, true and false in views,
table JSON and HTTP deliveries; a link takes a bool only into a bool.
A stored outbox's field types were read back with a check that refused
bool (at or past rows): a node whose output had a bool field and a send
waiting could not start again. test-module now stores such a send and
opens it (it fails on the old check), beside 28 bool refusals of the
verifier and bool states, fields, views, sends, links and migration.
The lane generator makes numbers and bools apart.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
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).
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
A message from another node was taken only in its input's exact shape
(the link's STREAM shape, fields and order alike; over HTTP, every
field). So a board whose nodes are upgraded one after the other stopped
both ways until both were, and an output and its input whose fields
differ only in order were refused for good (docs/design/014).
An input now takes a message when it has every field the sender sends,
by name, of the same type or one that holds its values (a u32 in a
number, text in bytes); a field only the input has is 0 or empty. One
that sends a field the input lacks is refused: taking it would drop the
value, and with its number heard the value would never come again (two
boards apart for good). So add fields to receivers first and take them
from senders first, and nothing stops or is lost.
The link carries a sender's fields in a new frame, FIELDS (0x0d: names,
shape, u8 count, each {type, name length, name}): after a REFUSED for
another shape the sender puts it in its packets (after OFFER, before
the records, so a receiver that knows no FIELDS reads what it read
before) until the stream is taken, the first time at once. A receiver
seeing another shape waits for the packet's FIELDS before refusing, and
asks its host with them (PureLinkHost.input takes them); REFUSED says 4
when the input lacks a field. Deliveries carry the fields and the host
lays each record out anew (pure_module_takes, pure_module_recast,
pure_module_fields, over pure_send_recast's rule). A stream whose sender
starts again in another shape lets go what it held; the sender sends it
again laid out anew. A refusal already queued for a stream now says the
last reason judged, not the first. Over HTTP a delivery (X-Pure-Source)
may lack fields; an unknown member is still refused.
test-link named: a stream of another shape naming its fields is taken,
200 stored in 47 ms with every delivery naming them; an input that does
not take them refuses (4) and the sender backs off. check.py
server_fields: five outputs, three linked and two over HTTP, fields in
another order taken, an input with a field more taking messages without
it, one lacking a field refusing until it starts again with it, then
taking all. server_upgrade's new receiver declares its fields in another
order. 012 names the frame and the rules.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Under AddressSanitizer with leaks counted, the module checks lost 672
KB in 10,185 allocations. Two causes, both from the snapshot rework
(d1e8f38):
- A snapshot's register counted its snapshots with ++ under its spin,
but a snapshot's last release took one off atomically outside it. A
release on a reader's thread racing the owner's next snapshot could
lose either change: the register then outlived every snapshot (the
leak seen), or went while one still used it. The count is atomic now.
- pure_app_stop handed what its lists let go to the newest snapshot (or
freed it) and only then freed the outbox and the numbers heard, whose
shared nodes and texts went to that hand-over's list again, for good.
They are freed with the other lists now.
make check builds the module checks a second time under AddressSanitizer
and UndefinedBehaviorSanitizer (build/test-module-sanitized, 25 s) and
fails on a leak. Before d1e8f38 the same build stops at a
heap-use-after-free in retire; now it is clean.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Review 004's F3 made a module refuse to start while sends waited on an
output whose fields it had changed: their bytes would have meant
something else. Safe, but it deadlocks a rolling upgrade. Growing a
board shared by two nodes: one upgraded to a card with a new field
refuses the other's old sends (another shape), and the other, its old
sends waiting, cannot start the new module at all ("Cannot start the
module on the store", saying nothing more).
Waiting sends now move to the new fields by name, as a list's items do:
a value goes over when the new type can hold it (u32 and number are
numbers, bytes and text are bytes; a number that is not a u32, or bytes
that are not UTF-8 for a text, cannot), the rest start at 0 or empty
(pure_send_recast, with the payload layout load uses, pure_fields_lay_out).
A start recasts them and a replace does into a new outbox.
Their meaning must survive a crash between the recast and the save that
names the new fields in the links. So the outbox's image now names the
fields its sends were laid out with ("PLO1": the module's outputs after
the save it holds), and is written again before any send is logged with
other fields; a start reads those names over the links'. Checkpoints of
the outbox name them too.
A module without an output that sends wait on is still refused, now
saying so in PureApp.why, which pure-serve prints ("sends wait on the
output 'ordered', which this module does not have"); a failed start
keeps it.
test-module send_recast (widened, narrowed, UTF-8, a payload not laid
out, there and back) and output_meaning (the swapped fields recast on a
replace, read right after a restart that never saved, back again, sends
logged after the image, the refusal and its reason). check.py
server_upgrade: five sends wait on the old output, the sender starts
with the new one, the old receiver refuses the new shape, the new one
takes all eight.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
A link's ring and a wire's queue took every saved send of their output
and kept it until delivered: with the receiver down they held the
outbox a second time, 178 B and 313 B more a send (104). Each outlet now
holds a window, --window bytes (4 MiB) and 65,536 sends past what its
receiver has, at least one; the outbox keeps the rest.
The owner remembers each outlet's place in the outbox and looks on from
there after a save and after its transports deliver. Places move back by
the sends that left the outbox since (PureApp.sends_gone), so a trim
before a place skips nothing, and sends queued before are not looked at
again however many wait. pure_app_sent reads a send by its place (the
newest-first visit it replaces is gone); pure_link_held and
pure_wire_held say what a transport holds.
With the receiver down a node now grows by the outbox alone once the
window is full: 219 and 218 B a send over the link and HTTP (399 and
534 B before). check.py server_windows keeps the receivers of a sender's
two outputs, one linked and one over HTTP, down through 300 buys with a
2,000-byte window, then starts them: each applies all 300 once. Without
the refill after deliveries the link stops at 117.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Review 004's timer fix (103) counted the deadlines on the monotonic
clock, but the owner still slept until a wall-clock time: with the
clock set back an hour a node's timers would stop for that hour. So
would a wire's pause between tries, and a lone commit after a group
would wait an hour for the others to join it. The test's LD_PRELOAD
moves only what the process reads, so there each wait ended at once
instead, and the timers went on ticking while the owner spun a core.
core/wait.h makes conditions that wait on the monotonic clock
(pthread_condattr_setclock; macOS keeps the wall clock) and deadlines
on it. The owner's waits, the wire's pauses and the group commit's
gathering use them.
clock-back.so can now move the clock forward too (CLOCK_SHIFT_S), and
check.py server_clocks moves it an hour each way under a node with a
timer and a wire to a port no one listens on, and under a document
server whose three threads commit together, then one alone. Before:
back, 159 % CPU and 50,886 tries in 1.2 s; forward, 1 tick, 1 try, and
a lone commit that never ended. After: 59 ticks, 0 % CPU, 4 tries and a
lone commit of 2.6 ms, both ways.
|
| |
|
|
|
|
|
|
|
|
| |
An event under a budget counted its states twice, before and after,
walking every state. For the smallest event (a number added, no store)
that cost 21 ns in an app of one state and 125 ns in one of 32 (+17 %,
+38 %). The app now keeps a bit for each list (not a message's rows) and
text when it opens its module, and walks those alone: +10 ns and +29 ns
(+8 %, +9 %), and nothing without a budget. A served write costs tens of
microseconds, so its throughput does not see it.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
pure-serve --memory BYTES gives the app a budget of state bytes: its
lists' items as they are stored, its texts, the outbox and the numbers
heard (docs/design/013-memory-budget.md). The count is deterministic,
the same on any device. An event after which the states hold more than
the budget, and more than before it, fails with the fault memory and
changes nothing; HTTP answers 503 memory. One that frees or keeps them
goes on, so an app over its budget can always shrink.
Sends waiting for their receivers are state: a full outbox refuses the
next send until some are stored, which is the backpressure a slow
receiver puts on clients. A delivery refused for memory is not heard:
the link keeps it (c9c0edf) and HTTP senders try again after 503.
An answer (--reply) now takes its send out of the outbox in its own
event (pure_app_answer), so it has the room its send held. Apart, an app
whose outbox filled the budget could never apply an answer that keeps
anything, and the send leaves only after its answer: both would stay for
good. An answer that still does not fit waits, with the wire's after it,
and is tried again every 100 ms: pure_wire_answer leaves it in place
until pure_wire_answered.
Checks: test-module memory_budget (refused and undone, freeing over the
budget, a full outbox, a delivery not heard, answers that fit or wait,
across a restart); check.py server_memory (a sender refused 503 memory
with its receiver down and taking buys once it is up; a receiver
restarted below what it keeps, refusing 7 times in 2 s, then taking all)
and server_answers_memory (answers wait while receipts fill the budget,
then apply once each; the API called once per order). The stats report
state_bytes and memory_refused.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Replacing a module, or starting one over a store, kept an output's
waiting sends when the module had the output with as many fields of the
same types. Their names were not compared, and the stored links kept the
types alone: an output whose two numbers swapped places read debit 10,
credit 20 as credit 10, debit 20, replaced and started again (review
004, F3). A send's bytes mean its fields' names and types in order; now
both are compared, in memory and in the store, whose links (PLK4) keep
each field's name. Links kept before (PLK3) have the types alone, as
before; the next save writes PLK4.
test-module's output_meaning: the swapped module is refused, replacing
and starting, while a send waits; trimmed, it replaces and its sends go
on; and the store then refuses the module before.
|
| |
|
|
|
|
|
|
|
|
|
|
| |
A save whose tree commit may or may not be stored leaves the app apart
from its store: no save may follow until it starts again from what the
store has. The app was marked so only when the save also logged a list's
change, so a save of numbers alone that came back uncertain let the next
event (a list's alone) save on the state the memory had rolled back to:
after a restart, count 1 and a row made from count 0 (review 004, F2).
Now any uncertain tree commit marks it; a failed one still takes back
the logged entry. test-module's uncertain_numbers does the review's
case: the list's event is refused, and the store is the commit's.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
A walk whose where bounds a keyed list's key finds the bound once, when
the walk begins, if its body writes nothing the bound reads. The body's
writes counted only states stored and lists changed, not what those
changes move with them: an insert or remove moves the indices into the
list, a text's change the cursors in it. A walk bounded by an index
into a list its body inserts into saw the bound it began with: of five
rows it took one (review 004, F1). Those states now count as written,
and a bound that moves an index (whose list is whichever the index's
is) is kept only when the body changes no list.
build/module-probe runs a module twice from the same keys, as it loads
and with every range let go, and says which state first differs.
check.py's module_ranges runs the review's case (all rows twice: done
10, at 10) and a walk whose bound its body cannot move, still ranged.
The probe finds the difference in the runtime before this.
|
| |
|
|
|
|
| |
A sender takes its messages' shape, and a listener asks its host which
input a stream goes to. The core gives the shape (pure_module_shape);
link/ now builds without the core's headers.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
| |
The last number heard from each source was written whole into the links
value at every save, and counted in two bytes: a node that heard from
more than 65,535 sources stored a wrong count, and each save cost as many
bytes as there were sources. The numbers are now a runtime-owned list
{source, seq} in order of source, stored as a list state is (its image
"0heard" and its changes in the log), changed with the event that
delivers, so a failed save takes them back with it. Links stored before
(PLK1) move their numbers to the list at a start and are stored again
without them (PLK2).
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
pure-serve --send OUTPUT=pure://host:port/INPUT sends an output's saved
sends to another node's --link-port with no handshake: the first packet
carries records. Keys come from the two nodes' keys (X25519, HKDF-SHA256,
AES-128-GCM), with a random run in each packet's header so no nonce
repeats across restarts; nothing is stored for them. What lasts is the
apps' own: the sender's outbox and the receiver's heard numbers
(pure_app_heard, new). The sender detects losses as RFC 9002 says, with
NewReno, and trims a send once the receiver says it stored it; the
receiver hands the owner whole records in order, which it applies from
the one after the source's last heard number, stopping at a gap, and
answers how far it stored with every acknowledgment. Stored bytes are
the bytes on the wire: an output and an input of one shape need no JSON.
server_links_udp kills the receiver, the sender, then both (-9) while
four clients buy: every saved order is applied once, with no handshake
(five runs, 10k-11k orders each). server_links_udp_lossy does it again in
a namespace of its own with the link's packets delayed, lost (3 %) and
reordered (10 %) by netem (three runs, 11k-12k orders).
|
| | |
|
| | |
|
| | |
|
| |
|
|
| |
store
|
| | |
|
| |
|
|
| |
searched without branches
|
| | |
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
A fold whose kind has PURE_FOLD_SLICED (128), and a walk whose argument
has PURE_EACH_SLICED (bit 0), first take two numbers, a low and a high
key, and run for the items of their list (keyed by a number) whose keys
are from low up to before high, found by key: the range is the program's
meaning, not an optimization, so their blocks may fault (items out of the
slice never run). A fold a leaf at a time now leaves out the lanes of a
leaf outside the items it runs for, and a leaf that would fault runs item
by item over those items alone. Slices are neither shaped nor given
automatic ranges.
ranges now checks a count over a slice whose test divides (a division by
zero failing it only when inside the slice) against a model, the same on
the item-by-item path, and a walk over a slice.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
A filter, a fold or a walk's where (a test at the start of its block and a
jump to its end when it fails) that ANDs comparisons of a keyed list's key
with values reading no item gets a range at load (PureRange: a lower bound
GT or GE, an upper LT or LE, EQ both). When it runs, the bounds are found
once and looked up by key, and only the leaves between the two positions
are read: O(log n + k) where it read every item. A filter leaves the items
out of range out anyway, so it always may; a fold or a walk only when the
rest of its test and its value cannot fault (no division, sum or product
that may overflow, key or item that may be missing), since the items it
skips would have run them; a walk's bounds must also read no state, local
or list its block writes, as the where reads them anew for every item.
A bound that faults leaves the test to run for every item, as written.
A fold of kind 5 (distinct) counts the different values its included
items give (-0 as 0), with a set per fold; it runs a leaf at a time and
is never shaped. max, min and first alone fault over no item.
ranges checks, against the same module reading every item, over 60 lists
of up to 400 keyed items and 3,600 views: a count between two bounds, a sum
between a lower and an upper bound with another condition, first equal to
a key, min with the bound on the right, a count whose test may fault (no
range), a filtered table in bounds, 359 walks changing and removing the
items in bounds, and a walk whose body moves its bound (no range).
lane_folds now makes distinct folds too.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
LOCAL_LOAD and LOCAL_STORE name one of an event's 64 slots, what it holds
(a number, or an index of a list) and that list: slots start at 0 when an
event begins, are shared by its handlers, the walks in them and the folds
in those, and are never saved nor in the states' namespace. A handler uses
a slot for one thing, so its type is verified as a state's is; views have
no locals (IN_LOCALS: a handler's block, a walk in it, a fold in either;
stores only in a handler and its walks). A fold reading a local still runs
a leaf at a time (one value for every item) and a shaped fold takes one
only on its key's side. The signature table's where widens to 16 bits.
locals checks a handler that sums items into a local in a walk, counts in
a fold the items below it, keeps an index in a local and reads it back,
over 80 events against a model, and five refusals. server_rows' shop now
takes stock through an index local and counts in one.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
An input of the new kind 6 holds the arguments a view takes: fields as a
message has, no handler, the view's number where a key input names its
key, and the view's name with .args after it; one set a view, never a
column's (a table's columns and filter read the table's). The view, its
columns and filter, and the folds in them read their arguments with
FIELD, verified as a handler reads its message (IN_ARGUMENTS: reads, no
reply or document), and a fold anywhere may now read the message or
arguments of the block it is in: a handler's count(a in accounts where
a.bid == pay.bid) verifies.
pure_app_arguments gives a view's arguments as a payload of their shape
(placed as a message's fields); the view shows nothing until they are
given, and a filtered table keeps its rows for the arguments they were
made for. A text argument a view shows stays in the caller's payload
(FROM_ARGUMENTS), so it outlives the evaluation. A fold reading a number
argument still runs a leaf at a time (the same value for every item), and
a shaped fold takes arguments only on its key's side, so its pass does not
depend on them. Message fields are placed by one function for messages
and arguments.
view_arguments checks a keyed lookup by argument, a count above an
argument for 43 values against a model, a text argument shown back as it
is, a table filtered by an argument whose column folds with it (rows kept
per arguments), a handler's fold over its message, and five refusals.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
A rows field's JSON value is an array of objects naming the record's
fields (numbers, strings; a field left out takes its default). The
connection thread encodes them as the list's stored form, which may be
longer than the JSON, grows the request's input by that much
(pure_runtime_grow: charged to the payload budget as admission charges an
input, 503 payload_budget when it does not fit) and places them after the
body, so the owner still applies a message it need not parse. A message
whose only variable field is rows takes a body that is not JSON as those
rows in their stored form: a bulk insert without JSON. An API's answer
(--reply) gives rows the same way. A delivered batch holds no rows.
server_rows loads 30,000 stock rows in one JSON request (some 250,000
rows a second, against 6,500 with a request a row) and 20,000 more as
bytes, refuses a load with a key already there whole (409 exists), then
checks 400 random orders against a model (294 applied, 106 refused with
none of their rows applied), texts with escapes and Korean, a walk that
removes, and a restart that keeps every state and no rows.
The format's document (008) describes walks, rows fields and lists of
rows, and OUTER_ROW.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
| |
OUTER_ROW pushes the row of the column a fold's block runs for, as an
index of the column's list; ROW inside the block stays the fold's own
item. The verifier accepts it only in a fold's block inside a column,
naming that column's list (a fold in a handler, a plain view or a filter
has no outer row). So a column can hold a correlated fold: per branch,
the sum of its accounts; per account, how many are richer. aup compiles
the column's row inside a fold to it.
|
| |
|
|
|
|
|
|
|
| |
A list's stored form is one value in the tree store, so the limit on a
document (1.38 MiB, what a host carries whole as an HTTP body) capped a
table at about 51,000 rows of 28 bytes. A value the runtime owns, a state
(a key starting with '.') or a draft without a key, may now grow to 1 GiB;
documents keep their limit. The store's format is unchanged: its trees
already reach far past either.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
A message for a document scanned the burst's pending keys with strcmp to
see whether its key was there, and the host scanned the burst's earlier
requests the same way before each one: both quadratic in the burst (64
concurrent reads, about 31 compares each, twice). The app now indexes its
pending documents by key (open addressing over an FNV-1a hash, 1 KiB),
answers pure_app_pending in one look, and the host asks it; whether the
current event's document is pending is a flag instead of a scan by
pointer. Bursts split where they did, except that on an owner, which
applies a round's reads first, an edit of a key read in the same round
now splits the burst at the host rather than the app saving on its own.
A unit test checks the index at 200 keys.
|
|
|
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.
|
