041 runs of b5 = bdfc4d7 and b6 = de9efad: batches knapsack 10.84 ms (the compiled code 7.93), matmul 36.41 (14.20), join 118.3 (78.7), sort 55.5 (35.6), roots 8.87 (9.57); the executor alone as many instructions as b4's; costs three ways on b5 and b6 (tagged by version, b4's too: adds 0.65, ops 4.00, recur 21.8, recur4 36.0); frontier.c: the suite's BFS as frontier batches (105,232 of 999,913 edges asked again in order, 99,997 added; walking a batch's edges together 2.17x the edges)

1 files changed, 47 insertions, 0 deletions

diff --git a/research/experiments/041-batches/frontier.c b/research/experiments/041-batches/frontier.c
new file mode 100644
index 0000000..a730644
--- /dev/null
+++ b/research/experiments/041-batches/frontier.c
@@ -0,0 +1,47 @@
+/* The suite's BFS (natural.h's graph: 100,000 nodes, 1,000,000 edges) run
+ * as a frontier batch would (research 129): rounds i .. min(i + B, the
+ * queue's count at the batch's open), each edge's has asked as the batch
+ * opened; candidates the edges it said no to (each asked again in order:
+ * added, or added already by an earlier round of the batch); lock-step
+ * lane-rounds what walking every round's edges together would cost (the
+ * most edges of a batch's rounds times its rounds). cc -O2 frontier.c;
+ * ./a.out [B]. */
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+static uint64_t st = 121;
+static uint64_t nx(void) { st ^= st << 13, st ^= st >> 7, st ^= st << 17; return st; }
+static int cmp(const void *a, const void *b) { uint64_t x = *(const uint64_t *)a, y = *(const uint64_t *)b; return (x > y) - (x < y); }
+int main(int argc, char **argv) {
+    unsigned B = argc > 1 ? atoi(argv[1]) : 1024, nodes = 100000; size_t edges = 1000000;
+    uint64_t *keys = malloc(edges * 8); size_t c = 0;
+    while (c < edges) { uint64_t a = nx() % nodes, b = nx() % nodes; if (a != b) keys[c++] = a << 20 | b; }
+    qsort(keys, c, 8, cmp);
+    size_t u = 0; for (size_t i = 0; i < c; ++i) if (!u || keys[i] != keys[u - 1]) keys[u++] = keys[i];
+    uint32_t *start = calloc(nodes + 1, 4), *to = malloc(4 * u);
+    for (size_t i = 0; i < u; ++i) ++start[(keys[i] >> 20) + 1], to[i] = keys[i] & 0xFFFFF;
+    for (unsigned v = 0; v < nodes; ++v) start[v + 1] += start[v];
+    unsigned char *seen = malloc(nodes), *open = malloc(nodes); uint32_t *queue = malloc(4 * nodes);
+    for (int s = 0; s < 6; ++s) {
+        uint32_t from = nx() % nodes, dest = nx() % nodes; (void)dest;
+        memset(seen, 0, nodes);
+        size_t steps = 0, count = 1, cand = 0, adds = 0, edges_seen = 0, batches = 0, small = 0, lanes = 0;
+        queue[0] = from, seen[from] = 1;
+        for (size_t i = 0; i < count;) {
+            size_t end = count < i + B ? count : i + B;
+            memcpy(open, seen, nodes); /* has at the batch's open */
+            ++batches, lanes += end - i, small += end - i < 16;
+            { uint32_t most = 0; for (size_t r = i; r < end; ++r) { uint32_t l = start[queue[r] + 1] - start[queue[r]]; if (l > most) most = l; } steps += (size_t)most * (end - i); }
+            for (size_t r = i; r < end; ++r)
+                for (uint32_t e = start[queue[r]]; e < start[queue[r] + 1]; ++e) {
+                    ++edges_seen;
+                    if (open[to[e]]) continue;
+                    ++cand;
+                    if (!seen[to[e]]) seen[to[e]] = 1, queue[count++] = to[e], ++adds;
+                }
+            i = end;
+        }
+        printf("B %u search %d: edges %zu candidates %zu adds %zu batches %zu (under 16 lanes %zu) lanes/batch %.0f lockstep lane-rounds %zu (%.2fx the edges)\n", B, s, edges_seen, cand, adds, batches, small, (double)lanes / batches, steps, (double)steps / edges_seen);
+    }
+}