From efb3abdf688f75f2d9436b63813cdbd9814cc285 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 28 Sep 2026 00:37:12 +0100 Subject: Run folds and filters a leaf of their list at a time 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. --- core/module-list.h | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) (limited to 'core/module-list.h') diff --git a/core/module-list.h b/core/module-list.h index a3f4ad6..e370b97 100644 --- a/core/module-list.h +++ b/core/module-list.h @@ -37,9 +37,14 @@ typedef struct { size_t start; unsigned count; union { const double *numbers; const PureSpan *texts; } column[16]; + /* Where the run is in the list's tree, for the next one. */ + const void *path[16]; + uint8_t taken[16]; + unsigned depth; } PureRun; -enum { PURE_LIST_ITEMS = 1 << 24 }; +/* A list holds up to PURE_LIST_ITEMS items, a run up to PURE_LIST_RUN. */ +enum { PURE_LIST_ITEMS = 1 << 24, PURE_LIST_RUN = 32 }; PureList *pure_list_new(unsigned fields, const uint8_t *text_fields); void pure_list_free(PureList *); @@ -63,9 +68,11 @@ PureResult pure_list_insert(PureList *, size_t at, const PureCell *cells, PureUn PureResult pure_list_remove(PureList *, size_t at, PureUndo *); PureResult pure_list_set(PureList *, size_t at, unsigned field, PureCell value, PureUndo *); PureCell pure_list_get(const PureList *, size_t at, unsigned field); -/* The run holding position at (false past the end): for reading item after - * item without finding each. Valid until the list changes. */ +/* The run holding position at (false past the end), and the run after + * run (false at the end): for reading item after item without finding each. + * Valid until the list changes. */ bool pure_list_run(const PureList *, size_t at, PureRun *); +bool pure_list_next(const PureList *, PureRun *); /* In a list ordered by field (a keyed list): the first position whose item's * field does not order below key (numbers by value, texts by bytes), and * whether that item's field is key. */ -- cgit v1.2.3