Keep a list's items field by field in its leaves

An item was its own allocation (a share stamp and a cell per field) that
a leaf pointed to, so reading a field of items one after another chased a
pointer to wherever each was made: a count over 100,000 accounts built by
HTTP took 14.5 ms, against 4.6 ms after a restart laid them out in order.
A leaf now holds its items' cells field by field, numbers as binary64
arrays and texts as spans, and pure_list_run gives a leaf's columns to
read item after item.

Copy on write moves to the leaf: a change copies the path including its
leaf, whose texts stay shared; texts carry the share stamp items had, so
one a snapshot may read is retired, not freed. An event's log keeps a
removed item's cells until the event is kept or undone. A node split at
the end of the list leaves the full node full, so lists that grow at
their end (histories, keyed lists filled in key order) fill their leaves.
An account of three numbers and a text now takes 41 bytes in a leaf, not
some 130 across its allocation and the leaf's pointer.

The same count now takes 4.7 ms however the list was built, below
SQLite's 6.1 ms on the same rows. list_trees passes unchanged, and the
app model's tests under ASan and UBSan.

2 files changed, 369 insertions, 239 deletions

diff --git a/core/module-list.c b/core/module-list.c
index cfa9cf9..6e13de0 100644
--- a/core/module-list.c
+++ b/core/module-list.c
@@ -6,53 +6,75 @@
 
 /* A list's items live in a persistent B+tree: leaves hold up to FANOUT
  * items, inner nodes up to FANOUT children, and every node knows how many
- * items lie below it, their stored bytes and the first of them. So an item
- * is found by position, a keyed list is searched by key and an item's place
- * in the stored form is computed in O(log n), whatever the list's length; a
- * run of positions is read through a finger (the last leaf a thread read).
+ * items lie below it, their stored bytes and the leaf holding the first of
+ * them. So an item is found by position, a keyed list is searched by key and
+ * an item's place in the stored form is computed in O(log n), whatever the
+ * list's length; a run of positions is read through a finger (the last leaf
+ * a thread read) or a leaf at a time (pure_list_run).
  *
- * Nodes, like items, carry the list's share count when they were made. One
- * made before the last share may be read by a shared copy (a snapshot), so
- * it never changes again: the list copies the nodes on the way to a change
- * (the path) and retires the ones it replaced, as it does items. A share is
- * then a root and a count, however long the list. */
+ * A leaf keeps its items field by field: each field's cells side by side,
+ * numbers as binary64 values and texts as spans of bytes the list owns. So
+ * reading one field of items after one another reads memory in order, an
+ * item takes no allocation of its own and a leaf is copied in one piece.
+ *
+ * Nodes carry the list's share count when they were made, and so do texts.
+ * One made before the last share may be read by a shared copy (a snapshot),
+ * so it never changes again: the list copies the nodes on the way to a change
+ * (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 };
 
 typedef struct Node {
-    uint64_t made;       /* the list's share count when made: shared once below it */
-    uint32_t count;      /* items (a leaf) or children */
+    uint64_t made;            /* the list's share count when made: shared once below it */
+    uint32_t count;           /* items (a leaf) or children */
     bool leaf;
-    size_t items, bytes; /* items below, and their stored bytes */
-    PureCell *first;     /* the first item below; NULL when there is none */
-    void *slot[FANOUT];  /* a leaf's items (PureCell *), an inner node's children (Node *) */
+    size_t items, bytes;      /* items below, and their stored bytes */
+    const struct Node *first; /* the leaf holding the first item below; NULL when there is none */
+    struct Node *child[];     /* an inner node's children; a leaf's columns are here instead */
 } Node;
 
-struct PureList {
-    unsigned fields;
+enum { INNER_SIZE = sizeof(Node) + FANOUT * sizeof(Node *) };
+
+/* Where a leaf keeps each field's cells, and what an item stores. */
+typedef struct {
+    unsigned fields, texts;
     uint8_t text_fields[16];
-    Node *root;           /* NULL when no item was ever placed */
+    uint8_t text_field[16]; /* the text fields, in order */
+    uint32_t column[16];    /* where each field's cells start in a leaf */
+    size_t leaf_size;
+    size_t number_bytes;    /* an item's numbers, stored */
+} Layout;
+
+struct PureList {
+    Layout layout;
+    Node *root;           /* NULL when the list has no item */
     size_t count;
     PureDraft *draft;     /* the stored copy, or NULL */
     size_t header;        /* draft bytes before the first item */
     uint64_t id, version; /* which list, and a number every change moves on */
-    uint64_t shares;      /* copies made so far: an item or node made before the last one is shared */
-    PureRetired *retired; /* where shared items and nodes go when the list lets them go */
-    Node *spare;          /* nodes let go that no copy read, kept for the next ones (linked by slot[0]) */
-    unsigned spares;
+    uint64_t shares;      /* copies made so far: a node or text made before the last one is shared */
+    PureRetired *retired; /* where shared nodes and texts go when the list lets them go */
+    Node *spare[2];       /* inner nodes and leaves let go that no copy read, kept for the next ones (linked by first) */
+    unsigned spares[2];
     unsigned refs;        /* a shared copy's references */
-    bool copy;            /* a shared copy: it owns none of its nodes or items */
+    bool copy;            /* a shared copy: it owns none of its nodes or texts */
 };
 
-typedef enum { INSERTED, REMOVED, CHANGED, REPLACED } Change;
+/* The log of an event's changes: a removed item's cells wait in the log's
+ * cells (its texts owned by the log) until the event is undone or kept. */
+typedef enum { INSERTED, REMOVED, CHANGED } Change;
 typedef struct {
     Change change;
+    unsigned field;
     PureList *list;
     size_t at;
-    unsigned field;
-    PureCell *item; /* REMOVED: the removed item; REPLACED: the shared item a copy replaced */
-    PureCell old;   /* CHANGED: the replaced cell */
+    union {
+        PureCell old; /* CHANGED: the replaced cell */
+        size_t cells; /* REMOVED: where the item's cells start in the log's cells */
+    };
 } Entry;
-typedef struct { void *pointer; uint16_t text; uint8_t fields; bool node; } Retired;
+typedef struct { void *pointer; bool text; } Retired;
 
 static uint64_t lists_made;
 
@@ -61,39 +83,51 @@ static uint64_t lists_made;
  * the list (its id) as it was (its version) and no other. */
 static _Thread_local struct { uint64_t id, version; const Node *leaf; size_t start; } finger;
 
-/* An item's cells follow the list's share count when the item was made. One
- * made before the last share may be read by a shared copy, so it never
- * changes again (a change copies it) and is retired instead of freed. */
-static PureCell *new_item(const PureList *list) {
-    uint64_t *made = calloc(1, sizeof(*made) + (list->fields ? list->fields : 1) * sizeof(PureCell));
-    if (!made) return NULL;
-    *made = list->shares;
-    return (PureCell *)(made + 1);
-}
+static Node *child(const Node *node, unsigned i) { return node->child[i]; }
+static double *numbers(const Layout *l, const Node *leaf, unsigned f) { return (double *)((char *)leaf + l->column[f]); }
+static PureSpan *texts(const Layout *l, const Node *leaf, unsigned f) { return (PureSpan *)((char *)leaf + l->column[f]); }
 
-static bool shared(const PureList *list, const PureCell *item) { return ((const uint64_t *)item)[-1] < list->shares; }
-static bool shared_node(const PureList *list, const Node *node) { return node->made < list->shares; }
-static Node *child(const Node *node, unsigned i) { return node->slot[i]; }
-static PureCell *item_in(const Node *leaf, unsigned i) { return leaf->slot[i]; }
+static PureCell cell_at(const Layout *l, const Node *leaf, unsigned i, unsigned f) {
+    if (!l->text_fields[f]) return (PureCell){numbers(l, leaf, f)[i], NULL, 0};
+    PureSpan text = texts(l, leaf, f)[i];
+    return (PureCell){0, (unsigned char *)text.data, text.size};
+}
 
-static void free_cells(PureCell *item, unsigned fields, unsigned text) {
-    for (unsigned f = 0; f < fields; ++f)
-        if (text >> f & 1) free(item[f].text);
-    free((uint64_t *)item - 1);
+static void put_cells(const Layout *l, Node *leaf, unsigned i, const PureCell *cells) {
+    for (unsigned f = 0; f < l->fields; ++f)
+        if (l->text_fields[f]) texts(l, leaf, f)[i] = (PureSpan){cells[f].text, cells[f].size};
+        else numbers(l, leaf, f)[i] = cells[f].num;
 }
 
-static unsigned text_mask(const PureList *list) {
-    unsigned text = 0;
-    for (unsigned f = 0; f < list->fields; ++f) text |= (unsigned)(list->text_fields[f] != 0) << f;
-    return text;
+/* count items or children of from, from start on, to at in to (they may overlap). */
+static void move_items(const Layout *l, Node *to, unsigned at, const Node *from, unsigned start, unsigned count) {
+    if (!count) return;
+    if (!from->leaf) {
+        memmove(&to->child[at], &from->child[start], count * sizeof(Node *));
+        return;
+    }
+    for (unsigned f = 0; f < l->fields; ++f) {
+        size_t width = l->text_fields[f] ? sizeof(PureSpan) : sizeof(double);
+        memmove((char *)to + l->column[f] + at * width, (const char *)from + l->column[f] + start * width, count * width);
+    }
 }
 
-static void free_item(const PureList *list, PureCell *item) {
-    if (item) free_cells(item, list->fields, text_mask(list));
+/* A text's bytes, the list's own: after the list's share count when they
+ * were made. One made before the last share may be read by a shared copy. */
+static unsigned char *new_text(const PureList *list, const unsigned char *bytes, size_t size) {
+    uint64_t *made = malloc(sizeof(*made) + size);
+    if (!made) return NULL;
+    *made = list->shares;
+    memcpy(made + 1, bytes, size);
+    return (unsigned char *)(made + 1);
 }
 
+static bool shared_text(const PureList *list, const unsigned char *text) { return ((const uint64_t *)text)[-1] < list->shares; }
+static bool shared_node(const PureList *list, const Node *node) { return node->made < list->shares; }
+static void free_text(const unsigned char *text) { if (text) free((uint64_t *)text - 1); }
+
 /* Kept until the copies that may read it are gone (pure_retired_free). */
-static void retire(PureList *list, void *pointer, bool node) {
+static void retire(PureList *list, void *pointer, bool text) {
     PureRetired *retired = list->retired;
     if (retired->count == retired->capacity) {
         size_t capacity = retired->capacity ? 2 * retired->capacity : 16;
@@ -102,32 +136,37 @@ static void retire(PureList *list, void *pointer, bool node) {
         retired->entries = grown;
         retired->capacity = capacity;
     }
-    ((Retired *)retired->entries)[retired->count++] =
-        (Retired){pointer, node ? 0 : (uint16_t)text_mask(list), node ? 0 : (uint8_t)list->fields, node};
+    ((Retired *)retired->entries)[retired->count++] = (Retired){pointer, text};
+}
+
+/* The list no longer has text: free it, or retire it while a copy may read it. */
+static void let_go_text(PureList *list, const unsigned char *text) {
+    if (!text) return;
+    if (!shared_text(list, text)) free_text(text);
+    else retire(list, (void *)text, true);
 }
 
-/* The list no longer has item: free it, or retire it while a copy may read it. */
-static void let_go(PureList *list, PureCell *item) {
-    if (!shared(list, item)) free_item(list, item);
-    else retire(list, item, false);
+/* The texts of an item the list no longer has. */
+static void let_go_cells(PureList *list, const PureCell *cells) {
+    for (unsigned t = 0; t < list->layout.texts; ++t) let_go_text(list, cells[list->layout.text_field[t]].text);
 }
 
 void pure_retired_free(PureRetired *retired) {
     Retired *entries = retired->entries;
     for (size_t i = 0; i < retired->count; ++i) {
-        if (entries[i].node) free(entries[i].pointer);
-        else free_cells(entries[i].pointer, entries[i].fields, entries[i].text);
+        if (entries[i].text) free_text(entries[i].pointer);
+        else free(entries[i].pointer);
     }
     free(entries);
     *retired = (PureRetired){0};
 }
 
 static Node *new_node(PureList *list, bool leaf) {
-    Node *node = list->spare;
+    Node *node = list->spare[leaf];
     if (node) {
-        list->spare = node->slot[0];
-        --list->spares;
-    } else if (!(node = malloc(sizeof(*node))))
+        list->spare[leaf] = (Node *)node->first;
+        --list->spares[leaf];
+    } else if (!(node = malloc(leaf ? list->layout.leaf_size : INNER_SIZE)))
         return NULL;
     node->made = list->shares;
     node->count = 0;
@@ -140,11 +179,11 @@ static Node *new_node(PureList *list, bool leaf) {
 /* A node the list no longer has (its items and children dealt with):
  * retired while a copy may read it, else kept for the next or freed. */
 static void drop_node(PureList *list, Node *node) {
-    if (shared_node(list, node)) retire(list, node, true);
-    else if (list->spares < SPARE_NODES) {
-        node->slot[0] = list->spare;
-        list->spare = node;
-        ++list->spares;
+    if (shared_node(list, node)) retire(list, node, false);
+    else if (list->spares[node->leaf] < SPARE_NODES) {
+        node->first = list->spare[node->leaf];
+        list->spare[node->leaf] = node;
+        ++list->spares[node->leaf];
     } else
         free(node);
 }
@@ -152,26 +191,30 @@ static void drop_node(PureList *list, Node *node) {
 /* ---- The stored form: each field in order, a number as its binary64 bits
  * (little-endian), a text as a u32le length and its bytes. */
 
-static size_t cell_bytes(const PureList *list, unsigned field, PureCell cell) {
-    return list->text_fields[field] ? 4 + cell.size : 8;
-}
+static size_t cell_bytes(const Layout *l, unsigned field, PureCell cell) { return l->text_fields[field] ? 4 + cell.size : 8; }
 
-static size_t item_bytes(const PureList *list, const PureCell *item) {
-    size_t size = 0;
-    for (unsigned f = 0; f < list->fields; ++f) size += cell_bytes(list, f, item[f]);
+static size_t item_bytes(const Layout *l, const Node *leaf, unsigned i) {
+    size_t size = l->number_bytes;
+    for (unsigned t = 0; t < l->texts; ++t) size += 4 + texts(l, leaf, l->text_field[t])[i].size;
     return size;
 }
 
 /* A node's summary, from its items or children. */
 static void sum(const PureList *list, Node *node) {
+    const Layout *l = &list->layout;
     size_t items = 0, bytes = 0;
-    for (unsigned i = 0; i < node->count; ++i) {
-        if (node->leaf) ++items, bytes += item_bytes(list, item_in(node, i));
-        else items += child(node, i)->items, bytes += child(node, i)->bytes;
-    }
+    if (node->leaf) {
+        items = node->count;
+        bytes = items * l->number_bytes;
+        for (unsigned t = 0; t < l->texts; ++t) {
+            const PureSpan *column = texts(l, node, l->text_field[t]);
+            for (unsigned i = 0; i < node->count; ++i) bytes += 4 + column[i].size;
+        }
+    } else
+        for (unsigned i = 0; i < node->count; ++i) items += child(node, i)->items, bytes += child(node, i)->bytes;
     node->items = items;
     node->bytes = bytes;
-    node->first = !node->count ? NULL : node->leaf ? item_in(node, 0) : child(node, 0)->first;
+    node->first = !node->count ? NULL : node->leaf ? node : child(node, 0)->first;
 }
 
 /* ---- Finding positions */
@@ -201,6 +244,7 @@ static const Node *leaf_of(const PureList *list, size_t at, size_t *within) {
 /* Where an item starts in the draft: the bytes of the children before it,
  * level by level. */
 static size_t item_offset(const PureList *list, size_t at) {
+    const Layout *l = &list->layout;
     size_t offset = list->header;
     const Node *node = list->root;
     if (!node) return offset;
@@ -213,23 +257,27 @@ static size_t item_offset(const PureList *list, size_t at) {
         }
         node = child(node, i);
     }
-    for (unsigned i = 0; i < at && i < node->count; ++i) offset += item_bytes(list, item_in(node, i));
+    if (!l->texts) return offset + (at < node->count ? at : node->count) * l->number_bytes;
+    for (unsigned i = 0; i < at && i < node->count; ++i) offset += item_bytes(l, node, i);
     return offset;
 }
 
 /* The node at *place, the list's own to change: a copy (the node retired)
  * while a shared copy of the list may read it. NULL without memory. A copy
  * moves the version on even when the change it is for does not happen: the
- * list no longer has the nodes its shared copies have. */
+ * list no longer has the nodes its shared copies have. A leaf's copy has the
+ * texts of the leaf it copies: they stay shared, and are retired, not freed,
+ * when the list lets them go. */
 static Node *own(PureList *list, Node **place) {
     Node *node = *place;
     if (!shared_node(list, node)) return node;
     Node *mine = new_node(list, node->leaf);
     if (!mine) return NULL;
     uint64_t made = mine->made;
-    memcpy(mine, node, sizeof(*mine));
+    memcpy(mine, node, node->leaf ? list->layout.leaf_size : INNER_SIZE);
     mine->made = made;
-    retire(list, node, true);
+    if (mine->leaf) mine->first = mine->count ? mine : NULL;
+    retire(list, node, false);
     *place = mine;
     ++list->version;
     return mine;
@@ -237,7 +285,8 @@ static Node *own(PureList *list, Node **place) {
 
 /* The path to the leaf holding position at, each node the list's own, and
  * at's place in the leaf: the number of steps, 0 without memory (the list
- * is as it was: copies replace what they copy). */
+ * is as it was: copies replace what they copy). The nodes on the path then
+ * name the leaf that holds their first item, a copied one too. */
 static unsigned descend(PureList *list, size_t at, Step path[DEPTH], unsigned *within) {
     Node **place = &list->root;
     for (unsigned depth = 0; depth < DEPTH; ++depth) {
@@ -246,12 +295,13 @@ static unsigned descend(PureList *list, size_t at, Step path[DEPTH], unsigned *w
         if (node->leaf) {
             path[depth] = (Step){node, 0};
             *within = (unsigned)at;
+            for (unsigned d = depth; d-- > 0;) path[d].node->first = child(path[d].node, 0)->first;
             return depth + 1;
         }
         unsigned i = 0;
         while (i + 1 < node->count && at >= child(node, i)->items) at -= child(node, i)->items, ++i;
         path[depth] = (Step){node, i};
-        place = (Node **)&node->slot[i];
+        place = &node->child[i];
     }
     return 0;
 }
@@ -262,22 +312,24 @@ static void sum_path(const PureList *list, const Step *path, unsigned depth) {
 
 /* ---- Placing and removing */
 
-/* A place for an item: the path to it, and the nodes a split may take (one
- * a level and a root), made before anything changes so that placing cannot
- * fail. */
+/* A place for an item: the path to it, and the nodes a split may take (a
+ * leaf, then one a level above it and a root), made before anything changes
+ * so that placing cannot fail. */
 typedef struct {
     Step path[DEPTH];
     unsigned depth, within, extras, used;
+    bool appending; /* at the end of the list */
     Node *extra[DEPTH + 1];
 } Place;
 
 static bool prepare(PureList *list, size_t at, Place *p) {
     if (!list->root && !(list->root = new_node(list, true))) return false;
     p->extras = p->used = 0;
+    p->appending = at == list->count;
     if (!(p->depth = descend(list, at, p->path, &p->within))) return false;
     if (p->path[p->depth - 1].node->count < FANOUT) return true;
     for (; p->extras <= p->depth; ++p->extras)
-        if (!(p->extra[p->extras] = new_node(list, false))) {
+        if (!(p->extra[p->extras] = new_node(list, !p->extras))) {
             while (p->extras) drop_node(list, p->extra[--p->extras]);
             return false;
         }
@@ -288,37 +340,47 @@ static void release_extras(PureList *list, Place *p) {
     while (p->extras > p->used) drop_node(list, p->extra[--p->extras]);
 }
 
-/* pointer into the node at the end of the path, before index: a full node
- * splits in two halves and the new half goes into its parent, up to a new
- * root. */
-static void place(PureList *list, Place *p, void *pointer) {
+/* An item's cells (the list owns its texts from then on) into the leaf at
+ * the end of the path, before its within: a full node splits and the new
+ * node goes into its parent, up to a new root. A node splits in halves, but
+ * at the end of the list it stays full and the new one starts with the item
+ * alone: a list that grows at its end (a history, a keyed list filled in key
+ * order) fills its leaves. */
+static void place(PureList *list, Place *p, const PureCell *cells) {
+    const Layout *l = &list->layout;
     unsigned index = p->within;
+    Node *pointer = NULL; /* above the leaf: the node that goes in */
     for (unsigned d = p->depth; d-- > 0;) {
         Node *node = p->path[d].node;
         if (node->count < FANOUT) {
-            memmove(&node->slot[index + 1], &node->slot[index], (node->count - index) * sizeof(void *));
-            node->slot[index] = pointer;
+            move_items(l, node, index + 1, node, index, node->count - index);
+            if (node->leaf) put_cells(l, node, index, cells);
+            else node->child[index] = pointer;
             ++node->count;
             sum_path(list, p->path, d + 1);
             break;
         }
-        void *all[FANOUT + 1];
-        memcpy(all, node->slot, index * sizeof(void *));
-        all[index] = pointer;
-        memcpy(all + index + 1, node->slot + index, (FANOUT - index) * sizeof(void *));
+        unsigned keep = p->appending && index == FANOUT ? FANOUT : (FANOUT + 1) / 2;
         Node *right = p->extra[p->used++];
-        right->leaf = node->leaf;
-        node->count = (FANOUT + 1) / 2;
-        right->count = FANOUT + 1 - node->count;
-        memcpy(node->slot, all, node->count * sizeof(void *));
-        memcpy(right->slot, all + node->count, right->count * sizeof(void *));
+        if (index < keep) {
+            move_items(l, right, 0, node, keep - 1, FANOUT - (keep - 1));
+            move_items(l, node, index + 1, node, index, keep - 1 - index);
+            if (node->leaf) put_cells(l, node, index, cells);
+            else node->child[index] = pointer;
+        } else {
+            move_items(l, right, 0, node, keep, index - keep);
+            if (node->leaf) put_cells(l, right, index - keep, cells);
+            else right->child[index - keep] = pointer;
+            move_items(l, right, index - keep + 1, node, index, FANOUT - index);
+        }
+        node->count = keep;
+        right->count = FANOUT + 1 - keep;
         sum(list, node);
         sum(list, right);
         if (!d) { /* the root split: a new one above both halves */
             Node *root = p->extra[p->used++];
-            root->leaf = false;
-            root->slot[0] = node;
-            root->slot[1] = right;
+            root->child[0] = node;
+            root->child[1] = right;
             root->count = 2;
             sum(list, root);
             list->root = root;
@@ -332,13 +394,14 @@ static void place(PureList *list, Place *p, void *pointer) {
     ++list->version;
 }
 
-/* The item at the leaf's within, out of the tree (the caller keeps it): an
- * emptied node leaves its parent, a node that fits with a neighbour merges
- * into one (when the neighbour can be made the list's own), and a root with
- * one child gives way to it. */
+/* The item at the leaf's within, out of the tree (the caller has its cells):
+ * an emptied node leaves its parent, a node that fits with a neighbour
+ * merges into one (when the neighbour can be made the list's own), and a
+ * root with one child gives way to it. */
 static void take_out(PureList *list, Step *path, unsigned depth, unsigned within) {
+    const Layout *l = &list->layout;
     Node *leaf = path[depth - 1].node;
-    memmove(&leaf->slot[within], &leaf->slot[within + 1], (leaf->count - within - 1) * sizeof(void *));
+    move_items(l, leaf, within, leaf, within + 1, leaf->count - within - 1);
     --leaf->count;
     unsigned d = depth - 1;
     for (;; --d) {
@@ -348,21 +411,21 @@ static void take_out(PureList *list, Step *path, unsigned depth, unsigned within
         Node *parent = path[d - 1].node;
         unsigned at = path[d - 1].index;
         if (!node->count) {
-            memmove(&parent->slot[at], &parent->slot[at + 1], (parent->count - at - 1) * sizeof(void *));
+            memmove(&parent->child[at], &parent->child[at + 1], (parent->count - at - 1) * sizeof(Node *));
             --parent->count;
             drop_node(list, node);
             continue;
         }
         unsigned other = at + 1 < parent->count ? at + 1 : at ? at - 1 : at;
         Node *neighbour = other != at && node->count + child(parent, other)->count <= FANOUT
-                              ? own(list, (Node **)&parent->slot[other]) : NULL;
+                              ? own(list, &parent->child[other]) : NULL;
         if (!neighbour) break;
         Node *left = other < at ? neighbour : node, *right = other < at ? node : neighbour;
         unsigned left_at = other < at ? other : at;
-        memcpy(&left->slot[left->count], right->slot, right->count * sizeof(void *));
+        move_items(l, left, left->count, right, 0, right->count);
         left->count += right->count;
         sum(list, left);
-        memmove(&parent->slot[left_at + 1], &parent->slot[left_at + 2], (parent->count - left_at - 2) * sizeof(void *));
+        memmove(&parent->child[left_at + 1], &parent->child[left_at + 2], (parent->count - left_at - 2) * sizeof(Node *));
         --parent->count;
         drop_node(list, right);
     }
@@ -386,20 +449,30 @@ PureList *pure_list_new(unsigned fields, const uint8_t *text_fields) {
     if (fields > 16) return NULL;
     PureList *list = calloc(1, sizeof(*list));
     if (!list) return NULL;
-    list->fields = fields;
-    memcpy(list->text_fields, text_fields, fields);
+    Layout *l = &list->layout;
+    l->fields = fields;
+    size_t at = sizeof(Node);
+    for (unsigned f = 0; f < fields; ++f) {
+        l->text_fields[f] = text_fields[f] != 0;
+        l->column[f] = (uint32_t)at;
+        at += FANOUT * (l->text_fields[f] ? sizeof(PureSpan) : sizeof(double));
+        if (l->text_fields[f]) l->text_field[l->texts++] = (uint8_t)f;
+        else l->number_bytes += 8;
+    }
+    l->leaf_size = at;
     list->id = __atomic_add_fetch(&lists_made, 1, __ATOMIC_RELAXED);
     return list;
 }
 
-/* Every node and item below node let go (retired where a copy may read them). */
+/* Every node and text below node let go (retired where a copy may read them). */
 static void let_go_tree(PureList *list, Node *node) {
     if (!node) return;
+    const Layout *l = &list->layout;
     for (unsigned i = 0; i < node->count; ++i) {
-        if (node->leaf) let_go(list, item_in(node, i));
-        else let_go_tree(list, child(node, i));
+        if (!node->leaf) let_go_tree(list, child(node, i));
+        else for (unsigned t = 0; t < l->texts; ++t) let_go_text(list, texts(l, node, l->text_field[t])[i].data);
     }
-    if (shared_node(list, node)) retire(list, node, true);
+    if (shared_node(list, node)) retire(list, node, false);
     else free(node);
 }
 
@@ -409,11 +482,12 @@ void pure_list_free(PureList *list) {
         if (__atomic_sub_fetch(&list->refs, 1, __ATOMIC_ACQ_REL)) return;
     } else {
         let_go_tree(list, list->root);
-        while (list->spare) {
-            Node *next = list->spare->slot[0];
-            free(list->spare);
-            list->spare = next;
-        }
+        for (unsigned kind = 0; kind < 2; ++kind)
+            while (list->spare[kind]) {
+                Node *next = (Node *)list->spare[kind]->first;
+                free(list->spare[kind]);
+                list->spare[kind] = next;
+            }
     }
     free(list);
 }
@@ -423,9 +497,8 @@ size_t pure_list_count(const PureList *list) { return list->count; }
 PureList *pure_list_share(PureList *list, PureRetired *retired) {
     PureList *copy = malloc(sizeof(*copy));
     if (!copy) return NULL;
-    *copy = (PureList){.fields = list->fields, .root = list->root, .count = list->count, .id = list->id,
+    *copy = (PureList){.layout = list->layout, .root = list->root, .count = list->count, .id = list->id,
                        .version = list->version, .refs = 1, .copy = true};
-    memcpy(copy->text_fields, list->text_fields, sizeof(copy->text_fields));
     list->retired = retired;
     ++list->shares;
     return copy;
@@ -449,22 +522,21 @@ static bool log_change(PureUndo *undo, Entry entry) {
     return true;
 }
 
-static bool copy_cell(const PureList *list, unsigned field, PureCell from, PureCell *to) {
-    *to = (PureCell){.num = list->text_fields[field] ? 0 : from.num};
-    if (!list->text_fields[field] || !from.size) return true;
-    to->text = malloc(from.size);
-    if (!to->text) return false;
-    memcpy(to->text, from.text, from.size);
+/* A cell the list can keep: a text's bytes copied (NULL when empty). */
+static bool own_cell(const PureList *list, unsigned field, PureCell from, PureCell *to) {
+    *to = (PureCell){.num = list->layout.text_fields[field] ? 0 : from.num};
+    if (!list->layout.text_fields[field] || !from.size) return true;
+    if (!(to->text = new_text(list, from.text, from.size))) return false;
     to->size = from.size;
     return true;
 }
 
-static unsigned char *encode_cell(const PureList *list, unsigned field, PureCell cell, unsigned char *out) {
+static unsigned char *encode_cell(const Layout *l, unsigned field, PureCell cell, unsigned char *out) {
     uint64_t bits = cell.size;
     unsigned width = 4;
-    if (!list->text_fields[field]) { memcpy(&bits, &cell.num, sizeof(bits)); width = 8; }
+    if (!l->text_fields[field]) { memcpy(&bits, &cell.num, sizeof(bits)); width = 8; }
     for (unsigned i = 0; i < width; ++i) *out++ = (unsigned char)(bits >> (8 * i));
-    if (list->text_fields[field] && cell.size) { memcpy(out, cell.text, cell.size); out += cell.size; }
+    if (l->text_fields[field] && cell.size) { memcpy(out, cell.text, cell.size); out += cell.size; }
     return out;
 }
 
@@ -481,18 +553,21 @@ void pure_list_mirror(PureList *list, PureDraft *draft, size_t header) {
     list->header = header;
 }
 
-/* Every item in order, to visit (false stops it). */
-static bool visit_items(const Node *node, bool (*visit)(void *, PureCell *), void *context) {
-    for (unsigned i = 0; node && i < node->count; ++i)
-        if (node->leaf ? !visit(context, item_in(node, i)) : !visit_items(child(node, i), visit, context)) return false;
+/* Every leaf in order, to visit (false stops it). */
+static bool visit_leaves(const Node *node, bool (*visit)(void *, const Node *), void *context) {
+    if (!node) return true;
+    if (node->leaf) return visit(context, node);
+    for (unsigned i = 0; i < node->count; ++i)
+        if (!visit_leaves(child(node, i), visit, context)) return false;
     return true;
 }
 
-typedef struct { const PureList *list; unsigned char *at; } Encoding;
+typedef struct { const Layout *layout; unsigned char *at; } Encoding;
 
-static bool encode_item(void *context, PureCell *item) {
+static bool encode_leaf(void *context, const Node *leaf) {
     Encoding *e = context;
-    for (unsigned f = 0; f < e->list->fields; ++f) e->at = encode_cell(e->list, f, item[f], e->at);
+    for (unsigned i = 0; i < leaf->count; ++i)
+        for (unsigned f = 0; f < e->layout->fields; ++f) e->at = encode_cell(e->layout, f, cell_at(e->layout, leaf, i, f), e->at);
     return true;
 }
 
@@ -500,23 +575,24 @@ PURE_COLD PureResult pure_list_write(PureList *list) {
     size_t size = list->root ? list->root->bytes : 0;
     unsigned char *bytes = size ? malloc(size) : NULL;
     if (size && !bytes) return PURE_ALLOCATION;
-    Encoding encoding = {list, bytes};
-    visit_items(list->root, encode_item, &encoding);
+    Encoding encoding = {&list->layout, bytes};
+    visit_leaves(list->root, encode_leaf, &encoding);
     PureResult result = mirror(list, 0, 0, 0, bytes, size);
     free(bytes);
     return result;
 }
 
 PURE_COLD PureResult pure_list_read(PureList *list, const unsigned char *bytes, size_t size) {
+    const Layout *l = &list->layout;
     PureCell cells[16];
     for (size_t at = 0; at < size;) {
-        for (unsigned f = 0; f < list->fields; ++f) {
-            size_t width = list->text_fields[f] ? 4 : 8;
+        for (unsigned f = 0; f < l->fields; ++f) {
+            size_t width = l->text_fields[f] ? 4 : 8;
             if (size - at < width) return PURE_STORE_ERROR;
             uint64_t bits = 0;
             for (size_t i = 0; i < width; ++i) bits |= (uint64_t)bytes[at + i] << (8 * i);
             at += width;
-            if (!list->text_fields[f]) {
+            if (!l->text_fields[f]) {
                 cells[f] = (PureCell){0};
                 memcpy(&cells[f].num, &bits, sizeof(bits));
                 if (!isfinite(cells[f].num)) return PURE_STORE_ERROR;
@@ -534,24 +610,26 @@ PURE_COLD PureResult pure_list_read(PureList *list, const unsigned char *bytes,
 }
 
 PureResult pure_list_insert(PureList *list, size_t at, const PureCell *cells, PureUndo *undo) {
+    const Layout *l = &list->layout;
     if (at > list->count || list->count == PURE_LIST_ITEMS) return PURE_LIMIT;
-    PureCell *item = new_item(list);
-    if (!item) return PURE_ALLOCATION;
-    for (unsigned f = 0; f < list->fields; ++f)
-        if (!copy_cell(list, f, cells[f], &item[f])) { free_item(list, item); return PURE_ALLOCATION; }
-    size_t size = list->draft ? item_bytes(list, item) : 0;
+    PureCell item[16];
+    unsigned owned = 0;
+    for (; owned < l->fields; ++owned)
+        if (!own_cell(list, owned, cells[owned], &item[owned])) break;
+    size_t size = 0;
+    for (unsigned f = 0; list->draft && f < l->fields; ++f) size += cell_bytes(l, f, cells[f]);
     unsigned char *bytes = size ? malloc(size) : NULL, *end = bytes;
     Place p;
-    if ((size && !bytes) || !prepare(list, at, &p)) {
+    if (owned < l->fields || (size && !bytes) || !prepare(list, at, &p)) {
         free(bytes);
-        free_item(list, item);
+        for (unsigned f = 0; f < owned; ++f) free_text(item[f].text);
         return PURE_ALLOCATION;
     }
-    for (unsigned f = 0; bytes && f < list->fields; ++f) end = encode_cell(list, f, item[f], end);
+    for (unsigned f = 0; bytes && f < l->fields; ++f) end = encode_cell(l, f, item[f], end);
     if (undo && !log_change(undo, (Entry){.change = INSERTED, .list = list, .at = at})) {
         release_extras(list, &p);
         free(bytes);
-        free_item(list, item);
+        for (unsigned f = 0; f < l->fields; ++f) free_text(item[f].text);
         return PURE_ALLOCATION;
     }
     PureResult result = mirror(list, at, 0, 0, bytes, size);
@@ -559,69 +637,79 @@ PureResult pure_list_insert(PureList *list, size_t at, const PureCell *cells, Pu
     if (result != PURE_OK) {
         if (undo) --undo->count;
         release_extras(list, &p);
-        free_item(list, item);
+        for (unsigned f = 0; f < l->fields; ++f) free_text(item[f].text);
         return result;
     }
     place(list, &p, item);
     return PURE_OK;
 }
 
+/* Room for one more item's cells in the log. */
+static PureCell *log_cells(PureUndo *undo, unsigned fields) {
+    if (undo->cell_count + fields > undo->cell_capacity) {
+        size_t capacity = undo->cell_capacity ? 2 * undo->cell_capacity : 64;
+        while (capacity < undo->cell_count + fields) capacity *= 2;
+        PureCell *cells = realloc(undo->cells, capacity * sizeof(*cells));
+        if (!cells) return NULL;
+        undo->cells = cells;
+        undo->cell_capacity = capacity;
+    }
+    return undo->cells + undo->cell_count;
+}
+
 PureResult pure_list_remove(PureList *list, size_t at, PureUndo *undo) {
+    const Layout *l = &list->layout;
     if (at >= list->count) return PURE_NOT_FOUND;
     Step path[DEPTH];
     unsigned within, depth = descend(list, at, path, &within);
     if (!depth) return PURE_ALLOCATION;
-    PureCell *item = item_in(path[depth - 1].node, within);
-    if (!log_change(undo, (Entry){.change = REMOVED, .list = list, .at = at, .item = item})) return PURE_ALLOCATION;
-    PureResult result = mirror(list, at, 0, item_bytes(list, item), NULL, 0);
-    if (result != PURE_OK) { --undo->count; return result; }
+    Node *leaf = path[depth - 1].node;
+    PureCell *cells = undo ? log_cells(undo, l->fields) : NULL, kept[16];
+    if (undo && (!cells || !log_change(undo, (Entry){.change = REMOVED, .list = list, .at = at, .cells = undo->cell_count})))
+        return PURE_ALLOCATION;
+    if (!cells) cells = kept;
+    for (unsigned f = 0; f < l->fields; ++f) cells[f] = cell_at(l, leaf, within, f);
+    PureResult result = mirror(list, at, 0, item_bytes(l, leaf, within), NULL, 0);
+    if (result != PURE_OK) {
+        if (undo) --undo->count;
+        return result;
+    }
+    if (undo) undo->cell_count += l->fields;
+    else let_go_cells(list, cells);
     take_out(list, path, depth, within);
     return PURE_OK;
 }
 
-/* A shared item's copy with every field but one (left empty). */
-static PureCell *copy_item(const PureList *list, const PureCell *item, unsigned except) {
-    PureCell *fresh = new_item(list);
-    for (unsigned f = 0; fresh && f < list->fields; ++f)
-        if (f != except && !copy_cell(list, f, item[f], &fresh[f])) {
-            free_item(list, fresh);
-            fresh = NULL;
-        }
-    return fresh;
-}
-
 PureResult pure_list_set(PureList *list, size_t at, unsigned field, PureCell value, PureUndo *undo) {
+    const Layout *l = &list->layout;
     if (at >= list->count) return PURE_NOT_FOUND;
     Step path[DEPTH];
     unsigned within, depth = descend(list, at, path, &within);
     PureCell copy;
-    if (!depth || !copy_cell(list, field, value, &copy)) return PURE_ALLOCATION;
+    if (!depth || !own_cell(list, field, value, &copy)) return PURE_ALLOCATION;
     Node *leaf = path[depth - 1].node;
-    PureCell *item = item_in(leaf, within);
-    PureCell *fresh = shared(list, item) ? copy_item(list, item, field) : item;
-    size_t size = list->draft ? cell_bytes(list, field, copy) : 0;
+    PureCell old = cell_at(l, leaf, within, field);
+    size_t size = list->draft ? cell_bytes(l, field, copy) : 0;
     unsigned char *bytes = size ? malloc(size) : NULL;
-    Entry entry = fresh == item ? (Entry){.change = CHANGED, .list = list, .at = at, .field = field, .old = item[field]} :
-                                  (Entry){.change = REPLACED, .list = list, .at = at, .item = item};
-    if (!fresh || (size && !bytes) || !log_change(undo, entry)) {
+    if ((size && !bytes) ||
+        (undo && !log_change(undo, (Entry){.change = CHANGED, .list = list, .at = at, .field = field, .old = old}))) {
         free(bytes);
-        free(copy.text);
-        if (fresh != item) free_item(list, fresh);
+        free_text(copy.text);
         return PURE_ALLOCATION;
     }
-    if (bytes) encode_cell(list, field, copy, bytes);
+    if (bytes) encode_cell(l, field, copy, bytes);
     size_t offset = 0;
-    for (unsigned f = 0; f < field; ++f) offset += cell_bytes(list, f, item[f]);
-    PureResult result = mirror(list, at, offset, cell_bytes(list, field, item[field]), bytes, size);
+    for (unsigned f = 0; f < field; ++f) offset += cell_bytes(l, f, cell_at(l, leaf, within, f));
+    PureResult result = mirror(list, at, offset, cell_bytes(l, field, old), bytes, size);
     free(bytes);
     if (result != PURE_OK) {
-        --undo->count;
-        free(copy.text);
-        if (fresh != item) free_item(list, fresh);
+        if (undo) --undo->count;
+        free_text(copy.text);
         return result;
     }
-    fresh[field] = copy;
-    leaf->slot[within] = fresh;
+    if (l->text_fields[field]) texts(l, leaf, field)[within] = (PureSpan){copy.text, copy.size};
+    else numbers(l, leaf, field)[within] = copy.num;
+    if (!undo) let_go_text(list, old.text);
     sum_path(list, path, depth);
     ++list->version;
     return PURE_OK;
@@ -629,13 +717,26 @@ PureResult pure_list_set(PureList *list, size_t at, unsigned field, PureCell val
 
 PureCell pure_list_get(const PureList *list, size_t at, unsigned field) {
     size_t within;
-    return item_in(leaf_of(list, at, &within), (unsigned)within)[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;
+    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);
+    return true;
 }
 
 /* How two cells of a field order: numbers by value (-0 and +0 are one key),
  * texts by their bytes. */
-static int order(const PureList *list, unsigned field, PureCell a, PureCell b) {
-    if (!list->text_fields[field]) return (a.num > b.num) - (a.num < b.num);
+static int order(const Layout *l, unsigned field, PureCell a, PureCell b) {
+    if (!l->text_fields[field]) return (a.num > b.num) - (a.num < b.num);
     size_t shorter = a.size < b.size ? a.size : b.size;
     int bytes = shorter ? memcmp(a.text, b.text, shorter) : 0;
     return bytes ? (bytes > 0) - (bytes < 0) : (a.size > b.size) - (a.size < b.size);
@@ -644,6 +745,7 @@ static int order(const PureList *list, unsigned field, PureCell a, PureCell b) {
 /* Down the child whose first item's key is the last at or below key (the
  * first child when none is), then the leaf's first item not below it. */
 size_t pure_list_seek(const PureList *list, unsigned field, PureCell key, bool *found) {
+    const Layout *l = &list->layout;
     const Node *node = list->root;
     size_t start = 0;
     *found = false;
@@ -652,7 +754,7 @@ size_t pure_list_seek(const PureList *list, unsigned field, PureCell key, bool *
         unsigned low = 1, high = node->count;
         while (low < high) {
             unsigned middle = low + (high - low) / 2;
-            if (order(list, field, child(node, middle)->first[field], key) <= 0) low = middle + 1;
+            if (order(l, field, cell_at(l, child(node, middle)->first, 0, field), key) <= 0) low = middle + 1;
             else high = middle;
         }
         for (unsigned i = 0; i + 1 < low; ++i) start += child(node, i)->items;
@@ -661,65 +763,74 @@ size_t pure_list_seek(const PureList *list, unsigned field, PureCell key, bool *
     unsigned low = 0, high = node->count;
     while (low < high) {
         unsigned middle = low + (high - low) / 2;
-        if (order(list, field, item_in(node, middle)[field], key) < 0) low = middle + 1;
+        if (order(l, field, cell_at(l, node, middle, field), key) < 0) low = middle + 1;
         else high = middle;
     }
-    *found = low < node->count && !order(list, field, item_in(node, low)[field], key);
+    *found = low < node->count && !order(l, field, cell_at(l, node, low, field), key);
     return start + low;
 }
 
+/* An item where it is: its leaf and its place there. */
+typedef struct { const Node *leaf; unsigned index; } Ref;
+
+static PureCell ref_cell(const Layout *l, Ref r, unsigned field) { return cell_at(l, r.leaf, r.index, field); }
+
 /* Positions sorted by their items' field, stably (spare holds count). */
-PURE_COLD static void merge_sort(const PureList *list, unsigned field, PureCell *const *items, size_t *at, size_t *spare,
+PURE_COLD static void merge_sort(const Layout *l, unsigned field, const Ref *items, size_t *at, size_t *spare,
                                  size_t count) {
     if (count < 2) return;
     size_t half = count / 2, i = 0, j = half, k = 0;
-    merge_sort(list, field, items, at, spare, half);
-    merge_sort(list, field, items, at + half, spare, count - half);
+    merge_sort(l, field, items, at, spare, half);
+    merge_sort(l, field, items, at + half, spare, count - half);
     while (i < half && j < count)
-        spare[k++] = order(list, field, items[at[j]][field], items[at[i]][field]) < 0 ? at[j++] : at[i++];
+        spare[k++] = order(l, field, ref_cell(l, items[at[j]], field), ref_cell(l, items[at[i]], field)) < 0 ? at[j++] : at[i++];
     while (i < half) spare[k++] = at[i++];
     while (j < count) spare[k++] = at[j++];
     memcpy(at, spare, count * sizeof(*at));
 }
 
-typedef struct { PureCell **items; size_t count; } Gathered;
+typedef struct { Ref *items; size_t count; } Gathered;
 
-static bool gather_item(void *context, PureCell *item) {
+static bool gather_leaf(void *context, const Node *leaf) {
     Gathered *g = context;
-    g->items[g->count++] = item;
+    for (unsigned i = 0; i < leaf->count; ++i) g->items[g->count++] = (Ref){leaf, i};
     return true;
 }
 
 PURE_COLD PureResult pure_list_sorted(const PureList *list, unsigned field, PureList **out, size_t *moved) {
+    const Layout *l = &list->layout;
     *out = NULL;
-    Gathered gathered = {list->count ? malloc(list->count * sizeof(PureCell *)) : NULL, 0};
+    Gathered gathered = {list->count ? malloc(list->count * sizeof(Ref)) : NULL, 0};
     if (list->count && !gathered.items) return PURE_ALLOCATION;
-    visit_items(list->root, gather_item, &gathered);
-    PureCell **items = gathered.items;
+    visit_leaves(list->root, gather_leaf, &gathered);
+    const Ref *items = gathered.items;
     bool ordered = true;
-    for (size_t i = 1; i < list->count && ordered; ++i) ordered = order(list, field, items[i - 1][field], items[i][field]) < 0;
+    for (size_t i = 1; i < list->count && ordered; ++i)
+        ordered = order(l, field, ref_cell(l, items[i - 1], field), ref_cell(l, items[i], field)) < 0;
     if (ordered) {
-        free(items);
+        free(gathered.items);
         return PURE_OK;
     }
     size_t *at = malloc(2 * list->count * sizeof(*at));
     if (!at) {
-        free(items);
+        free(gathered.items);
         return PURE_ALLOCATION;
     }
     for (size_t i = 0; i < list->count; ++i) at[i] = i;
-    merge_sort(list, field, items, at, at + list->count, list->count);
+    merge_sort(l, field, items, at, at + list->count, list->count);
     PureResult result = PURE_OK;
     for (size_t i = 1; i < list->count && result == PURE_OK; ++i)
-        if (!order(list, field, items[at[i - 1]][field], items[at[i]][field])) result = PURE_CONFLICT;
-    PureList *sorted = result == PURE_OK ? pure_list_new(list->fields, list->text_fields) : NULL;
+        if (!order(l, field, ref_cell(l, items[at[i - 1]], field), ref_cell(l, items[at[i]], field))) result = PURE_CONFLICT;
+    PureList *sorted = result == PURE_OK ? pure_list_new(l->fields, l->text_fields) : NULL;
     if (result == PURE_OK && !sorted) result = PURE_ALLOCATION;
     for (size_t i = 0; result == PURE_OK && i < list->count; ++i) {
-        result = pure_list_insert(sorted, i, items[at[i]], NULL);
+        PureCell cells[16];
+        for (unsigned f = 0; f < l->fields; ++f) cells[f] = ref_cell(l, items[at[i]], f);
+        result = pure_list_insert(sorted, i, cells, NULL);
         moved[at[i]] = i;
     }
     free(at);
-    free(items);
+    free(gathered.items);
     if (result != PURE_OK) {
         pure_list_free(sorted);
         return result;
@@ -730,36 +841,36 @@ PURE_COLD PureResult pure_list_sorted(const PureList *list, unsigned field, Pure
 
 /* Undoing needs no memory but for a node an item goes back into (the event
  * took one out and the tree was since reshaped): without it, the process
- * stops rather than keep half an event (the store keeps the last save). */
+ * stops rather than keep half an event (the store keeps the last save). The
+ * texts undone were made during the event: no copy reads them. */
 void pure_undo_rollback(PureUndo *undo, size_t mark) {
     Entry *entries = undo->entries;
     for (size_t i = undo->count; i-- > mark;) {
         Entry *e = &entries[i];
         PureList *list = e->list;
+        const Layout *l = &list->layout;
         Step path[DEPTH];
         unsigned within, depth;
         if (e->change == REMOVED) {
             Place p;
             if (!prepare(list, e->at, &p)) abort();
-            place(list, &p, e->item);
+            place(list, &p, undo->cells + e->cells);
+            undo->cell_count = e->cells;
             continue;
         }
         if (!(depth = descend(list, e->at, path, &within))) abort();
         Node *leaf = path[depth - 1].node;
         if (e->change == INSERTED) {
-            PureCell *item = item_in(leaf, within);
+            for (unsigned t = 0; t < l->texts; ++t) free_text(texts(l, leaf, l->text_field[t])[within].data);
             take_out(list, path, depth, within);
-            free_item(list, item);
             continue;
         }
-        PureCell *item = item_in(leaf, within);
-        if (e->change == REPLACED) {
-            free_item(list, item);
-            leaf->slot[within] = e->item;
-        } else {
-            if (list->text_fields[e->field]) free(item[e->field].text);
-            item[e->field] = e->old;
-        }
+        if (l->text_fields[e->field]) {
+            PureSpan *text = &texts(l, leaf, e->field)[within];
+            free_text(text->data);
+            *text = (PureSpan){e->old.text, e->old.size};
+        } else
+            numbers(l, leaf, e->field)[within] = e->old.num;
         sum_path(list, path, depth);
         ++list->version;
     }
@@ -770,13 +881,14 @@ void pure_undo_commit(PureUndo *undo) {
     Entry *entries = undo->entries;
     for (size_t i = 0; i < undo->count; ++i) {
         Entry *e = &entries[i];
-        if (e->change == REMOVED || e->change == REPLACED) let_go(e->list, e->item);
-        else if (e->change == CHANGED && e->list->text_fields[e->field]) free(e->old.text);
+        if (e->change == REMOVED) let_go_cells(e->list, undo->cells + e->cells);
+        else if (e->change == CHANGED) let_go_text(e->list, e->old.text);
     }
-    undo->count = 0;
+    undo->count = undo->cell_count = 0;
 }
 
 void pure_undo_free(PureUndo *undo) {
     free(undo->entries);
+    free(undo->cells);
     *undo = (PureUndo){0};
 }
diff --git a/core/module-list.h b/core/module-list.h
index 38eb0f7..a3f4ad6 100644
--- a/core/module-list.h
+++ b/core/module-list.h
@@ -21,9 +21,23 @@
  * successful one frees what it replaced. */
 typedef struct { double num; unsigned char *text; size_t size; } PureCell;
 typedef struct PureList PureList;
-typedef struct { void *entries; size_t count, capacity; } PureUndo;
-/* Items a list let go while a shared copy may still read them. */
+/* An event's list changes; a removed item's cells wait in cells. */
+typedef struct {
+    void *entries;
+    size_t count, capacity;
+    PureCell *cells;
+    size_t cell_count, cell_capacity;
+} PureUndo;
+/* Nodes and texts a list let go while a shared copy may still read them. */
 typedef struct { void *entries; size_t count, capacity; } PureRetired;
+/* Items one after another, as a leaf of the list keeps them: positions start
+ * to start + count - 1, each field's cells side by side (a number field's as
+ * numbers, a text field's as spans). */
+typedef struct {
+    size_t start;
+    unsigned count;
+    union { const double *numbers; const PureSpan *texts; } column[16];
+} PureRun;
 
 enum { PURE_LIST_ITEMS = 1 << 24 };
 
@@ -31,16 +45,17 @@ PureList *pure_list_new(unsigned fields, const uint8_t *text_fields);
 void pure_list_free(PureList *);
 size_t pure_list_count(const PureList *);
 /* Share the items as they are with a read-only copy (for readers on other
- * threads), without copying them: from then on the list copies an item it
- * changes, and items it lets go go to retired instead of being freed, since
- * the copy may still read them. The copy is freed with pure_list_free, on any
- * thread, when its last reference goes (pure_list_hold takes one more). Only
- * between events (no change waits to be committed or undone). */
+ * threads), without copying them: from then on the list copies the nodes it
+ * changes, and nodes and texts it lets go go to retired instead of being
+ * freed, since the copy may still read them. The copy is freed with
+ * pure_list_free, on any thread, when its last reference goes
+ * (pure_list_hold takes one more). Only between events (no change waits to
+ * be committed or undone). */
 PureList *pure_list_share(PureList *, PureRetired *retired);
 void pure_list_hold(PureList *copy);
 /* Whether copy shares list's items as they are now. */
 bool pure_list_current(const PureList *copy, const PureList *list);
-/* Free items retired while no copy that shared them remains. */
+/* Free what was retired while no copy that shared it remains. */
 void pure_retired_free(PureRetired *);
 /* Insert a copy of cells (text bytes are copied) before position at. A NULL
  * log means the change is not undone. */
@@ -48,6 +63,9 @@ 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. */
+bool pure_list_run(const PureList *, size_t at, 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. */