2 * UCW Library -- Testing the Sorter
4 * (c) 2007 Martin Mares <mj@ucw.cz>
6 * This software may be freely distributed and used according to the terms
7 * of the GNU Lesser General Public License.
11 #include "lib/getopt.h"
13 #include "lib/fastbuf.h"
14 #include "lib/hashfunc.h"
22 /*** Time measurement ***/
33 log(L_INFO, "Test took %.3fs", get_timer() / 1000.);
36 /*** Simple 4-byte integer keys ***/
42 #define SORT_KEY_REGULAR struct key1
43 #define SORT_PREFIX(x) s1_##x
45 #define SORT_OUTPUT_FB
47 #define SORT_INT(k) (k).x
49 #include "lib/sorter/sorter.h"
52 test_int(int mode, u64 size)
54 uns N = nextprime(MIN(size/4, 0xffff0000));
56 log(L_INFO, ">>> Integers (%s, N=%d)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);
58 struct fastbuf *f = bopen_tmp(65536);
59 for (uns i=0; i<N; i++)
60 bputl(f, (mode==0) ? i : (mode==1) ? N-1-i : ((u64)i * K + 17) % N);
64 f = s1_sort(f, NULL, N-1);
67 SORT_XTRACE(2, "Verifying");
68 for (uns i=0; i<N; i++)
72 die("Discrepancy: %d instead of %d", j, i);
77 /*** Integers with merging, but no data ***/
84 static inline void s2_write_merged(struct fastbuf *f, struct key2 **k, void **d UNUSED, uns n, void *buf UNUSED)
86 for (uns i=1; i<n; i++)
87 k[0]->cnt += k[i]->cnt;
88 bwrite(f, k[0], sizeof(struct key2));
91 static inline void s2_copy_merged(struct key2 **k, struct fastbuf **d UNUSED, uns n, struct fastbuf *dest)
93 for (uns i=1; i<n; i++)
94 k[0]->cnt += k[i]->cnt;
95 bwrite(dest, k[0], sizeof(struct key2));
98 #define SORT_KEY_REGULAR struct key2
99 #define SORT_PREFIX(x) s2_##x
100 #define SORT_INPUT_FB
101 #define SORT_OUTPUT_FB
103 #define SORT_INT(k) (k).x
105 #include "lib/sorter/sorter.h"
108 test_counted(int mode, u64 size)
110 u64 items = size / sizeof(struct key2);
112 while (items/(2*mult) > 0xffff0000)
114 uns N = nextprime(items/(2*mult));
116 log(L_INFO, ">>> Counted integers (%s, N=%d, mult=%d)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N, mult);
118 struct fastbuf *f = bopen_tmp(65536);
119 for (uns m=0; m<mult; m++)
120 for (uns i=0; i<N; i++)
121 for (uns j=0; j<2; j++)
123 bputl(f, (mode==0) ? (i%N) : (mode==1) ? N-1-(i%N) : ((u64)i * K + 17) % N);
129 f = s2_sort(f, NULL, N-1);
132 SORT_XTRACE(2, "Verifying");
133 for (uns i=0; i<N; i++)
137 die("Discrepancy: %d instead of %d", j, i);
140 die("Discrepancy: %d has count %d instead of %d", j, k, mult);
145 /*** Longer records with hashes (similar to Shepherd's index records) ***/
153 static inline int s3_compare(struct key3 *x, struct key3 *y)
155 /* FIXME: Maybe unroll manually? */
156 for (uns i=0; i<4; i++)
157 COMPARE(x->hash[i], y->hash[i]);
161 static inline uns s3_hash(struct key3 *x)
166 #define SORT_KEY_REGULAR struct key3
167 #define SORT_PREFIX(x) s3_##x
168 #define SORT_INPUT_FB
169 #define SORT_OUTPUT_FB
170 #define SORT_HASH_BITS 32
172 #include "lib/sorter/sorter.h"
175 gen_hash_key(int mode, struct key3 *k, uns i)
178 k->payload[0] = 7*i + 13;
179 k->payload[1] = 13*i + 19;
180 k->payload[2] = 19*i + 7;
185 k->hash[1] = k->payload[0];
186 k->hash[2] = k->payload[1];
187 k->hash[3] = k->payload[2];
191 k->hash[1] = k->payload[0];
192 k->hash[2] = k->payload[1];
193 k->hash[3] = k->payload[2];
196 struct MD5Context ctx;
198 MD5Update(&ctx, (byte*) &k->i, 4);
199 MD5Final((byte*) &k->hash, &ctx);
205 test_hashes(int mode, u64 size)
207 uns N = MIN(size / sizeof(struct key3), 0xffffffff);
208 log(L_INFO, ">>> Hashes (%s, N=%d)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);
209 struct key3 k, lastk;
211 struct fastbuf *f = bopen_tmp(65536);
213 for (uns i=0; i<N; i++)
215 gen_hash_key(mode, &k, i);
216 hash_sum += k.hash[3];
217 bwrite(f, &k, sizeof(k));
222 f = s3_sort(f, NULL);
225 SORT_XTRACE(2, "Verifying");
226 for (uns i=0; i<N; i++)
228 int ok = breadb(f, &k, sizeof(k));
230 if (i && s3_compare(&k, &lastk) <= 0)
232 gen_hash_key(mode, &lastk, k.i);
233 if (memcmp(&k, &lastk, sizeof(k)))
235 hash_sum -= k.hash[3];
241 /*** Variable-length records (strings) with and without var-length data ***/
250 static inline int s4_compare(struct key4 *x, struct key4 *y)
252 uns l = MIN(x->len, y->len);
253 int c = memcmp(x->s, y->s, l);
256 COMPARE(x->len, y->len);
260 static inline int s4_read_key(struct fastbuf *f, struct key4 *x)
263 if (x->len == 0xffffffff)
265 ASSERT(x->len < KEY4_MAX);
266 breadb(f, x->s, x->len);
270 static inline void s4_write_key(struct fastbuf *f, struct key4 *x)
272 ASSERT(x->len < KEY4_MAX);
274 bwrite(f, x->s, x->len);
277 #define SORT_KEY struct key4
278 #define SORT_PREFIX(x) s4_##x
279 #define SORT_KEY_SIZE(x) (sizeof(struct key4) - KEY4_MAX + (x).len)
280 #define SORT_INPUT_FB
281 #define SORT_OUTPUT_FB
283 #include "lib/sorter/sorter.h"
285 #define s4b_compare s4_compare
286 #define s4b_read_key s4_read_key
287 #define s4b_write_key s4_write_key
289 static inline uns s4_data_size(struct key4 *x)
291 return x->len ? (x->s[0] ^ 0xad) : 0;
294 #define SORT_KEY struct key4
295 #define SORT_PREFIX(x) s4b_##x
296 #define SORT_KEY_SIZE(x) (sizeof(struct key4) - KEY4_MAX + (x).len)
297 #define SORT_DATA_SIZE(x) s4_data_size(&(x))
298 #define SORT_INPUT_FB
299 #define SORT_OUTPUT_FB
301 #include "lib/sorter/sorter.h"
304 gen_key4(struct key4 *k)
306 k->len = random_max(KEY4_MAX);
307 for (uns i=0; i<k->len; i++)
312 gen_data4(byte *buf, uns len, uns h)
322 test_strings(uns mode, u64 size)
324 uns avg_item_size = KEY4_MAX/2 + 4 + (mode ? 128 : 0);
325 uns N = MIN(size / avg_item_size, 0xffffffff);
326 log(L_INFO, ">>> Strings %s(N=%d)", (mode ? "with data " : ""), N);
329 struct key4 k, lastk;
330 byte buf[256], buf2[256];
333 struct fastbuf *f = bopen_tmp(65536);
334 for (uns i=0; i<N; i++)
338 uns h = hash_block(k.s, k.len);
342 gen_data4(buf, s4_data_size(&k), h);
343 bwrite(f, buf, s4_data_size(&k));
349 f = (mode ? s4b_sort : s4_sort)(f, NULL);
352 SORT_XTRACE(2, "Verifying");
353 for (uns i=0; i<N; i++)
355 int ok = s4_read_key(f, &k);
357 uns h = hash_block(k.s, k.len);
358 if (mode && s4_data_size(&k))
360 ok = breadb(f, buf, s4_data_size(&k));
362 gen_data4(buf2, s4_data_size(&k), h);
363 ASSERT(!memcmp(buf, buf2, s4_data_size(&k)));
365 if (i && s4_compare(&k, &lastk) < 0)
375 run_test(uns i, u64 size)
380 test_int(0, size); break;
382 test_int(1, size); break;
384 test_int(2, size); break;
386 test_counted(0, size); break;
388 test_counted(1, size); break;
390 test_counted(2, size); break;
392 test_hashes(0, size); break;
394 test_hashes(1, size); break;
396 test_hashes(2, size); break;
398 test_strings(0, size); break;
400 test_strings(1, size); break;
406 main(int argc, char **argv)
413 while ((c = cf_getopt(argc, argv, CF_SHORT_OPTS "s:t:v", CF_NO_LONG_OPTS, NULL)) >= 0)
417 if (cf_parse_u64(optarg, &size))
430 fputs("Usage: sort-test [-s <size>] [-t <test>]\n", stderr);
439 for (uns i=0; i<TMAX; i++)