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