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