041 join ops: the recurrence interpreted and each round's rest as 11 operations apart, interpreted, 57.8 ms (C 32.6; fused by hand 48.4, the tier 2.46x); bfs: a node with more edges than the lanes runs its round alone (tested with lanes of 16, LANES_TEST); runs again

1 files changed, 12 insertions, 1 deletions

diff --git a/research/experiments/041-batches/bfs.c b/research/experiments/041-batches/bfs.c
index 3c25a98..2c61226 100644
--- a/research/experiments/041-batches/bfs.c
+++ b/research/experiments/041-batches/bfs.c
@@ -12,7 +12,8 @@
  *          lane's bit read again first (an earlier lane may have added it)
  * Against natural.h's c_bfs (offsets per node: CSR) and c_bfs_ahead (that
  * read ahead), on the suite's graph and routes (100,000 nodes, 1,000,000
- * edges drawn, seed 121). Built cc -O2. */
+ * edges drawn, seed 121). Built cc -O2; with -DLANES_TEST the edges' lanes
+ * are 16 (a node with more edges runs its round alone: the answers the same). */
 #define _POSIX_C_SOURCE 200809L
 #include <math.h>
 #include <stdbool.h>
@@ -29,7 +30,11 @@ static double now(void) {
     return t.tv_sec * 1e3 + t.tv_nsec / 1e6;
 }
 
+#ifdef LANES_TEST
+enum { B = 256, LANES = 16 };
+#else
 enum { B = 256, LANES = 8192 };
+#endif
 
 /* seen: list of Seen by node, DENSE */
 typedef struct { uint64_t *bits; uint32_t *depth; size_t count; } Seen;
@@ -81,6 +86,12 @@ static void batch_bfs(uint32_t from, uint32_t target, uint32_t nodes, double *ou
         unsigned e = 0, rounds = 0; /* the edges into lanes, as many rounds as fit */
         for (; rounds < m && e + (hi[rounds] - lo[rounds]) <= LANES; ++rounds)
             for (uint32_t k = lo[rounds]; k < hi[rounds]; ++k) edge_to[e] = to_col[k], edge_round[e] = rounds, ++e;
+        if (!rounds) { /* a node with more edges than the lanes: its round alone, round by round */
+            for (uint32_t k = lo[0]; k < hi[0]; ++k)
+                if (!seen_has(&seen, to_col[k])) seen_add(&seen, to_col[k], depth[0]), queue[count++] = to_col[k];
+            ++i;
+            continue;
+        }
         for (unsigned q = 0; q < e; ++q) has[q] = seen_has(&seen, edge_to[q]); /* seen.has(e.to), each lane */
         for (unsigned q = 0; q < e; ++q) /* the adds and appends, in order */
             if (!has[q] && !seen_has(&seen, edge_to[q])) seen_add(&seen, edge_to[q], depth[edge_round[q]]), queue[count++] = edge_to[q];