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