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