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/ff-binary.h"
15 #include "lib/hashfunc.h"
24 /*** Time measurement ***/
26 static timestamp_t timer;
40 msg(L_INFO, "Test %d took %.3fs", test_id, get_timer(&timer) / 1000.);
43 /*** Simple 4-byte integer keys ***/
49 #define SORT_KEY_REGULAR struct key1
50 #define SORT_PREFIX(x) s1_##x
52 #define SORT_OUTPUT_FB
54 #define SORT_INT(k) (k).x
55 #define SORT_DELETE_INPUT 0
57 #include "lib/sorter/sorter.h"
60 test_int(int mode, u64 size)
62 uns N = size ? nextprime(MIN(size/4, 0xffff0000)) : 0;
64 msg(L_INFO, ">>> Integers (%s, N=%u)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);
66 struct fastbuf *f = bopen_tmp(65536);
67 for (uns i=0; i<N; i++)
68 bputl(f, (mode==0) ? i : (mode==1) ? N-1-i : ((u64)i * K + 17) % N);
72 f = s1_sort(f, NULL, N-1);
75 SORT_XTRACE(2, "Verifying");
76 for (uns i=0; i<N; i++)
80 die("Discrepancy: %u instead of %u", j, i);
85 /*** Integers with merging, but no data ***/
92 static inline void s2_write_merged(struct fastbuf *f, struct key2 **k, void **d UNUSED, uns n, void *buf UNUSED)
94 for (uns i=1; i<n; i++)
95 k[0]->cnt += k[i]->cnt;
96 bwrite(f, k[0], sizeof(struct key2));
99 #define SORT_KEY_REGULAR struct key2
100 #define SORT_PREFIX(x) s2_##x
101 #define SORT_INPUT_FB
102 #define SORT_OUTPUT_FB
104 #define SORT_INT(k) (k).x
106 #include "lib/sorter/sorter.h"
109 test_counted(int mode, u64 size)
111 u64 items = size / sizeof(struct key2);
113 while (items/(2*mult) > 0xffff0000)
115 uns N = items ? nextprime(items/(2*mult)) : 0;
117 msg(L_INFO, ">>> Counted integers (%s, N=%u, mult=%u)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N, mult);
119 struct fastbuf *f = bopen_tmp(65536);
120 for (uns m=0; m<mult; m++)
121 for (uns i=0; i<N; i++)
122 for (uns j=0; j<2; j++)
124 bputl(f, (mode==0) ? (i%N) : (mode==1) ? N-1-(i%N) : ((u64)i * K + 17) % N);
130 f = s2_sort(f, NULL, N-1);
133 SORT_XTRACE(2, "Verifying");
134 for (uns i=0; i<N; i++)
138 die("Discrepancy: %u instead of %u", j, i);
141 die("Discrepancy: %u has count %u instead of %u", j, k, 2*mult);
146 /*** Longer records with hashes (similar to Shepherd's index records) ***/
154 static inline int s3_compare(struct key3 *x, struct key3 *y)
156 /* FIXME: Maybe unroll manually? */
157 for (uns i=0; i<4; i++)
158 COMPARE(x->hash[i], y->hash[i]);
162 static inline uns s3_hash(struct key3 *x)
167 #define SORT_KEY_REGULAR struct key3
168 #define SORT_PREFIX(x) s3_##x
169 #define SORT_INPUT_FB
170 #define SORT_OUTPUT_FB
171 #define SORT_HASH_BITS 32
173 #include "lib/sorter/sorter.h"
176 gen_hash_key(int mode, struct key3 *k, uns i)
179 k->payload[0] = 7*i + 13;
180 k->payload[1] = 13*i + 19;
181 k->payload[2] = 19*i + 7;
186 k->hash[1] = k->payload[0];
187 k->hash[2] = k->payload[1];
188 k->hash[3] = k->payload[2];
192 k->hash[1] = k->payload[0];
193 k->hash[2] = k->payload[1];
194 k->hash[3] = k->payload[2];
197 struct MD5Context ctx;
199 MD5Update(&ctx, (byte*) &k->i, 4);
200 MD5Final((byte*) &k->hash, &ctx);
206 test_hashes(int mode, u64 size)
208 uns N = MIN(size / sizeof(struct key3), 0xffffffff);
209 msg(L_INFO, ">>> Hashes (%s, N=%u)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);
210 struct key3 k, lastk;
212 struct fastbuf *f = bopen_tmp(65536);
214 for (uns i=0; i<N; i++)
216 gen_hash_key(mode, &k, i);
217 hash_sum += k.hash[3];
218 bwrite(f, &k, sizeof(k));
223 f = s3_sort(f, NULL);
226 SORT_XTRACE(2, "Verifying");
227 for (uns i=0; i<N; i++)
229 int ok = breadb(f, &k, sizeof(k));
231 if (i && s3_compare(&k, &lastk) <= 0)
233 gen_hash_key(mode, &lastk, k.i);
234 if (memcmp(&k, &lastk, sizeof(k)))
236 hash_sum -= k.hash[3];
242 /*** Variable-length records (strings) with and without var-length data ***/
251 static inline int s4_compare(struct key4 *x, struct key4 *y)
253 uns l = MIN(x->len, y->len);
254 int c = memcmp(x->s, y->s, l);
257 COMPARE(x->len, y->len);
261 static inline int s4_read_key(struct fastbuf *f, struct key4 *x)
264 if (x->len == 0xffffffff)
266 ASSERT(x->len < KEY4_MAX);
267 breadb(f, x->s, x->len);
271 static inline void s4_write_key(struct fastbuf *f, struct key4 *x)
273 ASSERT(x->len < KEY4_MAX);
275 bwrite(f, x->s, x->len);
278 #define SORT_KEY struct key4
279 #define SORT_PREFIX(x) s4_##x
280 #define SORT_KEY_SIZE(x) (sizeof(struct key4) - KEY4_MAX + (x).len)
281 #define SORT_INPUT_FB
282 #define SORT_OUTPUT_FB
284 #include "lib/sorter/sorter.h"
286 #define s4b_compare s4_compare
287 #define s4b_read_key s4_read_key
288 #define s4b_write_key s4_write_key
290 static inline uns s4_data_size(struct key4 *x)
292 return x->len ? (x->s[0] ^ 0xad) : 0;
295 #define SORT_KEY struct key4
296 #define SORT_PREFIX(x) s4b_##x
297 #define SORT_KEY_SIZE(x) (sizeof(struct key4) - KEY4_MAX + (x).len)
298 #define SORT_DATA_SIZE(x) s4_data_size(&(x))
299 #define SORT_INPUT_FB
300 #define SORT_OUTPUT_FB
302 #include "lib/sorter/sorter.h"
305 gen_key4(struct key4 *k)
307 k->len = random_max(KEY4_MAX);
308 for (uns i=0; i<k->len; i++)
313 gen_data4(byte *buf, uns len, uns h)
323 test_strings(uns mode, u64 size)
325 uns avg_item_size = KEY4_MAX/2 + 4 + (mode ? 128 : 0);
326 uns N = MIN(size / avg_item_size, 0xffffffff);
327 msg(L_INFO, ">>> Strings %s(N=%u)", (mode ? "with data " : ""), N);
330 struct key4 k, lastk;
331 byte buf[256], buf2[256];
334 struct fastbuf *f = bopen_tmp(65536);
335 for (uns i=0; i<N; i++)
339 uns h = hash_block(k.s, k.len);
343 gen_data4(buf, s4_data_size(&k), h);
344 bwrite(f, buf, s4_data_size(&k));
350 f = (mode ? s4b_sort : s4_sort)(f, NULL);
353 SORT_XTRACE(2, "Verifying");
354 for (uns i=0; i<N; i++)
356 int ok = s4_read_key(f, &k);
358 uns h = hash_block(k.s, k.len);
359 if (mode && s4_data_size(&k))
361 ok = breadb(f, buf, s4_data_size(&k));
363 gen_data4(buf2, s4_data_size(&k), h);
364 ASSERT(!memcmp(buf, buf2, s4_data_size(&k)));
366 if (i && s4_compare(&k, &lastk) < 0)
375 /*** Graph-like structure with custom presorting ***/
382 static uns s5_N, s5_K, s5_L, s5_i, s5_j;
388 static int s5_gen(struct s5_pair *p)
397 p->x = ((u64)s5_j * s5_K) % s5_N;
398 p->y = ((u64)(s5_i + s5_j) * s5_L) % s5_N;
403 #define ASORT_PREFIX(x) s5m_##x
404 #define ASORT_KEY_TYPE u32
405 #define ASORT_ELT(i) ary[i]
406 #define ASORT_EXTRA_ARGS , u32 *ary
407 #include "lib/arraysort.h"
409 static void s5_write_merged(struct fastbuf *f, struct key5 **keys, void **data, uns n, void *buf)
413 for (uns i=0; i<n; i++)
415 memcpy(&a[m], data[i], 4*keys[i]->cnt);
420 bwrite(f, keys[0], sizeof(struct key5));
421 bwrite(f, a, 4*m); /* FIXME: Might overflow here */
424 static void s5_copy_merged(struct key5 **keys, struct fastbuf **data, uns n, struct fastbuf *dest)
428 for (uns i=0; i<n; i++)
430 k[i] = bgetl(data[i]);
433 struct key5 key = { .x = keys[0]->x, .cnt = m };
434 bwrite(dest, &key, sizeof(key));
438 for (uns i=1; i<n; i++)
443 k[b] = bgetl(data[b]);
449 static inline int s5p_lt(struct s5_pair x, struct s5_pair y)
451 COMPARE_LT(x.x, y.x);
452 COMPARE_LT(x.y, y.y);
456 /* FIXME: Use smarter internal sorter when it's available */
457 #define ASORT_PREFIX(x) s5p_##x
458 #define ASORT_KEY_TYPE struct s5_pair
459 #define ASORT_ELT(i) ary[i]
460 #define ASORT_LT(x,y) s5p_lt(x,y)
461 #define ASORT_EXTRA_ARGS , struct s5_pair *ary
462 #include "lib/arraysort.h"
464 static int s5_presort(struct fastbuf *dest, void *buf, size_t bufsize)
466 uns max = MIN(bufsize/sizeof(struct s5_pair), 0xffffffff);
467 struct s5_pair *a = buf;
469 while (n<max && s5_gen(&a[n]))
478 while (i < n && a[i].x == a[j].x)
480 struct key5 k = { .x = a[j].x, .cnt = i-j };
481 bwrite(dest, &k, sizeof(k));
483 bputl(dest, a[j++].y);
488 #define SORT_KEY_REGULAR struct key5
489 #define SORT_PREFIX(x) s5_##x
490 #define SORT_DATA_SIZE(k) (4*(k).cnt)
492 #define SORT_UNIFY_WORKSPACE(k) SORT_DATA_SIZE(k)
493 #define SORT_INPUT_PRESORT
494 #define SORT_OUTPUT_THIS_FB
495 #define SORT_INT(k) (k).x
497 #include "lib/sorter/sorter.h"
499 #define SORT_KEY_REGULAR struct key5
500 #define SORT_PREFIX(x) s5b_##x
501 #define SORT_DATA_SIZE(k) (4*(k).cnt)
503 #define SORT_UNIFY_WORKSPACE(k) SORT_DATA_SIZE(k)
504 #define SORT_INPUT_FB
505 #define SORT_OUTPUT_THIS_FB
506 #define SORT_INT(k) (k).x
507 #define s5b_write_merged s5_write_merged
508 #define s5b_copy_merged s5_copy_merged
510 #include "lib/sorter/sorter.h"
513 test_graph(uns mode, u64 size)
516 while ((u64)N*(N+2)*4 < size)
518 msg(L_INFO, ">>> Graph%s (N=%u)", (mode ? "" : " with custom presorting"), N);
524 struct fastbuf *in = NULL;
528 in = bopen_tmp(65536);
531 struct key5 k = { .x = p.x, .cnt = 1 };
532 bwrite(in, &k, sizeof(k));
539 struct fastbuf *f = bopen_tmp(65536);
540 bputl(f, 0xfeedcafe);
541 struct fastbuf *g = (mode ? s5b_sort(in, f, s5_N-1) : s5_sort(NULL, f, s5_N-1));
545 SORT_XTRACE(2, "Verifying");
547 ASSERT(c == 0xfeedcafe);
548 for (uns i=0; i<N; i++)
551 int ok = breadb(f, &k, sizeof(k));
555 for (uns j=0; j<N; j++)
564 /*** Simple 8-byte integer keys ***/
570 #define SORT_KEY_REGULAR struct key6
571 #define SORT_PREFIX(x) s6_##x
572 #define SORT_INPUT_FB
573 #define SORT_OUTPUT_FB
575 #define SORT_INT64(k) (k).x
577 #include "lib/sorter/sorter.h"
580 test_int64(int mode, u64 size)
582 u64 N = size ? nextprime(MIN(size/8, 0xffff0000)) : 0;
584 msg(L_INFO, ">>> 64-bit integers (%s, N=%llu)", ((char *[]) { "increasing", "decreasing", "random" })[mode], (long long)N);
586 struct fastbuf *f = bopen_tmp(65536);
587 for (u64 i=0; i<N; i++)
588 bputq(f, 777777*((mode==0) ? i : (mode==1) ? N-1-i : ((u64)i * K + 17) % N));
592 f = s6_sort(f, NULL, 777777*(N-1));
595 SORT_XTRACE(2, "Verifying");
596 for (u64 i=0; i<N; i++)
600 die("Discrepancy: %llu instead of %llu", (long long)j, 777777*(long long)i);
608 run_test(uns i, u64 size)
614 test_int(0, size); break;
616 test_int(1, size); break;
618 test_int(2, size); break;
620 test_counted(0, size); break;
622 test_counted(1, size); break;
624 test_counted(2, size); break;
626 test_hashes(0, size); break;
628 test_hashes(1, size); break;
630 test_hashes(2, size); break;
632 test_strings(0, size); break;
634 test_strings(1, size); break;
636 test_graph(0, size); break;
638 test_graph(1, size); break;
640 test_int64(0, size); break;
642 test_int64(1, size); break;
644 test_int64(2, size); break;
650 main(int argc, char **argv)
657 while ((c = cf_getopt(argc, argv, CF_SHORT_OPTS "d:s:t:v", CF_NO_LONG_OPTS, NULL)) >= 0)
661 sorter_debug = atol(optarg);
664 if (cf_parse_u64(optarg, &size))
677 fputs("Usage: sort-test [-v] [-d <debug>] [-s <size>] [-t <test>]\n", stderr);
686 for (uns i=0; i<TMAX; i++)