From 68a1987919d18380abd38b0b60f46a5102f0fb2b Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 5 Oct 2026 10:41:18 +0100 Subject: Keep arrays' number columns as narrow as their values (u8, u32, f64; a DENSE list's keys as its slots), open a packed list's slice in code with an integer index, keep a nest of loops' values in registers of their own: BFS core 27.5 to 19.6 ms (022) --- core/test-module.c | 84 ++++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 69 insertions(+), 15 deletions(-) (limited to 'core/test-module.c') diff --git a/core/test-module.c b/core/test-module.c index 2ccdabb..f6283fe 100644 --- a/core/test-module.c +++ b/core/test-module.c @@ -1387,17 +1387,29 @@ static void same_list(const PureList *a, const PureList *t) { CHECK(pure_list_count(a) == pure_list_count(t) && pure_list_size(a) == pure_list_size(t)); size_t n = pure_list_count(t); for (size_t i = 0; i < n; i += 1 + i / 64) { - PureCell x = pure_list_get(a, i, 0), y = pure_list_get(t, i, 0), u = pure_list_get(a, i, 1), v = pure_list_get(t, i, 1); - CHECK(x.i64 == y.i64 && u.size == v.size && (!u.size || !memcmp(u.text, v.text, u.size))); + PureCell x = pure_list_get(a, i, 0), y = pure_list_get(t, i, 0), u = pure_list_get(a, i, 1), v = pure_list_get(t, i, 1), + w = pure_list_get(a, i, 2), z = pure_list_get(t, i, 2); + CHECK(x.i64 == y.i64 && u.size == v.size && (!u.size || !memcmp(u.text, v.text, u.size)) && w.i64 == z.i64); + } +} + +/* A third field's number: in some events small, in some large, in some + * anything (fractions, -0, below 0), so its column narrows and widens + * (docs/design/022). */ +static double some_number(unsigned event, uint32_t r) { + switch (event % 4) { + case 0: case 3: return (double)(r % 250); + case 1: return (double)(r % 4000000000u); + default: return r % 5 == 0 ? -0.0 : r % 5 == 1 ? -(double)(r % 77) : r % 5 == 2 ? (double)(r % 1000) / 8 : (double)(r % 300); } } static void arrays_equivalence(void) { - static const uint8_t fields[2] = {PURE_CELL_NUMBER, PURE_CELL_TEXT}; + static const uint8_t fields[3] = {PURE_CELL_NUMBER, PURE_CELL_TEXT, PURE_CELL_NUMBER}; uint32_t seed = 0x61727261u; size_t forms[3] = {0}, conversions = 0, steps = 0; for (unsigned keyed = 0; keyed < 2; ++keyed) { - PureList *a = pure_list_new(2, fields), *t = pure_list_new(2, fields); + PureList *a = pure_list_new(3, fields), *t = pure_list_new(3, fields); CHECK(a && t); if (keyed) { CHECK(pure_list_keyed(a, 0) == PURE_OK && pure_list_keyed(t, 0) == PURE_OK); @@ -1416,7 +1428,8 @@ static void arrays_equivalence(void) { : (double)(r % 80000) / 4; char text[16]; size_t size = (size_t)snprintf(text, sizeof(text), "t%u", r % 1000); - PureCell cells[2] = {{.num = key}, {.text = (unsigned char *)text, .size = r % 11 ? size : 0}}; + PureCell cells[3] = {{.num = key}, {.text = (unsigned char *)text, .size = r % 11 ? size : 0}, + {.num = some_number(event, r >> 7)}}; unsigned op = next_random(&seed) % 20; if (keyed && event % 3 == 1) op = op < 12 ? 1 + op % 8 : 13 + op % 2; /* by key alone, as a search does: DENSE stays */ if (keyed && op < 9) { /* add by key, where it went asked or not */ @@ -1434,6 +1447,9 @@ static void arrays_equivalence(void) { } else if (op < 12 && n) { /* a text changed; in a keyed list now and then its key, between its neighbours */ size_t at = next_random(&seed) % n; CHECK(pure_list_set(a, at, 1, cells[1], NULL) == PURE_OK && pure_list_set(t, at, 1, cells[1], NULL) == PURE_OK); + if (r % 2) /* the third field: wider now and then */ + CHECK(pure_list_set(a, at, 2, (PureCell){.num = some_number(event + r % 3, r >> 9)}, NULL) == PURE_OK && + pure_list_set(t, at, 2, (PureCell){.num = some_number(event + r % 3, r >> 9)}, NULL) == PURE_OK); if (keyed && at + 1 < n && r % 3 == 0) { double low = pure_list_get(t, at, 0).num, high = pure_list_get(t, at + 1, 0).num, to = low + (high - low) / 2; if (to > low && to < high) { @@ -1449,10 +1465,17 @@ static void arrays_equivalence(void) { fa = pure_list_lookup(a, 0, cells[0], 1, &ca); ft = pure_list_lookup(t, 0, cells[0], 1, &ct); CHECK(fa == ft && fa == ht && (!fa || (ca.size == ct.size && (!ca.size || !memcmp(ca.text, ct.text, ca.size))))); + fa = pure_list_lookup(a, 0, cells[0], 2, &ca); + ft = pure_list_lookup(t, 0, cells[0], 2, &ct); + CHECK(fa == ft && (!fa || ca.i64 == ct.i64)); + fa = pure_list_lookup(a, 0, cells[0], 0, &ca); /* the key itself: a DENSE list's slot */ + ft = pure_list_lookup(t, 0, cells[0], 0, &ct); + CHECK(fa == ft && (!fa || ca.i64 == ct.i64)); } else if (op < 17 && n) { /* by position */ size_t at = next_random(&seed) % n; - PureCell x = pure_list_get(a, at, 0), y = pure_list_get(t, at, 0); - CHECK(x.i64 == y.i64); + PureCell x = pure_list_get(a, at, 0), y = pure_list_get(t, at, 0), w = pure_list_get(a, at, 2), + z = pure_list_get(t, at, 2); + CHECK(x.i64 == y.i64 && w.i64 == z.i64); } else if (op < 18 && n) { /* run by run from somewhere */ size_t at = next_random(&seed) % n, seen = 0; PureRun ra, rt; @@ -1466,6 +1489,7 @@ static void arrays_equivalence(void) { break; } CHECK(ra.column[0].numbers[ia - ra.start] == rt.column[0].numbers[it - rt.start]); + CHECK(!memcmp(&ra.column[2].numbers[ia - ra.start], &rt.column[2].numbers[it - rt.start], sizeof(double))); PureSpan sa = ra.column[1].texts[ia - ra.start], st = rt.column[1].texts[it - rt.start]; CHECK(sa.size == st.size && (!sa.size || !memcmp(sa.data, st.data, sa.size))); ++ia, ++it; @@ -1486,16 +1510,16 @@ static void arrays_equivalence(void) { CHECK(forms[0] > 10000 && forms[1] > 10000 && forms[2] > 10000 && conversions > 100); /* A snapshot shares every list: an event's, empty between events, stays in arrays; one with items is a tree for its copy. */ { - PureList *list = pure_list_new(2, fields); + PureList *list = pure_list_new(3, fields); PureRetired retired = {0}; CHECK(list && pure_list_arrays(list)); PureList *copy = pure_list_share(list, &retired, 1); CHECK(copy && pure_list_count(copy) == 0 && pure_list_form(list) == 1); pure_list_free(copy); for (unsigned i = 0; i < 100; ++i) - CHECK(pure_list_insert(list, i, (PureCell[]){{.num = i}, {.size = 0}}, NULL) == PURE_OK); + CHECK(pure_list_insert(list, i, (PureCell[]){{.num = i}, {.size = 0}, {.num = i * 1000.5}}, NULL) == PURE_OK); CHECK((copy = pure_list_share(list, &retired, 2)) && pure_list_form(list) == 0 && pure_list_count(copy) == 100); - CHECK(pure_list_get(copy, 99, 0).num == 99); + CHECK(pure_list_get(copy, 99, 0).num == 99 && pure_list_get(copy, 99, 2).num == 99049.5); pure_list_free(copy); pure_list_clear(list); CHECK(pure_list_form(list) == 1); /* arrays again, the next event */ @@ -1517,6 +1541,18 @@ static size_t model_bound(const Model *m, double key) { return low; } +/* Two lists' stored forms, whole and a part at a time, the same. */ +static bool stored_numbers_same(const PureList *a, const PureList *b) { + size_t size = pure_list_size(a); + unsigned char *x = malloc(size + 1), *y = malloc(size + 1); + CHECK(x && y && size == pure_list_size(b)); + pure_list_encode(a, x); + pure_list_encode(b, y); + bool same = !memcmp(x, y, size); + free(x), free(y); + return same; +} + /* 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; @@ -1703,11 +1739,12 @@ static void packed_lists(void) { 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}; + /* The index's edges: each list packed, then searched as its tree (never packed) is; its second field's + * cells packed as narrow as they let (docs/design/022) and read back as they were, by position and by runs. */ + static const uint8_t number[2] = {PURE_CELL_NUMBER, 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); + PureList *packed = pure_list_new(2, number), *tree = pure_list_new(2, 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; @@ -1719,8 +1756,9 @@ static void packed_lists(void) { : (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); + double second = some_number(kind, (uint32_t)(i * 2654435761u)), third = kind == 4 ? (double)(i % 200) : second; + CHECK(pure_list_add(packed, (PureCell[]){{.num = key}, {.num = third}}, NULL, NULL, &exists) == PURE_OK); + CHECK(pure_list_add(tree, (PureCell[]){{.num = key}, {.num = third}}, 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 */ @@ -1729,6 +1767,22 @@ static void packed_lists(void) { (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 < n; ++i) { + PureCell x = pure_list_get(packed, i, 1), y = pure_list_get(tree, i, 1); + CHECK(x.i64 == y.i64); + } + PureRun rp, rt; + size_t at = n / 3, read = 0; + CHECK(pure_list_run(packed, at, &rp) && pure_list_run(tree, at, &rt)); + for (size_t ip = at, it = at; read < 500; ++read, ++ip, ++it) { + bool mp = true, mt = true; + while (mp && ip >= rp.start + rp.count) mp = pure_list_next(packed, &rp); + while (mt && it >= rt.start + rt.count) mt = pure_list_next(tree, &rt); + CHECK(mp == mt); + if (!mp) break; + CHECK(!memcmp(&rp.column[1].numbers[ip - rp.start], &rt.column[1].numbers[it - rt.start], sizeof(double))); + } + CHECK(stored_numbers_same(packed, tree)); for (size_t i = 0; i < 20000; ++i) { uint32_t r = next_random(&seed); double a = keys[r % n], b = keys[(r / 7) % n]; -- cgit v1.2.3