A HASHED list's table four fifths full at most (100,000 keys in 1 MB of slots, as C's table: in the L3), the generic code's APPEND into a HASHED list at its key's slot while its table need not grow, a whole number over a whole one above 0 never -0 (so MINSTD's floor(x * 48271 / p) is whole and x an integer in the tier). join 108 to 84 ms (2.8x C), sort 58 to 37 (1.4x)

3 files changed, 73 insertions, 9 deletions

diff --git a/core/module-jit.c b/core/module-jit.c
index 7703b63..2732b6a 100644
--- a/core/module-jit.c
+++ b/core/module-jit.c
@@ -1410,9 +1410,22 @@ static void append_books(Block *k, const PureOp *op, uint32_t pc, unsigned heigh
     slow_back(k, s, V_MEM, 0);
 }
 
+/* A key's bits in a HASHED list's table (module-list.c's key_bits: -0 as +0) into x17. */
+static void hashed_bits(Block *k, unsigned h) {
+    Emit *e = k->e;
+    int signed_zero = new_label(e);
+    unsigned bits = value_bits(k, h, X17);
+    if (bits != X17) mov_reg(e, X17, bits);
+    lsl_imm(e, X10, X17, 1);
+    cbnz_x(e, X10, signed_zero);
+    mov_imm(e, X17, 0);
+    bind(e, signed_zero);
+}
+
 /* LIST_APPEND to an event's list of numbers whose places no index follows:
- * at the end of a FLAT one, or at its key in a DENSE one, with room, each
- * cell fitting its column. */
+ * at the end of a FLAT one, at its key in a DENSE one, or at its key's slot
+ * in a HASHED one (its table not to grow), with room, each cell fitting its
+ * column. */
 static void append(Block *k, const PureOp *op, uint32_t pc, unsigned height) {
     Emit *e = k->e;
     const PureModule *m = k->m;
@@ -1425,14 +1438,48 @@ static void append(Block *k, const PureOp *op, uint32_t pc, unsigned height) {
     int slow = k->slows[s].label;
     load64(e, X16, X24, list * sizeof(PureList *));
     load8(e, X17, X16, pure_list_layout[LIST_FORM_AT]);
-    cmp_w_imm(e, X17, keyed ? DENSE_FORM : FLAT_FORM);
-    b_cond(e, NE, slow);
+    int cells = new_label(e);
     if (!keyed) {
+        cmp_w_imm(e, X17, FLAT_FORM);
+        b_cond(e, NE, slow);
         load64(e, X9, X16, pure_list_layout[LIST_COUNT_AT]);
         load64(e, X10, X16, pure_list_layout[LIST_ROOM_AT]);
         cmp_reg(e, X9, X10);
         b_cond(e, HS, slow);
     } else {
+        int dense = new_label(e), probe = new_label(e), vacant = new_label(e);
+        cmp_w_imm(e, X17, DENSE_FORM);
+        b_cond(e, EQ, dense);
+        cmp_w_imm(e, X17, HASHED_FORM);
+        b_cond(e, NE, slow);
+        if (k->vs[base + m->state_key[list] - 1u].kind == V_BIT) b(e, slow); /* (its bits made in x9, the slot's) */
+        load64(e, X10, X16, pure_list_layout[LIST_COUNT_AT]); /* room: its items and the new one four fifths of its table at most, else it grows (the step) */
+        add_imm(e, X10, X10, 1);
+        add_lsl(e, X10, X10, X10, 2); /* five times */
+        load64(e, X1, X16, pure_list_layout[LIST_MEMBER_CAPACITY_AT]);
+        cmp_lsl(e, X10, X1, 2);       /* against four times the slots */
+        b_cond(e, HI, slow);
+        hashed_bits(k, base + m->state_key[list] - 1u);
+        mov_imm(e, X10, UINT64_C(0xff51afd7ed558ccd)); /* member_slot */
+        put(e, 0xCA400000 | X17 << 16 | 33u << 10 | X17 << 5 | X0); /* EOR x0, x17, x17, LSR #33 */
+        mul_reg(e, X9, X0, X10);
+        put(e, 0xCA400000 | X9 << 16 | 33u << 10 | X9 << 5 | X9);  /* EOR x9, x9, x9, LSR #33 */
+        sub_imm(e, X1, X1, 1);
+        put(e, 0x8A000000 | X1 << 16 | X9 << 5 | X9);              /* AND x9, x9, x1 (the mask) */
+        load64(e, X0, X16, pure_list_layout[LIST_MEMBERS_AT]);
+        bind(e, probe);
+        load64_index(e, X10, X0, X9);
+        cmp_reg(e, X10, X17);
+        b_cond(e, EQ, fault_at(k, PURE_FAULT_EXISTS, pc));
+        fp2(e, FMOV_DX, D1, X10);
+        fcmp(e, D1, D1);
+        b_cond(e, VS, vacant); /* a NaN: VACANT (no key is one) */
+        add_imm(e, X9, X9, 1);
+        put(e, 0x8A000000 | X1 << 16 | X9 << 5 | X9);
+        b(e, probe);
+        bind(e, vacant);
+        b(e, cells);
+        bind(e, dense);
         unsigned key = value_key(k, base + m->state_key[list] - 1u, X9, slow);
         if (key != X9) mov_reg(e, X9, key);
         mov_imm(e, X10, (uint64_t)1 << 22); /* a small key (module-list.c's BITMAP_KEYS) */
@@ -1451,6 +1498,7 @@ static void append(Block *k, const PureOp *op, uint32_t pc, unsigned height) {
         lsr_reg(e, X17, X1, X9);
         tbnz(e, X17, 0, fault_at(k, PURE_FAULT_EXISTS, pc));
     }
+    bind(e, cells);
     for (unsigned f = 0; f < fields; ++f) { /* the cells, past the end or in the key's empty slot: not the list's until counted */
         load64(e, X10, X16, pure_list_layout[LIST_COLUMNS_AT] + f * sizeof(void *));
         load8(e, X17, X16, pure_list_layout[LIST_WIDTH_AT] + f);
@@ -1460,6 +1508,15 @@ static void append(Block *k, const PureOp *op, uint32_t pc, unsigned height) {
         add_imm(e, X9, X9, 1);
         store64(e, X9, X16, pure_list_layout[LIST_COUNT_AT]);
     } else {
+        int dense = new_label(e), counted = new_label(e);
+        load8(e, X17, X16, pure_list_layout[LIST_FORM_AT]);
+        cmp_w_imm(e, X17, HASHED_FORM);
+        b_cond(e, NE, dense);
+        hashed_bits(k, base + m->state_key[list] - 1u); /* its key in its slot: the item the list's */
+        load64(e, X0, X16, pure_list_layout[LIST_MEMBERS_AT]);
+        store64_index(e, X17, X0, X9);
+        b(e, counted);
+        bind(e, dense);
         load64(e, X0, X16, pure_list_layout[LIST_MEMBERS_AT]);
         lsr_imm(e, X10, X9, 6);
         load64_index(e, X1, X0, X10);
@@ -1467,6 +1524,7 @@ static void append(Block *k, const PureOp *op, uint32_t pc, unsigned height) {
         lsl_reg(e, X17, X17, X9);
         orr_reg(e, X1, X1, X17);
         store64_index(e, X1, X0, X10);
+        bind(e, counted);
         load64(e, X10, X16, pure_list_layout[LIST_MEMBER_COUNT_AT]);
         add_imm(e, X10, X10, 1);
         store64(e, X10, X16, pure_list_layout[LIST_MEMBER_COUNT_AT]);
@@ -3913,6 +3971,9 @@ static void tier_facts(Tier *t) {
                     double c[4] = {a->lo / b->lo, a->lo / b->hi, a->hi / b->lo, a->hi / b->hi};
                     lo = INFINITY, hi = -INFINITY;
                     for (int j = 0; j < 4; ++j) lo = fmin(lo, isnan(c[j]) ? -INFINITY : c[j]), hi = fmax(hi, isnan(c[j]) ? INFINITY : c[j]);
+                    /* -0 only of -0, of 0 over a number below 0, or of a fraction's underflow: a whole number over a
+                     * whole one is at least 1 / 2^53 in size unless it is 0 */
+                    zero = a->zero || !a->whole || !b->whole || (b->hi < 0 && a->lo <= 0 && a->hi >= 0);
                 }
                 break;
             case T_FLOOR:
diff --git a/core/module-list.c b/core/module-list.c
index 5f6cf0c..1abde3a 100644
--- a/core/module-list.c
+++ b/core/module-list.c
@@ -1209,6 +1209,9 @@ static inline void cell_copy(void *to_column, size_t to, const void *from_column
     }
 }
 
+/* Whether a HASHED list's table of capacity slots is too full for items: more than four fifths. */
+static bool hashed_full(size_t items, size_t capacity) { return 5 * items > 4 * capacity; }
+
 /* A HASHED list's slot of key (its cells there; a text's where its bytes are the key's too), or SIZE_MAX. */
 static size_t hashed_slot(const PureList *list, PureCell key) {
     uint64_t bits = cell_bits(list, key);
@@ -1266,7 +1269,7 @@ static bool hashed_table(PureList *list, size_t capacity) {
 static bool make_hashed(PureList *list) {
     if (hashed_field(list) < 0 || list->pack || list->flattened >= 2) return false;
     size_t capacity = 16;
-    while (capacity < 2 * (list->count + 1)) capacity *= 2;
+    while (hashed_full(list->count + 1, capacity)) 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 */
@@ -1276,14 +1279,14 @@ static bool make_hashed(PureList *list) {
 
 /* 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;
+    return hashed_full(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, its bits those)
  * into a HASHED list at its key's slot; false without memory (as it was). */
 static bool hashed_add(PureList *list, const PureCell *item, uint64_t bits) {
     const Layout *l = &list->layout;
-    if (2 * (list->count + 1) > list->member_capacity && !hashed_table(list, 2 * list->member_capacity)) return false;
+    if (hashed_full(list->count + 1, list->member_capacity) && !hashed_table(list, 2 * list->member_capacity)) return false;
     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;
diff --git a/docs/design/023-optimizing-tier.md b/docs/design/023-optimizing-tier.md
index 88645d7..2003af5 100644
--- a/docs/design/023-optimizing-tier.md
+++ b/docs/design/023-optimizing-tier.md
@@ -142,10 +142,10 @@ roots와 BFS만 기계어로 돈다. 나머지는 JIT의 값 모형이 거르거
 ### 6. 표현 (바닥이 가정한 것)
 
 - **희소한 키로 둔 이벤트의 리스트**(HASHED, 했다): 수 키가 차례를 어기고 작은 정수가 아니면, 항목의 셀을 키 집합(열린 주소,
-  키의 비트, 2배 넘는 칸)의 그 키의 칸에 둔다. DENSE가 키의 자리에 두듯 해서, 키로 찾기는 칸의 키와 셀을 같은 번호로 읽는다(C의 해시
+  키의 비트, 칸의 4/5까지: 표가 L3에 들게; 절반까지면 조인 112 ms, 4/5면 84)의 그 키의 칸에 둔다. DENSE가 키의 자리에 두듯 해서, 키로 찾기는 칸의 키와 셀을 같은 번호로 읽는다(C의 해시
   표처럼 두 미스가 겹친다; 넣은 차례로 두고 칸에 위치를 두면 미스가 줄을 선다: 조인 129 ms에서 108). 차례가 필요할 때(걷기, 위치,
   찾은 위치, 되돌리기, 공유, 저장) 칸들을 키의 비트 순서로 여덟 비트씩 기수 정렬해 FLAT이 된다. 지우기까지 두 번이고, 그다음은
-  FLAT이나 트리다(오가며 정렬하지 않게). 계층은 키로만 찾는 리스트의 비트 열 1번 비트로 HASHED를 알고(한계는 모두 1: 키의 경계 검사가
+  FLAT이나 트리다(오가며 정렬하지 않게). 일반 코드의 APPEND도 표가 자라지 않는 한 칸을 바로 찾아 넣는다(sort 58 ms에서 37). 계층은 키로만 찾는 리스트의 비트 열 1번 비트로 HASHED를 알고(한계는 모두 1: 키의 경계 검사가
   그대로 맞다), 찾기는 줄 밖에서 칸을 탐사한다(DENSE의 길에 분기가 늘지 않게).
 - **텍스트 키의 이벤트 리스트**(했다): 리스트가 그 키를 안다(`text_key`, 트리의 리드는 그대로 수 키만). 이벤트의 리스트는 처음
   넣을 때부터 HASHED이고, 칸에는 텍스트 바이트의 해시(FNV-1a)를 두며 같은 해시는 칸의 키 셀과 바이트로 견준다. HAS와 키로 읽기는