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, 4 insertions, 1 deletions

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