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