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