diff options
| -rw-r--r-- | Makefile | 6 | ||||
| -rw-r--r-- | core/module-list.c | 350 | ||||
| -rw-r--r-- | core/module-list.h | 17 | ||||
| -rw-r--r-- | core/module.c | 183 | ||||
| -rw-r--r-- | core/module.h | 3 | ||||
| -rw-r--r-- | core/test-module.c | 281 | ||||
| -rw-r--r-- | docs/design/020-computing-faster.md | 19 |
7 files changed, 762 insertions, 97 deletions
@@ -38,6 +38,12 @@ $(BUILD)/obj/%.o: %.c $(HEADERS) @mkdir -p $(dir $@) $(CC) $(CPPFLAGS) $(CFLAGS) $(INCLUDES) -c $< -o $@ +# The lists' searches count a node's keys and positions whole, and move +# items in a leaf column by column: -O3 makes vector instructions of them +# (docs/design/020: 8% of a breadth first search). +LIST_OPTIMIZE ?= -O3 +$(BUILD)/obj/core/module-list.o: CFLAGS += $(LIST_OPTIMIZE) + # The links know nothing of the core: they build without its headers. $(BUILD)/obj/link/%.o: link/%.c $(wildcard link/*.h) @mkdir -p $(dir $@) diff --git a/core/module-list.c b/core/module-list.c index 3e643ce..99d19ab 100644 --- a/core/module-list.c +++ b/core/module-list.c @@ -74,6 +74,13 @@ struct PureList { unsigned needed[2]; /* inner nodes and leaves it made lately: halved each time the retired come back */ unsigned refs; /* a shared copy's references */ bool copy; /* a shared copy: it owns none of its nodes or texts */ + /* Its keys as a set, beside the tree (pure_list_hashed; NULL: none): + * while every key is a whole number below BITMAP_KEYS, a bit per number + * (member_capacity words); else a key's bits (-0 as +0) by open + * addressing (member_capacity slots), VACANT where none is. */ + uint64_t *members; + size_t member_capacity, member_count; + bool bitmap; }; /* The log of an event's changes: a removed item's cells wait in the log's @@ -100,31 +107,176 @@ typedef struct { static uint64_t lists_made; -/* The leaf a thread read last, and where it starts: a list read position by - * position (a view's rows, a fold) finds each next item there. It holds for - * the list (its id) as it was (its version) and no other. */ -static _Thread_local struct { uint64_t id, version; const Node *leaf; size_t start; } finger; +/* The leaves a thread read last, and where they start, a few lists' (one + * each): a list read position by position (a view's rows, a fold, a walk) + * finds each next item there, and an item found by key is read there, while + * the thread reads other lists between (a search reads three). Each holds + * for its list (its id) as it was (its version) and no other. */ +enum { FINGERS = 4 }; +typedef struct { uint64_t id, version; const Node *leaf; size_t start; } Finger; +static _Thread_local Finger fingers[FINGERS]; +static _Thread_local unsigned finger_turn; + +/* The leaf a finger keeps that holds position at of the list as it is, or NULL. */ +static const Node *fingered(const PureList *list, size_t at, size_t *within) { + for (unsigned i = 0; i < FINGERS; ++i) { + const Finger *f = &fingers[i]; + if (f->leaf && f->id == list->id && f->version == list->version && at >= f->start && at < f->start + f->leaf->count) { + *within = at - f->start; + if (i) { Finger hit = *f; fingers[i] = fingers[0]; fingers[0] = hit; } /* first looked at next */ + return fingers[0].leaf; + } + } + return NULL; +} + +/* A leaf of the list as it is, from start: kept in the list's finger, or the one used longest ago. */ +static void finger_keep(const PureList *list, const Node *leaf, size_t start) { + unsigned at = FINGERS; + for (unsigned i = 0; i < FINGERS && at == FINGERS; ++i) if (fingers[i].id == list->id) at = i; + if (at == FINGERS) at = finger_turn++ % FINGERS; + fingers[at] = (Finger){list->id, list->version, leaf, start}; +} + +/* ---- A keyed list's keys as a set + * Node numbers, ranks and counts are small whole numbers: as bits they fit + * the caches (100,000 keys in 12.5 KB), where a table of them does not. */ + +enum { BITMAP_KEYS = 1 << 22, BITMAP_KEPT = 1 << 13 /* words a cleared bitmap keeps (64 KiB) */ }; +static const uint64_t VACANT = UINT64_C(0x7FF8000000000001); /* a NaN: never a key */ + +static uint64_t key_bits(double key) { + if (key == 0) key = 0; /* -0 and +0 are one key */ + uint64_t bits; + memcpy(&bits, &key, sizeof(bits)); + return bits; +} + +static bool small_key(double key) { return key >= 0 && key < BITMAP_KEYS && (double)(uint32_t)key == key; } + +static size_t member_slot(uint64_t bits, size_t mask) { + bits ^= bits >> 33; + bits *= UINT64_C(0xff51afd7ed558ccd); + bits ^= bits >> 33; + return (size_t)bits & mask; +} + +/* The set given up (memory ran out growing it): the list is searched without it. */ +static void members_drop(PureList *list) { + free(list->members); + list->members = NULL; + list->member_capacity = list->member_count = 0; +} + +/* A new set, empty, as bits. */ +static bool members_start(PureList *list) { + list->members = calloc(1, sizeof(*list->members)); + list->member_capacity = list->members ? 1 : 0; + list->member_count = 0; + list->bitmap = true; + return list->members != NULL; +} + +static void member_put(PureList *list, uint64_t bits) { + size_t mask = list->member_capacity - 1, at = member_slot(bits, mask); + while (list->members[at] != VACANT && list->members[at] != bits) at = (at + 1) & mask; + if (list->members[at] == VACANT) list->members[at] = bits, ++list->member_count; +} + +/* A table of capacity slots holding the keys the set holds. False when memory runs out. */ +static bool members_table(PureList *list, size_t capacity) { + uint64_t *old = list->members, *table = malloc(capacity * sizeof(*table)); + if (!table) return false; + size_t was = list->member_capacity; + bool bits = list->bitmap; + for (size_t i = 0; i < capacity; ++i) table[i] = VACANT; + list->members = table, list->member_capacity = capacity, list->member_count = 0, list->bitmap = false; + for (size_t i = 0; i < was; ++i) { + if (!bits) { if (old[i] != VACANT) member_put(list, old[i]); continue; } + for (uint64_t word = old[i]; word; word &= word - 1) + member_put(list, key_bits((double)(i * 64 + (size_t)__builtin_ctzll(word)))); + } + free(old); + return true; +} + +static void member_add(PureList *list, double key) { + if (!list->members) return; + if (list->bitmap && small_key(key)) { + size_t bit = (size_t)key, word = bit / 64; + if (word >= list->member_capacity) { /* the bits grown to hold it */ + size_t capacity = list->member_capacity; + while (capacity <= word) capacity *= 2; + uint64_t *grown = realloc(list->members, capacity * sizeof(*grown)); + if (!grown) { members_drop(list); return; } + memset(grown + list->member_capacity, 0, (capacity - list->member_capacity) * sizeof(*grown)); + list->members = grown, list->member_capacity = capacity; + } + uint64_t mask = UINT64_C(1) << (bit % 64); + list->member_count += !(list->members[word] & mask); + list->members[word] |= mask; + return; + } + size_t need = 2 * (list->member_count + 1), capacity = list->bitmap ? 64 : list->member_capacity; + while (capacity < need) capacity *= 2; + if ((list->bitmap || capacity != list->member_capacity) && !members_table(list, capacity)) { members_drop(list); return; } + member_put(list, key_bits(key)); +} + +/* A key out of the set; in a table the keys after it in its run moved back (no gap left behind them). */ +static void member_remove(PureList *list, double key) { + if (!list->members) return; + if (list->bitmap) { + if (!small_key(key) || (size_t)key / 64 >= list->member_capacity) return; + uint64_t *word = &list->members[(size_t)key / 64], mask = UINT64_C(1) << ((size_t)key % 64); + list->member_count -= (*word & mask) != 0; + *word &= ~mask; + return; + } + uint64_t bits = key_bits(key); + size_t mask = list->member_capacity - 1, at = member_slot(bits, mask); + while (list->members[at] != bits) { + if (list->members[at] == VACANT) return; + at = (at + 1) & mask; + } + for (size_t next = (at + 1) & mask; list->members[next] != VACANT; next = (next + 1) & mask) { + size_t home = member_slot(list->members[next], mask); + /* next may fill the gap at when its home is not cyclically within (at, next] */ + bool stays = at <= next ? (home > at && home <= next) : (home > at || home <= next); + if (!stays) list->members[at] = list->members[next], at = next; + } + list->members[at] = VACANT; + --list->member_count; +} static Node *child(const Node *node, unsigned i) { return node->child[i]; } static Guide *guide(const Node *node) { return (Guide *)((char *)node + sizeof(Node) + FANOUT * sizeof(Node *)); } -/* How many of n (at least one) ascending values are at or below key (upper) - * or below it (lower). */ -static unsigned upper(const double *values, unsigned n, double key) { - const double *base = values; - for (; n > 1; n -= n / 2) base = base[n / 2] <= key ? base + n / 2 : base; - return (unsigned)(base - values) + (*base <= key); -} +/* How many of n (at least one) ascending values are below key. */ static unsigned lower(const double *values, unsigned n, double key) { const double *base = values; for (; n > 1; n -= n / 2) base = base[n / 2] < key ? base + n / 2 : base; return (unsigned)(base - values) + (*base < key); } -/* The child of an inner node holding its item at (counted from the node's first). */ +/* The child of an inner node holding its item at (counted from the node's + * first): its children after the first whose items begin at or before at, + * counted rather than halved (no load waits for another; past the last + * child the counts are above any position). The end is in the last child. */ static unsigned child_at(const Node *node, size_t at) { - const uint32_t *before = guide(node)->before + 1, *base = before; - for (unsigned n = FANOUT - 1; n > 1; n -= n / 2) base = base[n / 2] <= at ? base + n / 2 : base; - return (unsigned)(base - before) + (*base <= at); + if (at >= node->items) return node->count - 1; + const uint32_t *before = guide(node)->before; + uint32_t n = 0, position = (uint32_t)at; /* every child, the first's 0 at or below any: a whole number of vectors */ + for (unsigned i = 0; i < FANOUT; ++i) n += before[i] <= position; + return n - 1; +} +/* An inner node's last child whose lead is at or below key (the first when + * none is): its leads after the first at or below key, counted (past the + * last child they are above any key). */ +static unsigned child_by_key(const Node *node, double key) { + const double *keys = guide(node)->keys; + uint64_t n = 0; /* every child's (a whole number of vectors), less the first's */ + for (unsigned i = 0; i < FANOUT; ++i) n += keys[i] <= key; + return (unsigned)n - (keys[0] <= key); } static double *numbers(const Layout *l, const Node *leaf, unsigned f) { return (double *)((char *)leaf + l->column[f]); } static int64_t *integers(const Layout *l, const Node *leaf, unsigned f) { return (int64_t *)((char *)leaf + l->column[f]); } @@ -345,11 +497,8 @@ typedef struct { Node *node; unsigned index; } Step; /* a node on the way, and t /* The leaf holding position at (the end is in the last leaf), and at's * place in it. */ static const Node *leaf_of(const PureList *list, size_t at, size_t *within) { - if (finger.leaf && finger.id == list->id && finger.version == list->version && at >= finger.start && - at < finger.start + finger.leaf->count) { - *within = at - finger.start; - return finger.leaf; - } + const Node *kept = fingered(list, at, within); + if (kept) return kept; const Node *node = list->root; size_t start = 0; while (!node->leaf) { @@ -357,7 +506,7 @@ static const Node *leaf_of(const PureList *list, size_t at, size_t *within) { start += guide(node)->before[i]; node = child(node, i); } - finger.id = list->id, finger.version = list->version, finger.leaf = node, finger.start = start; + finger_keep(list, node, start); *within = at - start; return node; } @@ -441,11 +590,8 @@ typedef struct { Node *extra[DEPTH + 1]; } Place; -static bool prepare(PureList *list, size_t at, Place *p) { - if (!list->root && !(list->root = new_node(list, true))) return false; - p->extras = p->used = 0; - p->appending = at == list->count; - if (!(p->depth = descend(list, at, p->path, &p->within))) return false; +/* The nodes a split may take, made now so that placing cannot fail. */ +static bool prepare_extras(PureList *list, Place *p) { if (p->path[p->depth - 1].node->count < FANOUT) return true; for (; p->extras <= p->depth; ++p->extras) if (!(p->extra[p->extras] = new_node(list, !p->extras))) { @@ -455,6 +601,44 @@ static bool prepare(PureList *list, size_t at, Place *p) { return true; } +static bool prepare(PureList *list, size_t at, Place *p) { + if (!list->root && !(list->root = new_node(list, true))) return false; + p->extras = p->used = 0; + p->appending = at == list->count; + if (!(p->depth = descend(list, at, p->path, &p->within))) return false; + return prepare_extras(list, p); +} + +/* The path to where key goes in a list kept in order of a number field (its + * key), the nodes on it the list's own; where in the list that is, and + * whether an item has the key there. False when memory runs out. */ +static bool descend_key(PureList *list, double key, Place *p, size_t *at, bool *found) { + const Layout *l = &list->layout; + Node **place = &list->root; + size_t start = 0; + for (unsigned depth = 0; depth < DEPTH; ++depth) { + Node *node = own(list, place); + if (!node) return false; + if (node->leaf) { + const double *keys = numbers(l, node, (unsigned)l->key); + unsigned low = node->count ? lower(keys, node->count, key) : 0; + *found = low < node->count && keys[low] == key; + p->path[depth] = (Step){node, 0}; + p->depth = depth + 1; + p->within = low; + *at = start + low; + for (unsigned d = depth; d-- > 0;) p->path[d].node->first = child(p->path[d].node, 0)->first; + return true; + } + const Guide *g = guide(node); + unsigned taken = child_by_key(node, key); + start += g->before[taken]; + p->path[depth] = (Step){node, taken}; + place = &node->child[taken]; + } + return false; +} + static void release_extras(PureList *list, Place *p) { while (p->extras > p->used) drop_node(list, p->extra[--p->extras]); } @@ -468,6 +652,7 @@ static void release_extras(PureList *list, Place *p) { static void place(PureList *list, Place *p, const PureCell *cells) { const Layout *l = &list->layout; unsigned index = p->within; + if (list->members) member_add(list, cells[l->key].num); Node *pointer = NULL; /* above the leaf: the node that goes in */ for (unsigned d = p->depth; d-- > 0;) { Node *node = p->path[d].node; @@ -520,6 +705,7 @@ static void place(PureList *list, Place *p, const PureCell *cells) { static void take_out(PureList *list, Step *path, unsigned depth, unsigned within) { const Layout *l = &list->layout; Node *leaf = path[depth - 1].node; + if (list->members) member_remove(list, numbers(l, leaf, (unsigned)l->key)[within]); move_items(l, leaf, within, leaf, within + 1, leaf->count - within - 1); --leaf->count; unsigned d = depth - 1; @@ -624,6 +810,7 @@ void pure_list_free(PureList *list) { if (__atomic_sub_fetch(&list->refs, 1, __ATOMIC_ACQ_REL)) return; } else { free(list->journal); + free(list->members); let_go_tree(list, list->root); for (unsigned kind = 0; kind < 2; ++kind) { while (list->spares[kind]) free(list->spare[kind][--list->spares[kind]]); @@ -639,8 +826,41 @@ void pure_list_clear(PureList *list) { list->root = NULL; list->count = list->bytes = 0; ++list->version; + if (!list->members) return; + if (list->bitmap && list->member_capacity <= BITMAP_KEPT) { /* small bits are kept for the next event */ + memset(list->members, 0, list->member_capacity * sizeof(*list->members)); + list->member_count = 0; + return; + } + members_drop(list); /* else bits again, from few */ + (void)members_start(list); } +bool pure_list_hashed(PureList *list) { + const Layout *l = &list->layout; + if (list->members) return true; + if (l->key < 0 || list->copy || !members_start(list)) return false; + for (size_t at = 0; at < list->count && list->members; ++at) /* the keys it has now, once */ + member_add(list, pure_list_get(list, at, (unsigned)l->key).num); + return list->members != NULL; +} + +bool pure_list_contains(const PureList *list, double key, bool *found) { + if (!list->members) return false; + 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; + return true; + } + uint64_t bits = key_bits(key); + size_t mask = list->member_capacity - 1, at = member_slot(bits, mask); + while (list->members[at] != VACANT && list->members[at] != bits) at = (at + 1) & mask; + *found = list->members[at] == bits; + return true; +} + +size_t pure_list_extra(const PureList *list) { return list->member_capacity * sizeof(*list->members); } + size_t pure_list_count(const PureList *list) { return list->count; } PureList *pure_list_share(PureList *list, PureRetired *retired, uint64_t epoch) { @@ -1005,6 +1225,49 @@ PureResult pure_list_insert(PureList *list, size_t at, const PureCell *cells, Pu return PURE_OK; } +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 (list->members) { /* the set says at once when the key is there */ + bool found; + if (pure_list_contains(list, cells[l->key].num, &found) && found) { + *at = pure_list_seek(list, (unsigned)l->key, cells[l->key], exists); + return PURE_OK; + } + } + if (list->count == PURE_LIST_ITEMS) return PURE_LIMIT; + if (!list->root && !(list->root = new_node(list, true))) return PURE_ALLOCATION; + Place p = {.extras = 0, .used = 0}; + if (!descend_key(list, cells[l->key].num, &p, at, exists)) return PURE_ALLOCATION; + if (*exists) return PURE_OK; + p.appending = *at == list->count; + PureCell item[16]; + unsigned owned = 0; + for (; owned < l->fields; ++owned) + if (!own_cell(list, owned, cells[owned], &item[owned])) break; + size_t size = RECORD_HEAD; + for (unsigned f = 0; list->journaled && f < l->fields; ++f) size += compact_bound(l, f, cells[f]); + unsigned char *record = list->journaled ? journal_room(list, size) : NULL; + if (owned < l->fields || (list->journaled && !record) || !prepare_extras(list, &p)) { + for (unsigned f = 0; f < owned; ++f) free_text(item[f].text); + return PURE_ALLOCATION; + } + if (undo && !log_change(undo, (Entry){.change = INSERTED, .list = list, .at = *at})) { + release_extras(list, &p); + for (unsigned f = 0; f < l->fields; ++f) free_text(item[f].text); + return PURE_ALLOCATION; + } + if (record) { + unsigned char *end = record_head(record, RECORD_INSERT, *at); + for (unsigned f = 0; f < l->fields; ++f) end = put_compact(l, f, item[f], end); + list->journal_size += (size_t)(end - record); + } + list->bytes += cells_bytes(l, item); + place(list, &p, item); + return PURE_OK; +} + /* Room for one more item's cells in the log. */ static PureCell *log_cells(PureUndo *undo, unsigned fields) { if (undo->cell_count + fields > undo->cell_capacity) { @@ -1051,10 +1314,11 @@ PureResult pure_list_set(PureList *list, size_t at, unsigned field, PureCell val unsigned within, depth = 0; bool keyed = (int)field == l->key; Node *leaf; - if (!keyed && finger.leaf && finger.id == list->id && finger.version == list->version && at >= finger.start && - at < finger.start + finger.leaf->count && !shared_node(list, finger.leaf)) { - leaf = (Node *)finger.leaf; - within = (unsigned)(at - finger.start); + size_t found_within; + const Node *kept = keyed ? NULL : fingered(list, at, &found_within); + if (kept && !shared_node(list, kept)) { + leaf = (Node *)kept; + within = (unsigned)found_within; } else { if (!(depth = descend(list, at, path, &within))) return PURE_ALLOCATION; leaf = path[depth - 1].node; @@ -1079,9 +1343,12 @@ PureResult pure_list_set(PureList *list, size_t at, unsigned field, PureCell val else if (l->kinds[field] == PURE_CELL_INTEGER) integers(l, leaf, field)[within] = copy.i64; else numbers(l, leaf, field)[within] = copy.num; if (!undo) let_go_text(list, old.text); - if (keyed) sum_path(list, path, depth); + if (keyed) { + sum_path(list, path, depth); + if (list->members) member_remove(list, old.num), member_add(list, copy.num); + } ++list->version; - finger.id = list->id, finger.version = list->version, finger.leaf = leaf, finger.start = at - within; + finger_keep(list, leaf, at - within); return PURE_OK; } @@ -1165,11 +1432,22 @@ size_t pure_list_seek(const PureList *list, unsigned field, PureCell key, bool * *found = false; if (!node || !list->count) return 0; if ((int)field == l->key) { + /* A leaf a finger keeps whose keys reach round key holds its place + * (a slice's high bound is near its low one, found just before). */ + for (unsigned i = 0; i < FINGERS; ++i) { + const Finger *f = &fingers[i]; + if (!f->leaf || f->id != list->id || f->version != list->version || !f->leaf->count) continue; + const double *keys = numbers(l, f->leaf, field); + if (!(keys[0] <= key.num && key.num <= keys[f->leaf->count - 1])) continue; + unsigned low = lower(keys, f->leaf->count, key.num); + *found = low < f->leaf->count && keys[low] == key.num; + return f->start + low; + } /* Each level: the last child whose lead is at or below key (the * first when none is); then the leaf's items below key. */ while (!node->leaf) { const Guide *g = guide(node); - unsigned taken = upper(g->keys + 1, FANOUT - 1, key.num); + unsigned taken = child_by_key(node, key.num); start += g->before[taken]; node = child(node, taken); } @@ -1178,6 +1456,7 @@ size_t pure_list_seek(const PureList *list, unsigned field, PureCell key, bool * for (unsigned i = 0; i < node->count; i += 8) __builtin_prefetch(keys + i); unsigned low = lower(keys, node->count, key.num); *found = low < node->count && keys[low] == key.num; + finger_keep(list, node, start); /* the item found is read there next */ return start + low; } while (!node->leaf) { @@ -1305,8 +1584,11 @@ void pure_undo_rollback(PureUndo *undo, size_t mark) { *text = (PureSpan){e->old.text, e->old.size}; } else if (l->kinds[e->field] == PURE_CELL_INTEGER) integers(l, leaf, e->field)[within] = e->old.i64; - else + else { + double now = numbers(l, leaf, e->field)[within]; numbers(l, leaf, e->field)[within] = e->old.num; + if (list->members && (int)e->field == l->key) member_remove(list, now), member_add(list, e->old.num); + } sum_path(list, path, depth); ++list->version; } diff --git a/core/module-list.h b/core/module-list.h index 69e0d7d..4778280 100644 --- a/core/module-list.h +++ b/core/module-list.h @@ -101,6 +101,12 @@ void pure_retired_free(PureRetired *); /* Insert a copy of cells (text bytes are copied) before position at. A NULL * log means the change is not undone. */ PureResult pure_list_insert(PureList *, size_t at, const PureCell *cells, PureUndo *); +/* An item into a list kept in order of a number field, where its key goes, + * found and placed in one descent (docs/design/020): at says where, exists + * whether an item had the key (then nothing changes). Its change is logged + * and journaled as pure_list_insert's. PURE_INVALID when the list is not + * such a one (search it and insert then). */ +PureResult pure_list_add(PureList *, const PureCell *cells, PureUndo *, size_t *at, bool *exists); PureResult pure_list_remove(PureList *, size_t at, PureUndo *); PureResult pure_list_set(PureList *, size_t at, unsigned field, PureCell value, PureUndo *); PureCell pure_list_get(const PureList *, size_t at, unsigned field); @@ -117,6 +123,17 @@ size_t pure_list_seek(const PureList *, unsigned field, PureCell key, bool *foun * field, seek by it reads each level's keys from one node (field -1, or a * text field: none). ALLOCATION leaves the list searched as if it had none. */ PureResult pure_list_keyed(PureList *, int field); +/* A list keyed by a number keeps its keys as a set too, beside its tree + * (docs/design/020): pure_list_contains answers whether a key is there + * without a search. Its changes and their undoing keep the set; a share of + * it has none. For the lists an event searches most (its own). False when + * it is not keyed by a number, is a copy, or memory runs out (it is + * searched as before). */ +bool pure_list_hashed(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); +/* The bytes it keeps beside its items for that. */ +size_t pure_list_extra(const PureList *); /* The list's items ordered by field, as a keyed list keeps them: *out is NULL * when they already are, or a new list in that order with moved[position * before] = position after for every item. CONFLICT when two items have the diff --git a/core/module.c b/core/module.c index ffcc9cb..5b43fea 100644 --- a/core/module.c +++ b/core/module.c @@ -354,6 +354,11 @@ static unsigned char state_type(const PureModule *m, uint32_t state) { return m->state_type[state] == PURE_STATE_BOOL ? T_BOOL : m->state_type[state] == PURE_STATE_I64 ? T_I64 : T_NUM; } +/* Whether a list's record field is a text. */ +static bool text_field(const PureModule *m, uint32_t list, uint32_t field) { + return m->record_field_type[m->record[m->state_ref[list]].first + field] == PURE_RECORD_TEXT; +} + /* What a local holds (its argument's bits 8-15): a number, an index, a bool or an i64. */ static unsigned char local_type(uint32_t arg) { static const unsigned char types[] = {T_NUM, T_INDEX, T_BOOL, T_I64}; @@ -1336,6 +1341,13 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule plan_folds(out, out->handler[i].code, input); range_code(out, out->handler[i].code, input); } + /* What a cell is, read once here: an item's field, or a keyed list's key, a text (plan) or not. */ + for (uint32_t pc = 0; pc < out->code_count; ++pc) { + PureOp *op = &out->code[pc]; + if (op->op == PURE_OP_ITEM_GET || op->op == PURE_OP_ITEM_SET) op->plan = text_field(out, list_of(op->arg), item_field(op->arg)); + else if (op->op == PURE_OP_LIST_FIND || op->op == PURE_OP_LIST_HAS) + op->plan = text_field(out, op->arg, out->state_key[op->arg] - 1u); + } return PURE_OK; refused: if (error_size) snprintf(error, error_size, "%s (%u)", why, bad); @@ -1477,6 +1489,18 @@ static bool related(uint32_t relation, int order) { /* A walk (EACH): the list, the item it runs for, where it ends (items the * walk removes move it), and whether that item left. */ typedef struct { uint32_t list; size_t at, end; bool removed; } Walk; +/* A loop that runs in its block's run (LOOP, EACH): its block, the arena as + * it began, a walk's walk and the event's walk and row around it, a + * count's values (low + k of count) and slot. */ +typedef struct { + uint32_t start, end; + size_t mark; + bool walking, integer; + Walk walk, *around; + size_t row; + uint64_t count, k; + PureValue low, *slot; +} Loop; typedef struct { PureApp *app; const PureInputShape *shape; /* message, or NULL */ @@ -1490,7 +1514,6 @@ typedef struct { PureValue *locals; /* the event's locals (a handler's, and what runs in it), or NULL */ bool arguments; /* FIELD reads the arguments given for a view, not the message */ bool modified, exists; - bool broke; /* a BREAK ended the loop whose block this runs */ uint32_t (*spans)[2]; /* a message's variable fields: start and size in the payload */ } Event; @@ -1517,7 +1540,7 @@ static inline bool charge(PureApp *app, uint64_t instructions) { typedef struct { size_t stored, kept; } Held; static inline Held list_held(const PureApp *app, const PureList *list) { - return (Held){pure_list_size(list), pure_list_changes(list).size + pure_undo_size(&app->undo)}; + return (Held){pure_list_size(list), pure_list_changes(list).size + pure_undo_size(&app->undo) + pure_list_extra(list)}; } static inline Held text_held(const PureApp *app, uint32_t text) { return (Held){pure_draft_size(app->texts[text]), 0}; } @@ -1643,9 +1666,7 @@ static void move_indices(const PureModule *m, PureValue *values, uint32_t list, } } -static bool text_field(const PureModule *m, uint32_t list, uint32_t field) { - return m->record_field_type[m->record[m->state_ref[list]].first + field] == PURE_RECORD_TEXT; -} + /* Append bytes to the arena as a value of it. */ static PureResult keep_bytes(PureArena *arena, const void *bytes, size_t length, PureBytes *out) { @@ -1904,7 +1925,8 @@ static bool run_lanes(const PureModule *m, const PureValue *values, PureBlock bl if (uniform(top)) { double value; if (!recalled(memo, pc - block.start, &value)) { - size_t at = pure_list_seek(keyed, key, (PureCell){.num = top->value}, &found); + size_t at = find || !pure_list_contains(keyed, top->value, &found) ? + pure_list_seek(keyed, key, (PureCell){.num = top->value}, &found) : 0; if (find && !found) return false; remember(memo, pc - block.start, value = find ? (double)at : found); } @@ -1913,7 +1935,8 @@ static bool run_lanes(const PureModule *m, const PureValue *values, PureBlock bl } const double *keys = lanes_of(top, scratch[0], items); for (unsigned i = 0; i < n; ++i) { - size_t at = pure_list_seek(keyed, key, (PureCell){.num = keys[i]}, &found); + size_t at = find || !pure_list_contains(keyed, keys[i], &found) ? + pure_list_seek(keyed, key, (PureCell){.num = keys[i]}, &found) : 0; if (find && !found) return false; out[i] = find ? (double)at : found; } @@ -2415,7 +2438,40 @@ static PureResult run(const PureModule *m, PureValue *values, PureBlock block, E PureResult status; PureFault kind; const PureOp *op = NULL; - for (uint32_t pc = block.start, end = block.start + block.length; pc < end;) { + /* The loops open here (LOOP, EACH), innermost last, and where the innermost's block ends. */ + Loop loops[PURE_MODULE_NESTING]; + unsigned depth = 0; + uint32_t loop_end = UINT32_MAX; + for (uint32_t pc = block.start, end = block.start + block.length;;) { + if (pc == loop_end) { /* a loop's block ran once: again, or the loop ends (its end may be the block's) */ + Loop *loop = &loops[depth - 1]; + arena->used = loop->mark; + if (loop->walking) { + Walk *walk = &loop->walk; + if (!walk->removed) ++walk->at; + walk->removed = false; + if (walk->at < walk->end && walk->at < pure_list_count(app->lists[walk->list])) { + ev->row = walk->at; + pc = loop->start; + continue; + } + ev->walk = loop->around, ev->row = loop->row; + } else if (++loop->k < loop->count) { + if (!charge(app, (uint64_t)(loop->end - loop->start) + 1)) { + kind = PURE_FAULT_WORK; + op = &m->code[loop->start - 1]; + goto failed; + } + if (loop->integer) loop->slot->i64 = (int64_t)((uint64_t)loop->low.i64 + loop->k); + else loop->slot->num = loop->low.num + (double)loop->k; + pc = loop->start; + continue; + } + --depth; + loop_end = depth ? loops[depth - 1].end : UINT32_MAX; + continue; + } + if (pc >= end) break; op = &m->code[pc++]; uint32_t arg = op->arg; Slot *top = sp ? &stack[sp - 1] : stack; @@ -2622,14 +2678,17 @@ static PureResult run(const PureModule *m, PureValue *values, PureBlock block, E return status; cells[f] = (PureCell){.i64 = stack[base + f].i64, .text = (unsigned char *)span.data, .size = span.size}; } - if (m->state_key[arg]) { /* a keyed list places the item by its key */ + Held before = list_held(app, list); + status = PURE_INVALID; + if (m->state_key[arg]) { /* a keyed list places the item by its key: found and placed at once when kept by a number */ bool found; - unsigned key = m->state_key[arg] - 1u; - at = pure_list_seek(list, key, cells[key], &found); + if ((status = pure_list_add(list, cells, undo_for(app, arg), &at, &found)) == PURE_INVALID) { + unsigned key = m->state_key[arg] - 1u; + at = pure_list_seek(list, key, cells[key], &found); + } if (found) { arena->used = mark; kind = PURE_FAULT_EXISTS; goto failed; } } - Held before = list_held(app, list); - status = pure_list_insert(list, at, cells, undo_for(app, arg)); + if (status == PURE_INVALID) status = pure_list_insert(list, at, cells, undo_for(app, arg)); arena->used = mark; if (status != PURE_OK) goto refused; move_indices(m, values, arg, pure_list_count(list), at, true); @@ -2656,7 +2715,7 @@ static PureResult run(const PureModule *m, PureValue *values, PureBlock block, E if (at >= pure_list_count(app->lists[list])) { kind = PURE_FAULT_NOT_FOUND; goto failed; } PureCell cell = pure_list_get(app->lists[list], at, field); /* A text is copied: the item may change or go before the value is used. */ - if (!text_field(m, list, field)) top->i64 = cell.i64; /* the bits: a number's, a bool's or an i64's */ + if (!op->plan) top->i64 = cell.i64; /* the bits: a number's, a bool's or an i64's (plan: a text, set at load) */ else if ((status = keep_bytes(arena, cell.text, cell.size, &top->bytes)) != PURE_OK) return status; continue; } @@ -2666,7 +2725,7 @@ static PureResult run(const PureModule *m, PureValue *values, PureBlock block, E size_t at = (size_t)stack[--sp].num, mark = arena->used; Held before = list_held(app, app->lists[list]); PureSpan span = {0}; - status = text_field(m, list, field) ? contiguous(app, arena, value.bytes, &span) : PURE_OK; + status = op->plan ? contiguous(app, arena, value.bytes, &span) : PURE_OK; /* plan: a text */ 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}, @@ -2722,44 +2781,37 @@ static PureResult run(const PureModule *m, PureValue *values, PureBlock block, E } case PURE_OP_EACH: { /* The block that follows runs for each item the list has, as the - * handler's code with ROW the item; the list only shrinks meanwhile. */ - PureBlock inner = {pc, arg >> 16}; - Walk walk = {arg >> 8 & 0xFF, 0, SIZE_MAX, false}; - pc += inner.length; - Event per = *ev; - per.walk = &walk; + * handler's code with ROW the item; the list only shrinks meanwhile. + * It runs here, a loop opened (its end takes pc back), not by recursion. */ + uint32_t length = arg >> 16; + Loop *loop = &loops[depth]; + loop->walking = true; + loop->walk = (Walk){arg >> 8 & 0xFF, 0, SIZE_MAX, false}; if (arg & PURE_EACH_SLICED) { /* the items with keys from low up to before high */ Slot high = stack[--sp], low = stack[--sp]; - slice_of(app->lists[walk.list], m->state_key[walk.list] - 1u, low, high, &walk.at, &walk.end); + slice_of(app->lists[loop->walk.list], m->state_key[loop->walk.list] - 1u, low, high, &loop->walk.at, + &loop->walk.end); } - size_t items = pure_list_count(app->lists[walk.list]); /* as written: what it starts with, the list only shrinking */ - if (!charge(app, (uint64_t)inner.length * ((walk.end < items ? walk.end : items) - walk.at))) { + size_t items = pure_list_count(app->lists[loop->walk.list]); /* as written: what it starts with, the list only shrinking */ + if (!charge(app, (uint64_t)length * ((loop->walk.end < items ? loop->walk.end : items) - loop->walk.at))) { kind = PURE_FAULT_WORK; goto failed; } if (!(arg & PURE_EACH_SLICED) && op->range) /* a where that bounds the key: only the items in bounds */ - range_bounds(m, values, &m->range[op->range - 1], app->lists[walk.list], m->state_key[walk.list] - 1u, &per, - &walk.at, &walk.end); - per.broke = false; - while (walk.at < walk.end && walk.at < pure_list_count(app->lists[walk.list])) { - size_t mark = arena->used; - per.row = walk.at; - walk.removed = false; - status = run(m, values, inner, &per, NULL); - arena->used = mark; - if (status != PURE_OK) return status; - if (per.broke) break; - if (!walk.removed) ++walk.at; - } - ev->modified = per.modified; - ev->exists = per.exists; + range_bounds(m, values, &m->range[op->range - 1], app->lists[loop->walk.list], m->state_key[loop->walk.list] - 1u, + ev, &loop->walk.at, &loop->walk.end); + if (!(loop->walk.at < loop->walk.end && loop->walk.at < items)) { pc += length; continue; } /* none */ + loop->start = pc, loop->end = pc + length, loop->mark = arena->used; + loop->around = ev->walk, loop->row = ev->row; + ev->walk = &loop->walk; + ev->row = loop->walk.at; + loop_end = loops[depth++].end; continue; } case PURE_OP_LOOP: { /* The block that follows runs once for each value from low up to before high, the slot holding it; its - * work counts as it runs (the LOOP too, so an empty block counts). */ - PureBlock inner = {pc, arg >> 16}; - pc += inner.length; + * work counts as it runs (the LOOP too, so an empty block counts). It runs here, as a walk does. */ + uint32_t length = arg >> 16; Slot high = stack[--sp], low = stack[--sp]; bool integer = arg & PURE_LOOP_INTEGER; uint64_t count = 0; @@ -2767,23 +2819,28 @@ static PureResult run(const PureModule *m, PureValue *values, PureBlock block, E else if (!(fabs(low.num) <= 0x1p53 && fabs(high.num) <= 0x1p53 && low.num == floor(low.num) && high.num == floor(high.num))) { kind = PURE_FAULT_LIMIT; goto failed; } else count = high.num > low.num ? (uint64_t)(high.num - low.num) : 0; - Event per = *ev; - per.broke = false; - PureValue *slot = &ev->locals[arg & 0xFF]; - for (uint64_t k = 0; k < count && !per.broke; ++k) { - if (!charge(app, (uint64_t)inner.length + 1)) { kind = PURE_FAULT_WORK; goto failed; } - if (integer) slot->i64 = (int64_t)((uint64_t)low.i64 + k); - else slot->num = low.num + (double)k; - size_t mark = arena->used; - status = run(m, values, inner, &per, NULL); - arena->used = mark; - if (status != PURE_OK) return status; - } - ev->modified = per.modified; - ev->exists = per.exists; + if (!count) { pc += length; continue; } + if (!charge(app, (uint64_t)length + 1)) { kind = PURE_FAULT_WORK; goto failed; } + Loop *loop = &loops[depth]; + loop->walking = false; + loop->integer = integer; + loop->count = count, loop->k = 0; + loop->low = (PureValue){.i64 = low.i64}; + loop->slot = &ev->locals[arg & 0xFF]; + if (integer) loop->slot->i64 = low.i64; + else loop->slot->num = low.num; + loop->start = pc, loop->end = pc + length, loop->mark = arena->used; + loop_end = loops[depth++].end; + continue; + } + case PURE_OP_BREAK: { /* the innermost loop ends: the code after its block runs next */ + Loop *loop = &loops[--depth]; + arena->used = loop->mark; + if (loop->walking) ev->walk = loop->around, ev->row = loop->row; + pc = loop->end; + loop_end = depth ? loops[depth - 1].end : UINT32_MAX; continue; } - case PURE_OP_BREAK: ev->broke = true; return PURE_OK; /* the loop that runs this block ends */ case PURE_OP_TEXT_COMPARE: { /* Texts order by their bytes: a shorter text before a longer one it begins. */ PureBytes right = stack[--sp].bytes, left = stack[sp - 1].bytes; @@ -2804,12 +2861,17 @@ static PureResult run(const PureModule *m, PureValue *values, PureBlock block, E unsigned key = m->state_key[arg] - 1u; size_t mark = arena->used; PureCell cell = {.i64 = top->i64}; - if (text_field(m, arg, key)) { + if (op->plan) { /* a text key (set at load) */ PureSpan span; if ((status = contiguous(app, arena, top->bytes, &span)) != PURE_OK) return status; cell = (PureCell){.text = (unsigned char *)span.data, .size = span.size}; } bool found; + /* 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)) { + top->num = found; + continue; + } size_t at = pure_list_seek(app->lists[arg], key, cell, &found); arena->used = mark; if (op->op == PURE_OP_LIST_HAS) { top->num = found; continue; } @@ -3604,6 +3666,7 @@ static bool own_lists(PureApp *app, uint32_t lists) { if (!app->own[i]) { if (!(app->own[i] = new_list(m, m->state_ref[i]))) return false; (void)pure_list_keyed(app->own[i], m->state_key[i] ? (int)m->state_key[i] - 1 : -1); + if (m->state_key[i]) (void)pure_list_hashed(app->own[i]); } app->lists[i] = app->own[i]; } @@ -4267,9 +4330,11 @@ PURE_COLD static PureResult open_module(PureApp *app, const PureModule *module) /* A stored list's changes are recorded from now on; a transient one's never. */ if (lists_stored && module->state_type[i] == PURE_STATE_LIST && !(module->state_flags[i] & PURE_LIST_ROWS >> 8)) pure_list_journal(lists[i], !pure_state_transient(module, i)); - /* Without memory for its keys a keyed list is still searched, only slower. */ + /* Without memory for its keys a keyed list is still searched, only slower; an event's keeps them as a set too (020). */ if (module->state_type[i] == PURE_STATE_LIST) (void)pure_list_keyed(lists[i], module->state_key[i] ? (int)module->state_key[i] - 1 : -1); + if (module->state_type[i] == PURE_STATE_LIST && module->state_key[i] && module->state_flags[i] & PURE_LIST_ROWS >> 8) + (void)pure_list_hashed(lists[i]); } if (old) remap_outputs(app, old, module, true, NULL, NULL); if (recast) { /* in the place of the outbox, its sends now the new module's */ diff --git a/core/module.h b/core/module.h index c5b7ba0..80d4460 100644 --- a/core/module.h +++ b/core/module.h @@ -198,7 +198,8 @@ const char *pure_fault_name(PureFault); /* plan, shape and range are the runtime's, set at load: a fold whose block * has a form for every instruction that works on a leaf of its list at once - * runs so (plan), one in a column may be answered for every row from one + * runs so (plan; for an item's field, or a keyed list's key, read or set: + * whether it is a text), one in a column may be answered for every row from one * pass over its list (shape: its PureShape + 1), and a fold or a walk whose * test bounds a keyed list's key reads only the items in bounds (range: its * PureRange + 1). */ diff --git a/core/test-module.c b/core/test-module.c index 9bf34ff..35a154f 100644 --- a/core/test-module.c +++ b/core/test-module.c @@ -1031,7 +1031,7 @@ static bool collect_bytes(void *context, PureSpan span) { b->bytes = realloc(b->bytes, b->capacity); CHECK(b->bytes); } - memcpy(b->bytes + b->size, span.data, span.size); + if (span.size) memcpy(b->bytes + b->size, span.data, span.size); /* none: a save of changes all undone */ b->size += span.size; return true; } @@ -1099,6 +1099,281 @@ static void retired_come_back(void) { pure_retired_free(&retired[1]); } +/* ---- A keyed list's keys as a set, and fingers (docs/design/020): a list + * keeping its keys as a set beside its tree answers as a model array does at + * every step of a random run of adds, removes and key changes (some undone), + * searches by key, reads by position and clears. Its keys go from bits to a + * table (a key not a small whole number), leave a table's runs from their + * middle, and grow bits past what a clear keeps; shares (a snapshot's copies, + * the same list as it was) and other lists read between, so a finger kept + * for one is never taken for another. */ + +static size_t model_lower(const Model *m, double key) { + size_t low = 0, high = m->count; + while (low < high) { + size_t middle = (low + high) / 2; + if (m->items[middle].key < key) low = middle + 1; + else high = middle; + } + return low; +} + +/* A key the set keeps as a bit. */ +static bool small_whole(double key) { return key >= 0 && key < 4194304 && floor(key) == key; } + +static bool model_has(const Model *m, double key) { + size_t at = model_lower(m, key); + return at < m->count && m->items[at].key == key; +} + +/* Position at read as the model has it, by get, and the search for its key. */ +static bool reads_as(const PureList *list, const Model *m, size_t at) { + PureCell key = pure_list_get(list, at, 0), text = pure_list_get(list, at, 1); + bool found; + return same_item(m, at, key.num, (PureSpan){text.text, text.size}) && + pure_list_seek(list, 0, (PureCell){.num = m->items[at].key}, &found) == at && found; +} + +static void key_sets(void) { + static const uint8_t fields[2] = {PURE_CELL_NUMBER, PURE_CELL_TEXT}; + enum { ROUNDS = 120000, OTHERS = 4 }; + uint32_t seed = 0x6b657973u; + PureList *list = pure_list_new(2, fields), *others[OTHERS], *copy = NULL; + PureRetired retired = {0}; + PureUndo undo = {0}; + Model model = {0}, shared = {0}; + CHECK(list && pure_list_keyed(list, 0) == PURE_OK); + /* Items there before it keeps a set: the set starts with them. */ + for (unsigned i = 0; i < 300; ++i) { + double key = (double)(i * 7); + PureCell cells[2] = {{.num = key}, {.text = (unsigned char *)"a", .size = 1}}; + CHECK(pure_list_insert(list, i, cells, NULL) == PURE_OK); + model_insert(&model, i, (ModelItem){key, "a", 1}); + } + CHECK(pure_list_hashed(list) && pure_list_hashed(list) && pure_list_extra(list) > 0); + bool found; + CHECK(pure_list_contains(list, 7, &found) && found && pure_list_contains(list, 8, &found) && !found); + CHECK(pure_list_contains(list, -0.0, &found) && found); /* -0 is the key 0 */ + for (unsigned o = 0; o < OTHERS; ++o) { /* other lists, read between: key i at i */ + CHECK((others[o] = pure_list_new(2, fields)) && pure_list_keyed(others[o], 0) == PURE_OK); + for (unsigned i = 0; i < 2000; ++i) + CHECK(pure_list_insert(others[o], i, (PureCell[]){{.num = i + o}, {.size = 0}}, NULL) == PURE_OK); + } + { + PureList *texts = pure_list_new(2, (const uint8_t[]){PURE_CELL_TEXT, PURE_CELL_NUMBER}); + CHECK(texts && pure_list_keyed(texts, 0) == PURE_OK && !pure_list_hashed(texts) && !pure_list_contains(texts, 1, &found)); + pure_list_free(texts); + } + size_t adds = 0, removes = 0, changes = 0, undone = 0, clears = 0, tables = 0, shares = 0; + bool table = false; + for (unsigned round = 0; round < ROUNDS; ++round) { + /* The keys: small whole ones (bits); some past what a clear keeps; + * then quarters too (a table), dense, so runs are long and removes + * from their middle many; then whole ones past the bits. */ + unsigned phase = round / (ROUNDS / 4), r = next_random(&seed); + double key = phase == 0 ? (double)(r % 30000) + : phase == 1 ? (r % 997 ? (double)(r % 30000) : (double)(r % 4000000)) + : phase == 2 ? (double)(r % 24000) / 4 + : (r % 5 ? (double)(r % 30000) : 4194304.0 + (double)(r % 100000)); + if (phase == 2 && r % 7 == 0) key = -key; /* negative keys too */ + CHECK(pure_list_contains(list, key, &found) && found == model_has(&model, key)); + unsigned op = next_random(&seed) % 16; + bool undoing = next_random(&seed) % 9 == 0; + if (op < 7) { /* add */ + char text[12]; + size_t size = (size_t)snprintf(text, sizeof(text), "%u", round % 100000); + PureCell cells[2] = {{.num = key}, {.text = (unsigned char *)text, .size = size}}; + size_t at, low = model_lower(&model, key); + bool exists; + CHECK(pure_list_add(list, cells, undoing ? &undo : NULL, &at, &exists) == PURE_OK); + CHECK(at == low && exists == found); + if (!exists && undoing) { + pure_undo_rollback(&undo, 0); + ++undone; + CHECK(pure_list_contains(list, key, &found) && !found && pure_list_count(list) == model.count); + } else if (!exists) { + ModelItem item = {key, {0}, size}; + memcpy(item.text, text, size); + model_insert(&model, at, item); + ++adds; + if (!table && !small_whole(key)) { + table = true, ++tables; /* a table: at most half full */ + CHECK(pure_list_extra(list) >= 2 * model.count * sizeof(uint64_t)); + } + } + pure_undo_commit(&undo); + } else if (op < 10 && model.count) { /* remove */ + size_t at = next_random(&seed) % model.count; + double gone = model.items[at].key; + CHECK(pure_list_remove(list, at, undoing ? &undo : NULL) == PURE_OK); + CHECK(pure_list_contains(list, gone, &found) && !found); + if (undoing) { + pure_undo_rollback(&undo, 0); + ++undone; + CHECK(pure_list_contains(list, gone, &found) && found && reads_as(list, &model, at)); + } else { + memmove(model.items + at, model.items + at + 1, (model.count - at - 1) * sizeof(*model.items)); + --model.count; + ++removes; + } + pure_undo_commit(&undo); + } else if (op < 12 && model.count) { /* a key changed to one between its neighbours */ + size_t at = next_random(&seed) % model.count; + double was = model.items[at].key, low = at ? model.items[at - 1].key : was - 4, + high = at + 1 < model.count ? model.items[at + 1].key : was + 4; + double to = phase == 2 ? low + (high - low) * (double)(1 + next_random(&seed) % 3) / 4 + : floor(low) + 1 + (double)(next_random(&seed) % 3); + if (to > low && to < high && (phase == 2 || to >= 0)) { + CHECK(pure_list_set(list, at, 0, (PureCell){.num = to}, undoing ? &undo : NULL) == PURE_OK); + CHECK(pure_list_contains(list, to, &found) && found); + CHECK(to == was || (pure_list_contains(list, was, &found) && !found)); + if (undoing) { + pure_undo_rollback(&undo, 0); + ++undone; + CHECK(pure_list_contains(list, was, &found) && found); + CHECK(to == was || (pure_list_contains(list, to, &found) && !found)); + } else { + model.items[at].key = to; + ++changes; + if (!table && !small_whole(to)) table = true, ++tables; + } + CHECK(reads_as(list, &model, at)); + pure_undo_commit(&undo); + } + } else if (op < 14) { /* a search, and the items around what it found */ + size_t at = pure_list_seek(list, 0, (PureCell){.num = key}, &found); + CHECK(at == model_lower(&model, key) && found == model_has(&model, key)); + for (size_t i = at ? at - 1 : 0; i < at + 2 && i < model.count; ++i) CHECK(reads_as(list, &model, i)); + } else if (model.count) { /* items read in order from one */ + size_t at = next_random(&seed) % model.count; + for (size_t i = at; i < at + 40 && i < model.count; ++i) { + PureCell k = pure_list_get(list, i, 0), t = pure_list_get(list, i, 1); + CHECK(same_item(&model, i, k.num, (PureSpan){t.text, t.size})); + } + } + /* Another list read between (fingers for five lists, four kept). */ + unsigned o = next_random(&seed) % OTHERS, i = next_random(&seed) % 2000; + CHECK(pure_list_get(others[o], i, 0).num == i + o); + CHECK(pure_list_seek(others[o], 0, (PureCell){.num = i + o + 0.5}, &found) == i + 1 && !found); + /* A share: the list as it was, read beside it while it changes. */ + if (copy) { + CHECK(pure_list_count(copy) == shared.count && !pure_list_contains(copy, key, &found)); + if (shared.count) CHECK(reads_as(copy, &shared, next_random(&seed) % shared.count)); + size_t at = pure_list_seek(copy, 0, (PureCell){.num = key}, &found); + CHECK(at == model_lower(&shared, key) && found == model_has(&shared, key)); + } + if (round % 6000 == 3000) { + if (copy) { + CHECK(same_items(copy, &shared)); + pure_list_free(copy); + } + CHECK((copy = pure_list_share(list, &retired, round + 1)) && !pure_list_hashed(copy)); + model_copy(&shared, &model); + ++shares; + } + if (round % 9973 == 9972) { /* cleared: an event's list begins each event empty */ + CHECK(same_items(list, &model)); + for (size_t k = 0; k < model.count; ++k) CHECK(pure_list_contains(list, model.items[k].key, &found) && found); + pure_list_clear(list); + model.count = 0, table = false, ++clears; + CHECK(pure_list_count(list) == 0 && pure_list_contains(list, key, &found) && !found); + } + } + CHECK(same_items(list, &model)); + for (size_t k = 0; k < model.count; ++k) CHECK(pure_list_contains(list, model.items[k].key, &found) && found); + CHECK(adds > 10000 && removes > 5000 && changes > 1000 && undone > 1000 && tables >= 2 && clears >= 10); + if (copy) pure_list_free(copy); + pure_list_free(list); + for (unsigned o = 0; o < OTHERS; ++o) pure_list_free(others[o]); + pure_retired_free(&retired); + pure_undo_free(&undo); + free(model.items); + free(shared.items); + printf("{\"key_sets\":{\"adds\":%zu,\"removes\":%zu,\"changes\":%zu,\"undone\":%zu,\"tables\":%zu,\"clears\":%zu,\"shares\":%zu}}\n", + adds, removes, changes, undone, tables, clears, shares); +} + +/* A stored keyed list adds by key too (an append to it, as an event's): + * what it journals after the items stored whole makes the list again, with + * adds of keys it has (no record), adds undone (their records forgotten), + * removes and key changes among them. */ +static void keyed_journal(void) { + static const uint8_t fields[2] = {PURE_CELL_NUMBER, PURE_CELL_TEXT}; + uint32_t seed = 0x6a6f7572u; + PureList *list = pure_list_new(2, fields); + CHECK(list && pure_list_keyed(list, 0) == PURE_OK); + pure_list_journal(list, true); + Grown stored = {0}; + size_t stored_items = 0, adds = 0, had = 0, undone = 0, restarts = 0; + PureUndo undo = {0}; + Model model = {0}, before = {0}; + for (unsigned event = 0; event < 3000; ++event) { + size_t mark = undo.count, journal = pure_list_changes(list).size; + model_copy(&before, &model); + for (unsigned change = 1 + (unsigned)(next_random(&seed) % 12); change--;) { + unsigned roll = (unsigned)(next_random(&seed) % 100); + if (roll < 60 || !model.count) { + ModelItem item = {(double)(next_random(&seed) % 20000) / 2 - 2000, "", next_random(&seed) % 11}; + for (size_t k = 0; k < item.size; ++k) item.text[k] = (char)('a' + next_random(&seed) % 26); + PureCell cells[2] = {{.num = item.key}, {.text = (unsigned char *)item.text, .size = item.size}}; + size_t at; + bool exists; + CHECK(pure_list_add(list, cells, &undo, &at, &exists) == PURE_OK); + CHECK(at == model_lower(&model, item.key) && exists == model_has(&model, item.key)); + if (exists) ++had; + else model_insert(&model, at, item), ++adds; + } else if (roll < 85) { + size_t at = next_random(&seed) % model.count; + CHECK(pure_list_remove(list, at, &undo) == PURE_OK); + memmove(model.items + at, model.items + at + 1, (model.count - at - 1) * sizeof(*model.items)); + --model.count; + } else { /* a key changed to one between its neighbours */ + size_t at = next_random(&seed) % model.count; + double low = at ? model.items[at - 1].key : model.items[at].key - 1, + high = at + 1 < model.count ? model.items[at + 1].key : model.items[at].key + 1; + double to = low + (high - low) / 2; + if (to > low && to < high) { + CHECK(pure_list_set(list, at, 0, (PureCell){.num = to}, &undo) == PURE_OK); + model.items[at].key = to; + } + } + } + if (next_random(&seed) % 5 == 0) { /* undone: the list and its journal as before */ + pure_undo_rollback(&undo, mark); + pure_list_forget(list, journal); + model_copy(&model, &before); + ++undone; + } else + pure_undo_commit(&undo); + if (event % 3 == 0) { /* a save: its records after the stored ones, or now and then the items whole */ + if (event % 120 == 0) { + stored.size = 0; + Grown whole = {malloc(pure_list_size(list) + 1), 0, 0}; + CHECK(whole.bytes); + pure_list_encode(list, whole.bytes); + collect_bytes(&stored, (PureSpan){whole.bytes, pure_list_size(list)}); + free(whole.bytes); + stored_items = pure_list_size(list); + } else + collect_bytes(&stored, pure_list_changes(list)); + pure_list_forget(list, 0); + if (event % 17 == 0) { /* what a restart finds is the list as it is */ + PureList *restarted = stored_list(&stored, stored_items); + CHECK(restarted && same_items(restarted, &model)); + pure_list_free(restarted); + ++restarts; + } + } + } + CHECK(same_items(list, &model) && adds > 5000 && had > 500 && undone > 400 && restarts > 40); + pure_list_free(list); + pure_undo_free(&undo); + free(stored.bytes); + free(model.items); + free(before.items); + printf("{\"keyed_journal\":{\"adds\":%zu,\"had\":%zu,\"undone\":%zu,\"restarts\":%zu}}\n", adds, had, undone, restarts); +} + static void list_trees(void) { static const uint8_t text_fields[2] = {0, 1}; uint32_t seed = 0x5eed1234u; @@ -5573,6 +5848,8 @@ int main(void) { lists(); retired_come_back(); list_trees(); + key_sets(); + keyed_journal(); folds(); filters(); lane_folds(); @@ -5601,6 +5878,6 @@ int main(void) { stored_states(); deferred(); printf("{\"sizeof_module\":%zu,\"sizeof_app\":%zu}\n", sizeof(PureModule), sizeof(PureApp)); - puts("{\"module_tests\":\"verified-load-atomic-events-faults-signed-zero-if-else-bools-replace-by-name-rejections-mutations-messages-documents-typed-verification-text-cursors-utf8-views-rollback-replace-lists-indices-undo-migration-joins-tables-columns-pick-slide-stored-equivalence-crashes-frames-messages-migration-deferred-bursts-pointing-marks-folds-filters-keyed-lists-text-order-message-fields-timers-now-snapshots-links\"}"); + puts("{\"module_tests\":\"verified-load-atomic-events-faults-signed-zero-if-else-bools-replace-by-name-rejections-mutations-messages-documents-typed-verification-text-cursors-utf8-views-rollback-replace-lists-indices-undo-migration-joins-tables-columns-pick-slide-stored-equivalence-crashes-frames-messages-migration-deferred-bursts-pointing-marks-folds-filters-keyed-lists-key-sets-text-order-message-fields-timers-now-snapshots-links\"}"); return 0; } diff --git a/docs/design/020-computing-faster.md b/docs/design/020-computing-faster.md index b839e83..35cc071 100644 --- a/docs/design/020-computing-faster.md +++ b/docs/design/020-computing-faster.md @@ -1,6 +1,6 @@ # 020 — 계산을 빠르게, 긴 보기를 연결 스레드 밖에서 -작성일: 2026-10-04. 상태: 설계와 착수 기준(구현 전). +작성일: 2026-10-04. 상태: 설계와 착수 기준. 1단계 구현(아래 "1단계에서 달라진 것"), 검사로 고정했다. [018](018-lifetimes-and-computation.md)이 계산을 들였지만 그 값이 컸다: BFS(노드 10만, 간선 100만) 한 이벤트가 396 ms로 CPython과 비슷하고 C의 44배였다([118](../research/118-computing-in-one-event.md)). 계산하는 보기는 연결 스레드에서 돌아 그동안 그 스레드의 다른 연결을 기다리게 했다([119](../research/119-views-that-compute.md)). @@ -50,6 +50,23 @@ - 본문이 없는 보기(식 하나)는 지금처럼 연결 스레드가 계산한다(가장 흔하고 짧은 길을 그대로 둔다). - 넘긴 일이 `--queue`만큼 쌓이면 503 `busy`다. +### 1단계에서 달라진 것 + +재면서 만들었고, 잰 것이 모양을 바꿨다(코어만의 BFS, 중앙값). + +- **소속 표는 비트와 표 둘이다.** 키가 2^22 아래의 0 이상 정수인 동안은 비트(노드 번호 10만이면 12.5 KB, 캐시에 든다)이고, 그 밖의 + 키가 처음 오면 열린 주소의 표(선형 탐사, 반 넘게 차지 않게, 지우면 뒤를 당긴다)로 바뀐다. 표만으로는 286 ms였고 비트로 207 ms다. + 비우면 64 KiB까지의 비트는 지우고 남긴다(다음 이벤트가 다시 쓴다). `-0`과 `+0`은 한 키다. +- **키로 넣기는 한 번 내려간다**(`pure_list_add`). 찾고 나서 넣으면 두 번이다. 저장되는 키 있는 리스트의 덧붙이기도 이 길로 가고, + 기록과 되돌리기는 `pure_list_insert`의 것과 같다. +- **손가락은 스레드마다 넷이다**(리스트 하나가 아니라: 걷기와 큐와 `seen`이 번갈아 읽는다). 리스트의 번호와 판이 맞을 때만 쓴다. + 스냅숏의 사본은 리스트와 번호가 같고 판이 다르다. 키로 찾기도 손가락의 잎에서 먼저 본다. +- 설계에 없던 넷: 항목의 필드가 text인지를 로드할 때 명령에 적기(실행할 때마다 찾지 않게), 각 단에서 자식 찾기를 이분 탐색이 + 아니라 세기로(가지 32개를 모두 비교해 센다, 벡터가 된다), 실행기의 루프를 재귀 없이(루프 기록의 스택), `module-list.c`를 + `-O3`로(`Makefile`의 `LIST_OPTIMIZE`). 넷의 몫은 204 ms에서 186 ms이고 거의 다 `-O3`다. +- 해 보고 뺀 것: 잎의 울타리(키로 찾은 잎의 다음 잎의 첫 키, 손가락이 키 범위를 더 넓게 알게) — 185.5 대 185.5 ms. 손가락의 + 앞으로 옮기기는 남겼지만 차이는 재지 못했다(206 대 204 ms). + ## 단계 1. 키로 찾기(소속 표, 손가락). |