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.

1 files changed, 10 insertions, 3 deletions

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. */