lib/sorter/sort-test.c

   1 /*
   2  *      UCW Library -- Testing the Sorter
   3  *
   4  *      (c) 2007 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #include "lib/lib.h"
  11 #include "lib/getopt.h"
  12 #include "lib/conf.h"
  13 #include "lib/fastbuf.h"
  14 #include "lib/hashfunc.h"
  15 #include "lib/md5.h"
  16
  17 #include <stdlib.h>
  18 #include <stdio.h>
  19 #include <string.h>
  20 #include <fcntl.h>
  21 #include <unistd.h>
  22
  23 /*** Time measurement ***/
  24
  25 static timestamp_t timer;
  26
  27 static void
  28 start(void)
  29 {
  30   sync();
  31   init_timer(&timer);
  32 }
  33
  34 static void
  35 stop(void)
  36 {
  37   sync();
  38   log(L_INFO, "Test took %.3fs", get_timer(&timer) / 1000.);
  39 }
  40
  41 /*** Simple 4-byte integer keys ***/
  42
  43 struct key1 {
  44   u32 x;
  45 };
  46
  47 #define SORT_KEY_REGULAR struct key1
  48 #define SORT_PREFIX(x) s1_##x
  49 #define SORT_INPUT_FB
  50 #define SORT_OUTPUT_FB
  51 #define SORT_UNIQUE
  52 #define SORT_INT(k) (k).x
  53
  54 #include "lib/sorter/sorter.h"
  55
  56 static void
  57 test_int(int mode, u64 size)
  58 {
  59   uns N = size ? nextprime(MIN(size/4, 0xffff0000)) : 0;
  60   uns K = N/4*3;
  61   log(L_INFO, ">>> Integers (%s, N=%u)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);
  62
  63   struct fastbuf *f = bopen_tmp(65536);
  64   for (uns i=0; i<N; i++)
  65     bputl(f, (mode==0) ? i : (mode==1) ? N-1-i : ((u64)i * K + 17) % N);
  66   brewind(f);
  67
  68   start();
  69   f = s1_sort(f, NULL, N-1);
  70   stop();
  71
  72   SORT_XTRACE(2, "Verifying");
  73   for (uns i=0; i<N; i++)
  74     {
  75       uns j = bgetl(f);
  76       if (i != j)
  77         die("Discrepancy: %u instead of %u", j, i);
  78     }
  79   bclose(f);
  80 }
  81
  82 /*** Integers with merging, but no data ***/
  83
  84 struct key2 {
  85   u32 x;
  86   u32 cnt;
  87 };
  88
  89 static inline void s2_write_merged(struct fastbuf *f, struct key2 **k, void **d UNUSED, uns n, void *buf UNUSED)
  90 {
  91   for (uns i=1; i<n; i++)
  92     k[0]->cnt += k[i]->cnt;
  93   bwrite(f, k[0], sizeof(struct key2));
  94 }
  95
  96 static inline void s2_copy_merged(struct key2 **k, struct fastbuf **d UNUSED, uns n, struct fastbuf *dest)
  97 {
  98   for (uns i=1; i<n; i++)
  99     k[0]->cnt += k[i]->cnt;
 100   bwrite(dest, k[0], sizeof(struct key2));
 101 }
 102
 103 #define SORT_KEY_REGULAR struct key2
 104 #define SORT_PREFIX(x) s2_##x
 105 #define SORT_INPUT_FB
 106 #define SORT_OUTPUT_FB
 107 #define SORT_UNIFY
 108 #define SORT_INT(k) (k).x
 109
 110 #include "lib/sorter/sorter.h"
 111
 112 static void
 113 test_counted(int mode, u64 size)
 114 {
 115   u64 items = size / sizeof(struct key2);
 116   uns mult = 2;
 117   while (items/(2*mult) > 0xffff0000)
 118     mult++;
 119   uns N = items ? nextprime(items/(2*mult)) : 0;
 120   uns K = N/4*3;
 121   log(L_INFO, ">>> Counted integers (%s, N=%u, mult=%u)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N, mult);
 122
 123   struct fastbuf *f = bopen_tmp(65536);
 124   for (uns m=0; m<mult; m++)
 125     for (uns i=0; i<N; i++)
 126       for (uns j=0; j<2; j++)
 127         {
 128           bputl(f, (mode==0) ? (i%N) : (mode==1) ? N-1-(i%N) : ((u64)i * K + 17) % N);
 129           bputl(f, 1);
 130         }
 131   brewind(f);
 132
 133   start();
 134   f = s2_sort(f, NULL, N-1);
 135   stop();
 136
 137   SORT_XTRACE(2, "Verifying");
 138   for (uns i=0; i<N; i++)
 139     {
 140       uns j = bgetl(f);
 141       if (i != j)
 142         die("Discrepancy: %u instead of %u", j, i);
 143       uns k = bgetl(f);
 144       if (k != 2*mult)
 145         die("Discrepancy: %u has count %u instead of %u", j, k, mult);
 146     }
 147   bclose(f);
 148 }
 149
 150 /*** Longer records with hashes (similar to Shepherd's index records) ***/
 151
 152 struct key3 {
 153   u32 hash[4];
 154   u32 i;
 155   u32 payload[3];
 156 };
 157
 158 static inline int s3_compare(struct key3 *x, struct key3 *y)
 159 {
 160   /* FIXME: Maybe unroll manually? */
 161   for (uns i=0; i<4; i++)
 162     COMPARE(x->hash[i], y->hash[i]);
 163   return 0;
 164 }
 165
 166 static inline uns s3_hash(struct key3 *x)
 167 {
 168   return x->hash[0];
 169 }
 170
 171 #define SORT_KEY_REGULAR struct key3
 172 #define SORT_PREFIX(x) s3_##x
 173 #define SORT_INPUT_FB
 174 #define SORT_OUTPUT_FB
 175 #define SORT_HASH_BITS 32
 176
 177 #include "lib/sorter/sorter.h"
 178
 179 static void
 180 gen_hash_key(int mode, struct key3 *k, uns i)
 181 {
 182   k->i = i;
 183   k->payload[0] = 7*i + 13;
 184   k->payload[1] = 13*i + 19;
 185   k->payload[2] = 19*i + 7;
 186   switch (mode)
 187     {
 188     case 0:
 189       k->hash[0] = i;
 190       k->hash[1] = k->payload[0];
 191       k->hash[2] = k->payload[1];
 192       k->hash[3] = k->payload[2];
 193       break;
 194     case 1:
 195       k->hash[0] = ~i;
 196       k->hash[1] = k->payload[0];
 197       k->hash[2] = k->payload[1];
 198       k->hash[3] = k->payload[2];
 199       break;
 200     default: ;
 201       struct MD5Context ctx;
 202       MD5Init(&ctx);
 203       MD5Update(&ctx, (byte*) &k->i, 4);
 204       MD5Final((byte*) &k->hash, &ctx);
 205       break;
 206     }
 207 }
 208
 209 static void
 210 test_hashes(int mode, u64 size)
 211 {
 212   uns N = MIN(size / sizeof(struct key3), 0xffffffff);
 213   log(L_INFO, ">>> Hashes (%s, N=%u)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);
 214   struct key3 k, lastk;
 215
 216   struct fastbuf *f = bopen_tmp(65536);
 217   uns hash_sum = 0;
 218   for (uns i=0; i<N; i++)
 219     {
 220       gen_hash_key(mode, &k, i);
 221       hash_sum += k.hash[3];
 222       bwrite(f, &k, sizeof(k));
 223     }
 224   brewind(f);
 225
 226   start();
 227   f = s3_sort(f, NULL);
 228   stop();
 229
 230   SORT_XTRACE(2, "Verifying");
 231   for (uns i=0; i<N; i++)
 232     {
 233       int ok = breadb(f, &k, sizeof(k));
 234       ASSERT(ok);
 235       if (i && s3_compare(&k, &lastk) <= 0)
 236         ASSERT(0);
 237       gen_hash_key(mode, &lastk, k.i);
 238       if (memcmp(&k, &lastk, sizeof(k)))
 239         ASSERT(0);
 240       hash_sum -= k.hash[3];
 241     }
 242   ASSERT(!hash_sum);
 243   bclose(f);
 244 }
 245
 246 /*** Variable-length records (strings) with and without var-length data ***/
 247
 248 #define KEY4_MAX 256
 249
 250 struct key4 {
 251   uns len;
 252   byte s[KEY4_MAX];
 253 };
 254
 255 static inline int s4_compare(struct key4 *x, struct key4 *y)
 256 {
 257   uns l = MIN(x->len, y->len);
 258   int c = memcmp(x->s, y->s, l);
 259   if (c)
 260     return c;
 261   COMPARE(x->len, y->len);
 262   return 0;
 263 }
 264
 265 static inline int s4_read_key(struct fastbuf *f, struct key4 *x)
 266 {
 267   x->len = bgetl(f);
 268   if (x->len == 0xffffffff)
 269     return 0;
 270   ASSERT(x->len < KEY4_MAX);
 271   breadb(f, x->s, x->len);
 272   return 1;
 273 }
 274
 275 static inline void s4_write_key(struct fastbuf *f, struct key4 *x)
 276 {
 277   ASSERT(x->len < KEY4_MAX);
 278   bputl(f, x->len);
 279   bwrite(f, x->s, x->len);
 280 }
 281
 282 #define SORT_KEY struct key4
 283 #define SORT_PREFIX(x) s4_##x
 284 #define SORT_KEY_SIZE(x) (sizeof(struct key4) - KEY4_MAX + (x).len)
 285 #define SORT_INPUT_FB
 286 #define SORT_OUTPUT_FB
 287
 288 #include "lib/sorter/sorter.h"
 289
 290 #define s4b_compare s4_compare
 291 #define s4b_read_key s4_read_key
 292 #define s4b_write_key s4_write_key
 293
 294 static inline uns s4_data_size(struct key4 *x)
 295 {
 296   return x->len ? (x->s[0] ^ 0xad) : 0;
 297 }
 298
 299 #define SORT_KEY struct key4
 300 #define SORT_PREFIX(x) s4b_##x
 301 #define SORT_KEY_SIZE(x) (sizeof(struct key4) - KEY4_MAX + (x).len)
 302 #define SORT_DATA_SIZE(x) s4_data_size(&(x))
 303 #define SORT_INPUT_FB
 304 #define SORT_OUTPUT_FB
 305
 306 #include "lib/sorter/sorter.h"
 307
 308 static void
 309 gen_key4(struct key4 *k)
 310 {
 311   k->len = random_max(KEY4_MAX);
 312   for (uns i=0; i<k->len; i++)
 313     k->s[i] = random();
 314 }
 315
 316 static void
 317 gen_data4(byte *buf, uns len, uns h)
 318 {
 319   while (len--)
 320     {
 321       *buf++ = h >> 24;
 322       h = h*259309 + 17;
 323     }
 324 }
 325
 326 static void
 327 test_strings(uns mode, u64 size)
 328 {
 329   uns avg_item_size = KEY4_MAX/2 + 4 + (mode ? 128 : 0);
 330   uns N = MIN(size / avg_item_size, 0xffffffff);
 331   log(L_INFO, ">>> Strings %s(N=%u)", (mode ? "with data " : ""), N);
 332   srand(1);
 333
 334   struct key4 k, lastk;
 335   byte buf[256], buf2[256];
 336   uns sum = 0;
 337
 338   struct fastbuf *f = bopen_tmp(65536);
 339   for (uns i=0; i<N; i++)
 340     {
 341       gen_key4(&k);
 342       s4_write_key(f, &k);
 343       uns h = hash_block(k.s, k.len);
 344       sum += h;
 345       if (mode)
 346         {
 347           gen_data4(buf, s4_data_size(&k), h);
 348           bwrite(f, buf, s4_data_size(&k));
 349         }
 350     }
 351   brewind(f);
 352
 353   start();
 354   f = (mode ? s4b_sort : s4_sort)(f, NULL);
 355   stop();
 356
 357   SORT_XTRACE(2, "Verifying");
 358   for (uns i=0; i<N; i++)
 359     {
 360       int ok = s4_read_key(f, &k);
 361       ASSERT(ok);
 362       uns h = hash_block(k.s, k.len);
 363       if (mode && s4_data_size(&k))
 364         {
 365           ok = breadb(f, buf, s4_data_size(&k));
 366           ASSERT(ok);
 367           gen_data4(buf2, s4_data_size(&k), h);
 368           ASSERT(!memcmp(buf, buf2, s4_data_size(&k)));
 369         }
 370       if (i && s4_compare(&k, &lastk) < 0)
 371         ASSERT(0);
 372       sum -= h;
 373       lastk = k;
 374     }
 375   ASSERT(!sum);
 376   bclose(f);
 377 }
 378
 379 /*** Graph-like structure with custom presorting ***/
 380
 381 struct key5 {
 382   u32 x;
 383   u32 cnt;
 384 };
 385
 386 static uns s5_N, s5_K, s5_L, s5_i, s5_j;
 387
 388 struct s5_pair {
 389   uns x, y;
 390 };
 391
 392 static int s5_gen(struct s5_pair *p)
 393 {
 394   if (s5_j >= s5_N)
 395     {
 396       if (s5_i >= s5_N-1)
 397         return 0;
 398       s5_j = 0;
 399       s5_i++;
 400     }
 401   p->x = ((u64)s5_j * s5_K) % s5_N;
 402   p->y = ((u64)(s5_i + s5_j) * s5_L) % s5_N;
 403   s5_j++;
 404   return 1;
 405 }
 406
 407 #define ASORT_PREFIX(x) s5m_##x
 408 #define ASORT_KEY_TYPE u32
 409 #define ASORT_ELT(i) ary[i]
 410 #define ASORT_EXTRA_ARGS , u32 *ary
 411 #include "lib/arraysort.h"
 412
 413 static void s5_write_merged(struct fastbuf *f, struct key5 **keys, void **data, uns n, void *buf)
 414 {
 415   u32 *a = buf;
 416   uns m = 0;
 417   for (uns i=0; i<n; i++)
 418     {
 419       memcpy(&a[m], data[i], 4*keys[i]->cnt);
 420       m += keys[i]->cnt;
 421     }
 422   s5m_sort(m, a);
 423   keys[0]->cnt = m;
 424   bwrite(f, keys[0], sizeof(struct key5));
 425   bwrite(f, a, 4*m);                    /* FIXME: Might overflow here */
 426 }
 427
 428 static void s5_copy_merged(struct key5 **keys, struct fastbuf **data, uns n, struct fastbuf *dest)
 429 {
 430   u32 k[n];
 431   uns m = 0;
 432   for (uns i=0; i<n; i++)
 433     {
 434       k[i] = bgetl(data[i]);
 435       m += keys[i]->cnt;
 436     }
 437   struct key5 key = { .x = keys[0]->x, .cnt = m };
 438   bwrite(dest, &key, sizeof(key));
 439   while (key.cnt--)
 440     {
 441       uns b = 0;
 442       for (uns i=1; i<n; i++)
 443         if (k[i] < k[b])
 444           b = i;
 445       bputl(dest, k[b]);
 446       if (--keys[b]->cnt)
 447         k[b] = bgetl(data[b]);
 448       else
 449         k[b] = ~0U;
 450     }
 451 }
 452
 453 static inline int s5p_lt(struct s5_pair x, struct s5_pair y)
 454 {
 455   COMPARE_LT(x.x, y.x);
 456   COMPARE_LT(x.y, y.y);
 457   return 0;
 458 }
 459
 460 /* FIXME: Use smarter internal sorter when it's available */
 461 #define ASORT_PREFIX(x) s5p_##x
 462 #define ASORT_KEY_TYPE struct s5_pair
 463 #define ASORT_ELT(i) ary[i]
 464 #define ASORT_LT(x,y) s5p_lt(x,y)
 465 #define ASORT_EXTRA_ARGS , struct s5_pair *ary
 466 #include "lib/arraysort.h"
 467
 468 static int s5_presort(struct fastbuf *dest, void *buf, size_t bufsize)
 469 {
 470   uns max = MIN(bufsize/sizeof(struct s5_pair), 0xffffffff);
 471   struct s5_pair *a = buf;
 472   uns n = 0;
 473   while (n<max && s5_gen(&a[n]))
 474     n++;
 475   if (!n)
 476     return 0;
 477   s5p_sort(n, a);
 478   uns i = 0;
 479   while (i < n)
 480     {
 481       uns j = i;
 482       while (i < n && a[i].x == a[j].x)
 483         i++;
 484       struct key5 k = { .x = a[j].x, .cnt = i-j };
 485       bwrite(dest, &k, sizeof(k));
 486       while (j < i)
 487         bputl(dest, a[j++].y);
 488     }
 489   return 1;
 490 }
 491
 492 #define SORT_KEY_REGULAR struct key5
 493 #define SORT_PREFIX(x) s5_##x
 494 #define SORT_DATA_SIZE(k) (4*(k).cnt)
 495 #define SORT_UNIFY
 496 #define SORT_INPUT_PRESORT
 497 #define SORT_OUTPUT_THIS_FB
 498 #define SORT_INT(k) (k).x
 499
 500 #include "lib/sorter/sorter.h"
 501
 502 #define SORT_KEY_REGULAR struct key5
 503 #define SORT_PREFIX(x) s5b_##x
 504 #define SORT_DATA_SIZE(k) (4*(k).cnt)
 505 #define SORT_UNIFY
 506 #define SORT_INPUT_FB
 507 #define SORT_OUTPUT_THIS_FB
 508 #define SORT_INT(k) (k).x
 509 #define s5b_write_merged s5_write_merged
 510 #define s5b_copy_merged s5_copy_merged
 511
 512 #include "lib/sorter/sorter.h"
 513
 514 static void
 515 test_graph(uns mode, u64 size)
 516 {
 517   uns N = 3;
 518   while ((u64)N*(N+2)*4 < size)
 519     N = nextprime(N);
 520   log(L_INFO, ">>> Graph%s (N=%u)", (mode ? "" : " with custom presorting"), N);
 521   s5_N = N;
 522   s5_K = N/4*3;
 523   s5_L = N/3*2;
 524   s5_i = s5_j = 0;
 525
 526   struct fastbuf *in = NULL;
 527   if (mode)
 528     {
 529       struct s5_pair p;
 530       in = bopen_tmp(65536);
 531       while (s5_gen(&p))
 532         {
 533           struct key5 k = { .x = p.x, .cnt = 1 };
 534           bwrite(in, &k, sizeof(k));
 535           bputl(in, p.y);
 536         }
 537       brewind(in);
 538     }
 539
 540   start();
 541   struct fastbuf *f = bopen_tmp(65536);
 542   bputl(f, 0xfeedcafe);
 543   struct fastbuf *g = (mode ? s5b_sort(in, f, s5_N-1) : s5_sort(NULL, f, s5_N-1));
 544   ASSERT(f == g);
 545   stop();
 546
 547   SORT_XTRACE(2, "Verifying");
 548   uns c = bgetl(f);
 549   ASSERT(c == 0xfeedcafe);
 550   for (uns i=0; i<N; i++)
 551     {
 552       struct key5 k;
 553       int ok = breadb(f, &k, sizeof(k));
 554       ASSERT(ok);
 555       ASSERT(k.x == i);
 556       ASSERT(k.cnt == N);
 557       for (uns j=0; j<N; j++)
 558         {
 559           uns y = bgetl(f);
 560           ASSERT(y == j);
 561         }
 562     }
 563   bclose(f);
 564 }
 565
 566 /*** Main ***/
 567
 568 static void
 569 run_test(uns i, u64 size)
 570 {
 571   switch (i)
 572     {
 573     case 0:
 574       test_int(0, size); break;
 575     case 1:
 576       test_int(1, size); break;
 577     case 2:
 578       test_int(2, size); break;
 579     case 3:
 580       test_counted(0, size); break;
 581     case 4:
 582       test_counted(1, size); break;
 583     case 5:
 584       test_counted(2, size); break;
 585     case 6:
 586       test_hashes(0, size); break;
 587     case 7:
 588       test_hashes(1, size); break;
 589     case 8:
 590       test_hashes(2, size); break;
 591     case 9:
 592       test_strings(0, size); break;
 593     case 10:
 594       test_strings(1, size); break;
 595     case 11:
 596       test_graph(0, size); break;
 597     case 12:
 598       test_graph(1, size); break;
 599 #define TMAX 13
 600     }
 601 }
 602
 603 int
 604 main(int argc, char **argv)
 605 {
 606   log_init(NULL);
 607   int c;
 608   u64 size = 10000000;
 609   uns t = ~0;
 610
 611   while ((c = cf_getopt(argc, argv, CF_SHORT_OPTS "d:s:t:v", CF_NO_LONG_OPTS, NULL)) >= 0)
 612     switch (c)
 613       {
 614       case 'd':
 615         sorter_debug = atol(optarg);
 616         break;
 617       case 's':
 618         if (cf_parse_u64(optarg, &size))
 619           goto usage;
 620         break;
 621       case 't':
 622         t = atol(optarg);
 623         if (t >= TMAX)
 624           goto usage;
 625         break;
 626       case 'v':
 627         sorter_trace++;
 628         break;
 629       default:
 630       usage:
 631         fputs("Usage: sort-test [-v] [-d <debug>] [-s <size>] [-t <test>]\n", stderr);
 632         exit(1);
 633       }
 634   if (optind != argc)
 635     goto usage;
 636
 637   if (t != ~0U)
 638     run_test(t, size);
 639   else
 640     for (uns i=0; i<TMAX; i++)
 641       run_test(i, size);
 642
 643   return 0;
 644 }