From 72f8e1ca1fba181eeed6d2643a21f05881272d83 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Sun, 27 Sep 2026 23:38:54 +0100 Subject: Keep a list's items in a persistent tree A list was one array of item pointers: an item's place in the stored form was found by adding up the sizes of every item before it, so each change and each appended row cost O(n); a snapshot copied a changed list's whole array at each save; and a list held at most 65,536 items. A bank of 30,000 accounts ran transfers at 299 us of CPU each, and set up in time growing with the square of its rows. Items now live in a B+tree of fanout 32 whose nodes know the items below them, their stored bytes and the first of them: positions, keys (keyed lists) and stored offsets are found in O(log n). Nodes carry the list's share count when made, as items do: one a snapshot may read never changes, so a change copies the path to it and retires the nodes it replaced, and a share is a root and a count. Reads in order go through a finger, each thread's last leaf. A list may hold 2^24 items. list_trees checks it against a model array: 6,000 events of inserts, removals and field changes, 1,195 of them undone, up to 8,983 items (three levels), the stored form equal byte for byte, four shares kept whole while the list changes on, and 13,959 keyed items found by key as a binary search finds them. The app model's tests pass under ASan and UBSan too. --- core/test-module.c | 210 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 210 insertions(+) (limited to 'core/test-module.c') diff --git a/core/test-module.c b/core/test-module.c index 307d565..e6df3ad 100644 --- a/core/test-module.c +++ b/core/test-module.c @@ -920,6 +920,215 @@ static const char *item_title(const PureApp *app, uint32_t list, size_t at) { /* A task list: made (num), tasks (list of task {title, done}), at (index of * tasks). Indices follow their item across inserts and removes; a failed * event undoes every list change. */ +/* ---- Lists as persistent trees (module-list.c): a model array beside a list + * of thousands of items, changed by events that are committed or undone at + * random, with a stored copy (a draft) kept byte for byte, shares (a + * snapshot's copies) that keep what they shared while the list changes on, + * and a keyed list searched by key. */ + +typedef struct { double key; char text[12]; size_t size; } ModelItem; +typedef struct { ModelItem *items; size_t count, capacity; } Model; + +static void model_insert(Model *m, size_t at, ModelItem item) { + if (m->count == m->capacity) { + m->capacity = m->capacity ? 2 * m->capacity : 64; + m->items = realloc(m->items, m->capacity * sizeof(*m->items)); + CHECK(m->items); + } + memmove(m->items + at + 1, m->items + at, (m->count - at) * sizeof(*m->items)); + m->items[at] = item; + ++m->count; +} + +static void model_copy(Model *to, const Model *from) { + to->count = from->count; + if (to->capacity < from->count) { + to->capacity = from->capacity; + to->items = realloc(to->items, to->capacity * sizeof(*to->items)); + CHECK(to->items); + } + if (from->count) memcpy(to->items, from->items, from->count * sizeof(*to->items)); +} + +static bool same_items(const PureList *list, const Model *m) { + if (pure_list_count(list) != m->count) return false; + for (size_t i = 0; i < m->count; ++i) { + PureCell key = pure_list_get(list, i, 0), text = pure_list_get(list, i, 1); + if (key.num != m->items[i].key || text.size != m->items[i].size || + (text.size && memcmp(text.text, m->items[i].text, text.size))) + return false; + } + return true; +} + +typedef struct { unsigned char *bytes; size_t size, capacity; } Grown; + +static bool collect_bytes(void *context, PureSpan span) { + Grown *b = context; + if (b->size + span.size > b->capacity) { + b->capacity = 2 * (b->size + span.size); + b->bytes = realloc(b->bytes, b->capacity); + CHECK(b->bytes); + } + memcpy(b->bytes + b->size, span.data, span.size); + b->size += span.size; + return true; +} + +/* The stored form of the model: a number's binary64 bits, a text's u32le length and bytes. */ +static bool stored_as(PureDraft *draft, const Model *m) { + Grown got = {0}; + CHECK(pure_draft_read(draft, 0, pure_draft_size(draft), collect_bytes, &got) == PURE_OK); + size_t at = 0; + bool same = true; + for (size_t i = 0; i < m->count && same; ++i) { + uint64_t bits, size = 0; + memcpy(&bits, &m->items[i].key, 8); + for (unsigned k = 0; k < 8; ++k) same = same && at + k < got.size && got.bytes[at + k] == (unsigned char)(bits >> (8 * k)); + at += 8; + for (unsigned k = 0; k < 4 && at + k < got.size; ++k) size |= (uint64_t)got.bytes[at + k] << (8 * k); + at += 4; + same = same && size == m->items[i].size && at + size <= got.size && !memcmp(got.bytes + at, m->items[i].text, size); + at += size; + } + same = same && at == got.size; + free(got.bytes); + return same; +} + +static void list_trees(void) { + static const uint8_t text_fields[2] = {0, 1}; + uint32_t seed = 0x5eed1234u; + PureList *list = pure_list_new(2, text_fields); + PureDraft *draft = pure_draft_new(); + CHECK(list && draft); + pure_list_mirror(list, draft, 0); + PureUndo undo = {0}; + Model model = {0}, before = {0}; + /* Up to four shares at a time, each with what it shared and the items + * and nodes retired while it was the newest. */ + enum { SHARES = 4 }; + PureList *copies[SHARES]; + Model shared[SHARES] = {{0}}; + PureRetired retired[SHARES + 1] = {{0}}; + unsigned first = 0, held = 0, splits_seen = 0; + size_t largest = 0, events = 0, undone = 0; + for (unsigned event = 0; event < 6000; ++event) { + size_t mark = undo.count; + model_copy(&before, &model); + pure_draft_hold(draft, true); + PureVersion version = pure_draft_version(draft); + /* Mostly growing to a few thousand, then shrinking back down, so the + * tree gains and loses levels. */ + unsigned grow = event < 2500 ? 70 : event < 4500 ? 30 : 60; + for (unsigned change = 1 + (unsigned)(next_random(&seed) % 12); change--;) { + unsigned roll = (unsigned)(next_random(&seed) % 100); + if (roll < grow || !model.count) { + size_t at = model.count ? next_random(&seed) % (model.count + 1) : 0; + ModelItem item = {(double)(next_random(&seed) % 100000) - 50000, "", 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] = {{item.key, NULL, 0}, {0, (unsigned char *)item.text, item.size}}; + CHECK(pure_list_insert(list, at, cells, &undo) == PURE_OK); + model_insert(&model, at, item); + } else if (roll < grow + 25) { + 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; + if (next_random(&seed) % 2) { + double key = (double)(next_random(&seed) % 1000); + CHECK(pure_list_set(list, at, 0, (PureCell){key, NULL, 0}, &undo) == PURE_OK); + model.items[at].key = key; + } else { + ModelItem *item = &model.items[at]; + 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){0, (unsigned char *)item->text, item->size}, &undo) == PURE_OK); + } + } + } + if (next_random(&seed) % 5 == 0) { /* undone: the list and its stored copy as before */ + pure_undo_rollback(&undo, mark); + pure_draft_restore(draft, version); + model_copy(&model, &before); + ++undone; + } else + pure_undo_commit(&undo); + pure_draft_hold(draft, false); + ++events; + largest = model.count > largest ? model.count : largest; + splits_seen += model.count > 32; + if (event % 7 == 0) CHECK(same_items(list, &model)); + if (event % 50 == 0) CHECK(stored_as(draft, &model)); + /* A share now and then, as a snapshot takes one; the oldest goes with + * the items and nodes retired while it was the newest. */ + if (event % 40 == 20) { + if (held == SHARES) { + CHECK(same_items(copies[first], &shared[first])); + pure_list_free(copies[first]); + pure_retired_free(&retired[first]); + first = (first + 1) % SHARES; + --held; + } + unsigned slot = (first + held) % SHARES; + CHECK((copies[slot] = pure_list_share(list, &retired[slot]))); + model_copy(&shared[slot], &model); + ++held; + } + if (event % 25 == 0) + for (unsigned i = 0; i < held; ++i) CHECK(same_items(copies[(first + i) % SHARES], &shared[(first + i) % SHARES])); + } + CHECK(same_items(list, &model) && stored_as(draft, &model) && largest > 2000 && undone > 500); + 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_list_free(list); + pure_draft_close(draft); + pure_undo_free(&undo); + + /* A keyed list: items kept in key order, found by key. */ + PureList *keyed = pure_list_new(2, text_fields); + Model keys = {0}; + CHECK(keyed); + for (unsigned round = 0; round < 40000; ++round) { + double key = (double)(next_random(&seed) % 20000); + bool found; + size_t at = pure_list_seek(keyed, 0, (PureCell){key, NULL, 0}, &found); + size_t low = 0, high = keys.count; + while (low < high) { + size_t middle = (low + high) / 2; + if (keys.items[middle].key < key) low = middle + 1; + else high = middle; + } + CHECK(at == low && found == (low < keys.count && keys.items[low].key == key)); + if (!found) { + PureCell cells[2] = {{key, NULL, 0}, {0, (unsigned char *)"k", 1}}; + CHECK(pure_list_insert(keyed, at, cells, NULL) == PURE_OK); + model_insert(&keys, at, (ModelItem){key, "k", 1}); + } else if (next_random(&seed) % 3 == 0) { + PureUndo removal = {0}; + CHECK(pure_list_remove(keyed, at, &removal) == PURE_OK); + pure_undo_commit(&removal); + pure_undo_free(&removal); + memmove(keys.items + at, keys.items + at + 1, (keys.count - at - 1) * sizeof(*keys.items)); + --keys.count; + } + } + CHECK(same_items(keyed, &keys) && keys.count > 5000); + pure_list_free(keyed); + free(model.items); + free(before.items); + free(keys.items); + for (unsigned i = 0; i < SHARES; ++i) free(shared[i].items); + for (unsigned i = 0; i <= SHARES; ++i) pure_retired_free(&retired[i]); + printf("{\"list_tree_events\":%zu,\"undone\":%zu,\"largest\":%zu,\"keyed_items\":%zu}\n", events, undone, + largest, keys.count); +} + static void lists(void) { static const S nums[] = {{"made", 0}}; static const T states[] = {{"tasks", 3, 0}, {"at", 4, 1}}; @@ -2867,6 +3076,7 @@ int main(void) { marks(); text_mutations(); lists(); + list_trees(); folds(); filters(); keyed(); -- cgit v1.2.3