Research 124's floors: each workload by hand as Pure could run it (its lists' representation, its meaning) bare, with the checks a compiler could hoist, and with every check where the meaning puts it: hoisted 0.64-1.02x C (0.90 by the geometric mean), naive up to 12x

1 files changed, 201 insertions, 0 deletions

diff --git a/research/experiments/040-against-c/natural.h b/research/experiments/040-against-c/natural.h
new file mode 100644
index 0000000..dfd8a44
--- /dev/null
+++ b/research/experiments/040-against-c/natural.h
@@ -0,0 +1,201 @@
+/* The C each workload of research 124's suite is held to (suite-run.c,
+ * floor.c): what one would write for the task, its answers in out[]. */
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+static uint64_t minstd(uint64_t x) { return x * 48271 % 2147483647; }
+
+/* ---- The C of each workload: its answers in out[] */
+
+static void c_roots(const uint32_t *in, double *out) {
+    double sum = 0, count = 0;
+    for (uint32_t i = 1; i <= in[0]; ++i) {
+        double r = i;
+        for (int s = 0; s < 64; ++s) {
+            double next = (r + i / r) / 2;
+            if (next >= r) break;
+            r = next;
+            ++count;
+        }
+        sum += r;
+    }
+    out[0] = sum, out[1] = count;
+}
+
+static void c_knapsack(const uint32_t *in, double *out) {
+    uint32_t n = in[0], capacity = in[1];
+    uint32_t *weight = malloc(4 * (size_t)n), *worth = malloc(4 * (size_t)n);
+    int64_t *best = calloc((size_t)capacity + 1, 8);
+    uint64_t x = 1;
+    for (uint32_t i = 0; i < n; ++i) {
+        x = minstd(x), weight[i] = (uint32_t)(x % 1000) + 1;
+        x = minstd(x), worth[i] = (uint32_t)(x % 1000);
+    }
+    for (uint32_t i = 0; i < n; ++i)
+        for (uint32_t c = capacity; c >= weight[i] && c <= capacity; --c) {
+            int64_t with = best[c - weight[i]] + worth[i];
+            if (with > best[c]) best[c] = with;
+        }
+    out[0] = (double)best[capacity];
+    free(weight), free(worth), free(best);
+}
+
+static int compare_u32(const void *a, const void *b) {
+    uint32_t x = *(const uint32_t *)a, y = *(const uint32_t *)b;
+    return (x > y) - (x < y);
+}
+
+static void c_sort(const uint32_t *in, double *out) {
+    uint32_t n = in[0];
+    uint32_t *keys = malloc(4 * (size_t)n);
+    uint64_t x = 1;
+    for (uint32_t i = 0; i < n; ++i) x = minstd(x), keys[i] = (uint32_t)x;
+    qsort(keys, n, 4, compare_u32);
+    uint32_t wrong = 0;
+    for (uint32_t i = 1; i < n; ++i) wrong += keys[i] < keys[i - 1];
+    out[0] = keys[0], out[1] = keys[n / 2], out[2] = keys[n - 1], out[3] = wrong;
+    free(keys);
+}
+
+static uint32_t hash32(uint32_t x) { return x * 2654435761u; }
+
+static void c_join(const uint32_t *in, double *out) {
+    uint32_t customers = in[0], orders = in[1], size = 1;
+    while (size < 2 * customers) size *= 2;
+    uint32_t *ids = malloc(4 * (size_t)customers), *keys = calloc(size, 4), *regions = malloc(4 * (size_t)size);
+    uint64_t x = 1, totals[16] = {0};
+    for (uint32_t i = 0; i < customers; ++i) {
+        x = minstd(x), ids[i] = (uint32_t)x;
+        uint32_t at = hash32(ids[i]) & (size - 1);
+        while (keys[at]) at = (at + 1) & (size - 1);
+        keys[at] = ids[i], regions[at] = i % 16;
+    }
+    for (uint32_t o = 0; o < orders; ++o) {
+        x = minstd(x);
+        uint32_t id = ids[x % customers], at = hash32(id) & (size - 1);
+        while (keys[at] != id) at = (at + 1) & (size - 1);
+        totals[regions[at]] += x % 1000;
+    }
+    uint64_t most = 0, sum = 0;
+    for (int r = 0; r < 16; ++r) most = totals[r] > most ? totals[r] : most, sum += totals[r];
+    out[0] = (double)most, out[1] = (double)sum;
+    free(ids), free(keys), free(regions);
+}
+
+static uint32_t fnv(const char *s) {
+    uint32_t h = 2166136261u;
+    for (; *s; ++s) h = (h ^ (unsigned char)*s) * 16777619u;
+    return h;
+}
+
+static void c_words(const uint32_t *in, double *out) {
+    uint32_t n = in[0], vocabulary = in[1], size = 1;
+    while (size < 2 * vocabulary) size *= 2;
+    char (*words)[16] = calloc(size, 16);
+    uint32_t *counts = calloc(size, 4), distinct = 0, most = 0;
+    uint64_t x = 1;
+    for (uint32_t i = 0; i < n; ++i) {
+        x = minstd(x);
+        char w[16];
+        snprintf(w, sizeof(w), "w%u", (unsigned)(x % vocabulary));
+        uint32_t at = fnv(w) & (size - 1);
+        while (counts[at] && strcmp(words[at], w)) at = (at + 1) & (size - 1);
+        if (!counts[at]) memcpy(words[at], w, sizeof(w)), ++distinct;
+        if (++counts[at] > most) most = counts[at];
+    }
+    out[0] = distinct, out[1] = most;
+    free(words), free(counts);
+}
+
+static void c_matmul(const uint32_t *in, double *out) {
+    uint32_t n = in[0];
+    double *a = malloc(8 * (size_t)n * n), *b = malloc(8 * (size_t)n * n), total = 0, last = 0;
+    uint64_t x = 1;
+    for (uint32_t i = 0; i < n * n; ++i) {
+        x = minstd(x), a[i] = (double)(x % 100);
+        x = minstd(x), b[i] = (double)(x % 100);
+    }
+    for (uint32_t i = 0; i < n; ++i)
+        for (uint32_t j = 0; j < n; ++j) {
+            double s = 0;
+            for (uint32_t k = 0; k < n; ++k) s += a[i * n + k] * b[k * n + j];
+            total += s, last = s;
+        }
+    out[0] = total, out[1] = last;
+    free(a), free(b);
+}
+
+/* ---- BFS: 033's graph (bfs-run's generator, seed 121), bfs.c's loop */
+
+typedef struct { uint32_t nodes, *start, *to, *queue; int32_t *depth; } Graph;
+static Graph graph;
+static uint64_t graph_state = 121;
+static uint64_t graph_next(void) {
+    graph_state ^= graph_state << 13, graph_state ^= graph_state >> 7, graph_state ^= graph_state << 17;
+    return graph_state;
+}
+static int compare_u64(const void *a, const void *b) {
+    uint64_t x = *(const uint64_t *)a, y = *(const uint64_t *)b;
+    return (x > y) - (x < y);
+}
+
+static void c_bfs(const uint32_t *in, double *out) {
+    const Graph *g = &graph;
+    for (uint32_t v = 0; v < g->nodes; ++v) g->depth[v] = -1;
+    uint32_t head = 0, tail = 0;
+    g->queue[tail++] = in[0];
+    g->depth[in[0]] = 0;
+    while (head < tail) {
+        uint32_t v = g->queue[head++];
+        for (uint32_t k = g->start[v]; k < g->start[v + 1]; ++k)
+            if (g->depth[g->to[k]] < 0) g->depth[g->to[k]] = g->depth[v] + 1, g->queue[tail++] = g->to[k];
+    }
+    out[0] = g->depth[in[1]], out[1] = tail;
+}
+
+/* bfs.c read ahead as 022's floor reads Pure's (bfsfloor's c_ahead): the
+ * offsets of the node 16 on in the queue, the first edge of the one 8 on
+ * (context for Pure's reading ahead, not the C it is held to). */
+static void c_bfs_ahead(const uint32_t *in, double *out) {
+    const Graph *g = &graph;
+    for (uint32_t v = 0; v < g->nodes; ++v) g->depth[v] = -1;
+    uint32_t head = 0, tail = 0;
+    g->queue[tail++] = in[0];
+    g->depth[in[0]] = 0;
+    while (head < tail) {
+        if (head + 16 < tail) __builtin_prefetch(&g->start[g->queue[head + 16]]);
+        if (head + 8 < tail) __builtin_prefetch(&g->to[g->start[g->queue[head + 8]]]);
+        uint32_t v = g->queue[head++];
+        for (uint32_t k = g->start[v]; k < g->start[v + 1]; ++k)
+            if (g->depth[g->to[k]] < 0) g->depth[g->to[k]] = g->depth[v] + 1, g->queue[tail++] = g->to[k];
+    }
+    out[0] = g->depth[in[1]], out[1] = tail;
+}
+
+
+/* 033's graph of nodes and edges (bfs-run's generator, seed 121): C's
+ * adjacency in graph, and the edges as from * 2^20 + to, sorted, each once,
+ * in *keys (the caller's to free); their count. */
+static size_t graph_build(uint32_t nodes, size_t edges, uint64_t **keys_out) {
+    graph_state = 121; /* the same graph each time */
+    free(graph.start), free(graph.to), free(graph.queue), free(graph.depth);
+    uint64_t *keys = malloc(edges * sizeof(*keys));
+    size_t count = 0;
+    while (count < edges) {
+        uint64_t a = graph_next() % nodes, b = graph_next() % nodes;
+        if (a != b) keys[count++] = a << 20 | b;
+    }
+    qsort(keys, count, sizeof(*keys), compare_u64);
+    size_t unique = 0;
+    for (size_t i = 0; i < count; ++i)
+        if (!unique || keys[i] != keys[unique - 1]) keys[unique++] = keys[i];
+    graph.nodes = nodes;
+    graph.start = calloc((size_t)nodes + 1, 4), graph.to = malloc(4 * unique), graph.queue = malloc(4ull * nodes);
+    graph.depth = malloc(4ull * nodes);
+    for (size_t i = 0; i < unique; ++i) ++graph.start[(keys[i] >> 20) + 1], graph.to[i] = (uint32_t)(keys[i] & 0xFFFFF);
+    for (uint32_t v = 0; v < nodes; ++v) graph.start[v + 1] += graph.start[v];
+    *keys_out = keys;
+    return unique;
+}