diff options
Diffstat (limited to 'research/experiments/041-batches')
| -rw-r--r-- | research/experiments/041-batches/2026-10-05-batches.jsonl | 26 | ||||
| -rw-r--r-- | research/experiments/041-batches/batch.c | 62 |
2 files changed, 70 insertions, 18 deletions
diff --git a/research/experiments/041-batches/2026-10-05-batches.jsonl b/research/experiments/041-batches/2026-10-05-batches.jsonl index 6fe3fea..fd9eca6 100644 --- a/research/experiments/041-batches/2026-10-05-batches.jsonl +++ b/research/experiments/041-batches/2026-10-05-batches.jsonl @@ -1,15 +1,15 @@ -{"work":"matmul","c_natural_ms":7.59,"c_ms":7.09,"c_ikj_ms":8.51,"c_ikj_u32_ms":7.41,"c_ikj_vec_ms":4.89,"c_ikj_dvec_ms":7.87,"batch_k_ms":22.08,"batch_j_ms":17.75,"axpy_ms":6.68,"same":true} -{"work":"knapsack","c_natural_ms":6.30,"c_ms":6.47,"c_u32_ms":7.62,"c_vec_ms":9.51,"c_block_ms":1.96,"batch_ms":11.21,"u32_ms":2.71,"same":true} +{"work":"matmul","c_natural_ms":7.65,"c_ms":7.09,"c_ikj_ms":8.49,"c_ikj_u32_ms":7.43,"c_ikj_vec_ms":4.89,"c_ikj_dvec_ms":7.89,"batch_k_ms":22.07,"batch_j_ms":17.75,"axpy_ms":6.68,"same":true} +{"work":"knapsack","c_natural_ms":6.25,"c_ms":6.37,"c_u32_ms":7.62,"c_vec_ms":9.50,"c_block_ms":1.97,"batch_ms":11.22,"u32_ms":2.71,"u32_ops_ms":4.55,"same":true} {"work":"roots","c_ms":6.86,"batch_ms":6.79,"same":true} -{"work":"join","c_ms":30.73,"batch_ms":38.10,"interpreted_ms":51.01,"reciprocal_ms":46.73,"same":true} -{"work":"bfs","c_ms":9.99,"c_ahead_ms":7.10,"forms_ms":10.32,"batch_ms":10.29,"reached":99998,"same":true} -{"work":"matmul","c_natural_ms":7.62,"c_ms":7.10,"c_ikj_ms":8.56,"c_ikj_u32_ms":7.41,"c_ikj_vec_ms":4.88,"c_ikj_dvec_ms":7.94,"batch_k_ms":22.06,"batch_j_ms":17.73,"axpy_ms":6.67,"same":true} -{"work":"knapsack","c_natural_ms":6.24,"c_ms":6.47,"c_u32_ms":7.62,"c_vec_ms":9.50,"c_block_ms":1.94,"batch_ms":11.21,"u32_ms":2.70,"same":true} +{"work":"join","c_ms":33.09,"batch_ms":39.36,"interpreted_ms":52.81,"reciprocal_ms":47.64,"same":true} +{"work":"bfs","c_ms":10.01,"c_ahead_ms":7.05,"forms_ms":10.44,"batch_ms":10.28,"reached":99998,"same":true} +{"work":"matmul","c_natural_ms":8.06,"c_ms":7.10,"c_ikj_ms":8.59,"c_ikj_u32_ms":7.41,"c_ikj_vec_ms":4.90,"c_ikj_dvec_ms":7.98,"batch_k_ms":22.08,"batch_j_ms":17.74,"axpy_ms":6.68,"same":true} +{"work":"knapsack","c_natural_ms":6.24,"c_ms":6.38,"c_u32_ms":7.62,"c_vec_ms":9.50,"c_block_ms":1.94,"batch_ms":11.22,"u32_ms":2.70,"u32_ops_ms":4.53,"same":true} {"work":"roots","c_ms":6.86,"batch_ms":6.79,"same":true} -{"work":"join","c_ms":30.34,"batch_ms":37.31,"interpreted_ms":50.63,"reciprocal_ms":45.01,"same":true} -{"work":"bfs","c_ms":10.04,"c_ahead_ms":7.00,"forms_ms":10.36,"batch_ms":10.38,"reached":99998,"same":true} -{"work":"matmul","c_natural_ms":7.61,"c_ms":7.11,"c_ikj_ms":8.52,"c_ikj_u32_ms":7.41,"c_ikj_vec_ms":4.88,"c_ikj_dvec_ms":7.91,"batch_k_ms":22.09,"batch_j_ms":17.74,"axpy_ms":6.68,"same":true} -{"work":"knapsack","c_natural_ms":6.25,"c_ms":6.52,"c_u32_ms":7.62,"c_vec_ms":9.50,"c_block_ms":1.94,"batch_ms":11.21,"u32_ms":2.70,"same":true} -{"work":"roots","c_ms":6.86,"batch_ms":6.79,"same":true} -{"work":"join","c_ms":29.37,"batch_ms":35.69,"interpreted_ms":49.15,"reciprocal_ms":44.59,"same":true} -{"work":"bfs","c_ms":10.04,"c_ahead_ms":7.01,"forms_ms":10.39,"batch_ms":10.44,"reached":99998,"same":true} +{"work":"join","c_ms":28.45,"batch_ms":36.14,"interpreted_ms":50.29,"reciprocal_ms":45.72,"same":true} +{"work":"bfs","c_ms":9.96,"c_ahead_ms":6.99,"forms_ms":10.39,"batch_ms":10.34,"reached":99998,"same":true} +{"work":"matmul","c_natural_ms":7.69,"c_ms":7.09,"c_ikj_ms":8.51,"c_ikj_u32_ms":7.42,"c_ikj_vec_ms":4.89,"c_ikj_dvec_ms":7.88,"batch_k_ms":22.06,"batch_j_ms":17.74,"axpy_ms":6.68,"same":true} +{"work":"knapsack","c_natural_ms":6.25,"c_ms":6.38,"c_u32_ms":7.62,"c_vec_ms":9.50,"c_block_ms":1.97,"batch_ms":11.22,"u32_ms":2.71,"u32_ops_ms":4.54,"same":true} +{"work":"roots","c_ms":6.87,"batch_ms":6.79,"same":true} +{"work":"join","c_ms":28.77,"batch_ms":36.50,"interpreted_ms":49.19,"reciprocal_ms":44.60,"same":true} +{"work":"bfs","c_ms":9.97,"c_ahead_ms":7.02,"forms_ms":10.34,"batch_ms":10.24,"reached":99998,"same":true} diff --git a/research/experiments/041-batches/batch.c b/research/experiments/041-batches/batch.c index d4da1a7..c209488 100644 --- a/research/experiments/041-batches/batch.c +++ b/research/experiments/041-batches/batch.c @@ -16,7 +16,8 @@ * order: the same numbers), a row of b a batch; axpy: that with * the multiply and the add as one operation * knapsack each item's rounds a batch, lanes of 8 bytes; u32: lanes of - * the column's 4 bytes, the add, max and store one operation + * the column's 4 bytes, the add, max and store one operation; + * u32_ops: those lanes, the operations apart (interpreted) * roots a batch of i, each lane's Newton rounds while it goes on * Built cc -O2 -std=c17 -I../040-against-c batch.c -lm (the batch operations * at -O3: their loops made vector), as join.c and bfs.c; their runs in @@ -233,6 +234,55 @@ __attribute__((optimize("O3"))) static void u32_addk_max_store(uint32_t *restric *over |= o; if (!o) for (unsigned l = 0; l < n; ++l) to[l] = tmp[l]; } +/* The same as interpreted operations over lanes of four bytes (no operation fused): the store last, made only when no check failed */ +__attribute__((optimize("O3"))) static void u32_loads(uint32_t *restrict d, const uint32_t *restrict col, int64_t low, unsigned n) { + for (unsigned l = 0; l < n; ++l) d[l] = col[low + l]; +} +__attribute__((optimize("O3"))) static void u32_addk(uint32_t *restrict d, const uint32_t *restrict a, uint32_t k, unsigned n, uint32_t *over) { + uint32_t o = 0; + for (unsigned l = 0; l < n; ++l) { uint32_t x = a[l] + k; o |= x < k; d[l] = x; } + *over |= o; +} +__attribute__((optimize("O3"))) static void u32_max(uint32_t *restrict d, const uint32_t *restrict a, const uint32_t *restrict b, unsigned n) { + for (unsigned l = 0; l < n; ++l) d[l] = a[l] > b[l] ? a[l] : b[l]; +} +__attribute__((optimize("O3"))) static void u32_stores(uint32_t *restrict col, int64_t low, const uint32_t *restrict v, unsigned n) { + for (unsigned l = 0; l < n; ++l) col[low + l] = v[l]; +} +enum { Q_LOADS, Q_ADDK, Q_MAX, Q_STORES }; +typedef struct { uint8_t op, d, a, b; uint32_t k; int64_t low; uint32_t *col; } QOp; +static void run32(const QOp *prog, unsigned ops, uint32_t (*r)[B], unsigned n, uint32_t *over) { + for (unsigned p = 0; p < ops; ++p) { + const QOp *o = &prog[p]; + switch (o->op) { + case Q_LOADS: u32_loads(r[o->d], o->col, o->low, n); break; + case Q_ADDK: u32_addk(r[o->d], r[o->a], o->k, n, over); break; + case Q_MAX: u32_max(r[o->d], r[o->a], r[o->b], n); break; + case Q_STORES: if (!*over) u32_stores(o->col, o->low, r[o->a], n); break; + } + } +} +static double knapsack_u32_ops(uint32_t n, uint32_t capacity, const uint32_t *weight, const uint32_t *worth, uint32_t *best) { + static uint32_t r[4][B]; + uint32_t over = 0; + QOp prog[] = { + {Q_LOADS, 0, 0, 0, 0, 0, best}, /* best[c - w], lanes ascending in memory (the batch's rounds read before any writes) */ + {Q_ADDK, 0, 0, 0, 0, 0, NULL}, /* + worth, past 32 bits a failed check */ + {Q_LOADS, 1, 0, 0, 0, 0, best}, /* best[c] */ + {Q_MAX, 2, 0, 1, 0, 0, NULL}, + {Q_STORES, 0, 2, 0, 0, 0, best}, + }; + for (uint32_t i = 0; i < n; ++i) { + uint32_t rounds = capacity + 1 - weight[i]; + for (uint32_t k = 0; k < rounds; k += B) { + unsigned m = rounds - k < B ? rounds - k : B; + int64_t low = (int64_t)capacity - k - (m - 1); + prog[0].low = low - weight[i], prog[1].k = worth[i], prog[2].low = low, prog[4].low = low; + run32(prog, 5, r, m, &over); + } + } + return over ? -1 : best[capacity]; +} static double knapsack_u32(uint32_t n, uint32_t capacity, const uint32_t *weight, const uint32_t *worth, uint32_t *best) { uint32_t over = 0; for (uint32_t i = 0; i < n; ++i) { @@ -408,7 +458,7 @@ int main(void) { weight[i] = minstd_next() % 1000 + 1; worth[i] = minstd_next() % 1000; } - double kc[11], k6[11], k3[11], kv[11], kk[11], kb[11], ku[11], kgot[6]; + double kc[11], k6[11], k3[11], kv[11], kk[11], kb[11], ku[11], ko[11], kgot[7]; uint32_t kin[2] = {items, capacity}; for (int r = 0; r < 11; ++r) { TIME(kc[r], natural[1](kin, out)); @@ -426,11 +476,13 @@ int main(void) { TIME(kb[r], kgot[3] = knapsack(items, capacity, weight, worth, best)); memset(best, 0, 4 * (capacity + 1)); TIME(ku[r], kgot[4] = knapsack_u32(items, capacity, weight, worth, best)); + memset(best, 0, 4 * (capacity + 1)); + TIME(ko[r], kgot[6] = knapsack_u32_ops(items, capacity, weight, worth, best)); } same = true; - for (int g = 0; g < 6; ++g) same &= kgot[g] == want; - printf("{\"work\":\"knapsack\",\"c_natural_ms\":%.2f,\"c_ms\":%.2f,\"c_u32_ms\":%.2f,\"c_vec_ms\":%.2f,\"c_block_ms\":%.2f,\"batch_ms\":%.2f,\"u32_ms\":%.2f,\"same\":%s}\n", - MEDIAN(kc), MEDIAN(k6), MEDIAN(k3), MEDIAN(kv), MEDIAN(kk), MEDIAN(kb), MEDIAN(ku), same ? "true" : "false"); + for (int g = 0; g < 7; ++g) same &= kgot[g] == want; + printf("{\"work\":\"knapsack\",\"c_natural_ms\":%.2f,\"c_ms\":%.2f,\"c_u32_ms\":%.2f,\"c_vec_ms\":%.2f,\"c_block_ms\":%.2f,\"batch_ms\":%.2f,\"u32_ms\":%.2f,\"u32_ops_ms\":%.2f,\"same\":%s}\n", + MEDIAN(kc), MEDIAN(k6), MEDIAN(k3), MEDIAN(kv), MEDIAN(kk), MEDIAN(kb), MEDIAN(ku), MEDIAN(ko), same ? "true" : "false"); /* roots, 100,000 */ double rc[11], rb[11], rgot = 0, steps; uint32_t rin[1] = {sizes[3]}; |