diff options
| -rw-r--r-- | core/module-jit.c | 86 | ||||
| -rw-r--r-- | core/module-list.c | 203 | ||||
| -rw-r--r-- | core/test-module.c | 8 | ||||
| -rw-r--r-- | docs/design/023-optimizing-tier.md | 9 | ||||
| -rw-r--r-- | tests/check.py | 18 |
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', '}', '']) |