diff options
| -rw-r--r-- | core/module-list.c | 135 | ||||
| -rw-r--r-- | core/module-list.h | 6 | ||||
| -rw-r--r-- | core/module-run.h | 2 | ||||
| -rw-r--r-- | core/module.c | 58 | ||||
| -rw-r--r-- | core/test-module.c | 84 | ||||
| -rw-r--r-- | docs/design/023-optimizing-tier.md | 9 |
6 files changed, 264 insertions, 30 deletions
diff --git a/core/module-list.c b/core/module-list.c index 9f576a8..5f6cf0c 100644 --- a/core/module-list.c +++ b/core/module-list.c @@ -116,6 +116,7 @@ struct PureList { bool full; uint32_t *ranks; size_t ranks_room; + int text_key; /* the text field it is keyed by (its layout's key -1), or -1: HASHED by its texts' hashes (023) */ }; /* The log of an event's changes: a removed item's cells wait in the log's @@ -1182,6 +1183,20 @@ static bool make_flat(PureList *list) { return true; } +static int order(const Layout *l, unsigned field, PureCell a, PureCell b); + +/* The field a HASHED list is keyed by: its text key, else its number key. */ +static int hashed_field(const PureList *list) { return list->text_key >= 0 ? list->text_key : list->layout.key; } + +/* A key's bits in a HASHED list's table: a number's (key_bits), or its + * text's hash (FNV-1a over its bytes; never VACANT). */ +static uint64_t cell_bits(const PureList *list, PureCell key) { + if (list->text_key < 0) return key_bits(key.num); + uint64_t h = UINT64_C(0xcbf29ce484222325); + for (size_t i = 0; i < key.size; ++i) h = (h ^ key.text[i]) * UINT64_C(0x100000001b3); + return h == VACANT ? h ^ 2 : h; +} + /* 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; @@ -1194,13 +1209,17 @@ static inline void cell_copy(void *to_column, size_t to, const void *from_column } } -/* 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); +/* 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); 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; + if (list->members[at] == bits) { + if (list->text_key < 0) return at; + PureCell there = array_cell(list, at, (unsigned)list->text_key); + if (there.size == key.size && (!key.size || !memcmp(there.text, key.text, key.size))) return at; + } else if (list->members[at] == VACANT) + return SIZE_MAX; } } @@ -1221,11 +1240,10 @@ static bool hashed_table(PureList *list, size_t capacity) { } 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]); + uint64_t bits = hashed ? list->members[row] : cell_bits(list, array_cell(list, row, (unsigned)hashed_field(list))); size_t at = member_slot(bits, mask); while (table[at] != VACANT) at = (at + 1) & mask; table[at] = bits; @@ -1246,7 +1264,7 @@ static bool hashed_table(PureList *list, size_t capacity) { * 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; + if (hashed_field(list) < 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; @@ -1261,12 +1279,11 @@ 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) { +/* 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; - 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; @@ -1298,9 +1315,30 @@ static bool make_ordered(PureList *list) { } 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}; + if (bits == VACANT) continue; + if (list->text_key >= 0) { /* a text's first eight bytes, as a number in their order (past its end, 0) */ + PureCell text = array_cell(list, slot, (unsigned)list->text_key); + bits = 0; + for (size_t c = 0; c < 8; ++c) bits = bits << 8 | (c < text.size ? text.text[c] : 0); + a[i++] = (Ordered){bits, (uint32_t)slot}; + } else + a[i++] = (Ordered){bits >> 63 ? ~bits : bits | UINT64_C(1) << 63, (uint32_t)slot}; + } + for (size_t width = 1; list->text_key >= 0 && width < n; width *= 2) { /* texts: merged in order (their first bytes, then all), a run's width doubling */ + for (size_t low = 0; low < n; low += 2 * width) { + size_t middle = low + width < n ? low + width : n, high = low + 2 * width < n ? low + 2 * width : n, i = low, j = middle, k = low; + while (i < middle && j < high) + b[k++] = (a[j].key != a[i].key ? a[j].key < a[i].key + : order(l, (unsigned)list->text_key, array_cell(list, a[j].slot, (unsigned)list->text_key), + array_cell(list, a[i].slot, (unsigned)list->text_key)) < 0) + ? a[j++] : a[i++]; + while (i < middle) b[k++] = a[i++]; + while (j < high) b[k++] = a[j++]; + } + Ordered *t = a; + a = b, b = t; } - for (unsigned shift = 0; n && shift < 64; shift += 8) { + for (unsigned shift = 0; list->text_key < 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; @@ -1320,6 +1358,7 @@ static bool make_ordered(PureList *list) { arrays_free(list); memcpy(list->columns, columns, sizeof(columns)); list->room = room; + if (list->text_key >= 0) members_drop(list); /* a text's hashes are no key set of a FLAT list (searched by its texts) */ list->form = FLAT; list->moved = 0; ++list->flattened; @@ -1554,6 +1593,7 @@ PureList *pure_list_new(unsigned fields, const uint8_t *kinds) { } l->leaf_size = at; l->key = -1; + list->text_key = -1; list->id = __atomic_add_fetch(&lists_made, 1, __ATOMIC_RELAXED); return list; } @@ -1570,7 +1610,12 @@ static bool rekey(PureList *list, Node **place) { PureResult pure_list_keyed(PureList *list, int field) { Layout *l = &list->layout; - int key = field >= 0 && (unsigned)field < l->fields && l->kinds[field] == PURE_CELL_NUMBER ? field : -1; + int key = field >= 0 && (unsigned)field < l->fields && l->kinds[field] == PURE_CELL_NUMBER ? field : -1, + text = field >= 0 && (unsigned)field < l->fields && pure_cell_text(l->kinds[field]) ? field : -1; + if (text != list->text_key) { + if (list->form == HASHED && !make_ordered(list)) return PURE_ALLOCATION; + list->text_key = text; + } if (key == l->key) return PURE_OK; if (list->count && !make_tree(list)) return PURE_ALLOCATION; if (list->arrays) arrays_free(list); /* its columns as wide as the new key wants */ @@ -1689,7 +1734,7 @@ bool pure_list_hashed(PureList *list) { } bool pure_list_contains(const PureList *list, double key, bool *found) { - if (!list->members) return false; + if (!list->members || list->text_key >= 0) return false; /* a text's hashes: pure_list_contains_text */ if (list->bitmap) { *found = small_key(key) && (size_t)key / 64 < list->member_capacity && list->members[(size_t)key / 64] >> ((size_t)key % 64) & 1; @@ -1702,6 +1747,37 @@ bool pure_list_contains(const PureList *list, double key, bool *found) { return true; } +static bool own_cell(const PureList *list, unsigned field, PureCell from, PureCell *to); + +bool pure_list_contains_text(const PureList *list, PureCell key, bool *found) { + if (list->form != HASHED || list->text_key < 0) return false; + *found = hashed_slot(list, key) != SIZE_MAX; + return true; +} + +size_t pure_list_find_row(const PureList *list, unsigned field, PureCell key, bool *found) { + if (list->form == HASHED && (int)field == hashed_field(list)) { + size_t slot = hashed_slot(list, key); + *found = slot != SIZE_MAX; + return slot; + } + return pure_list_seek(list, field, key, found); +} + +PureResult pure_list_set_row(PureList *list, size_t row, unsigned field, PureCell value, PureUndo *undo) { + const Layout *l = &list->layout; + if (list->form != HASHED || undo || (int)field == hashed_field(list)) return pure_list_set(list, row, field, value, undo); + PureCell copy, old = array_cell(list, row, field); /* at its key's slot, as found (no position made) */ + uint8_t need = narrows(l->kinds[field]) && (list->width[field] == 1 || list->width[field] == 4) ? width_of(value.num) : 0; + if (need > list->width[field] && !widen(list, field, need)) return PURE_ALLOCATION; + if (!own_cell(list, field, value, ©)) return PURE_ALLOCATION; + list->bytes += cell_bytes(l, field, copy) - cell_bytes(l, field, old); + array_put(list, row, field, copy); + let_go_text(list, old.text); + ++list->version; + return PURE_OK; +} + /* An event's arrays are its items, as a tree's nodes are: neither counts * here (the stored bytes stand for both), so a list's room runs out at the * same item whatever it keeps them in (021). */ @@ -1747,8 +1823,8 @@ 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 (list->form == HASHED && (int)key_field == hashed_field(list)) { /* at its key's slot, by its table */ + size_t slot = hashed_slot(list, key); if (slot == SIZE_MAX) return false; *cell = array_cell(list, slot, field); return true; @@ -2176,20 +2252,37 @@ PureResult pure_list_insert(PureList *list, size_t at, const PureCell *cells, Pu PureResult pure_list_add(PureList *list, const PureCell *cells, PureUndo *undo, size_t *at, bool *exists) { const Layout *l = &list->layout; *exists = false; - if (l->key < 0) return PURE_INVALID; /* searched and inserted apart, then */ + if (l->key < 0) { /* by a text key: an event's list HASHED by its texts' hashes; else searched and inserted apart */ + if (list->text_key < 0 || at || undo || list->journaled || list->pack || !list->arrays) return PURE_INVALID; + if (list->form == FLAT && !make_hashed(list)) return PURE_INVALID; + if (list->form != HASHED) return PURE_INVALID; + if (hashed_slot(list, cells[list->text_key]) != SIZE_MAX) return *exists = true, PURE_OK; + if (hashed_large(list)) return make_ordered(list) ? PURE_INVALID : PURE_ALLOCATION; + 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, cell_bits(list, cells[list->text_key]))) { + 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 (!logged(list, undo)) return PURE_ALLOCATION; 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 (hashed_slot(list, cells[l->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)) { + if (owned < l->fields || !arrays_fit(list, cells) || !hashed_add(list, item, cell_bits(list, cells[l->key]))) { for (unsigned f = 0; f < owned; ++f) free_text(item[f].text); return PURE_ALLOCATION; } diff --git a/core/module-list.h b/core/module-list.h index 3ae468f..369e8ed 100644 --- a/core/module-list.h +++ b/core/module-list.h @@ -159,6 +159,12 @@ bool pure_list_suits(PureList *, unsigned needs, unsigned narrow); bool pure_list_full(PureList *); /* Whether key is there, by the set: false when the list keeps none (search it then). */ bool pure_list_contains(const PureList *, double key, bool *found); +/* Whether a HASHED list keyed by a text has key (false: it is not one; search it). */ +bool pure_list_contains_text(const PureList *list, PureCell key, bool *found); +/* Where key is, for a set of the item found (pure_list_set_row): a HASHED + * list's slot (no position made), else its position (pure_list_seek). */ +size_t pure_list_find_row(const PureList *list, unsigned field, PureCell key, bool *found); +PureResult pure_list_set_row(PureList *list, size_t row, unsigned field, PureCell value, PureUndo *undo); /* The bytes it keeps beside its items for that. */ size_t pure_list_extra(const PureList *); /* An event's list (empty, never shared, journaled or undone) may keep its diff --git a/core/module-run.h b/core/module-run.h index 74f188b..fac77a4 100644 --- a/core/module-run.h +++ b/core/module-run.h @@ -6,7 +6,7 @@ #include "module.h" /* An item's or a key's op->plan: its cell a text; a FIND joined to the ITEM_GET after it. */ -enum { PLAN_TEXT = 1, PLAN_JOINED = 2 }; +enum { PLAN_TEXT = 1, PLAN_JOINED = 2, PLAN_ROW = 4 }; /* An item instruction's argument: its list and its field. */ static inline uint32_t list_of(uint32_t arg) { return arg & 0xFFFF; } diff --git a/core/module.c b/core/module.c index bc9fb8f..2228725 100644 --- a/core/module.c +++ b/core/module.c @@ -1371,6 +1371,48 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule if (op->op == PURE_OP_LIST_FIND && next->op == PURE_OP_ITEM_GET && list_of(next->arg) == op->arg && !landed[pc + 1]) op->plan |= PLAN_JOINED; } + /* A FIND whose index waits on the stack for an ITEM_SET of its list, + * the code between in a line (no jump in or out) that touches no list but + * to find by key (joined, or HAS): the item is set where it was found, a + * HASHED list's slot, no position made (PLAN_ROW, docs/design/023). */ + for (uint32_t pc = 0; pc < out->code_count; ++pc) { + PureOp *find = &out->code[pc]; + if (find->op != PURE_OP_LIST_FIND || find->plan & PLAN_JOINED) continue; + int height = 1; + for (uint32_t at = pc + 1; at < out->code_count && height >= 1 && !landed[at]; ++at) { + const PureOp *o = &out->code[at]; + int pops = -1, pushes = 1; + switch (o->op) { + case PURE_OP_CONST: case PURE_OP_LOAD: case PURE_OP_LOCAL_LOAD: case PURE_OP_TEXT_CONST: case PURE_OP_TEXT_LOAD: + case PURE_OP_FIELD: case PURE_OP_LIST_COUNT: + pops = 0; + break; + case PURE_OP_NEG: case PURE_OP_NOT: case PURE_OP_FLOOR: case PURE_OP_NUM_TEXT: case PURE_OP_I64_NEG: + case PURE_OP_I64_FROM: case PURE_OP_NUM_FROM: case PURE_OP_LIST_HAS: + pops = 1; + break; + case PURE_OP_ADD: case PURE_OP_SUB: case PURE_OP_MUL: case PURE_OP_DIV: case PURE_OP_MIN: case PURE_OP_MAX: + case PURE_OP_MOD: case PURE_OP_AND: case PURE_OP_OR: case PURE_OP_LT: case PURE_OP_LE: case PURE_OP_GT: + case PURE_OP_GE: case PURE_OP_EQ: case PURE_OP_NE: case PURE_OP_CONCAT: case PURE_OP_TEXT_COMPARE: + case PURE_OP_I64_ADD: case PURE_OP_I64_SUB: case PURE_OP_I64_MUL: case PURE_OP_I64_DIV: case PURE_OP_I64_MOD: + case PURE_OP_I64_MIN: case PURE_OP_I64_MAX: case PURE_OP_I64_COMPARE: + pops = 2; + break; + case PURE_OP_LIST_FIND: /* joined: its ITEM_GET with it (a key in, the field out) */ + if (o->plan & PLAN_JOINED && !landed[at + 1]) pops = 1, ++at; + break; + case PURE_OP_ITEM_SET: + if (height == 2 && list_of(o->arg) == find->arg) { + find->plan |= PLAN_ROW; + out->code[at].plan |= PLAN_ROW; + } + break; + default: break; + } + if (pops < 0) break; + height += pushes - pops; + } + } free(landed); /* The lists an index state refers to: their inserts tell where (move_indices). */ for (uint32_t i = 0; i < out->states; ++i) @@ -2822,10 +2864,10 @@ static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp Held before = list_held(app, app->lists[list]); PureSpan span = {0}; status = op->plan & PLAN_TEXT ? contiguous(app, arena, value.bytes, &span) : PURE_OK; - if (status == PURE_OK) - status = pure_list_set(app->lists[list], at, field, - (PureCell){.i64 = value.i64, .text = (unsigned char *)span.data, .size = span.size}, - undo_for(app, list)); + PureCell cell = {.i64 = value.i64, .text = (unsigned char *)span.data, .size = span.size}; + if (status == PURE_OK) /* where its FIND found it (PLAN_ROW: a HASHED list's slot), else its position */ + status = op->plan & PLAN_ROW ? pure_list_set_row(app->lists[list], at, field, cell, undo_for(app, list)) + : pure_list_set(app->lists[list], at, field, cell, undo_for(app, list)); arena->used = mark; if (status != PURE_OK) REFUSED; if (!grows(app, before, list_held(app, app->lists[list]))) { kind = PURE_FAULT_MEMORY; FAILED; } @@ -2912,12 +2954,14 @@ static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp else if ((status = keep_bytes(arena, value.text, value.size, &top->bytes)) != PURE_OK) STOPPED(status); NEXT; } - /* An event's list keeps its keys as a set: HAS asks it alone (020). */ - if (op->op == PURE_OP_LIST_HAS && pure_list_contains(app->lists[arg], cell.num, &found)) { + /* An event's list keeps its keys as a set: HAS asks it alone (020); a text key's HASHED list, its table. */ + if (op->op == PURE_OP_LIST_HAS && (op->plan & PLAN_TEXT ? pure_list_contains_text(app->lists[arg], cell, &found) + : pure_list_contains(app->lists[arg], cell.num, &found))) { + arena->used = mark; top->num = found; NEXT; } - size_t at = pure_list_seek(app->lists[arg], key, cell, &found); + size_t at = op->plan & PLAN_ROW ? pure_list_find_row(app->lists[arg], key, cell, &found) : pure_list_seek(app->lists[arg], key, cell, &found); arena->used = mark; if (op->op == PURE_OP_LIST_HAS) { top->num = found; NEXT; } if (!found) { kind = PURE_FAULT_NOT_FOUND; FAILED; } diff --git a/core/test-module.c b/core/test-module.c index 3fc0985..371fca5 100644 --- a/core/test-module.c +++ b/core/test-module.c @@ -1404,6 +1404,89 @@ static double some_number(unsigned event, uint32_t r) { } } +/* An item into a list keyed by its text field 0, as the executor does: added at once (HASHED), else found and inserted. */ +static PureResult text_add(PureList *list, const PureCell *cells, bool *exists) { + PureResult result = pure_list_add(list, cells, NULL, NULL, exists); + if (result != PURE_INVALID) return result; + size_t at = pure_list_seek(list, 0, cells[0], exists); + return *exists ? PURE_OK : pure_list_insert(list, at, cells, NULL); +} + +/* An event's list keyed by a text (HASHED by its texts' hashes, docs/design + * 023) against a tree keyed so: adds, has, a field by key, a set where its + * key was found, positions, runs, removes, and the event's end. */ +static void text_keys_equivalence(void) { + static const uint8_t fields[3] = {PURE_CELL_TEXT, PURE_CELL_NUMBER, PURE_CELL_TEXT}; + uint32_t seed = 0x74657874u; + size_t hashed = 0, steps = 0; + PureList *a = pure_list_new(3, fields), *t = pure_list_new(3, fields); + CHECK(a && t && pure_list_keyed(a, 0) == PURE_OK && pure_list_keyed(t, 0) == PURE_OK && pure_list_arrays(a)); + for (unsigned event = 0; event < 120; ++event) { + unsigned changes = 20 + next_random(&seed) % (event % 5 == 0 ? 3000 : 300), words = 1 + next_random(&seed) % 2000; + for (unsigned c = 0; c < changes; ++c, ++steps) { + uint32_t r = next_random(&seed); + char key[24], other[16]; + size_t size = (size_t)snprintf(key, sizeof(key), r % 7 ? "w%u" : "%u-word", (r >> 3) % words); + size_t other_size = (size_t)snprintf(other, sizeof(other), "o%u", r % 97); + PureCell cells[3] = {{.text = (unsigned char *)key, .size = size}, {.num = (double)(r % 1000)}, + {.text = (unsigned char *)other, .size = r % 5 ? other_size : 0}}; + size_t n = pure_list_count(t); + unsigned op = next_random(&seed) % (event % 4 == 1 ? 10 : 16); /* some events by key alone: HASHED stays */ + if (op < 5) { + bool ea, et; + CHECK(text_add(a, cells, &ea) == PURE_OK && text_add(t, cells, &et) == PURE_OK && ea == et); + } else if (op < 8) { /* has, and fields by key */ + bool ha, ht, fa, ft; + PureCell ca, ct; + if (!pure_list_contains_text(a, cells[0], &ha)) (void)pure_list_seek(a, 0, cells[0], &ha); + (void)pure_list_seek(t, 0, cells[0], &ht); + CHECK(ha == ht); + fa = pure_list_lookup(a, 0, cells[0], 1, &ca); + ft = pure_list_lookup(t, 0, cells[0], 1, &ct); + CHECK(fa == ft && fa == ht && (!fa || ca.i64 == ct.i64)); + fa = pure_list_lookup(a, 0, cells[0], 2, &ca); + ft = pure_list_lookup(t, 0, cells[0], 2, &ct); + CHECK(fa == ft && (!fa || (ca.size == ct.size && (!ca.size || !memcmp(ca.text, ct.text, ca.size))))); + } else if (op < 10) { /* set where its key was found (a slot, in a HASHED list) */ + bool fa, ft; + size_t ra = pure_list_find_row(a, 0, cells[0], &fa), rt = pure_list_seek(t, 0, cells[0], &ft); + CHECK(fa == ft); + if (fa) { + unsigned field = r % 2 ? 1 : 2; + CHECK(pure_list_set_row(a, ra, field, cells[field], NULL) == PURE_OK && + pure_list_set(t, rt, field, cells[field], NULL) == PURE_OK); + } + } else if (op < 12 && n) { /* by position: in order now */ + size_t at = next_random(&seed) % n; + PureCell x = pure_list_get(a, at, 0), y = pure_list_get(t, at, 0), w = pure_list_get(a, at, 1), z = pure_list_get(t, at, 1); + CHECK(x.size == y.size && !memcmp(x.text, y.text, x.size) && w.i64 == z.i64); + } else if (op < 14 && n) { /* a run from somewhere */ + size_t at = next_random(&seed) % n; + PureRun ra, rt; + CHECK(pure_list_run(a, at, &ra) && pure_list_run(t, at, &rt)); + PureSpan sa = ra.column[0].texts[at - ra.start], st = rt.column[0].texts[at - rt.start]; + CHECK(sa.size == st.size && (!sa.size || !memcmp(sa.data, st.data, sa.size))); + } else if (op < 16 && n) { /* remove */ + size_t at = next_random(&seed) % n; + CHECK(pure_list_remove(a, at, NULL) == PURE_OK && pure_list_remove(t, at, NULL) == PURE_OK); + } + hashed += pure_list_form(a) == 3; + } + CHECK(pure_list_count(a) == pure_list_count(t) && pure_list_size(a) == pure_list_size(t)); + for (size_t i = 0; i < pure_list_count(t); i += 1 + i / 64) + for (unsigned f = 0; f < 3; ++f) { + PureCell x = pure_list_get(a, i, f), y = pure_list_get(t, i, f); + CHECK(f == 1 ? x.i64 == y.i64 : x.size == y.size && (!x.size || !memcmp(x.text, y.text, x.size))); + } + pure_list_clear(a); + pure_list_clear(t); + } + pure_list_free(a); + pure_list_free(t); + CHECK(hashed > 10000); + printf("{\"text_keys\":{\"steps\":%zu,\"hashed\":%zu}}\n", steps, hashed); +} + static void arrays_equivalence(void) { static const uint8_t fields[3] = {PURE_CELL_NUMBER, PURE_CELL_TEXT, PURE_CELL_NUMBER}; uint32_t seed = 0x61727261u; @@ -6280,6 +6363,7 @@ int main(void) { list_trees(); key_sets(); keyed_journal(); + text_keys_equivalence(); arrays_equivalence(); packed_lists(); folds(); diff --git a/docs/design/023-optimizing-tier.md b/docs/design/023-optimizing-tier.md index 0c4666d..88645d7 100644 --- a/docs/design/023-optimizing-tier.md +++ b/docs/design/023-optimizing-tier.md @@ -146,7 +146,14 @@ roots와 BFS만 기계어로 돈다. 나머지는 JIT의 값 모형이 거르거 표처럼 두 미스가 겹친다; 넣은 차례로 두고 칸에 위치를 두면 미스가 줄을 선다: 조인 129 ms에서 108). 차례가 필요할 때(걷기, 위치, 찾은 위치, 되돌리기, 공유, 저장) 칸들을 키의 비트 순서로 여덟 비트씩 기수 정렬해 FLAT이 된다. 지우기까지 두 번이고, 그다음은 FLAT이나 트리다(오가며 정렬하지 않게). 계층은 키로만 찾는 리스트의 비트 열 1번 비트로 HASHED를 알고(한계는 모두 1: 키의 경계 검사가 - 그대로 맞다), 찾기는 줄 밖에서 칸을 탐사한다(DENSE의 길에 분기가 늘지 않게). 텍스트 키는 아직(해시하고 칸의 셀과 견준다). + 그대로 맞다), 찾기는 줄 밖에서 칸을 탐사한다(DENSE의 길에 분기가 늘지 않게). +- **텍스트 키의 이벤트 리스트**(했다): 리스트가 그 키를 안다(`text_key`, 트리의 리드는 그대로 수 키만). 이벤트의 리스트는 처음 + 넣을 때부터 HASHED이고, 칸에는 텍스트 바이트의 해시(FNV-1a)를 두며 같은 해시는 칸의 키 셀과 바이트로 견준다. HAS와 키로 읽기는 + 표에서 바로. 차례는 텍스트의 앞 여덟 바이트를 수로 견주고 같으면 바이트 전부를 견주는 병합 정렬로 낸다. 정렬되면 해시는 FLAT의 + 키 집합이 아니므로 버린다. +- **찾은 자리에 쓰기**(PLAN_ROW, 했다): `counts[w].n = counts[w].n + 1`처럼 FIND가 낸 위치를 ITEM_SET만 받고 그 사이가 한 줄(뛰어 + 들거나 나가지 않음)이며 리스트를 키로 찾기(합친 FIND, HAS) 말고 건드리지 않으면, 로더가 둘을 묶는다. HASHED 리스트는 위치 대신 + 칸에 쓴다(위치를 내면 정렬된다). words 453 ms에서 217. - 텍스트 보간의 정수는 정수의 자릿수로 바로 쓴다(지금의 수→텍스트가 정수에서 내는 것과 같은 바이트). - 저장된 리스트는 022 그대로(트리, 많이 찾으면 편 배열). |