HASHED (023): an event's list keyed by numbers that came out of order keeps each item's cells at its key's slot in its members' table, found by key there (the key and its cells read at one slot, as C's table); its order made by a radix sort of the slots' keys when something asks for a position (twice an event, then FLAT or a tree). The tier finds by key alone in a HASHED list (its bits' bit 1, its limit all ones: the bounds checked at a loop's opening still hold) out of the line; a list keyed by each count in order is DENSE from its first item. join 531 to 108 ms (3.5x C), sort 98 to 58 (2.1x)

arrays_equivalence counts the HASHED form against a tree; module_tier's programs read a HASHED list by key

3 files changed, 279 insertions, 18 deletions

diff --git a/core/module-jit.c b/core/module-jit.c
index 4e91a38..7703b63 100644
--- a/core/module-jit.c
+++ b/core/module-jit.c
@@ -243,7 +243,7 @@ enum { SLOT = sizeof(Slot) };
 #define AT(h) ((size_t)(h) * SLOT)
 /* An index's list, beside its value in its slot. */
 enum { OWNER = offsetof(Slot, bytes) + offsetof(PureBytes, owner) };
-enum { TREE_FORM = 0, FLAT_FORM = 1, DENSE_FORM = 2 }; /* pure_list_form */
+enum { TREE_FORM = 0, FLAT_FORM = 1, DENSE_FORM = 2, HASHED_FORM = 3 }; /* pure_list_form */
 
 /* A slot's value as compiled: in the slot (MEM), a constant (its bits), a
  * number in a d register, a whole number from 0 below 2^64 in an x register
@@ -3005,8 +3005,13 @@ typedef struct {
     uint64_t *live_in;     /* by instruction from the block's start: the locals read before written from there (tier_liveness) */
     int fields[64];        /* the message's fields read: each once (+1; 0 none yet) */
     uint64_t slots;        /* the nest's loops' slots (kept as live: their loops write them) */
+    struct TProbe *probes; /* HASHED lists' finds, made after the items (tier_probe) */
+    size_t probe_count, probe_room;
 } Tier;
 
+/* A find in a HASHED list, out of the line: value v's, its result r, its key's and bits' registers, its labels. */
+typedef struct TProbe { int v; unsigned r, key, bits; int hashed, fail, done; } TProbe;
+
 static void titem(Tier *t, unsigned kind, int value, int merge, int loop);
 
 static int tval(Tier *t, unsigned op, unsigned rep, int a, int b, int c) {
@@ -4122,6 +4127,11 @@ static void tuse_way(Tier *t, const bool *need, int g, int way, int at, int k, i
     }
 }
 
+/* Whether value v finds by key in a list that may be HASHED (found by key alone, not full). */
+static bool thashes(const Tier *t, const TVal *v) {
+    return (v->op == T_FIND_GET || v->op == T_HAS) && t->lists && !t->lists[v->list].full;
+}
+
 /* Whether loop l's latch pays for its next round: the outermost count's (the generic code opened it); the others paid for all their rounds as they opened. */
 static bool tlatch_pays(const Tier *t, int l) { return l == 0 && !t->loops[l].walk; }
 
@@ -4707,6 +4717,52 @@ static unsigned tcompare(Tier *t, const TVal *v) {
     return v->op == T_LT ? LT : v->op == T_LE ? LE : v->op == T_GT ? GT : v->op == T_GE ? GE : v->op == T_EQ ? EQ : NE;
 }
 
+/* A HASHED list's key (value v's) found by its table, out of the line (at
+ * label hashed): the slot of the key's bits (member_slot) and on while
+ * another key holds it; there, its cell at that slot (FIND_GET) or 1 (HAS);
+ * a VACANT slot, not there: to fail (FIND_GET) or 0 (HAS). Its members
+ * from its bits (their bit 1 cleared), its mask from the list. */
+static void tier_probe(Tier *t, const TVal *v, unsigned r, unsigned key, unsigned bits, int hashed, int fail, int done) {
+    Emit *e = t->k->e;
+    int probe = new_label(e), there = new_label(e);
+    bind(e, hashed);
+    fp2(e, SCVTF_X, D0, key);
+    fp2(e, FMOV_XD, X16, D0); /* the key's bits (a whole number's: never -0) */
+    mov_imm(e, X17, UINT64_C(0xff51afd7ed558ccd));
+    put(e, 0xCA400000 | X16 << 16 | 33u << 10 | X16 << 5 | X10); /* EOR x10, x16, x16, LSR #33 */
+    mul_reg(e, X17, X10, X17);
+    put(e, 0xCA400000 | X17 << 16 | 33u << 10 | X17 << 5 | X17); /* EOR x17, x17, x17, LSR #33 */
+    load64(e, X9, tbase(t, B_LISTS, X9), (size_t)v->list * sizeof(PureList *));
+    load64(e, X10, X9, pure_list_layout[LIST_MEMBER_CAPACITY_AT]);
+    sub_imm(e, X10, X10, 1);
+    put(e, 0x8A000000 | X10 << 16 | X17 << 5 | X17);  /* AND x17, x17, x10: the slot */
+    put(e, 0x927EF400 | bits << 5 | X9);               /* AND x9, bits, #~3: the members */
+    mov_imm(e, X1, UINT64_C(0x7FF8000000000001));      /* VACANT */
+    bind(e, probe);
+    load64_index(e, X0, X9, X17);
+    cmp_reg(e, X0, X16);
+    b_cond(e, EQ, there);
+    cmp_reg(e, X0, X1);
+    if (v->op == T_HAS) {
+        cset(e, r, NE);
+        b_cond(e, EQ, done);
+    } else
+        b_cond(e, EQ, fail);
+    add_imm(e, X17, X17, 1);
+    put(e, 0x8A000000 | X10 << 16 | X17 << 5 | X17);
+    b(e, probe);
+    bind(e, there);
+    if (v->op == T_HAS) mov_w(e, r, 1);
+    else load32_index(e, r, treg(t, v->c), X17); /* its cell at its slot: four bytes (pure_list_suits widened one) */
+    b(e, done);
+}
+
+/* A find in a HASHED list kept to be made after the items. */
+static void tier_later(Tier *t, TProbe probe) {
+    if (!grow_array((void **)&t->probes, &t->probe_room, t->probe_count + 1, sizeof(*t->probes))) t->k->e->failed = true;
+    else t->probes[t->probe_count++] = probe;
+}
+
 /* A value's code. */
 static void tier_value(Tier *t, int vi) {
     Block *k = t->k;
@@ -4738,11 +4794,15 @@ static void tier_value(Tier *t, int vi) {
                 load8(e, X9, X16, pure_list_layout[LIST_WIDTH_AT] + v->field);
                 orr_lsl(e, r, r, X9, 56);
             } else if (v->field == L_COUNT) load64(e, r, X16, pure_list_layout[LIST_COUNT_AT]);
-            else if (v->field == L_BITS) { /* bit 0 set: every key below the count there (as pure_list_suits found it), no bit to test */
+            else if (v->field == L_BITS) { /* bit 0 set: every key below the count there (as pure_list_suits found it), no bit to test; bit 1: HASHED */
                 load64(e, r, X16, pure_list_layout[LIST_MEMBERS_AT]);
                 load8(e, X17, X16, pure_list_layout[LIST_FULL_AT]);
                 orr_reg(e, r, r, X17);
-            } else { /* the keys the bits reach: none without bits; a full list's, its count */
+                load8(e, X17, X16, pure_list_layout[LIST_FORM_AT]);
+                cmp_w_imm(e, X17, HASHED_FORM);
+                cset(e, X17, EQ);
+                orr_lsl(e, r, r, X17, 1);
+            } else if (v->field == L_LIMIT) { /* the keys the bits reach: none without bits; a full list's, its count; a HASHED one's all */
                 load64(e, r, X16, pure_list_layout[LIST_MEMBER_CAPACITY_AT]);
                 lsl_imm(e, r, r, 6);
                 load8(e, X17, X16, pure_list_layout[LIST_BITMAP_AT]);
@@ -4752,6 +4812,9 @@ static void tier_value(Tier *t, int vi) {
                 load64(e, X17, X16, pure_list_layout[LIST_COUNT_AT]);
                 cmp_w_imm(e, X9, 0);
                 csel(e, r, X17, r, NE);
+                load8(e, X17, X16, pure_list_layout[LIST_FORM_AT]);
+                cmp_w_imm(e, X17, HASHED_FORM);
+                put(e, 0xDA9F1000 | r << 5 | r); /* CSINV r, r, xzr, NE: all ones where HASHED */
             }
             return;
         }
@@ -4938,10 +5001,11 @@ static void tier_value(Tier *t, int vi) {
         load32_index(e, r, column, at); /* four bytes (pure_list_suits widened one) */
         return;
     }
-    case T_FIND_GET: case T_FIND: case T_HAS: { /* by key: in the bits (below their reach), its cell at its key */
+    case T_FIND_GET: case T_FIND: case T_HAS: { /* by key: in the bits (below their reach), its cell at its key; a HASHED list's by its table */
         unsigned key = tx(t, v->a, X0, fail), bits = treg(t, v->b);
         unsigned limit = treg(t, v->op == T_FIND_GET ? v->d : v->c);
         bool full = t->lists[v->list].full; /* every key below its count there (pure_list_suits): the bits not read */
+        int hashed = thashes(t, v) ? new_label(e) : -1, done = new_label(e); /* its bits' bit 1: HASHED (its limit all ones) */
         if (v->op == T_HAS && full) {
             if (v->proven) mov_w(e, r, 1);
             else {
@@ -4951,7 +5015,7 @@ static void tier_value(Tier *t, int vi) {
             return;
         }
         if (v->op == T_HAS) {
-            int no = new_label(e), done = new_label(e), bit = new_label(e);
+            int no = new_label(e), bit = new_label(e);
             if (!v->proven) {
                 cmp_reg(e, key, limit);
                 b_cond(e, HS, no);
@@ -4960,13 +5024,16 @@ static void tier_value(Tier *t, int vi) {
             mov_w(e, r, 1); /* full: there */
             b(e, done);
             bind(e, bit);
+            if (hashed >= 0) tbnz(e, bits, 1, hashed);
             lsr_imm(e, X16, key, 6);
             load64_index(e, X16, bits, X16);
             lsr_reg(e, X16, X16, key);
             and_w_one(e, r, X16);
             b(e, done);
             bind(e, no);
+            if (hashed >= 0) tbnz(e, bits, 1, hashed); /* a HASHED list's key past its limit: -1 */
             mov_w(e, r, 0);
+            if (hashed >= 0) tier_later(t, (TProbe){vi, r, key, bits, hashed, -1, done});
             bind(e, done);
             return;
         }
@@ -4977,6 +5044,7 @@ static void tier_value(Tier *t, int vi) {
         if (!full) {
             int there = new_label(e);
             tbnz(e, bits, 0, there); /* full as it began: every key below its count there */
+            if (hashed >= 0) tbnz(e, bits, 1, hashed);
             lsr_imm(e, X16, key, 6);
             load64_index(e, X16, bits, X16);
             lsr_reg(e, X16, X16, key);
@@ -4988,6 +5056,8 @@ static void tier_value(Tier *t, int vi) {
             return;
         }
         load32_index(e, r, treg(t, v->c), key); /* four bytes (pure_list_suits widened one) */
+        if (hashed >= 0) tier_later(t, (TProbe){vi, r, key, bits, hashed, fail, done});
+        bind(e, done);
         return;
     }
     case T_SET: { /* by position (below the count; a position found is), a whole number fitting its column's cells */
@@ -5193,6 +5263,10 @@ static void tier_emit(Tier *t, int entry, int fallback) {
         default: break;
         }
     }
+    for (size_t i = 0; i < t->probe_count; ++i) {
+        const TProbe *p = &t->probes[i];
+        tier_probe(t, &t->vals[p->v], p->r, p->key, p->bits, p->hashed, p->fail, p->done);
+    }
     for (size_t s = 0; s < t->snap_count; ++s)
         if (t->snaps[s].needed) tier_stub(t, (int)s);
 }
@@ -5205,7 +5279,7 @@ static void tier_free(Tier *t) {
         free(t->merges[i].ways);
         free(t->merges[i].phis);
     }
-    free(t->vals), free(t->snaps), free(t->merges), free(t->items), free(t->merge_at), free(t->entry), free(t->lists), free(t->live_in);
+    free(t->vals), free(t->snaps), free(t->merges), free(t->items), free(t->merge_at), free(t->entry), free(t->lists), free(t->live_in), free(t->probes);
 }
 
 /* The handler's message input the block is, or -1. */
diff --git a/core/module-list.c b/core/module-list.c
index a798c41..9f576a8 100644
--- a/core/module-list.c
+++ b/core/module-list.c
@@ -86,9 +86,11 @@ struct PureList {
     /* An event's list may keep its items in arrays rather than a tree
      * (pure_list_arrays, docs/design/021): FLAT, each field's cells side by
      * side in the list's order; DENSE (keyed by small whole numbers, its keys
-     * as bits), each field's cells at its key. What the arrays cannot answer
-     * at once (a position in a DENSE list; a change logged to be undone, a
-     * record, a share) makes them FLAT, or a tree, first. */
+     * as bits), each field's cells at its key; HASHED (keyed by numbers that
+     * came out of order), each field's cells at its key's slot in its
+     * members' table (as a DENSE list's at its key). What the arrays cannot answer at
+     * once (a position in a DENSE or HASHED list; a change logged to be
+     * undone, a record, a share) makes them FLAT, or a tree, first. */
     uint8_t form;
     bool arrays;       /* it may be FLAT or DENSE: an event's list */
     uint8_t flattened; /* DENSE made FLAT since it was cleared: twice, and it stays FLAT or a tree */
@@ -777,7 +779,7 @@ static void take_out(PureList *list, Step *path, unsigned depth, unsigned within
 
 /* ---- An event's list in arrays (docs/design/021) */
 
-enum { TREE, FLAT, DENSE };
+enum { TREE, FLAT, DENSE, HASHED };
 /* The arrays a clear keeps for the next event; the most they grow to (a
  * larger list is a tree: doubling arrays would hold twice its items); a
  * DENSE list's slack beyond four times its items (so it never holds far more
@@ -985,7 +987,7 @@ static bool arrays_room(PureList *list, size_t room) {
 
 /* Field f's column bytes wide (wider): false without memory (as it was). */
 static bool widen(PureList *list, unsigned f, uint8_t bytes) {
-    size_t rows = list->form == DENSE ? list->room : list->count;
+    size_t rows = list->form == DENSE || list->form == HASHED ? list->room : list->count;
     void *made = malloc((list->room ? list->room : 1) * bytes);
     if (!made) return false;
     for (size_t i = 0; i < rows; ++i) cell_out(made, bytes, i, array_cell(list, i, f));
@@ -1094,6 +1096,8 @@ static void let_go_rows(PureList *list) {
     if (!l->texts) return;
     for (size_t i = 0; list->form == FLAT && i < list->count; ++i)
         for (unsigned t = 0; t < l->texts; ++t) free_text(array_cell(list, i, l->text_field[t]).text);
+    for (size_t i = 0; list->form == HASHED && i < list->member_capacity; ++i)
+        for (unsigned t = 0; list->members[i] != VACANT && t < l->texts; ++t) free_text(array_cell(list, i, l->text_field[t]).text);
     for (size_t w = 0; list->form == DENSE && w < list->member_capacity; ++w)
         for (uint64_t word = list->members[w]; word; word &= word - 1)
             for (unsigned t = 0; t < l->texts; ++t)
@@ -1178,6 +1182,157 @@ static bool make_flat(PureList *list) {
     return true;
 }
 
+/* Cell from of a column of cells w bytes wide copied to cell to of another. */
+static inline void cell_copy(void *to_column, size_t to, const void *from_column, size_t from, size_t w) {
+    char *t = (char *)to_column + to * w;
+    const char *f = (const char *)from_column + from * w;
+    switch (w) {
+    case 1: *t = *f; break;
+    case 4: memcpy(t, f, 4); break;
+    case 8: memcpy(t, f, 8); break;
+    default: memcpy(t, f, sizeof(PureSpan));
+    }
+}
+
+/* A HASHED list's slot of key (its cells there), or SIZE_MAX. */
+static size_t hashed_slot(const PureList *list, double key) {
+    uint64_t bits = key_bits(key);
+    size_t mask = list->member_capacity - 1;
+    for (size_t at = member_slot(bits, mask);; at = (at + 1) & mask) {
+        if (list->members[at] == bits) return at;
+        if (list->members[at] == VACANT) return SIZE_MAX;
+    }
+}
+
+/* A HASHED list's table and columns of capacity slots (a power of two
+ * above twice its items), each item's cells at its key's slot: from a FLAT
+ * list's rows, or a HASHED one's slots. False without memory (the list as
+ * it was). */
+static bool hashed_table(PureList *list, size_t capacity) {
+    const Layout *l = &list->layout;
+    uint64_t *table = malloc(capacity * sizeof(*table));
+    void *columns[16] = {0};
+    bool ok = table != NULL;
+    for (unsigned f = 0; ok && f < l->fields; ++f) ok = !list->width[f] || (columns[f] = malloc(capacity * list->width[f])) != NULL;
+    if (!ok) {
+        free(table);
+        for (unsigned f = 0; f < 16; ++f) free(columns[f]);
+        return false;
+    }
+    for (size_t i = 0; i < capacity; ++i) table[i] = VACANT;
+    bool hashed = list->form == HASHED;
+    const double *keys = list->columns[l->key];
+    size_t mask = capacity - 1, rows = hashed ? list->member_capacity : list->count;
+    for (size_t row = 0; row < rows; ++row) {
+        if (hashed && list->members[row] == VACANT) continue;
+        uint64_t bits = hashed ? list->members[row] : key_bits(keys[row]);
+        size_t at = member_slot(bits, mask);
+        while (table[at] != VACANT) at = (at + 1) & mask;
+        table[at] = bits;
+        for (unsigned f = 0; f < l->fields; ++f)
+            if (list->width[f]) cell_copy(columns[f], at, list->columns[f], row, list->width[f]);
+    }
+    arrays_free(list);
+    memcpy(list->columns, columns, sizeof(columns));
+    list->room = capacity;
+    free(list->members);
+    ++list->removes;
+    list->members = table, list->member_capacity = capacity, list->member_count = list->count;
+    list->bitmap = false;
+    return true;
+}
+
+/* A FLAT list whose keys come out of order as HASHED; false when it may
+ * not be (made FLAT twice since it was cleared, or packed) or without
+ * memory: it stays FLAT. */
+static bool make_hashed(PureList *list) {
+    if (list->layout.key < 0 || list->pack || list->flattened >= 2) return false;
+    size_t capacity = 16;
+    while (capacity < 2 * (list->count + 1)) capacity *= 2;
+    if (!hashed_table(list, capacity)) return false;
+    list->form = HASHED;
+    list->full = false, list->keys_seen = 0; /* a DENSE list's keys: counted again when it is one again */
+    ++list->version;
+    return true;
+}
+
+/* Whether a HASHED list's next item would grow its arrays past ARRAYS_LARGE. */
+static bool hashed_large(const PureList *list) {
+    return 2 * (list->count + 1) > list->member_capacity && 2 * list->member_capacity * row_width(&list->layout) > ARRAYS_LARGE;
+}
+
+/* An item (its cells the list's own, its key not there) into a HASHED
+ * list at its key's slot; false without memory (as it was). */
+static bool hashed_add(PureList *list, const PureCell *item) {
+    const Layout *l = &list->layout;
+    if (2 * (list->count + 1) > list->member_capacity && !hashed_table(list, 2 * list->member_capacity)) return false;
+    uint64_t bits = key_bits(item[l->key].num);
+    size_t mask = list->member_capacity - 1, at = member_slot(bits, mask);
+    while (list->members[at] != VACANT) at = (at + 1) & mask;
+    list->members[at] = bits;
+    for (unsigned f = 0; f < l->fields; ++f) array_put(list, at, f, item[f]);
+    ++list->member_count;
+    ++list->count;
+    ++list->version;
+    return true;
+}
+
+typedef struct { uint64_t key; uint32_t slot; } Ordered;
+
+/* A HASHED list as FLAT, its items in key order: its slots sorted by their
+ * keys' bits as unsigned numbers in the keys' order (-0 as +0), eight bits
+ * a pass from the lowest (a pass whose bits every key shares skipped), each
+ * column made again in that order; its members' table stays its keys' set.
+ * False without memory (the list as it was). */
+static bool make_ordered(PureList *list) {
+    const Layout *l = &list->layout;
+    size_t n = list->count, room = n > 16 ? n : 16;
+    Ordered *a = malloc((n ? n : 1) * sizeof(*a)), *b = malloc((n ? n : 1) * sizeof(*b));
+    void *columns[16] = {0};
+    bool ok = a && b;
+    for (unsigned f = 0; ok && f < l->fields; ++f) ok = !list->width[f] || (columns[f] = malloc(room * list->width[f])) != NULL;
+    if (!ok) {
+        free(a), free(b);
+        for (unsigned f = 0; f < 16; ++f) free(columns[f]);
+        return false;
+    }
+    for (size_t slot = 0, i = 0; slot < list->member_capacity; ++slot) {
+        uint64_t bits = list->members[slot];
+        if (bits != VACANT) a[i++] = (Ordered){bits >> 63 ? ~bits : bits | UINT64_C(1) << 63, (uint32_t)slot};
+    }
+    for (unsigned shift = 0; n && shift < 64; shift += 8) {
+        size_t counts[256] = {0};
+        for (size_t i = 0; i < n; ++i) ++counts[a[i].key >> shift & 255];
+        if (counts[a[0].key >> shift & 255] == n) continue;
+        for (size_t d = 0, sum = 0; d < 256; ++d) {
+            size_t c = counts[d];
+            counts[d] = sum, sum += c;
+        }
+        for (size_t i = 0; i < n; ++i) b[counts[a[i].key >> shift & 255]++] = a[i];
+        Ordered *t = a;
+        a = b, b = t;
+    }
+    for (unsigned f = 0; f < l->fields; ++f) {
+        size_t w = list->width[f];
+        for (size_t i = 0; w && i < n; ++i) cell_copy(columns[f], i, list->columns[f], a[i].slot, w);
+    }
+    free(a), free(b);
+    arrays_free(list);
+    memcpy(list->columns, columns, sizeof(columns));
+    list->room = room;
+    list->form = FLAT;
+    list->moved = 0;
+    ++list->flattened;
+    ++list->version;
+    return true;
+}
+
+/* A list read by position that may be HASHED made FLAT: memory for it or
+ * none (the process stops rather than read items out of their order). */
+static void ordered_now(const PureList *list) {
+    if (list->form == HASHED && !make_ordered((PureList *)list)) abort();
+}
+
 /* Every node below node freed, its texts not (they are a FLAT list's still). */
 static void free_nodes(Node *node) {
     if (!node) return;
@@ -1241,6 +1396,7 @@ static bool build_tree(PureList *list, Node **root) {
 static bool make_tree(PureList *list) {
     if (list->form == TREE) return true;
     if (list->form == DENSE && !make_flat(list)) return false;
+    if (list->form == HASHED && !make_ordered(list)) return false;
     Node *root;
     if (!build_tree(list, &root)) return false;
     arrays_free(list);
@@ -1368,6 +1524,7 @@ static bool dense_add(PureList *list, const PureCell *item, double number) {
 /* The list as a form that answers by position (FLAT or a tree): a DENSE
  * one made FLAT, a tree when it was made FLAT too often; false without memory. */
 static bool positioned(PureList *list) {
+    if (list->form == HASHED) return make_ordered(list);
     if (list->form != DENSE) return true;
     if (list->flattened >= 2) return make_tree(list);
     return make_flat(list);
@@ -1510,10 +1667,10 @@ bool pure_list_full(PureList *list) { return list->form == DENSE && list->count
 
 bool pure_list_suits(PureList *list, unsigned needs, unsigned narrow) {
     if (list->form == DENSE && !dense_keys(list)) return false; /* its keys counted: full as it is (the tier reads it, LIST_FULL_AT) */
-    if (needs & 1 && list->form != DENSE) return false;                                /* by key: at its keys */
+    if (needs & 1 && list->form != DENSE && !(list->form == HASHED && needs == 1)) return false; /* by key: at its keys, or its rows (by key alone) */
     if (needs & 2 && list->form != FLAT && !(list->form == DENSE && dense_keys(list) && list->full)) return false; /* by position */
     if (needs & 4 && !(list->form == DENSE && dense_keys(list) && list->full)) return false; /* a key its position */
-    if (list->form != FLAT && list->form != DENSE) return false;
+    if (list->form != FLAT && list->form != DENSE && list->form != HASHED) return false;
     for (unsigned f = 0; f < list->layout.fields; ++f) { /* its cells of one byte widened to four: the tier's code reads four */
         if (!(narrow >> f & 1)) continue;
         if (list->width[f] == 1 && !widen(list, f, 4)) return false;
@@ -1590,6 +1747,12 @@ bool pure_list_lookup(const PureList *list, unsigned key_field, PureCell key, un
         *cell = array_cell(list, (size_t)key.num, field);
         return true;
     }
+    if (list->form == HASHED && (int)key_field == list->layout.key) { /* at its key's slot, by its table */
+        size_t slot = hashed_slot(list, key.num);
+        if (slot == SIZE_MAX) return false;
+        *cell = array_cell(list, slot, field);
+        return true;
+    }
     size_t at = pure_list_seek(list, key_field, key, &found);
     if (found) *cell = pure_list_get(list, at, field);
     return found;
@@ -2018,6 +2181,23 @@ PureResult pure_list_add(PureList *list, const PureCell *cells, PureUndo *undo,
     if (list->form != TREE) {
         double key = cells[l->key].num;
         bool found = false;
+        if (list->form == HASHED) { /* by its table, at its end: no position, unless asked */
+            if (hashed_slot(list, key) != SIZE_MAX && !at) return *exists = true, PURE_OK;
+            if (!at && !hashed_large(list)) {
+                if (list->count == PURE_LIST_ITEMS) return PURE_LIMIT;
+                PureCell item[16];
+                unsigned owned = 0;
+                for (; owned < l->fields; ++owned)
+                    if (!own_cell(list, owned, cells[owned], &item[owned])) break;
+                if (owned < l->fields || !arrays_fit(list, cells) || !hashed_add(list, item)) {
+                    for (unsigned f = 0; f < owned; ++f) free_text(item[f].text);
+                    return PURE_ALLOCATION;
+                }
+                list->bytes += cells_bytes(l, item);
+                return PURE_OK;
+            }
+            if (!positioned(list)) return PURE_ALLOCATION;
+        }
         if (list->form == DENSE) { /* by its bits, at its key: no position, unless asked */
             if (pure_list_contains(list, key, &found) && found && !at) return *exists = true, PURE_OK;
             if (!at && !found && dense_holds(list, key)) {
@@ -2041,7 +2221,10 @@ PureResult pure_list_add(PureList *list, const PureCell *cells, PureUndo *undo,
                 if (at) *at = low;
                 return *exists = true, PURE_OK;
             }
-            if (!at && n >= FLAT_SMALL && (low < n || !list->flattened) && make_dense(list, key)) /* small keys: DENSE (in order too, 023) */
+            if (!at && (n >= FLAT_SMALL || (low == n && key == (double)n)) && (low < n || !list->flattened) && make_dense(list, key))
+                /* small keys: DENSE (in order too, and from the first when each is the count, 023) */
+                return pure_list_add(list, cells, undo, at, exists);
+            if (!at && n >= FLAT_SMALL && low < n && make_hashed(list)) /* other keys out of order: HASHED (023) */
                 return pure_list_add(list, cells, undo, at, exists);
             if (low < n && !flat_moves(list, low) && !make_tree(list)) return PURE_ALLOCATION;
             if (list->form == FLAT) {
@@ -2208,6 +2391,7 @@ 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) {
+    ordered_now(list);
     if (list->form != TREE) { /* a DENSE list by position: FLAT from now, or counted along its bits without memory */
         if (list->form == DENSE) return array_cell(list, dense_slot(list, at), field); /* at its slot (dense_slot) */
         if (list->form == FLAT) return array_cell(list, at, field);
@@ -2251,6 +2435,7 @@ static void open_array_run(const PureList *list, size_t at, PureRun *run) {
 
 bool pure_list_run(const PureList *list, size_t at, PureRun *run) {
     if (at >= list->count) return false;
+    ordered_now(list);
     if (list->form != TREE) {
         {
             open_array_run(list, at, run);
@@ -2289,6 +2474,7 @@ bool pure_list_run(const PureList *list, size_t at, PureRun *run) {
  * 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) {
+    ordered_now(list);
     if (list->form != TREE) {
         if (run->start + run->count >= list->count) return false;
         open_array_run(list, run->start + run->count, run);
@@ -2351,6 +2537,7 @@ size_t pure_list_seek(const PureList *list, unsigned field, PureCell key, bool *
     const Layout *l = &list->layout;
     *found = false;
     if (!list->count) return 0;
+    ordered_now(list);
     if (list->form == DENSE && (int)field != l->key) (void)positioned((PureList *)list); /* another field: in order */
     if (list->form == DENSE) { /* the keys below key (whole numbers below its ceiling), counted (dense_rank) */
         size_t all = list->member_capacity * 64;
diff --git a/core/test-module.c b/core/test-module.c
index f6283fe..3fc0985 100644
--- a/core/test-module.c
+++ b/core/test-module.c
@@ -1407,7 +1407,7 @@ static double some_number(unsigned event, uint32_t r) {
 static void arrays_equivalence(void) {
     static const uint8_t fields[3] = {PURE_CELL_NUMBER, PURE_CELL_TEXT, PURE_CELL_NUMBER};
     uint32_t seed = 0x61727261u;
-    size_t forms[3] = {0}, conversions = 0, steps = 0;
+    size_t forms[4] = {0}, conversions = 0, steps = 0;
     for (unsigned keyed = 0; keyed < 2; ++keyed) {
         PureList *a = pure_list_new(3, fields), *t = pure_list_new(3, fields);
         CHECK(a && t);
@@ -1507,7 +1507,7 @@ static void arrays_equivalence(void) {
         pure_list_free(a);
         pure_list_free(t);
     }
-    CHECK(forms[0] > 10000 && forms[1] > 10000 && forms[2] > 10000 && conversions > 100);
+    CHECK(forms[0] > 10000 && forms[1] > 10000 && forms[2] > 10000 && forms[3] > 10000 && conversions > 100);
     /* A snapshot shares every list: an event's, empty between events, stays in arrays; one with items is a tree for its copy. */
     {
         PureList *list = pure_list_new(3, fields);
@@ -1526,8 +1526,8 @@ static void arrays_equivalence(void) {
         pure_list_free(list);
         pure_retired_free(&retired);
     }
-    printf("{\"arrays\":{\"steps\":%zu,\"tree\":%zu,\"flat\":%zu,\"dense\":%zu,\"conversions\":%zu}}\n", steps, forms[0], forms[1],
-           forms[2], conversions);
+    printf("{\"arrays\":{\"steps\":%zu,\"tree\":%zu,\"flat\":%zu,\"dense\":%zu,\"hashed\":%zu,\"conversions\":%zu}}\n", steps,
+           forms[0], forms[1], forms[2], forms[3], conversions);
 }
 
 /* The first position in a model (in key order) whose key is not below key. */