042 tiles: knapsack's two passes with the lanes numbered the batch executor's way (memory's order, ascending): clang -O2 1.87 ms, gcc -O3 2.11, gcc -O2 9.02 (C 6.2, the compiled code 7.9)

2 files changed, 32 insertions, 3 deletions

diff --git a/research/experiments/042-tiles/2026-10-08-tiles.jsonl b/research/experiments/042-tiles/2026-10-08-tiles.jsonl
index cb32e72..0cf0d27 100644
--- a/research/experiments/042-tiles/2026-10-08-tiles.jsonl
+++ b/research/experiments/042-tiles/2026-10-08-tiles.jsonl
@@ -52,3 +52,9 @@
 {"binary":"tiles-16-O3 (computed goto, spilled)","body":"bfs","T":16,"tiles_ms":16.199,"passes_ms":11.197,"c_ms":11.365,"same":true,"reached":99998}
 {"binary":"tiles-16-O3 (computed goto, spilled)","body":"bfs","T":16,"tiles_ms":15.623,"passes_ms":11.305,"c_ms":11.387,"same":true,"reached":99998}
 {"binary":"tiles-16-O3 (computed goto, spilled)","body":"bfs","T":16,"tiles_ms":15.889,"passes_ms":11.203,"c_ms":11.597,"same":true,"reached":99998}
+{"binary":"tail-2-4 clang -O2","body":"knapsack","K":2,"S":4,"T":4,"tiles_ms":29.864,"passes_ms":2.925,"ascending_ms":1.872,"c_ms":8.114,"same":true,"answer":49720}
+{"binary":"tail-2-4 gcc -O3","body":"knapsack","K":2,"S":4,"T":4,"tiles_ms":41.785,"passes_ms":3.549,"ascending_ms":2.118,"c_ms":6.166,"same":true,"answer":49720}
+{"binary":"tail-2-4 gcc -O2","body":"knapsack","K":2,"S":4,"T":4,"tiles_ms":41.781,"passes_ms":9.803,"ascending_ms":9.024,"c_ms":6.165,"same":true,"answer":49720}
+{"binary":"tail-2-4 clang -O2","body":"knapsack","K":2,"S":4,"T":4,"tiles_ms":29.819,"passes_ms":2.944,"ascending_ms":1.873,"c_ms":8.184,"same":true,"answer":49720}
+{"binary":"tail-2-4 gcc -O3","body":"knapsack","K":2,"S":4,"T":4,"tiles_ms":41.780,"passes_ms":3.562,"ascending_ms":2.113,"c_ms":6.164,"same":true,"answer":49720}
+{"binary":"tail-2-4 gcc -O2","body":"knapsack","K":2,"S":4,"T":4,"tiles_ms":41.818,"passes_ms":9.807,"ascending_ms":9.022,"c_ms":6.166,"same":true,"answer":49720}
diff --git a/research/experiments/042-tiles/make2.py b/research/experiments/042-tiles/make2.py
index 5278d1b..b332a35 100644
--- a/research/experiments/042-tiles/make2.py
+++ b/research/experiments/042-tiles/make2.py
@@ -220,6 +220,28 @@ static double knapsack_passes(unsigned n, unsigned capacity, const uint32_t *wei
     return best[capacity];
 }
 
+/* The same two passes with the lanes numbered the other way (the batch executor's reverse): memory's order, ascending. */
+static double knapsack_ascending(unsigned n, unsigned capacity, const uint32_t *weight, const uint32_t *worth, uint32_t *best, double *ms) {
+    enum { LANES = 1024 };
+    static uint32_t with[LANES];
+    double a = now_ms();
+    for (unsigned i = 0; i < n; ++i) {
+        uint32_t w = weight[i], v = worth[i];
+        if (w > capacity) continue;
+        size_t count = capacity + 1 - w;
+        for (size_t k0 = 0; k0 < count; k0 += LANES) {
+            size_t m = count - k0 < LANES ? count - k0 : LANES;
+            size_t low = capacity - k0 - (m - 1); /* the batch's lowest c */
+            const uint32_t *restrict from = best + low - w;
+            uint32_t *restrict to = best + low;
+            for (size_t l = 0; l < m; ++l) with[l] = from[l] + v;
+            for (size_t l = 0; l < m; ++l) to[l] = with[l] > to[l] ? with[l] : to[l];
+        }
+    }
+    *ms = now_ms() - a;
+    return best[capacity];
+}
+
 static double knapsack_c(unsigned n, unsigned capacity, const uint32_t *weight, const uint32_t *worth, uint32_t *best, double *ms) {
     double a = now_ms();
     for (uint32_t i = 0; i < n; ++i)
@@ -350,12 +372,13 @@ int main(int argc, char **argv) {
         uint64_t x = 1;
         for (unsigned 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 (int r = 0; r < rounds; ++r) {
-            double ms[3], answers[3];
+            double ms[4], answers[4];
             memset(best, 0, 4 * (capacity + 1)), answers[0] = knapsack_tiles(n, capacity, weight, worth, best, &ms[0]);
             memset(best, 0, 4 * (capacity + 1)), answers[1] = knapsack_passes(n, capacity, weight, worth, best, &ms[1]);
             memset(best, 0, 4 * (capacity + 1)), answers[2] = knapsack_c(n, capacity, weight, worth, best, &ms[2]);
-            printf("{\\"body\\":\\"knapsack\\",\\"K\\":%d,\\"S\\":%d,\\"T\\":%d,\\"tiles_ms\\":%.3f,\\"passes_ms\\":%.3f,\\"c_ms\\":%.3f,\\"same\\":%s,\\"answer\\":%.17g}\\n", K, S, T, ms[0], ms[1], ms[2],
-                   answers[0] == answers[2] && answers[1] == answers[2] ? "true" : "false", answers[0]);
+            memset(best, 0, 4 * (capacity + 1)), answers[3] = knapsack_ascending(n, capacity, weight, worth, best, &ms[3]);
+            printf("{\\"body\\":\\"knapsack\\",\\"K\\":%d,\\"S\\":%d,\\"T\\":%d,\\"tiles_ms\\":%.3f,\\"passes_ms\\":%.3f,\\"ascending_ms\\":%.3f,\\"c_ms\\":%.3f,\\"same\\":%s,\\"answer\\":%.17g}\\n", K, S, T, ms[0], ms[1], ms[3], ms[2],
+                   answers[0] == answers[2] && answers[1] == answers[2] && answers[3] == answers[2] ? "true" : "false", answers[0]);
         }
     }
     if (all || !strcmp(body, "roots")) {