Say that prefetching items did not pay, and why (109)

Fetching a found item's cells, a leaf's keys and each level's keys ahead
made finding and reading items 20% faster on 100,000 items in a micro
benchmark, but TPC-C's clean pairs moved 1% at most and finding alone got
48% slower, so it is not in. The owner's finding samples were the descent,
not the fields: a write right after a read copies the leaf whole anyway,
and what costs is walking structures larger than the caches at random.

1 files changed, 80 insertions, 0 deletions

diff --git a/research/experiments/024-finding-items/bench-seek.c b/research/experiments/024-finding-items/bench-seek.c
new file mode 100644
index 0000000..6be7245
--- /dev/null
+++ b/research/experiments/024-finding-items/bench-seek.c
@@ -0,0 +1,80 @@
+/* Finding items in a keyed list the way TPC-C's stock is found (docs/research/109):
+ *     bench-seek ITEMS OPERATIONS
+ * A list of ITEMS items, five number fields, keyed by the first (keys 1..ITEMS);
+ * then OPERATIONS random keys, four ways: a seek alone; a seek and three
+ * fields read; and three fields read and each changed (journaled); the same
+ * with a share every 30 changes, as a snapshot a save takes. Prints ns each,
+ * and the machine's latency to memory (a random pointer chase over 64 MiB). */
+#include "module-list.h"
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+static uint64_t now_ns(void) {
+    struct timespec t;
+    clock_gettime(CLOCK_MONOTONIC, &t);
+    return (uint64_t)t.tv_sec * 1000000000u + (uint64_t)t.tv_nsec;
+}
+
+static uint64_t state = 0x9e3779b97f4a7c15u;
+static uint64_t next(void) {
+    state ^= state << 13, state ^= state >> 7, state ^= state << 17;
+    return state;
+}
+
+int main(int argc, char **argv) {
+    size_t items = argc > 1 ? strtoull(argv[1], NULL, 10) : 100000, operations = argc > 2 ? strtoull(argv[2], NULL, 10) : 2000000;
+    static const uint8_t numbers[5] = {0};
+    PureList *list = pure_list_new(5, numbers);
+    if (!list || pure_list_keyed(list, 0) != PURE_OK) return 1;
+    for (size_t i = 0; i < items; ++i) {
+        PureCell cells[5] = {{.num = (double)(i + 1)}, {.num = 50}, {.num = 0}, {.num = 0}, {.num = 0}};
+        if (pure_list_insert(list, i, cells, NULL) != PURE_OK) return 1;
+    }
+    pure_list_journal(list, true);
+    double sink = 0;
+    const char *names[4] = {"seek", "seek+3 reads", "seek+3 reads+3 changes", "same, a share each 30"};
+    for (int way = 0; way < 4; ++way) {
+        PureRetired retired = {0};
+        PureList *copy = NULL;
+        uint64_t epoch = 0;
+        uint64_t began = now_ns();
+        for (size_t op = 0; op < operations; ++op) {
+            bool found;
+            size_t at = pure_list_seek(list, 0, (PureCell){.num = (double)(next() % items + 1)}, &found);
+            if (way == 0) { sink += (double)at; continue; }
+            for (unsigned f = 1; f <= 3; ++f) {
+                double value = pure_list_get(list, at, f).num;
+                sink += value;
+                if (way >= 2) pure_list_set(list, at, f, (PureCell){.num = value + 1}, NULL);
+            }
+            if (way >= 2 && op % 64 == 63) pure_list_forget(list, 0);
+            if (way == 3 && op % 30 == 29) {
+                if (copy) {
+                    pure_list_free(copy);
+                    pure_retired_reuse(&retired, &list, 1);
+                }
+                copy = pure_list_share(list, &retired, ++epoch);
+            }
+        }
+        uint64_t took = now_ns() - began;
+        if (copy) pure_list_free(copy);
+        pure_retired_free(&retired);
+        printf("%-26s %7.1f ns\n", names[way], (double)took / (double)operations);
+    }
+    /* The latency to memory: a random cycle through 64 MiB of pointers. */
+    size_t slots = (64u << 20) / sizeof(size_t);
+    size_t *chain = malloc(slots * sizeof(*chain)), *order = malloc(slots * sizeof(*order));
+    for (size_t i = 0; i < slots; ++i) order[i] = i;
+    for (size_t i = slots - 1; i > 0; --i) { size_t j = next() % (i + 1), t = order[i]; order[i] = order[j]; order[j] = t; }
+    for (size_t i = 0; i < slots; ++i) chain[order[i]] = order[(i + 1) % slots];
+    size_t at = order[0];
+    uint64_t began = now_ns();
+    for (size_t i = 0; i < 4000000; ++i) at = chain[at];
+    printf("%-26s %7.1f ns\n", "memory latency", (double)(now_ns() - began) / 4000000.0);
+    sink += (double)at;
+    fprintf(stderr, "%g\n", sink);
+    pure_list_free(list);
+    return 0;
+}