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