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, 46 insertions, 7 deletions

diff --git a/core/module-list.c b/core/module-list.c
index 6e13de0..55c6812 100644
--- a/core/module-list.c
+++ b/core/module-list.c
@@ -23,7 +23,7 @@
  * (the path) and retires the ones it replaced, and retires a text it lets go
  * instead of freeing it. A share is then a root and a count, however long
  * the list. */
-enum { FANOUT = 32, DEPTH = 16, SPARE_NODES = 8 };
+enum { FANOUT = PURE_LIST_RUN, DEPTH = 16, SPARE_NODES = 8 };
 
 typedef struct Node {
     uint64_t made;            /* the list's share count when made: shared once below it */
@@ -720,16 +720,55 @@ PureCell pure_list_get(const PureList *list, size_t at, unsigned field) {
     return cell_at(&list->layout, leaf_of(list, at, &within), (unsigned)within, field);
 }
 
-bool pure_list_run(const PureList *list, size_t at, PureRun *run) {
-    const Layout *l = &list->layout;
-    if (at >= list->count) return false;
-    size_t within;
-    const Node *leaf = leaf_of(list, at, &within);
-    run->start = at - within;
+static void open_run(const Layout *l, const Node *leaf, PureRun *run) {
     run->count = leaf->count;
     for (unsigned f = 0; f < l->fields; ++f)
         if (l->text_fields[f]) run->column[f].texts = texts(l, leaf, f);
         else run->column[f].numbers = numbers(l, leaf, f);
+}
+
+bool pure_list_run(const PureList *list, size_t at, PureRun *run) {
+    if (at >= list->count) return false;
+    const Node *node = list->root;
+    size_t start = 0;
+    unsigned depth = 0;
+    while (!node->leaf) {
+        unsigned i = 0;
+        while (i + 1 < node->count && at - start >= child(node, i)->items) start += child(node, i)->items, ++i;
+        run->path[depth] = node;
+        run->taken[depth++] = (uint8_t)i;
+        node = child(node, i);
+    }
+    run->path[depth] = node;
+    run->depth = depth;
+    run->start = start;
+    open_run(&list->layout, node, run);
+    return true;
+}
+
+/* Up to the nearest node with a child after the one taken, then down its
+ * first children to a leaf. The leaf after it (a sibling) is fetched ahead:
+ * leaves copied at different times lie far apart in memory. */
+bool pure_list_next(const PureList *list, PureRun *run) {
+    size_t start = run->start + run->count;
+    unsigned depth = run->depth;
+    while (depth && run->taken[depth - 1] + 1u >= ((const Node *)run->path[depth - 1])->count) --depth;
+    if (!depth) return false;
+    const Node *parent = run->path[depth - 1], *node = child(parent, ++run->taken[depth - 1]);
+    while (!node->leaf) {
+        run->path[depth] = parent = node;
+        run->taken[depth++] = 0;
+        node = child(node, 0);
+    }
+    unsigned after = run->taken[depth - 1] + 1u;
+    if (after < parent->count) {
+        const char *leaf = (const char *)child(parent, after);
+        for (size_t at = 0; at < list->layout.leaf_size; at += 64) __builtin_prefetch(leaf + at);
+    }
+    run->path[depth] = node;
+    run->depth = depth;
+    run->start = start;
+    open_run(&list->layout, node, run);
     return true;
 }