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.

5 files changed, 685 insertions, 48 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;
 }
 
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. */
diff --git a/core/module.c b/core/module.c
index 32d0629..36e13c3 100644
--- a/core/module.c
+++ b/core/module.c
@@ -399,6 +399,40 @@ PURE_COLD static const char *verify_block(const PureModule *m, PureBlock block,
     return why;
 }
 
+/* Whether an instruction has a form that works on the items of a run at
+ * once: numbers and indexes, with no branch and no text. */
+PURE_COLD static bool has_lanes(const PureModule *m, const PureOp *op) {
+    switch (op->op) {
+    case PURE_OP_CONST: case PURE_OP_ADD: case PURE_OP_SUB: case PURE_OP_MUL: case PURE_OP_DIV: case PURE_OP_NEG:
+    case PURE_OP_LT: case PURE_OP_LE: case PURE_OP_GT: case PURE_OP_GE: case PURE_OP_EQ: case PURE_OP_NE:
+    case PURE_OP_AND: case PURE_OP_OR: case PURE_OP_NOT: case PURE_OP_MIN: case PURE_OP_MAX: case PURE_OP_CLAMP:
+    case PURE_OP_FLOOR: case PURE_OP_MOD: case PURE_OP_LOAD: case PURE_OP_LIST_COUNT: case PURE_OP_INDEX_LOAD:
+    case PURE_OP_INDEX_MOVE: case PURE_OP_INDEX_FIRST: case PURE_OP_INDEX_LAST: case PURE_OP_INDEX_NUM:
+    case PURE_OP_ROW: case PURE_OP_OUTER_ROW: case PURE_OP_PICK: case PURE_OP_SLIDE:
+        return true;
+    case PURE_OP_ITEM_GET: return field_type(m, list_of(op->arg), item_field(op->arg)) == T_NUM;
+    case PURE_OP_LIST_FIND: case PURE_OP_LIST_HAS: return field_type(m, op->arg, m->state_key[op->arg] - 1u) == T_NUM;
+    default: return false;
+    }
+}
+
+PURE_COLD static bool block_has_lanes(const PureModule *m, PureBlock block) {
+    for (uint32_t pc = block.start; pc < block.start + block.length; ++pc)
+        if (!has_lanes(m, &m->code[pc])) return false;
+    return true;
+}
+
+/* A fold in a verified block whose own block has lane forms throughout runs
+ * a leaf of its list at a time. */
+PURE_COLD static void plan_folds(PureModule *m, PureBlock block) {
+    for (uint32_t pc = block.start; pc < block.start + block.length; ++pc) {
+        PureOp *op = &m->code[pc];
+        if (op->op != PURE_OP_FOLD) continue;
+        op->plan = block_has_lanes(m, (PureBlock){pc + 1, op->arg >> 16});
+        pc += op->arg >> 16;
+    }
+}
+
 PURE_COLD PureResult pure_module_read(const char *path, PureModule *out, char *error, size_t error_size) {
     FILE *file = fopen(path, "rb");
     unsigned char *bytes = NULL;
@@ -668,6 +702,12 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule
         bad = i;
         if ((why = verify_block(out, out->handler[i].code, -1, -1, -1, out->handler[i].event, &bad))) goto refused;
     }
+    for (uint32_t i = 0; i < out->views; ++i) {
+        plan_folds(out, out->view_code[i]);
+        out->view_plan[i] = out->view_type[i] == PURE_VIEW_TABLE && out->view_code[i].length &&
+                            block_has_lanes(out, out->view_code[i]);
+    }
+    for (uint32_t i = 0; i < out->handlers; ++i) plan_folds(out, out->handler[i].code);
     return PURE_OK;
 refused:
     if (error_size) snprintf(error, error_size, "%s (%u)", why, bad);
@@ -906,6 +946,339 @@ static PureResult send(PureApp *app, uint32_t output, const Slot *fields, const
     return PURE_OK;
 }
 
+static PureResult run(const PureModule *m, double *values, PureBlock block, Event *ev, Slot *result);
+
+/* ---- Folds and filters a leaf at a time ------------------------------
+ * A block whose instructions all have lane forms (has_lanes) runs for a run
+ * of its list's items at once: each value is one per item (a lane), the
+ * items' own positions, or one for all. An item for which run would fault
+ * makes the whole run go again item by item through run, so a fold faults,
+ * and a filter leaves an item out, exactly as they would have; the lanes
+ * only see what run would compute. */
+typedef struct {
+    const double *lane; /* a value per item, or NULL */
+    double value;       /* without lanes: the value for all */
+    bool rows;          /* without lanes: the items' own positions */
+    uint16_t owner;     /* an index's list */
+} Lanes;
+
+static bool uniform(const Lanes *v) { return !v->lane && !v->rows; }
+
+/* A lookup by a value for all items reads no item of the run: every run of
+ * a fold (or a filter) finds the same, so it is made once, by instruction. */
+enum { MEMO = 64 };
+typedef struct { double value[MEMO]; uint64_t known; } Memo;
+
+static bool recalled(const Memo *memo, uint32_t slot, double *value) {
+    if (slot >= MEMO || !(memo->known >> slot & 1)) return false;
+    *value = memo->value[slot];
+    return true;
+}
+
+static void remember(Memo *memo, uint32_t slot, double value) {
+    if (slot >= MEMO) return;
+    memo->value[slot] = value;
+    memo->known |= (uint64_t)1 << slot;
+}
+
+/* A value per item, in scratch when it is not one already. */
+static const double *lanes_of(const Lanes *v, double *scratch, const PureRun *items) {
+    if (v->lane) return v->lane;
+    for (unsigned i = 0; i < items->count; ++i) scratch[i] = v->rows ? (double)(items->start + i) : v->value;
+    return scratch;
+}
+
+/* a op b as run computes it; false where run faults. */
+static bool number_op(uint8_t op, double a, double b, double *out) {
+    double value;
+    switch (op) {
+    case PURE_OP_ADD: value = a + b; break;
+    case PURE_OP_SUB: value = a - b; break;
+    case PURE_OP_MUL: value = a * b; break;
+    case PURE_OP_DIV:
+        if (b == 0) return false;
+        value = a / b;
+        break;
+    case PURE_OP_LT: value = a < b; break;
+    case PURE_OP_LE: value = a <= b; break;
+    case PURE_OP_GT: value = a > b; break;
+    case PURE_OP_GE: value = a >= b; break;
+    case PURE_OP_EQ: value = a == b; break;
+    case PURE_OP_NE: value = a != b; break;
+    case PURE_OP_AND: value = a != 0 && b != 0; break;
+    case PURE_OP_OR: value = a != 0 || b != 0; break;
+    case PURE_OP_MIN: value = minimum(a, b); break;
+    case PURE_OP_MOD:
+        if (b == 0) return false;
+        value = fmod(a, b);
+        if (value != 0 && (value < 0) != (b < 0)) value += b;
+        else if (value == 0) value = copysign(0.0, b);
+        break;
+    default: value = maximum(a, b); break;
+    }
+    *out = value;
+    return isfinite(value);
+}
+
+/* a op b for every item into out: a loop per operation, reading a value for
+ * all with stride 0. false where run faults for some item. */
+static bool lanes_op(uint8_t op, const double *a, size_t sa, const double *b, size_t sb, double *out, unsigned n) {
+    bool bad = false;
+#define EACH(expr) for (unsigned i = 0; i < n; ++i) { double x = a[i * sa], y = b[i * sb]; out[i] = (expr); }
+    switch (op) {
+    case PURE_OP_ADD: EACH(x + y) break;
+    case PURE_OP_SUB: EACH(x - y) break;
+    case PURE_OP_MUL: EACH(x * y) break;
+    case PURE_OP_LT: EACH(x < y) return true;
+    case PURE_OP_LE: EACH(x <= y) return true;
+    case PURE_OP_GT: EACH(x > y) return true;
+    case PURE_OP_GE: EACH(x >= y) return true;
+    case PURE_OP_EQ: EACH(x == y) return true;
+    case PURE_OP_NE: EACH(x != y) return true;
+    case PURE_OP_AND: EACH(x != 0 && y != 0) return true;
+    case PURE_OP_OR: EACH(x != 0 || y != 0) return true;
+    case PURE_OP_MIN: EACH(minimum(x, y)) return true;
+    case PURE_OP_MAX: EACH(maximum(x, y)) return true;
+    default:
+        for (unsigned i = 0; i < n; ++i) bad |= !number_op(op, a[i * sa], b[i * sb], &out[i]);
+        return !bad;
+    }
+#undef EACH
+    for (unsigned i = 0; i < n; ++i) bad |= !isfinite(out[i]);
+    return !bad;
+}
+
+/* The block for the items of a run at once, as a column of their list:
+ * result holds what it leaves (lanes may point into store, a row of lanes
+ * per stack depth, or into the list's leaf). false when run would fault for
+ * some item. */
+static bool run_lanes(const PureModule *m, const double *values, PureBlock block, const Event *ev, const PureRun *items,
+                      Lanes *result, double (*store)[PURE_LIST_RUN], Memo *memo) {
+    PureApp *app = ev->app;
+    Lanes stack[PURE_MODULE_STACK];
+    double scratch[2][PURE_LIST_RUN];
+    size_t sp = 0;
+    unsigned n = items->count;
+    for (uint32_t pc = block.start, end = block.start + block.length; pc < end; ++pc) {
+        const PureOp *op = &m->code[pc];
+        uint32_t arg = op->arg;
+        Lanes *top = sp ? &stack[sp - 1] : stack;
+        double *out = store[sp ? sp - 1 : 0]; /* where the top's new lanes go */
+        switch (op->op) {
+        case PURE_OP_CONST: stack[sp++] = (Lanes){NULL, op->value, false, 0}; continue;
+        case PURE_OP_LOAD: stack[sp++] = (Lanes){NULL, values[arg], false, 0}; continue;
+        case PURE_OP_INDEX_LOAD: stack[sp++] = (Lanes){NULL, values[arg], false, m->state_ref[arg]}; continue;
+        case PURE_OP_ROW: stack[sp++] = (Lanes){NULL, 0, true, (uint16_t)arg}; continue;
+        case PURE_OP_OUTER_ROW: stack[sp++] = (Lanes){NULL, (double)ev->outer, false, (uint16_t)arg}; continue;
+        case PURE_OP_LIST_COUNT: stack[sp++] = (Lanes){NULL, (double)pure_list_count(app->lists[arg]), false, 0}; continue;
+        case PURE_OP_INDEX_FIRST: case PURE_OP_INDEX_LAST: {
+            size_t last = op->op == PURE_OP_INDEX_LAST ? pure_list_count(app->lists[arg]) : 0;
+            stack[sp++] = (Lanes){NULL, last ? (double)(last - 1) : 0, false, (uint16_t)arg};
+            continue;
+        }
+        case PURE_OP_INDEX_NUM: continue;
+        case PURE_OP_PICK: stack[sp] = stack[sp - 1 - arg]; ++sp; continue;
+        case PURE_OP_SLIDE: {
+            /* The top moves down: lanes kept in a depth it leaves come along. */
+            Lanes moved = stack[sp - 1];
+            size_t to = sp - 1 - arg;
+            if ((uintptr_t)moved.lane >= (uintptr_t)store[to + 1] && (uintptr_t)moved.lane < (uintptr_t)store[sp]) {
+                memcpy(store[to], moved.lane, n * sizeof(double));
+                moved.lane = store[to];
+            }
+            stack[to] = moved;
+            sp = to + 1;
+            continue;
+        }
+        case PURE_OP_ITEM_GET: {
+            uint32_t list = list_of(arg), field = item_field(arg);
+            const PureList *from = app->lists[list];
+            size_t count = pure_list_count(from);
+            if (top->rows) { /* the items themselves: the leaf's column */
+                *top = (Lanes){items->column[field].numbers, 0, false, 0};
+                continue;
+            }
+            if (!top->lane) {
+                top->owner = 0;
+                if (recalled(memo, pc - block.start, &top->value)) continue;
+                if (top->value >= (double)count) return false;
+                top->value = pure_list_get(from, (size_t)top->value, field).num;
+                remember(memo, pc - block.start, top->value);
+                continue;
+            }
+            for (unsigned i = 0; i < n; ++i) {
+                if (top->lane[i] >= (double)count) return false;
+                out[i] = pure_list_get(from, (size_t)top->lane[i], field).num;
+            }
+            *top = (Lanes){out, 0, false, 0};
+            continue;
+        }
+        case PURE_OP_LIST_FIND: case PURE_OP_LIST_HAS: {
+            const PureList *keyed = app->lists[arg];
+            unsigned key = m->state_key[arg] - 1u;
+            bool find = op->op == PURE_OP_LIST_FIND, found;
+            if (uniform(top)) {
+                double value;
+                if (!recalled(memo, pc - block.start, &value)) {
+                    size_t at = pure_list_seek(keyed, key, (PureCell){top->value, NULL, 0}, &found);
+                    if (find && !found) return false;
+                    remember(memo, pc - block.start, value = find ? (double)at : found);
+                }
+                *top = (Lanes){NULL, value, false, find ? (uint16_t)arg : 0};
+                continue;
+            }
+            const double *keys = lanes_of(top, scratch[0], items);
+            for (unsigned i = 0; i < n; ++i) {
+                size_t at = pure_list_seek(keyed, key, (PureCell){keys[i], NULL, 0}, &found);
+                if (find && !found) return false;
+                out[i] = find ? (double)at : found;
+            }
+            *top = (Lanes){out, 0, false, find ? (uint16_t)arg : 0};
+            continue;
+        }
+        case PURE_OP_INDEX_MOVE: {
+            Lanes by = stack[--sp];
+            top = &stack[sp - 1];
+            out = store[sp - 1];
+            size_t count = pure_list_count(app->lists[top->owner]);
+            double last = count ? (double)(count - 1) : 0;
+            if (uniform(top) && uniform(&by)) {
+                if (by.value != floor(by.value)) return false;
+                top->value = maximum(0, minimum(top->value + by.value, last));
+                continue;
+            }
+            const double *at = lanes_of(top, scratch[0], items), *step = lanes_of(&by, scratch[1], items);
+            for (unsigned i = 0; i < n; ++i) {
+                if (step[i] != floor(step[i])) return false;
+                out[i] = maximum(0, minimum(at[i] + step[i], last));
+            }
+            *top = (Lanes){out, 0, false, top->owner};
+            continue;
+        }
+        case PURE_OP_NEG: case PURE_OP_NOT: case PURE_OP_FLOOR: {
+            if (uniform(top)) {
+                top->value = op->op == PURE_OP_NEG ? -top->value : op->op == PURE_OP_NOT ? top->value == 0 : floor(top->value);
+                top->owner = 0;
+                continue;
+            }
+            const double *a = lanes_of(top, scratch[0], items);
+            if (op->op == PURE_OP_NEG) for (unsigned i = 0; i < n; ++i) out[i] = -a[i];
+            else if (op->op == PURE_OP_NOT) for (unsigned i = 0; i < n; ++i) out[i] = a[i] == 0;
+            else for (unsigned i = 0; i < n; ++i) out[i] = floor(a[i]);
+            *top = (Lanes){out, 0, false, 0};
+            continue;
+        }
+        case PURE_OP_CLAMP: {
+            Lanes high = stack[--sp], low = stack[--sp];
+            top = &stack[sp - 1];
+            out = store[sp - 1];
+            if (uniform(top) && uniform(&low) && uniform(&high)) {
+                if (low.value > high.value) return false;
+                top->value = maximum(low.value, minimum(top->value, high.value));
+                continue;
+            }
+            double spare[PURE_LIST_RUN];
+            const double *x = lanes_of(top, scratch[0], items), *lo = lanes_of(&low, scratch[1], items),
+                         *hi = lanes_of(&high, spare, items);
+            for (unsigned i = 0; i < n; ++i) {
+                if (lo[i] > hi[i]) return false;
+                out[i] = maximum(lo[i], minimum(x[i], hi[i]));
+            }
+            *top = (Lanes){out, 0, false, 0};
+            continue;
+        }
+        default: { /* two numbers */
+            Lanes b = stack[--sp];
+            top = &stack[sp - 1];
+            out = store[sp - 1];
+            if (uniform(top) && uniform(&b)) {
+                if (!number_op(op->op, top->value, b.value, &top->value)) return false;
+                top->owner = 0;
+                continue;
+            }
+            const double *x = top->rows ? lanes_of(top, scratch[0], items) : top->lane ? top->lane : &top->value;
+            const double *y = b.rows ? lanes_of(&b, scratch[1], items) : b.lane ? b.lane : &b.value;
+            if (!lanes_op(op->op, x, uniform(top) ? 0 : 1, y, uniform(&b) ? 0 : 1, out, n)) return false;
+            *top = (Lanes){out, 0, false, 0};
+            continue;
+        }
+        }
+    }
+    memcpy(result, stack, sp * sizeof(*stack));
+    return true;
+}
+
+/* A fold's running value: what count, sum, max, min or first has so far. */
+typedef struct { unsigned how; double total; bool any, done; } Fold;
+
+/* One item: its value, and whether it counts (for count and first, the value is). */
+static void fold_in(Fold *fold, size_t row, double value, double counts) {
+    if (counts == 0) return;
+    unsigned how = fold->how;
+    if (how == PURE_FOLD_FIRST) {
+        fold->total = (double)row;
+        fold->any = fold->done = true;
+        return;
+    }
+    fold->total = how == PURE_FOLD_COUNT ? fold->total + 1 : how == PURE_FOLD_SUM ? fold->total + value :
+                  !fold->any ? value : how == PURE_FOLD_MAX ? maximum(fold->total, value) : minimum(fold->total, value);
+    fold->any = true;
+}
+
+/* The fold's block for its items from first to last, one at a time. */
+static PureResult fold_rows(const PureModule *m, double *values, PureBlock inner, Event *per, size_t first,
+                            size_t last, Fold *fold) {
+    bool one = fold->how == PURE_FOLD_COUNT || fold->how == PURE_FOLD_FIRST;
+    for (size_t row = first; row < last && !fold->done; ++row) {
+        Slot out[2];
+        size_t mark = per->arena->used;
+        per->row = row;
+        PureResult status = run(m, values, inner, per, out);
+        per->arena->used = mark;
+        if (status != PURE_OK) return status;
+        fold_in(fold, row, out[0].num, one ? out[0].num : out[1].num);
+    }
+    return PURE_OK;
+}
+
+/* The fold's block a leaf of its list at a time; a run where an item would
+ * fault goes item by item. The items join the fold in order, so a sum adds
+ * as it would one at a time. */
+static PureResult fold_runs(const PureModule *m, double *values, PureBlock inner, const PureList *list, Event *per,
+                            Fold *fold) {
+    double store[PURE_MODULE_STACK][PURE_LIST_RUN], scratch[2][PURE_LIST_RUN];
+    bool one = fold->how == PURE_FOLD_COUNT || fold->how == PURE_FOLD_FIRST;
+    PureRun items;
+    Memo memo;
+    memo.known = 0;
+    for (bool more = pure_list_run(list, 0, &items); more && !fold->done; more = pure_list_next(list, &items)) {
+        Lanes out[2];
+        if (!run_lanes(m, values, inner, per, &items, out, store, &memo)) {
+            PureResult status = fold_rows(m, values, inner, per, items.start, items.start + items.count, fold);
+            if (status != PURE_OK) return status;
+            continue;
+        }
+        const Lanes *counts = &out[one ? 0 : 1];
+        if (uniform(counts) && counts->value == 0) continue;
+        const double *c = lanes_of(counts, scratch[0], &items), *v = lanes_of(&out[0], scratch[1], &items);
+        if (fold->how == PURE_FOLD_COUNT) {
+            size_t counted = 0;
+            for (unsigned i = 0; i < items.count; ++i) counted += c[i] != 0;
+            fold->total += (double)counted;
+            fold->any = fold->any || counted;
+        } else if (fold->how == PURE_FOLD_SUM) {
+            double total = fold->total;
+            bool any = fold->any;
+            for (unsigned i = 0; i < items.count; ++i)
+                if (c[i] != 0) total += v[i], any = true;
+            fold->total = total;
+            fold->any = any;
+        } else
+            for (unsigned i = 0; i < items.count && !fold->done; ++i) fold_in(fold, items.start + i, v[i], c[i]);
+    }
+    return PURE_OK;
+}
+
 static PureResult run(const PureModule *m, double *values, PureBlock block, Event *ev, Slot *result) {
     Slot stack[PURE_MODULE_STACK];
     size_t sp = 0;
@@ -1157,32 +1530,20 @@ static PureResult run(const PureModule *m, double *values, PureBlock block, Even
             continue;
         }
         case PURE_OP_FOLD: {
-            /* The block that follows runs once per item, as a column of the list. */
-            unsigned how = arg & 0xFF;
+            /* The block that follows runs once per item, as a column of the
+             * list: a leaf of it at a time when planned so. */
             PureBlock inner = {pc, arg >> 16};
             PureList *list = app->lists[arg >> 8 & 0xFF];
             pc += inner.length;
-            double total = 0;
-            bool any = false;
+            Fold fold = {arg & 0xFF, 0, false, false};
             Event per = *ev;
             per.outer = ev->row;
-            for (size_t row = 0, items = pure_list_count(list); row < items; ++row) {
-                Slot out[2];
-                size_t mark = arena->used;
-                per.row = row;
-                status = run(m, values, inner, &per, out);
-                arena->used = mark;
-                if (status != PURE_OK) return status;
-                double value = out[0].num;
-                if (how == PURE_FOLD_COUNT || how == PURE_FOLD_FIRST ? value == 0 : out[1].num == 0) continue;
-                if (how == PURE_FOLD_FIRST) { total = (double)row; any = true; break; }
-                total = how == PURE_FOLD_COUNT ? total + 1 : how == PURE_FOLD_SUM ? total + value :
-                        !any ? value : how == PURE_FOLD_MAX ? maximum(total, value) : minimum(total, value);
-                any = true;
-            }
-            if (!any && how >= PURE_FOLD_MAX) { kind = PURE_FAULT_NOT_FOUND; goto failed; }
-            if (!isfinite(total)) { kind = PURE_FAULT_NON_FINITE; goto failed; }
-            stack[sp].num = total;
+            status = op->plan ? fold_runs(m, values, inner, list, &per, &fold)
+                              : fold_rows(m, values, inner, &per, 0, pure_list_count(list), &fold);
+            if (status != PURE_OK) return status;
+            if (!fold.any && fold.how >= PURE_FOLD_MAX) { kind = PURE_FAULT_NOT_FOUND; goto failed; }
+            if (!isfinite(fold.total)) { kind = PURE_FAULT_NON_FINITE; goto failed; }
+            stack[sp].num = fold.total;
             stack[sp++].bytes.owner = (uint16_t)(arg >> 8 & 0xFF); /* first: the list the index is in */
             continue;
         }
@@ -1766,6 +2127,24 @@ static PureResult evaluate(PureApp *app, uint32_t view, size_t row, Slot *out) {
     return result;
 }
 
+static bool keep_row(struct PureRows *rows, size_t item) {
+    if (rows->count == rows->capacity) {
+        size_t capacity = rows->capacity ? 2 * rows->capacity : 16;
+        size_t *grown = realloc(rows->items, capacity * sizeof(*grown));
+        if (!grown) return false;
+        rows->items = grown;
+        rows->capacity = capacity;
+    }
+    rows->items[rows->count++] = item;
+    return true;
+}
+
+/* The item kept when the filter, run for it alone, keeps it; false without room. */
+static bool keep_evaluated(PureApp *app, uint32_t table, struct PureRows *rows, size_t item) {
+    Slot kept;
+    return evaluate(app, table, item, &kept) != PURE_OK || kept.num == 0 || keep_row(rows, item);
+}
+
 /* A filtered table's items, as fresh as the app's states: the filter runs
  * once per item after each change (an item it fails on is left out), not
  * once per cell. NULL for a table without a filter, or without room. */
@@ -1783,18 +2162,28 @@ static struct PureRows *filtered(PureApp *app, uint32_t table) {
     }
     if (rows->changes == app->changes) return rows;
     rows->count = 0;
-    for (size_t item = 0, items = pure_list_count(app->lists[m->view_list[table]]); item < items; ++item) {
-        Slot keep;
-        if (evaluate(app, table, item, &keep) != PURE_OK || keep.num == 0) continue;
-        if (rows->count == rows->capacity) {
-            size_t capacity = rows->capacity ? 2 * rows->capacity : 16;
-            size_t *grown = realloc(rows->items, capacity * sizeof(*grown));
-            if (!grown) return NULL;
-            rows->items = grown;
-            rows->capacity = capacity;
-        }
-        rows->items[rows->count++] = item;
-    }
+    /* A leaf of the list at a time when the filter has lane forms; a leaf
+     * where an item would fault goes item by item, leaving that item out. */
+    const PureList *list = app->lists[m->view_list[table]];
+    PureRun run;
+    if (m->view_plan[table]) {
+        double store[PURE_MODULE_STACK][PURE_LIST_RUN], scratch[PURE_LIST_RUN];
+        Event ev = {.app = app, .arena = &app->view_arena};
+        Memo memo;
+        memo.known = 0;
+        for (bool more = pure_list_run(list, 0, &run); more; more = pure_list_next(list, &run)) {
+            Lanes keep;
+            if (run_lanes(m, app->values, m->view_code[table], &ev, &run, &keep, store, &memo)) {
+                const double *kept = lanes_of(&keep, scratch, &run);
+                for (unsigned i = 0; i < run.count; ++i)
+                    if (kept[i] != 0 && !keep_row(rows, run.start + i)) return NULL;
+            } else
+                for (size_t item = run.start; item < run.start + run.count; ++item)
+                    if (!keep_evaluated(app, table, rows, item)) return NULL;
+        }
+    } else
+        for (size_t item = 0, items = pure_list_count(list); item < items; ++item)
+            if (!keep_evaluated(app, table, rows, item)) return NULL;
     rows->changes = app->changes;
     return rows;
 }
diff --git a/core/module.h b/core/module.h
index 328c358..9a491c9 100644
--- a/core/module.h
+++ b/core/module.h
@@ -84,7 +84,9 @@ typedef enum {
     PURE_FAULT_LIMIT, PURE_FAULT_NOT_FOUND, PURE_FAULT_ENCODING, PURE_FAULT_EXISTS
 } PureFault;
 
-typedef struct { double value; uint32_t arg; uint8_t op; } PureOp;
+/* plan is the runtime's, set at load: a fold whose block has a form for
+ * every instruction that works on a leaf of its list at once runs so. */
+typedef struct { double value; uint32_t arg; uint8_t op, plan; } PureOp;
 typedef struct { uint32_t start, length; } PureBlock;
 typedef struct { uint32_t event; PureBlock code; } PureHandler;
 typedef struct { char name[PURE_MODULE_NAME]; uint8_t type; uint32_t offset; } PureField;
@@ -120,6 +122,7 @@ typedef struct {
     uint16_t view_table[PURE_MODULE_VIEWS]; /* a column's table view + 1, or 0 */
     uint16_t view_list[PURE_MODULE_VIEWS];  /* the list of a table or column */
     PureBlock view_code[PURE_MODULE_VIEWS];
+    uint8_t view_plan[PURE_MODULE_VIEWS]; /* a table's filter runs a leaf of its list at once (as a fold may) */
     PureHandler handler[PURE_MODULE_HANDLERS];
     /* The code and the text constants, sized to the module in one block
      * (storage) that load takes and pure_module_release gives back. */
diff --git a/core/test-module.c b/core/test-module.c
index e6df3ad..b222597 100644
--- a/core/test-module.c
+++ b/core/test-module.c
@@ -950,15 +950,30 @@ static void model_copy(Model *to, const Model *from) {
     if (from->count) memcpy(to->items, from->items, from->count * sizeof(*to->items));
 }
 
+static bool same_item(const Model *m, size_t i, double key, PureSpan text) {
+    return key == m->items[i].key && text.size == m->items[i].size && (!text.size || !memcmp(text.data, m->items[i].text, text.size));
+}
+
+/* The items by position, and run after run from the first and from a middle one. */
 static bool same_items(const PureList *list, const Model *m) {
     if (pure_list_count(list) != m->count) return false;
     for (size_t i = 0; i < m->count; ++i) {
         PureCell key = pure_list_get(list, i, 0), text = pure_list_get(list, i, 1);
-        if (key.num != m->items[i].key || text.size != m->items[i].size ||
-            (text.size && memcmp(text.text, m->items[i].text, text.size)))
-            return false;
+        if (!same_item(m, i, key.num, (PureSpan){text.text, text.size})) return false;
     }
-    return true;
+    PureRun run;
+    for (size_t from = 0; from < m->count; from += m->count / 2 + 1) {
+        size_t at = 0;
+        bool more = pure_list_run(list, from, &run);
+        if (!more || from < run.start || from >= run.start + run.count) return false;
+        for (at = run.start; more; more = pure_list_next(list, &run)) {
+            if (run.start != at || !run.count || run.count > PURE_LIST_RUN) return false;
+            for (unsigned i = 0; i < run.count; ++i, ++at)
+                if (!same_item(m, at, run.column[0].numbers[i], run.column[1].texts[i])) return false;
+        }
+        if (at != m->count) return false;
+    }
+    return !pure_list_run(list, m->count, &run);
 }
 
 typedef struct { unsigned char *bytes; size_t size, capacity; } Grown;
@@ -2159,6 +2174,189 @@ static void filters(void) {
         }
 }
 
+/* ---- Folds and filters a leaf at a time --------------------------------
+ * Random well-typed folds (plain views, a table's columns reading their row,
+ * a handler storing them), filters and lists: a module whose folds run a
+ * leaf at a time answers bit for bit as the same module run item by item,
+ * faults included (their kind and instruction). */
+typedef struct { O code[8192]; size_t count; uint32_t seed; int fold_list, outer; } Gen;
+enum { LANE_K = 0, LANE_L = 4, LANE_M = 5 };
+
+static void put_op(Gen *g, uint8_t op, uint32_t arg, double value) {
+    CHECK(g->count < LEN(g->code));
+    g->code[g->count++] = (O){op, arg, value};
+}
+
+static unsigned roll(Gen *g, unsigned n) { return next_random(&g->seed) % n; }
+
+static void gen_num(Gen *g, int depth);
+
+/* An index of list: the fold's item, the column's row, a key found, an end, or one moved. */
+static void gen_index(Gen *g, int list, int depth) {
+    unsigned choice = roll(g, depth <= 0 ? 3 : 7);
+    if (choice == 0 && list == g->fold_list) put_op(g, PURE_OP_ROW, (uint32_t)list, 0);
+    else if (choice == 1 && list == LANE_L && g->outer >= 0) put_op(g, PURE_OP_OUTER_ROW, LANE_L, 0);
+    else if (choice >= 3 && choice <= 4 && list == LANE_L) {
+        gen_num(g, depth - 1);
+        put_op(g, PURE_OP_LIST_FIND, LANE_L, 0);
+    } else if (choice == 5) {
+        gen_index(g, list, depth - 1);
+        gen_num(g, depth - 1);
+        put_op(g, PURE_OP_INDEX_MOVE, 0, 0);
+    } else
+        put_op(g, roll(g, 2) ? PURE_OP_INDEX_FIRST : PURE_OP_INDEX_LAST, (uint32_t)list, 0);
+}
+
+static void gen_num(Gen *g, int depth) {
+    static const double pool[] = {0, -0.0, 1, -1, 2, 0.5, 3, 7, 100, -3.5, 1e308, -1e308, 4, 10};
+    static const uint8_t binary[] = {PURE_OP_ADD, PURE_OP_SUB, PURE_OP_MUL, PURE_OP_DIV, PURE_OP_LT, PURE_OP_LE,
+                                     PURE_OP_GT, PURE_OP_GE, PURE_OP_EQ, PURE_OP_NE, PURE_OP_AND, PURE_OP_OR,
+                                     PURE_OP_MIN, PURE_OP_MAX, PURE_OP_MOD};
+    static const uint8_t unary[] = {PURE_OP_NEG, PURE_OP_NOT, PURE_OP_FLOOR};
+    switch (roll(g, depth <= 0 ? 4 : 12)) {
+    case 0: put_op(g, C, 0, pool[roll(g, LEN(pool))]); return;
+    case 1: put_op(g, L, LANE_K, 0); return;
+    case 2: case 3: { /* a field of an item */
+        int list = depth <= 0 || roll(g, 3) ? g->fold_list : roll(g, 2) ? LANE_L : LANE_M;
+        gen_index(g, list, depth - 1);
+        put_op(g, PURE_OP_ITEM_GET, (uint32_t)list | (uint32_t)roll(g, list == LANE_L ? 3 : 2) << 16, 0);
+        return;
+    }
+    case 4: put_op(g, PURE_OP_LIST_COUNT, roll(g, 2) ? LANE_L : LANE_M, 0); return;
+    case 5:
+        gen_index(g, roll(g, 2) ? LANE_L : LANE_M, depth - 1);
+        put_op(g, PURE_OP_INDEX_NUM, 0, 0);
+        return;
+    case 6: gen_num(g, depth - 1); put_op(g, PURE_OP_LIST_HAS, LANE_L, 0); return;
+    case 7: gen_num(g, depth - 1); put_op(g, unary[roll(g, LEN(unary))], 0, 0); return;
+    case 8: gen_num(g, depth - 1); gen_num(g, depth - 1); gen_num(g, depth - 1); put_op(g, CL, 0, 0); return;
+    case 9: gen_num(g, depth - 1); put_op(g, PURE_OP_PICK, 0, 0); put_op(g, binary[roll(g, LEN(binary))], 0, 0); return;
+    case 10: gen_num(g, depth - 1); gen_num(g, depth - 1); put_op(g, PURE_OP_SLIDE, 1, 0); return;
+    default: gen_num(g, depth - 1); gen_num(g, depth - 1); put_op(g, binary[roll(g, LEN(binary))], 0, 0); return;
+    }
+}
+
+/* A fold over list leaving a number (first's index as one), in a column of L (outer) or not. */
+static void gen_fold(Gen *g, int list, int outer) {
+    unsigned how = roll(g, 5);
+    size_t at = g->count;
+    put_op(g, PURE_OP_FOLD, 0, 0);
+    int fold_list = g->fold_list, fold_outer = g->outer;
+    g->fold_list = list, g->outer = outer;
+    if (how != PURE_FOLD_COUNT && how != PURE_FOLD_FIRST) gen_num(g, 3);
+    gen_num(g, 3);
+    g->fold_list = fold_list, g->outer = fold_outer;
+    g->code[at].arg = FOLDING(how, list, g->count - at - 1);
+    if (how == PURE_FOLD_FIRST) put_op(g, PURE_OP_INDEX_NUM, 0, 0);
+}
+
+static bool same_number(bool a_ok, double a, bool b_ok, double b) {
+    return a_ok == b_ok && (!a_ok || !memcmp(&a, &b, sizeof(a)));
+}
+
+static void lane_folds(void) {
+    static const S numbers[] = {{"k", 3}, {"h0", 0}, {"h1", 0}, {"h2", 0}};
+    static const T lists[] = {{"l", 3 | 1 << 8, 0}, {"m", 3, 1}};
+    static const RF l_fields[] = {{"key", 0, 0}, {"a", 0, 0}, {"b", 0, 0}}, m_fields[] = {{"x", 0, 0}, {"y", 0, 0}};
+    static const R records[] = {{"lrec", l_fields, 3}, {"mrec", m_fields, 2}};
+    static const I inputs[] = {KEY("go", "KeyG")};
+    static const double values[] = {0, -0.0, 1, -1, 2, 3, 0.5, -2.5, 5, 10, 1e308, -7};
+    enum { VIEWS = 6, COLUMNS = 3, HANDLED = 3 };
+    static Gen g;
+    uint32_t seed = 0x1a2b3c4du;
+    unsigned planned = 0, folds = 0, faults = 0, cells = 0;
+    for (unsigned round = 0; round < 300; ++round) {
+        g = (Gen){.seed = next_random(&seed), .fold_list = -1, .outer = -1};
+        V views[VIEWS];
+        char names[VIEWS + 1 + COLUMNS][4];
+        W tables[1 + COLUMNS];
+        for (unsigned v = 0; v < VIEWS; ++v) {
+            snprintf(names[v], sizeof(names[v]), "v%u", v);
+            views[v] = (V){names[v], (uint32_t)g.count, 0};
+            gen_fold(&g, roll(&g, 3) ? LANE_L : LANE_M, -1);
+            views[v].length = (uint32_t)(g.count - views[v].start);
+        }
+        tables[0] = (W){"t", 2 | (LANE_L + 1) << 8, 0, (uint32_t)g.count, 0};
+        g.fold_list = LANE_L;
+        gen_num(&g, 3);
+        g.fold_list = -1;
+        tables[0].length = (uint32_t)(g.count - tables[0].start);
+        for (unsigned c = 0; c < COLUMNS; ++c) {
+            snprintf(names[VIEWS + 1 + c], sizeof(names[0]), "c%u", c);
+            tables[1 + c] = (W){names[VIEWS + 1 + c], 0, VIEWS + 1, (uint32_t)g.count, 0};
+            gen_fold(&g, roll(&g, 3) ? LANE_L : LANE_M, LANE_L);
+            tables[1 + c].length = (uint32_t)(g.count - tables[1 + c].start);
+        }
+        H handler = {1, (uint32_t)g.count, 0};
+        for (unsigned h = 0; h < HANDLED; ++h) {
+            gen_fold(&g, roll(&g, 2) ? LANE_L : LANE_M, -1);
+            put_op(&g, ST, 1 + h, 0);
+        }
+        handler.length = (uint32_t)(g.count - handler.start);
+        Spec spec = {numbers, LEN(numbers), inputs, LEN(inputs), views, VIEWS, &handler, 1, g.code, g.count, NULL, 0,
+                     lists, LEN(lists), NULL, 0, NULL, 0, records, LEN(records), tables, LEN(tables)};
+        if (load(spec, &module_a) != PURE_OK || load(spec, &module_b) != PURE_OK) {
+            fprintf(stderr, "lane round %u: %s\n", round, error);
+            abort();
+        }
+        for (uint32_t i = 0; i < module_b.code_count; ++i) {
+            folds += module_a.code[i].op == PURE_OP_FOLD;
+            planned += module_a.code[i].plan;
+            module_b.code[i].plan = 0;
+        }
+        planned += module_a.view_plan[VIEWS];
+        memset(module_b.view_plan, 0, sizeof(module_b.view_plan));
+        PureApp a, b;
+        CHECK(pure_app_start(&a, &module_a, (PureData){0}) == PURE_OK && pure_app_start(&b, &module_b, (PureData){0}) == PURE_OK);
+        size_t l_items = roll(&g, 4) ? roll(&g, 200) : 0, m_items = roll(&g, 4) ? roll(&g, 100) : 0;
+        for (size_t i = 0; i < l_items + m_items; ++i) {
+            bool in_l = i < l_items;
+            PureCell cells_[3] = {{in_l ? 2.0 * (double)i : values[roll(&g, LEN(values))], NULL, 0},
+                                  {values[roll(&g, LEN(values))], NULL, 0}, {values[roll(&g, LEN(values))], NULL, 0}};
+            PureList *list_a = a.lists[in_l ? LANE_L : LANE_M], *list_b = b.lists[in_l ? LANE_L : LANE_M];
+            CHECK(pure_list_insert(list_a, pure_list_count(list_a), cells_, NULL) == PURE_OK &&
+                  pure_list_insert(list_b, pure_list_count(list_b), cells_, NULL) == PURE_OK);
+        }
+        for (unsigned v = 0; v < VIEWS; ++v) {
+            double x = 0, y = 0;
+            bool ok_a = pure_app_view(&a, v, &x), ok_b = pure_app_view(&b, v, &y);
+            faults += !ok_a;
+            if (!same_number(ok_a, x, ok_b, y)) {
+                fprintf(stderr, "lane round %u view %u: %d %g / %d %g\n", round, v, ok_a, x, ok_b, y);
+                abort();
+            }
+        }
+        size_t rows = pure_app_rows(&a, VIEWS);
+        CHECK(rows == pure_app_rows(&b, VIEWS));
+        for (size_t row = 0; row < rows; ++row) {
+            size_t item_a, item_b;
+            CHECK(pure_app_row_item(&a, VIEWS, row, &item_a) && pure_app_row_item(&b, VIEWS, row, &item_b) && item_a == item_b);
+            for (unsigned c = 0; c < COLUMNS; ++c) {
+                double x = 0, y = 0;
+                bool ok_a = pure_app_cell(&a, VIEWS + 1 + c, row, &x), ok_b = pure_app_cell(&b, VIEWS + 1 + c, row, &y);
+                ++cells;
+                if (!same_number(ok_a, x, ok_b, y)) {
+                    fprintf(stderr, "lane round %u column %u row %zu: %d %g / %d %g\n", round, c, row, ok_a, x, ok_b, y);
+                    abort();
+                }
+            }
+        }
+        PureResult went_a = pure_app_input(&a, 0, PURE_EDGE_DOWN), went_b = pure_app_input(&b, 0, PURE_EDGE_DOWN);
+        if (went_a != went_b || a.fault != b.fault || a.fault_pc != b.fault_pc || memcmp(a.values, b.values, 4 * sizeof(double))) {
+            fprintf(stderr, "lane round %u handler: %d %d %u / %d %d %u\n", round, went_a, a.fault, a.fault_pc, went_b, b.fault,
+                    b.fault_pc);
+            abort();
+        }
+        faults += went_a != PURE_OK;
+        pure_app_stop(&a);
+        pure_app_stop(&b);
+        pure_module_release(&module_a);
+        pure_module_release(&module_b);
+    }
+    CHECK(planned > folds / 2 && faults > 100 && cells > 1000);
+    printf("{\"lane_folds\":%u,\"planned\":%u,\"faults_alike\":%u,\"cells\":%u}\n", folds, planned, faults, cells);
+}
+
 /* Damaged fold and filter modules: whatever loads runs safely. */
 static void fold_mutations(void) {
     static unsigned char valid[65536], bytes[65536];
@@ -3079,6 +3277,7 @@ int main(void) {
     list_trees();
     folds();
     filters();
+    lane_folds();
     keyed();
     keyed_mutations();
     snapshots();