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

5 files changed, 298 insertions, 26 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. */
diff --git a/docs/design/023-optimizing-tier.md b/docs/design/023-optimizing-tier.md
index a0e2011..0c4666d 100644
--- a/docs/design/023-optimizing-tier.md
+++ b/docs/design/023-optimizing-tier.md
@@ -141,9 +141,12 @@ roots와 BFS만 기계어로 돈다. 나머지는 JIT의 값 모형이 거르거
 
 ### 6. 표현 (바닥이 가정한 것)
 
-- **희소한 키로 둔 이벤트의 리스트**(해시 색인): 항목은 넣은 차례로 열에 두고, 칸 하나에 키와 위치를 함께 둔 열린 주소 색인으로
-  찾는다. 키가 정수이고 4바이트에 들면 키도 4바이트. 차례가 필요할 때(걷기, `first`, 조각) 정렬한다(런타임의 정렬: 비교가 인라인).
-  정렬은 바뀌기 전까지 유효하다. 텍스트 키는 해시하고 견준다.
+- **희소한 키로 둔 이벤트의 리스트**(HASHED, 했다): 수 키가 차례를 어기고 작은 정수가 아니면, 항목의 셀을 키 집합(열린 주소,
+  키의 비트, 2배 넘는 칸)의 그 키의 칸에 둔다. DENSE가 키의 자리에 두듯 해서, 키로 찾기는 칸의 키와 셀을 같은 번호로 읽는다(C의 해시
+  표처럼 두 미스가 겹친다; 넣은 차례로 두고 칸에 위치를 두면 미스가 줄을 선다: 조인 129 ms에서 108). 차례가 필요할 때(걷기, 위치,
+  찾은 위치, 되돌리기, 공유, 저장) 칸들을 키의 비트 순서로 여덟 비트씩 기수 정렬해 FLAT이 된다. 지우기까지 두 번이고, 그다음은
+  FLAT이나 트리다(오가며 정렬하지 않게). 계층은 키로만 찾는 리스트의 비트 열 1번 비트로 HASHED를 알고(한계는 모두 1: 키의 경계 검사가
+  그대로 맞다), 찾기는 줄 밖에서 칸을 탐사한다(DENSE의 길에 분기가 늘지 않게). 텍스트 키는 아직(해시하고 칸의 셀과 견준다).
 - 텍스트 보간의 정수는 정수의 자릿수로 바로 쓴다(지금의 수→텍스트가 정수에서 내는 것과 같은 바이트).
 - 저장된 리스트는 022 그대로(트리, 많이 찾으면 편 배열).
 
diff --git a/tests/check.py b/tests/check.py
index c7a6c79..30ee5f0 100644
--- a/tests/check.py
+++ b/tests/check.py
@@ -1195,14 +1195,15 @@ def module_assumptions(aup, pure, work):
 
 def tier_program(rng):
     """A random handler for module_tier: loops over counts and a list,
-    numbers in locals and states, a keyed list read and set by key, ifs and
+    numbers in locals and states, a keyed list read and set by key, one
+    whose keys came out of order read by key alone (HASHED), ifs and
     breaks, with what fails (a key not there, not whole, 0 divided by, a
     cell past its column's width) as likely as not."""
     names = iter('jklpqrxyz')
     def number(depth, loops):
         choices = ['const', 'const', 'loop', 'local', 'field']
         if depth < 3:
-            choices += ['add', 'sub', 'mul', 'div', 'floor', 'minmax', 'cell', 'add', 'sub']
+            choices += ['add', 'sub', 'mul', 'div', 'floor', 'minmax', 'cell', 'add', 'sub', 'hashed']
         kind = rng.choice(choices)
         if kind == 'const':
             return rng.choice(['0', '1', '2', '3', '7', '255', '256', '1000', '0.5', '2.25', '(0 - 3)', '(0 - 0)', '65536'])
@@ -1214,6 +1215,8 @@ def tier_program(rng):
             return rng.choice(['s', 'u'])
         if kind == 'cell':
             return f't[{key(depth + 1, loops)}].v' if rng.random() < 0.7 else 'c.v' if 'c' in loops else 's'
+        if kind == 'hashed':
+            return f'h[{hashed_key(depth + 1, loops)}].v'
         if kind == 'floor':
             return f'floor({number(depth + 1, loops)} / {rng.choice(["2", "3", "7", "go.q", "u"])})'
         if kind == 'minmax':
@@ -1223,12 +1226,17 @@ def tier_program(rng):
     def key(depth, loops):
         return rng.choice([rng.choice(loops) if loops else '0', number(depth + 1, loops), 'go.q', '3',
                            f'floor({number(depth + 1, loops)} / 2)'])
+    def hashed_key(depth, loops):  # h's keys: i * 7919 mod 1009, past 5,000,000
+        k = key(depth, loops)
+        return f'(({k}) * 7919 - floor(({k}) * 7919 / 1009) * 1009 + 5000000)' if rng.random() < 0.8 else '5000001'
     def cond(depth, loops):
-        kind = rng.choice(['cmp', 'cmp', 'has', 'not', 'and'] if depth < 2 else ['cmp', 'has'])
+        kind = rng.choice(['cmp', 'cmp', 'has', 'not', 'and', 'hashed'] if depth < 2 else ['cmp', 'has'])
         if kind == 'cmp':
             return f'{number(depth + 1, loops)} {rng.choice(["<", "<=", ">", ">=", "==", "!="])} {number(depth + 1, loops)}'
         if kind == 'has':
             return f't.has({key(depth + 1, loops)})'
+        if kind == 'hashed':
+            return f'h.has({hashed_key(depth + 1, loops)})'
         if kind == 'not':
             return f'!({cond(depth + 1, loops)})'
         return f'({cond(depth + 1, loops)}) && ({cond(depth + 1, loops)})'
@@ -1270,9 +1278,9 @@ def tier_program(rng):
     return '\n'.join([
         'record Cell {', '  at = 0', '  v = 0', '}', 'state out = 0', 'state acc = 0',
         'input go = message {', '  n: u32', '  m: u32', '  q: u32', '}',
-        'on go {', '  let t: list of Cell by at', '  let f: list of Cell',
+        'on go {', '  let t: list of Cell by at', '  let f: list of Cell', '  let h: list of Cell by at',
         '  for i in 0 .. go.n {', f'    t.add(Cell {{ at: i, v: {rng.choice(["i", "0", "(i * 3)", "1"])} }})',
-        '    f.append(Cell { at: i * 2, v: i })', '  }',
+        '    f.append(Cell { at: i * 2, v: i })', '    h.add(Cell { at: i * 7919 - floor(i * 7919 / 1009) * 1009 + 5000000, v: i * 5 })', '  }',
         '  let s = 0', '  let u = 1',
         '  for i in 0 .. go.m {', *body, '  }',
         '  out = s', '  acc = acc + u', '}', ''])