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