From 83c3f20a005086a9433ddd772c884c65b07b7187 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 5 Oct 2026 09:52:54 +0100 Subject: Pack a stored keyed list searched often into arrays and a bucket index fitted to the keys searched, between events, and build trees from the leaves up: BFS core 89 to 55 ms (022) --- core/module-list.c | 318 +++++++++++++++++++++++++++++++++++++++++++++++------ core/module-list.h | 12 ++ core/module.c | 9 +- core/test-module.c | 241 ++++++++++++++++++++++++++++++++++++++++ 4 files changed, 546 insertions(+), 34 deletions(-) diff --git a/core/module-list.c b/core/module-list.c index b3a9ed3..3d4404f 100644 --- a/core/module-list.c +++ b/core/module-list.c @@ -95,6 +95,15 @@ struct PureList { void *columns[16]; /* each field's cells */ size_t room; /* the rows the columns hold: FLAT items, DENSE keys */ size_t moved; /* FLAT: items moved by changes inside it since it was cleared */ + /* A stored list keyed by a number and searched by key often at one + * version is packed when an event ends (pure_list_settle, docs/design + * 022): FLAT, its columns a Pack's, which its copies share and nothing + * changes (a change makes the list a tree again first). searched counts + * its searches by key at searched_version; aligned is the fewest + * trailing zero bits of a whole key searched then (64: none). */ + struct Pack *pack; + uint64_t searched, searched_version; + uint8_t aligned; }; /* The log of an event's changes: a removed item's cells wait in the log's @@ -761,6 +770,104 @@ enum { TREE, FLAT, DENSE }; * than a tree would); the items a FLAT list moves freely. */ enum { ARRAYS_KEPT = 1 << 22, ARRAYS_LARGE = 1 << 26, DENSE_SLACK = 1 << 21, FLAT_SMALL = 64 }; +/* A packed list's arrays (docs/design/022): each field's cells in order and, + * keyed by a number, a bucket index: the keys' range cut into buckets a + * power of two wide (their starts multiples of it), each bucket's first + * position whose key is not below its start. A search for a key at a + * bucket's start reads that one cell; another steps through its bucket's + * keys. Never changed; freed with its last list. */ +typedef struct Pack { + unsigned refs; /* the list and its copies */ + void *columns[16]; + double low, high; /* the first key and the last */ + double origin, width, scale; /* the first bucket's start, a bucket's width, 1 / width */ + size_t buckets; /* 0: none (searched by halves) */ + uint32_t *first; /* by bucket, and the end past the last */ +} Pack; + +/* Searched by key at least an eighth of its items' times at one version, a + * list of PACK_ITEMS or more is packed; about PACK_BUCKET items a bucket. */ +enum { PACK_ITEMS = 4096, PACK_SEARCHES = 8, PACK_BUCKET = 8 }; + +static void pack_release(Pack *pack) { + if (!pack || __atomic_sub_fetch(&pack->refs, 1, __ATOMIC_ACQ_REL)) return; + for (unsigned f = 0; f < 16; ++f) free(pack->columns[f]); + free(pack->first); + free(pack); +} + +/* The bucket holding key (the first or the last past them), and its start: + * computed again from the bucket, which is exact (pack_index), so a + * rounding of the division moves it one bucket at most. */ +static size_t bucket_of(const Pack *pack, double key, double *start) { + double at = (key - pack->origin) * pack->scale; + size_t b = !(at > 0) ? 0 : at >= (double)(pack->buckets - 1) ? pack->buckets - 1 : (size_t)at; + double begins = pack->origin + (double)b * pack->width; + if (begins > key && b) begins = pack->origin + (double)--b * pack->width; + else if (b + 1 < pack->buckets && pack->origin + (double)(b + 1) * pack->width <= key) + begins = pack->origin + (double)++b * pack->width; + *start = begins; + return b; +} + +/* The index of keys (n, ascending, finite): buckets about PACK_BUCKET items + * wide, or narrower to start at every key searched (aligned: their fewest + * trailing zero bits), never finer than the keys' own precision (so every + * start is exact) nor more of them than items. False without memory; none + * (buckets 0) when the keys span too far. */ +static bool pack_index(Pack *pack, const double *keys, size_t n, unsigned aligned) { + double low = keys[0], high = keys[n - 1], span = high - low; + pack->low = low, pack->high = high, pack->buckets = 0; + if (!isfinite(span)) return true; + int exponent = 0, top; + if (span > 0) (void)frexp(span / (double)(n / PACK_BUCKET + 1), &exponent); /* 2^exponent above span per bucket */ + if ((int)aligned < exponent) exponent = (int)aligned; + (void)frexp(fabs(low) > fabs(high) ? low : high, &top); + if (exponent < top - 53) exponent = top - 53; /* the keys' last bit */ + double width, origin, buckets; + for (;; ++exponent) { + width = ldexp(1.0, exponent), origin = floor(low / width) * width; + buckets = floor((high - origin) / width) + 1; + if (buckets <= (double)n) break; + } + pack->origin = origin, pack->width = width, pack->scale = 1 / width, pack->buckets = (size_t)buckets; + if (!(pack->first = malloc((pack->buckets + 1) * sizeof(*pack->first)))) return false; + size_t filled = 0; + for (size_t i = 0; i < n; ++i) { + double start; + size_t b = bucket_of(pack, keys[i], &start); + while (filled <= b) pack->first[filled++] = (uint32_t)i; + } + while (filled <= pack->buckets) pack->first[filled++] = (uint32_t)n; + return true; +} + +/* The first position whose key is not below key, in a packed list. */ +static size_t pack_seek(const PureList *list, double key) { + const Pack *pack = list->pack; + const double *keys = list->columns[list->layout.key]; + if (!pack->buckets) return lower(keys, (unsigned)list->count, key); + if (!(key > pack->low)) return 0; + if (key > pack->high) return list->count; + double start; + size_t b = bucket_of(pack, key, &start), at = pack->first[b]; + if (start == key) return at; + for (size_t end = pack->first[b + 1]; at < end && keys[at] < key;) ++at; + return at; +} + +/* A search of a stored tree by its key, counted for packing it. */ +static void searched_by(const PureList *list, double key) { + PureList *kept = (PureList *)list; /* what it counts to choose its form, not what it holds */ + if (kept->searched_version != list->version || !kept->searched) + kept->searched_version = list->version, kept->searched = 0, kept->aligned = 64; + ++kept->searched; + double whole = fabs(key); + if (whole == 0) return; + unsigned zeros = whole < 9007199254740992.0 && whole == floor(whole) ? (unsigned)__builtin_ctzll((uint64_t)whole) : 0; + if (zeros < kept->aligned) kept->aligned = (uint8_t)zeros; +} + static size_t width(const Layout *l, unsigned f) { return pure_cell_text(l->kinds[f]) ? sizeof(PureSpan) : 8; } static size_t row_width(const Layout *l) { @@ -810,7 +917,12 @@ static bool arrays_room(PureList *list, size_t room) { } static void arrays_free(PureList *list) { - for (unsigned f = 0; f < 16; ++f) free(list->columns[f]), list->columns[f] = NULL; + if (list->pack) { /* a packed list's are its pack's */ + pack_release(list->pack); + list->pack = NULL; + memset(list->columns, 0, sizeof(list->columns)); + } else + for (unsigned f = 0; f < 16; ++f) free(list->columns[f]), list->columns[f] = NULL; list->room = 0; } @@ -911,28 +1023,110 @@ static void free_nodes(Node *node) { free(node); } -/* A FLAT or DENSE list as a tree, its items placed in order (a tree that - * grows at its end fills its leaves); false without memory (it is as it was). */ -static bool make_tree(PureList *list) { - if (list->form == TREE) return true; - if (list->form == DENSE && !make_flat(list)) return false; - size_t count = list->count; - list->form = TREE; - list->count = 0; +/* A FLAT list's items as a tree's root, built from the leaves up with full + * leaves and full inner nodes (as a tree filled at its end has them); false + * without memory (none made). */ +static bool build_tree(PureList *list, Node **root) { + const Layout *l = &list->layout; + size_t n = list->count, count = (n + FANOUT - 1) / FANOUT; + *root = NULL; + if (!n) return true; + Node **level = malloc(count * sizeof(*level)); + if (!level) return false; for (size_t i = 0; i < count; ++i) { - PureCell cells[16]; - for (unsigned f = 0; f < list->layout.fields; ++f) cells[f] = array_cell(list, i, f); - Place p; - if (!prepare(list, list->count, &p)) { - free_nodes(list->root); - list->root = NULL; - list->count = count; - list->form = FLAT; + Node *leaf = new_node(list, true); + if (!leaf) { + while (i) free(level[--i]); + free(level); return false; } - place(list, &p, cells); + unsigned items = (unsigned)(n - i * FANOUT < FANOUT ? n - i * FANOUT : FANOUT); + for (unsigned f = 0; f < l->fields; ++f) + memcpy((char *)leaf + l->column[f], (const char *)list->columns[f] + i * FANOUT * width(l, f), items * width(l, f)); + leaf->count = items; + sum(list, leaf); + level[i] = leaf; + } + while (count > 1) { + size_t above = (count + FANOUT - 1) / FANOUT; + for (size_t i = 0; i < above; ++i) { + Node *node = new_node(list, false); + if (!node) { /* the nodes made above, and those not yet under one */ + for (size_t j = 0; j < i; ++j) free_nodes(level[j]); + for (size_t j = i * FANOUT; j < count; ++j) free_nodes(level[j]); + free(level); + return false; + } + unsigned children = (unsigned)(count - i * FANOUT < FANOUT ? count - i * FANOUT : FANOUT); + memcpy(node->child, level + i * FANOUT, children * sizeof(*level)); + node->count = children; + sum(list, node); + level[i] = node; /* i is below i * FANOUT, read already */ + } + count = above; } + *root = level[0]; + free(level); + return true; +} + +/* A FLAT or DENSE list as a tree (a packed one's pack let go); false + * without memory (it is as it was). Its version moves: what was read of its + * arrays (a finger, a run) is not read again. */ +static bool make_tree(PureList *list) { + if (list->form == TREE) return true; + if (list->form == DENSE && !make_flat(list)) return false; + Node *root; + if (!build_tree(list, &root)) return false; arrays_free(list); + list->root = root; + list->form = TREE; + ++list->version; + return true; +} + +static bool visit_leaves(const Node *node, bool (*visit)(void *, const Node *), void *context); + +typedef struct { const Layout *layout; void *const *columns; size_t at; } Packing; + +static bool pack_leaf(void *context, const Node *leaf) { + Packing *p = context; + const Layout *l = p->layout; + for (unsigned f = 0; f < l->fields; ++f) + memcpy((char *)p->columns[f] + p->at * width(l, f), (const char *)leaf + l->column[f], leaf->count * width(l, f)); + p->at += leaf->count; + return true; +} + +static void let_go_nodes(PureList *list, Node *node); + +/* A stored tree as a packed list (its texts kept, its nodes let go); false + * without memory (it is as it was). */ +static bool pack(PureList *list) { + const Layout *l = &list->layout; + size_t n = list->count; + Pack *made = calloc(1, sizeof(*made)); + bool ok = made != NULL; + for (unsigned f = 0; ok && f < l->fields; ++f) ok = (made->columns[f] = malloc(n * width(l, f))) != NULL; + if (ok) { + Packing packing = {l, made->columns, 0}; + visit_leaves(list->root, pack_leaf, &packing); + ok = l->key < 0 || pack_index(made, made->columns[l->key], n, list->aligned); + } + if (!ok) { + if (made) made->refs = 1; + pack_release(made); + return false; + } + made->refs = 1; + let_go_nodes(list, list->root); + list->root = NULL; + list->pack = made; + memcpy(list->columns, made->columns, sizeof(list->columns)); + list->room = n; + list->form = FLAT; + list->moved = 0; + ++list->version; return true; } @@ -990,9 +1184,10 @@ static bool positioned(PureList *list) { return make_flat(list); } -/* The list as a tree, for a change logged to be undone or recorded. */ +/* The list as a tree, for a change logged to be undone or recorded, or to a + * packed list (whose arrays never change). */ static bool logged(PureList *list, const PureUndo *undo) { - return list->form == TREE || (!undo && !list->journaled) || make_tree(list); + return list->form == TREE || (!undo && !list->journaled && !list->pack) || make_tree(list); } /* ---- The list */ @@ -1040,6 +1235,15 @@ PureResult pure_list_keyed(PureList *list, int field) { return PURE_OK; } +/* Every node below node let go (retired where a copy may read it), not its + * texts: the list packed keeps them. */ +static void let_go_nodes(PureList *list, Node *node) { + if (!node) return; + for (unsigned i = 0; !node->leaf && i < node->count; ++i) let_go_nodes(list, child(node, i)); + if (shared_node(list, node)) retire(list, node, false); + else free(node); +} + /* Every node and text below node let go (retired where a copy may read them). */ static void let_go_tree(PureList *list, Node *node) { if (!node) return; @@ -1052,12 +1256,21 @@ static void let_go_tree(PureList *list, Node *node) { else free(node); } +/* A packed list's texts let go (retired where a copy may read them). */ +static void let_go_packed(PureList *list) { + const Layout *l = &list->layout; + for (size_t i = 0; l->texts && i < list->count; ++i) + for (unsigned t = 0; t < l->texts; ++t) let_go_text(list, array_cell(list, i, l->text_field[t]).text); +} + void pure_list_free(PureList *list) { if (!list) return; if (list->copy) { if (__atomic_sub_fetch(&list->refs, 1, __ATOMIC_ACQ_REL)) return; + pack_release(list->pack); } else { - if (list->form != TREE) let_go_rows(list); + if (list->pack) let_go_packed(list); + else if (list->form != TREE) let_go_rows(list); arrays_free(list); free(list->journal); free(list->members); @@ -1073,7 +1286,8 @@ void pure_list_free(PureList *list) { void pure_list_clear(PureList *list) { bool had = list->count != 0; if (had) { - if (list->form != TREE) let_go_rows(list); + if (list->pack) let_go_packed(list), arrays_free(list), list->form = TREE; + else if (list->form != TREE) let_go_rows(list); let_go_tree(list, list->root); list->root = NULL; list->count = list->bytes = 0; @@ -1125,8 +1339,8 @@ bool pure_list_contains(const PureList *list, double key, bool *found) { size_t pure_list_extra(const PureList *list) { return list->member_capacity * sizeof(*list->members); } bool pure_list_arrays(PureList *list) { - if (list->form != TREE || list->arrays) return true; - if (list->copy || list->journaled || list->count) return false; + if (list->arrays) return true; + if (list->form != TREE || list->copy || list->journaled || list->count) return false; list->arrays = true; list->form = FLAT; return true; @@ -1134,6 +1348,15 @@ bool pure_list_arrays(PureList *list) { unsigned pure_list_form(const PureList *list) { return list->form; } +bool pure_list_settle(PureList *list) { + if (list->pack || list->copy || list->arrays || list->form != TREE || list->layout.key < 0 || list->count < PACK_ITEMS || + list->searched_version != list->version || list->searched < list->count / PACK_SEARCHES) + return false; + return pack(list); +} + +bool pure_list_packed(const PureList *list) { return list->pack != NULL; } + const size_t pure_list_layout[] = { [LIST_COUNT_AT] = offsetof(PureList, count), [LIST_MEMBERS_AT] = offsetof(PureList, members), [LIST_MEMBER_CAPACITY_AT] = offsetof(PureList, member_capacity), [LIST_BITMAP_AT] = offsetof(PureList, bitmap), @@ -1155,12 +1378,17 @@ bool pure_list_lookup(const PureList *list, unsigned key_field, PureCell key, un size_t pure_list_count(const PureList *list) { return list->count; } PureList *pure_list_share(PureList *list, PureRetired *retired, uint64_t epoch) { - /* A copy reads a tree; an empty list (an event's, between events) stays as it is. */ - if (list->count && !make_tree(list)) return NULL; + /* A copy reads a tree or a pack; an empty list (an event's, between events) stays as it is. */ + if (list->count && !list->pack && !make_tree(list)) return NULL; PureList *copy = malloc(sizeof(*copy)); if (!copy) return NULL; *copy = (PureList){.layout = list->layout, .root = list->root, .count = list->count, .bytes = list->bytes, .id = list->id, .version = list->version, .refs = 1, .copy = true}; + if (list->pack) { + __atomic_add_fetch(&list->pack->refs, 1, __ATOMIC_RELAXED); + copy->pack = list->pack, copy->form = FLAT, copy->room = list->count; + memcpy(copy->columns, list->columns, sizeof(copy->columns)); + } list->retired = retired; list->shares = epoch > list->shares ? epoch : list->shares + 1; return copy; @@ -1405,14 +1633,18 @@ static bool encode_leaf(void *context, const Node *leaf) { size_t pure_list_size(const PureList *list) { return list->bytes; } /* An event's list is never stored, shared or sorted: one that was is made a - * tree first (memory for it or none: the process stops rather than lose items). */ + * tree first (memory for it or none: the process stops rather than lose + * items). A packed list is read as it is. */ static void tree_now(const PureList *list) { - if (list->form != TREE && !make_tree((PureList *)list)) abort(); + if (list->form != TREE && !list->pack && !make_tree((PureList *)list)) abort(); } void pure_list_encode(const PureList *list, unsigned char *out) { tree_now(list); - Encoding encoding = {&list->layout, out}; + const Layout *l = &list->layout; + for (size_t i = 0; list->pack && i < list->count; ++i) + for (unsigned f = 0; f < l->fields; ++f) out = encode_cell(l, f, array_cell(list, i, f), out); + Encoding encoding = {l, out}; visit_leaves(list->root, encode_leaf, &encoding); } @@ -1422,6 +1654,22 @@ size_t pure_list_encode_part(const PureList *list, size_t *at, unsigned char *ou PureRun run; size_t used = 0; *needed = 0; + if (list->pack) { + for (; *at < list->count; ++*at) { + PureCell cells[16]; + size_t size = l->number_bytes; + for (unsigned f = 0; f < l->fields; ++f) cells[f] = array_cell(list, *at, f); + for (unsigned t = 0; t < l->texts; ++t) size += 4 + cells[l->text_field[t]].size; + if (size > capacity - used) { + if (!used) *needed = size; + return used; + } + unsigned char *end = out + used; + for (unsigned f = 0; f < l->fields; ++f) end = encode_cell(l, f, cells[f], end); + used += size; + } + return used; + } if (!pure_list_run(list, *at, &run)) return 0; do { const Node *leaf = run.path[run.depth]; @@ -1881,7 +2129,7 @@ size_t pure_list_seek(const PureList *list, unsigned field, PureCell key, bool * } if (list->form == FLAT) { size_t low = 0, high = list->count; - if ((int)field == l->key) low = lower(list->columns[field], (unsigned)list->count, key.num); + if ((int)field == l->key) low = list->pack ? pack_seek(list, key.num) : lower(list->columns[field], (unsigned)list->count, key.num); else while (low < high) { size_t middle = low + (high - low) / 2; @@ -1895,6 +2143,7 @@ size_t pure_list_seek(const PureList *list, unsigned field, PureCell key, bool * size_t start = 0; if (!node) return 0; if ((int)field == l->key) { + if (!list->copy && !list->arrays) searched_by(list, key.num); /* The finger's leaf, when its keys reach round key, holds its place * (a slice's high bound is near its low one, found just before). */ if (finger.leaf && finger.id == list->id && finger.version == list->version && finger.leaf->count) { @@ -1942,6 +2191,12 @@ size_t pure_list_seek(const PureList *list, unsigned field, PureCell key, bool * return start + low; } +size_t pure_list_bound(const PureList *list, unsigned field, PureCell key) { + if (list->pack && (int)field == list->layout.key && list->count) return pack_seek(list, key.num); + bool found; + return pure_list_seek(list, field, key, &found); +} + /* An item where it is: its leaf and its place there. */ typedef struct { const Node *leaf; unsigned index; } Ref; @@ -1970,7 +2225,7 @@ static bool gather_leaf(void *context, const Node *leaf) { } PURE_COLD PureResult pure_list_sorted(const PureList *list, unsigned field, PureList **out, size_t *moved) { - tree_now(list); + if (list->form != TREE && !make_tree((PureList *)list)) abort(); /* the app's own, its module changing */ const Layout *l = &list->layout; *out = NULL; Gathered gathered = {list->count ? malloc(list->count * sizeof(Ref)) : NULL, 0}; @@ -2024,6 +2279,7 @@ void pure_undo_rollback(PureUndo *undo, size_t mark) { const Layout *l = &list->layout; Step path[DEPTH]; unsigned within, depth; + if (list->form != TREE && !make_tree(list)) abort(); /* packed since: the changes were a tree's */ if (e->change == REMOVED) { Place p; if (!prepare(list, e->at, &p)) abort(); diff --git a/core/module-list.h b/core/module-list.h index 6251786..0d4d7dc 100644 --- a/core/module-list.h +++ b/core/module-list.h @@ -123,6 +123,18 @@ bool pure_list_next(const PureList *, PureRun *); * field does not order below key (numbers and integers by value, texts by * bytes), and whether that item's field is key. */ size_t pure_list_seek(const PureList *, unsigned field, PureCell key, bool *found); +/* The first position whose item's field does not order below key, as + * pure_list_seek's but without whether it is key (a slice's bound: a packed + * list then reads its index alone). */ +size_t pure_list_bound(const PureList *, unsigned field, PureCell key); +/* A stored list keyed by a number and searched by key at least an eighth of + * its items' times since it last changed (4,096 items or more) is packed + * (docs/design/022): its items in arrays, each field's in order, with an + * index of its keys in buckets, which its copies share; a change makes it a + * tree again first. Answers are the tree's. Called between events (no run of + * the list is open): true when it packed the list. */ +bool pure_list_settle(PureList *); +bool pure_list_packed(const PureList *); /* The field a keyed list keeps its items in order of: when it is a number * 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. */ diff --git a/core/module.c b/core/module.c index 8771cab..a01a411 100644 --- a/core/module.c +++ b/core/module.c @@ -2172,9 +2172,8 @@ static PureResult fold_runs(const PureModule *m, PureValue *values, PureBlock in /* The positions of the items whose keys are from low up to before high. */ /* The items whose keys are from low up to before high (numbers or i64s, as the key is). */ static void slice_of(const PureList *list, unsigned key, Slot low, Slot high, size_t *from, size_t *to) { - bool found; - *from = pure_list_seek(list, key, (PureCell){.i64 = low.i64}, &found); - *to = pure_list_seek(list, key, (PureCell){.i64 = high.i64}, &found); + *from = pure_list_bound(list, key, (PureCell){.i64 = low.i64}); + *to = pure_list_bound(list, key, (PureCell){.i64 = high.i64}); if (*to < *from) *to = *from; } @@ -3518,6 +3517,10 @@ static PureResult dispatch(PureApp *app, uint32_t event, Event *ev) { return result; } clear_rows(app); + /* No run of a list is open between events: one searched often since it + * last changed is packed now (docs/design/022). */ + for (uint32_t i = 0; i < m->states; ++i) + if (app->lists[i]) (void)pure_list_settle(app->lists[i]); memcpy(app->values, pending, sizeof(pending)); ++app->events; ++app->changes; diff --git a/core/test-module.c b/core/test-module.c index b7fea70..2ccdabb 100644 --- a/core/test-module.c +++ b/core/test-module.c @@ -1506,6 +1506,246 @@ static void arrays_equivalence(void) { forms[2], conversions); } +/* The first position in a model (in key order) whose key is not below key. */ +static size_t model_bound(const Model *m, double key) { + size_t low = 0, high = m->count; + while (low < high) { + size_t middle = low + (high - low) / 2; + if (m->items[middle].key < key) low = middle + 1; + else high = middle; + } + return low; +} + +/* The stored form of a list a part at a time, against it whole. */ +static bool encoded_in_parts(const PureList *list, size_t capacity) { + size_t size = pure_list_size(list), at = 0, used = 0, needed; + unsigned char *whole = malloc(size + 1), *parts = malloc(size + 1), *buffer = malloc(capacity); + CHECK(whole && parts && buffer); + pure_list_encode(list, whole); + for (;;) { + size_t got = pure_list_encode_part(list, &at, buffer, capacity, &needed); + if (!got) { + if (!needed) break; + unsigned char *grown = realloc(buffer, needed); + CHECK(grown); + buffer = grown, capacity = needed; + continue; + } + CHECK(used + got <= size); + memcpy(parts + used, buffer, got); + used += got; + } + bool same = used == size && at == pure_list_count(list) && (!size || !memcmp(whole, parts, size)); + free(whole), free(parts), free(buffer); + return same; +} + +/* A stored keyed list packed between events once searched often (docs/design + * 022): at every step its answers are a model's, through searches by key at + * a bucket's start and between, its changes (a tree again), their undoing + * (also of changes made before it was packed), its journal and stored form, + * a restart from them, and its copies, which share its pack and outlive its + * changes. Then packs of keys at the edges of the index: fractions, near + * 2^53, negative, and a span too wide for buckets. */ +static void packed_lists(void) { + static const uint8_t fields[2] = {PURE_CELL_NUMBER, PURE_CELL_TEXT}; + uint32_t seed = 0x7061636bu; + PureList *list = pure_list_new(2, fields); + CHECK(list && pure_list_keyed(list, 0) == PURE_OK && pure_list_hashed(list)); + pure_list_journal(list, true); + PureUndo undo = {0}; + Model model = {0}, before = {0}; + Grown stored = {0}; + size_t stored_items = 0; + enum { SHARES = 4 }; + PureList *copies[SHARES]; + Model shared[SHARES] = {{0}}; + PureRetired retired[SHARES] = {{0}}; + unsigned first = 0, held = 0, open = 0; + uint64_t epoch = 0; + size_t packs = 0, unpacked = 0, searches = 0, packed_searches = 0, undone_packed = 0, mark = 0, journal = 0; + for (unsigned event = 0; event < 3000; ++event) { + if (!open) mark = undo.count, journal = pure_list_changes(list).size, model_copy(&before, &model); + bool was_packed = pure_list_packed(list); + /* Grow to some thousands, searched at times in bursts (packing it), changed at others. */ + unsigned changes = event < 300 ? 60 : next_random(&seed) % 4 ? 0 : 1 + next_random(&seed) % 6; + for (unsigned c = 0; c < changes; ++c) { + uint32_t r = next_random(&seed); + unsigned roll = r % 100; + if (roll < 60 || model.count < 100) { + ModelItem item = {(double)(next_random(&seed) % 700) * 1024 + next_random(&seed) % 1000, "", r % 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); + size_t want = model_bound(&model, item.key); + CHECK(at == want && exists == (want < model.count && model.items[want].key == item.key)); + if (!exists) model_insert(&model, at, item); + } else if (roll < 80) { + 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 { + size_t at = next_random(&seed) % model.count; + ModelItem *item = &model.items[at]; + if (r % 3 == 0 && at + 1 < model.count && item[1].key - item[0].key > 1) { /* its key, between its neighbours */ + double key = item[0].key + 1; + CHECK(pure_list_set(list, at, 0, (PureCell){.num = key}, &undo) == PURE_OK); + item->key = key; + } else { + item->size = next_random(&seed) % 11; + for (size_t k = 0; k < item->size; ++k) item->text[k] = (char)('A' + next_random(&seed) % 26); + CHECK(pure_list_set(list, at, 1, (PureCell){.text = (unsigned char *)item->text, .size = item->size}, &undo) == + PURE_OK); + } + } + } + unpacked += was_packed && !pure_list_packed(list); + /* Searches: a node's slice bounds (at a bucket's start once packed), a key between, by halves of keys, a field by key. */ + unsigned burst = event % 9 == 4 ? 1500 + next_random(&seed) % 1500 : next_random(&seed) % 40; + for (unsigned k = 0; k < burst && model.count; ++k, ++searches) { + uint32_t r = next_random(&seed); + double key = r % 4 == 0 ? (double)(r % 720) * 1024 + : r % 4 == 1 ? model.items[r % model.count].key + : r % 4 == 2 ? (double)(next_random(&seed) % 740000) - 10000 + : (double)(next_random(&seed) % 2900000) / 4; + size_t want = model_bound(&model, key); + bool found, want_found = want < model.count && model.items[want].key == key; + packed_searches += pure_list_packed(list); + CHECK(pure_list_bound(list, 0, (PureCell){.num = key}) == want); + if (r % 3 == 0) CHECK(pure_list_seek(list, 0, (PureCell){.num = key}, &found) == want && found == want_found); + if (r % 5 == 0) { + PureCell text; + CHECK(pure_list_lookup(list, 0, (PureCell){.num = key}, 1, &text) == want_found); + if (want_found) CHECK(same_item(&model, want, key, (PureSpan){text.text, text.size})); + } + } + /* The event's end: kept, or undone (now and then with the one before it, packed between them). */ + if (open || next_random(&seed) % 8) { + if (!open && next_random(&seed) % 12 == 0) { + ++open; /* left open across one more event */ + } else if (next_random(&seed) % 6 == 0) { + undone_packed += pure_list_packed(list); + pure_undo_rollback(&undo, mark); + pure_list_forget(list, journal); + model_copy(&model, &before); + open = 0; + } else { + pure_undo_commit(&undo); + open = 0; + } + } else { + pure_undo_rollback(&undo, mark); + pure_list_forget(list, journal); + model_copy(&model, &before); + } + if (pure_list_settle(list)) ++packs; + if (event % 11 == 0) CHECK(same_items(list, &model)); + if (!open && event % 3 == 0) { /* a save: records, or now and then the items whole */ + if (event % 90 == 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 (!open && event % 3 == 0 && event % 51 == 0) { + PureList *restarted = stored_list(&stored, stored_items); + CHECK(restarted && same_items(restarted, &model)); + pure_list_free(restarted); + CHECK(stored_as(list, &model) && encoded_in_parts(list, 64 + next_random(&seed) % 4096)); + } + if (!open && event % 30 == 15) { /* a share, as a snapshot takes one */ + if (held == SHARES) { + CHECK(same_items(copies[first], &shared[first]) && stored_as(copies[first], &shared[first])); + CHECK(encoded_in_parts(copies[first], 100)); + pure_list_free(copies[first]); + pure_retired_reuse(&retired[first], &list, 1); + first = (first + 1) % SHARES; + --held; + } + unsigned slot = (first + held) % SHARES; + CHECK((copies[slot] = pure_list_share(list, &retired[slot], ++epoch))); + CHECK(pure_list_packed(copies[slot]) == pure_list_packed(list)); + model_copy(&shared[slot], &model); + ++held; + } + if (event % 25 == 0) + for (unsigned i = 0; i < held; ++i) { + const PureList *copy = copies[(first + i) % SHARES]; + const Model *m = &shared[(first + i) % SHARES]; + CHECK(same_items(copy, m)); + for (unsigned k = 0; k < 50 && m->count; ++k) { + double key = (double)(next_random(&seed) % 720) * 1024; + CHECK(pure_list_bound(copy, 0, (PureCell){.num = key}) == model_bound(m, key)); + } + } + } + CHECK(same_items(list, &model) && stored_as(list, &model)); + CHECK(packs > 20 && unpacked > 10 && packed_searches > 10000 && undone_packed > 0); + pure_list_free(list); /* first, as an app's: its copies read on what they share */ + for (; held; --held, first = (first + 1) % SHARES) { + CHECK(same_items(copies[first], &shared[first])); + pure_list_free(copies[first]); + pure_retired_free(&retired[first]); + } + pure_undo_free(&undo); + free(stored.bytes); + free(model.items); + free(before.items); + for (unsigned i = 0; i < SHARES; ++i) free(shared[i].items); + + /* The index's edges: each list packed, then searched as its tree (never packed) is. */ + static const uint8_t number[1] = {PURE_CELL_NUMBER}; + size_t indexed = 0; + for (unsigned kind = 0; kind < 5; ++kind) { + PureList *packed = pure_list_new(1, number), *tree = pure_list_new(1, number); + CHECK(packed && tree && pure_list_keyed(packed, 0) == PURE_OK && pure_list_keyed(tree, 0) == PURE_OK); + double keys[6000]; + size_t n = 0; + for (size_t i = 0; i < 6000; ++i) { + double key = kind == 0 ? (double)i * 0.25 - 700 /* fractions, negative and positive, -0 among them */ + : kind == 1 ? 9007199254740992.0 - 2 * (double)(6000 - i) * 2 /* near 2^53: the keys' last bits */ + : kind == 2 ? -1e300 + (double)i * 1e296 /* wide, negative */ + : kind == 3 ? (i % 2 ? 1e300 : -1e300) * (double)(i + 1) / 6000 /* too wide for buckets */ + : (double)(i / 7) * 65536 + (double)(i % 7) * 3; /* slices at multiples of 2^16 */ + if (kind == 0 && i == 2800) key = -0.0; + bool exists; + CHECK(pure_list_add(packed, (PureCell[]){{.num = key}}, NULL, NULL, &exists) == PURE_OK); + CHECK(pure_list_add(tree, (PureCell[]){{.num = key}}, NULL, NULL, &exists) == PURE_OK); + keys[n++] = key; + } + for (size_t i = 0; i < 1000; ++i) { /* searched enough, at the slices' starts for the last kind */ + bool found; + double key = kind == 4 ? (double)(next_random(&seed) % 900) * 65536 : keys[next_random(&seed) % n]; + (void)pure_list_seek(packed, 0, (PureCell){.num = key}, &found); + } + CHECK(pure_list_settle(packed) && pure_list_packed(packed)); + for (size_t i = 0; i < 20000; ++i) { + uint32_t r = next_random(&seed); + double a = keys[r % n], b = keys[(r / 7) % n]; + double key = r % 5 == 0 ? a : r % 5 == 1 ? a + (b - a) * 0.37 : r % 5 == 2 ? -a : r % 5 == 3 ? a * 1.0000001 + : kind == 4 ? (double)(r % 900) * 65536 : (r % 2 ? 1 : -1) * 1e308; + bool fp, ft; + size_t got = pure_list_seek(packed, 0, (PureCell){.num = key}, &fp), want = pure_list_seek(tree, 0, (PureCell){.num = key}, &ft); + CHECK(got == want && fp == ft && pure_list_bound(packed, 0, (PureCell){.num = key}) == want); + } + indexed += kind != 3; /* the too wide one has no buckets: searched by halves */ + pure_list_free(packed); + pure_list_free(tree); + } + printf("{\"packed\":{\"searches\":%zu,\"packed_searches\":%zu,\"packs\":%zu,\"unpacked\":%zu,\"undone_packed\":%zu,\"edges\":%zu}}\n", + searches, packed_searches, packs, unpacked, undone_packed, indexed); +} + static void list_trees(void) { static const uint8_t text_fields[2] = {0, 1}; uint32_t seed = 0x5eed1234u; @@ -5987,6 +6227,7 @@ int main(void) { key_sets(); keyed_journal(); arrays_equivalence(); + packed_lists(); folds(); filters(); lane_folds(); -- cgit v1.2.3