1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
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;
}
|
