ucw/sorter/debug/retros.c

   1 /*
   2  *  Experiments with various sorting algorithms
   3  *
   4  *  (c) 2007--2008 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 #include <ucw/lib.h>
   8 #include <ucw/getopt.h>
   9 #include <ucw/md5.h>
  10 #include <ucw/heap.h>
  11 #include <ucw/time.h>
  12
  13 #include <stdio.h>
  14 #include <stdlib.h>
  15 #include <string.h>
  16 #include <sys/mman.h>
  17 #include <sys/user.h>
  18
  19 struct elt {
  20   u32 key;
  21   u32 ballast[3];
  22 };
  23
  24 static struct elt *ary, *alt, **ind, *array0, *array1;
  25 static uns n = 10000000;
  26 static u32 sum;
  27
  28 static struct elt *alloc_elts(uns n)
  29 {
  30   return big_alloc(n * sizeof(struct elt));
  31 }
  32
  33 static void free_elts(struct elt *a, uns n)
  34 {
  35   big_free(a, n * sizeof(struct elt));
  36 }
  37
  38 static int comp(const void *x, const void *y)
  39 {
  40   const struct elt *xx = x, *yy = y;
  41   return (xx->key < yy->key) ? -1 : (xx->key > yy->key) ? 1 : 0;
  42 }
  43
  44 static int comp_ind(const void *x, const void *y)
  45 {
  46   const struct elt * const *xx = x, * const *yy = y;
  47   return comp(*xx, *yy);
  48 }
  49
  50 #define ASORT_PREFIX(x) as_##x
  51 #define ASORT_KEY_TYPE u32
  52 #define ASORT_ELT(i) a[i].key
  53 #define ASORT_SWAP(i,j) do { struct elt t=a[i]; a[i]=a[j]; a[j]=t; } while (0)
  54 #define ASORT_EXTRA_ARGS , struct elt *a
  55 #include <ucw/sorter/array-simple.h>
  56
  57 #define ASORT_PREFIX(x) asi_##x
  58 #define ASORT_KEY_TYPE u32
  59 #define ASORT_ELT(i) ind[i]->key
  60 #define ASORT_SWAP(i,j) do { struct elt *t=ind[i]; ind[i]=ind[j]; ind[j]=t; } while (0)
  61 #include <ucw/sorter/array-simple.h>
  62
  63 static void r1_sort(void)
  64 {
  65   struct elt *from = ary, *to = alt, *tmp;
  66 #define BITS 8
  67   uns cnt[1 << BITS];
  68   for (uns sh=0; sh<32; sh+=BITS)
  69     {
  70       bzero(cnt, sizeof(cnt));
  71       for (uns i=0; i<n; i++)
  72         cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++;
  73       uns pos = 0;
  74       for (uns i=0; i<(1<<BITS); i++)
  75         {
  76           uns c = cnt[i];
  77           cnt[i] = pos;
  78           pos += c;
  79         }
  80       ASSERT(pos == n);
  81       for (uns i=0; i<n; i++)
  82         to[cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++] = from[i];
  83       ASSERT(cnt[(1 << BITS)-1] == n);
  84       tmp=from, from=to, to=tmp;
  85     }
  86   ary = from;
  87 #undef BITS
  88 }
  89
  90 static void r1b_sort(void)
  91 {
  92   struct elt *from = ary, *to = alt, *tmp;
  93 #define BITS 8
  94   uns cnt[1 << BITS], cnt2[1 << BITS];
  95   for (uns sh=0; sh<32; sh+=BITS)
  96     {
  97       if (sh)
  98         memcpy(cnt, cnt2, sizeof(cnt));
  99       else
 100         {
 101           bzero(cnt, sizeof(cnt));
 102           for (uns i=0; i<n; i++)
 103             cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++;
 104         }
 105       uns pos = 0;
 106       for (uns i=0; i<(1<<BITS); i++)
 107         {
 108           uns c = cnt[i];
 109           cnt[i] = pos;
 110           pos += c;
 111         }
 112       ASSERT(pos == n);
 113       bzero(cnt2, sizeof(cnt2));
 114       for (uns i=0; i<n; i++)
 115         {
 116           cnt2[(from[i].key >> (sh + BITS)) & ((1 << BITS) - 1)]++;
 117           to[cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++] = from[i];
 118         }
 119       ASSERT(cnt[(1 << BITS)-1] == n);
 120       tmp=from, from=to, to=tmp;
 121     }
 122   ary = from;
 123 #undef BITS
 124 }
 125
 126 static void r1c_sort(void)
 127 {
 128   uns cnt[256];
 129   struct elt *ptrs[256], *x, *lim;
 130
 131   x = ary; lim = ary + n;
 132   bzero(cnt, sizeof(cnt));
 133   while (x < lim)
 134     cnt[x++->key & 255]++;
 135
 136 #define PTRS(start) x=start; for (uns i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
 137
 138   PTRS(alt);
 139   x = ary; lim = ary + n;
 140   bzero(cnt, sizeof(cnt));
 141   while (x < lim)
 142     {
 143       cnt[(x->key >> 8) & 255]++;
 144       *ptrs[x->key & 255]++ = *x;
 145       x++;
 146     }
 147
 148   PTRS(ary);
 149   x = alt; lim = alt + n;
 150   bzero(cnt, sizeof(cnt));
 151   while (x < lim)
 152     {
 153       cnt[(x->key >> 16) & 255]++;
 154       *ptrs[(x->key >> 8) & 255]++ = *x;
 155       x++;
 156     }
 157
 158   PTRS(alt);
 159   x = ary; lim = ary + n;
 160   bzero(cnt, sizeof(cnt));
 161   while (x < lim)
 162     {
 163       cnt[(x->key >> 24) & 255]++;
 164       *ptrs[(x->key >> 16) & 255]++ = *x;
 165       x++;
 166     }
 167
 168   PTRS(ary);
 169   x = alt; lim = alt + n;
 170   while (x < lim)
 171     {
 172       *ptrs[(x->key >> 24) & 255]++ = *x;
 173       x++;
 174     }
 175 #undef PTRS
 176 }
 177
 178 #include <emmintrin.h>
 179
 180 static inline void sse_copy_elt(struct elt *to, struct elt *from)
 181 {
 182   __m128i m = _mm_load_si128((__m128i *) from);
 183   _mm_store_si128((__m128i *) to, m);
 184 }
 185
 186 static void r1c_sse_sort(void)
 187 {
 188   uns cnt[256];
 189   struct elt *ptrs[256], *x, *lim;
 190
 191   ASSERT(sizeof(struct elt) == 16);
 192   ASSERT(!((uintptr_t)alt & 15));
 193   ASSERT(!((uintptr_t)ary & 15));
 194
 195   x = ary; lim = ary + n;
 196   bzero(cnt, sizeof(cnt));
 197   while (x < lim)
 198     cnt[x++->key & 255]++;
 199
 200 #define PTRS(start) x=start; for (uns i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
 201
 202   PTRS(alt);
 203   x = ary; lim = ary + n;
 204   bzero(cnt, sizeof(cnt));
 205   while (x < lim)
 206     {
 207       cnt[(x->key >> 8) & 255]++;
 208       sse_copy_elt(ptrs[x->key & 255]++, x);
 209       x++;
 210     }
 211
 212   PTRS(ary);
 213   x = alt; lim = alt + n;
 214   bzero(cnt, sizeof(cnt));
 215   while (x < lim)
 216     {
 217       cnt[(x->key >> 16) & 255]++;
 218       sse_copy_elt(ptrs[(x->key >> 8) & 255]++, x);
 219       x++;
 220     }
 221
 222   PTRS(alt);
 223   x = ary; lim = ary + n;
 224   bzero(cnt, sizeof(cnt));
 225   while (x < lim)
 226     {
 227       cnt[(x->key >> 24) & 255]++;
 228       sse_copy_elt(ptrs[(x->key >> 16) & 255]++, x);
 229       x++;
 230     }
 231
 232   PTRS(ary);
 233   x = alt; lim = alt + n;
 234   while (x < lim)
 235     {
 236       sse_copy_elt(ptrs[(x->key >> 24) & 255]++, x);
 237       x++;
 238     }
 239 #undef PTRS
 240 }
 241
 242 static void r1d_sort(void)
 243 {
 244   uns cnt[256];
 245   struct elt *ptrs[256], *x, *y, *lim;
 246
 247   ASSERT(!(n % 4));
 248
 249   x = ary; lim = ary + n;
 250   bzero(cnt, sizeof(cnt));
 251   while (x < lim)
 252     {
 253       cnt[x++->key & 255]++;
 254       cnt[x++->key & 255]++;
 255       cnt[x++->key & 255]++;
 256       cnt[x++->key & 255]++;
 257     }
 258
 259 #define PTRS(start) x=start; for (uns i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
 260
 261   PTRS(alt);
 262   x = ary; y = ary+n/2; lim = ary + n/2;
 263   bzero(cnt, sizeof(cnt));
 264   while (x < lim)
 265     {
 266       cnt[(x->key >> 8) & 255]++;
 267       cnt[(y->key >> 8) & 255]++;
 268       *ptrs[x->key & 255]++ = *x;
 269       *ptrs[y->key & 255]++ = *y;
 270       x++, y++;
 271       cnt[(x->key >> 8) & 255]++;
 272       cnt[(y->key >> 8) & 255]++;
 273       *ptrs[x->key & 255]++ = *x;
 274       *ptrs[y->key & 255]++ = *y;
 275       x++, y++;
 276     }
 277
 278   PTRS(ary);
 279   x = alt; lim = alt + n;
 280   bzero(cnt, sizeof(cnt));
 281   while (x < lim)
 282     {
 283       cnt[(x->key >> 16) & 255]++;
 284       *ptrs[(x->key >> 8) & 255]++ = *x;
 285       x++;
 286       cnt[(x->key >> 16) & 255]++;
 287       *ptrs[(x->key >> 8) & 255]++ = *x;
 288       x++;
 289     }
 290
 291   PTRS(alt);
 292   x = ary; lim = ary + n;
 293   bzero(cnt, sizeof(cnt));
 294   while (x < lim)
 295     {
 296       cnt[(x->key >> 24) & 255]++;
 297       *ptrs[(x->key >> 16) & 255]++ = *x;
 298       x++;
 299       cnt[(x->key >> 24) & 255]++;
 300       *ptrs[(x->key >> 16) & 255]++ = *x;
 301       x++;
 302     }
 303
 304   PTRS(ary);
 305   x = alt; lim = alt + n;
 306   while (x < lim)
 307     {
 308       *ptrs[(x->key >> 24) & 255]++ = *x;
 309       x++;
 310       *ptrs[(x->key >> 24) & 255]++ = *x;
 311       x++;
 312     }
 313 #undef PTRS
 314 }
 315
 316 static void r2_sort(void)
 317 {
 318   struct elt *from = ary, *to = alt;
 319 #define BITS 14
 320   uns cnt[1 << BITS];
 321   bzero(cnt, sizeof(cnt));
 322   for (uns i=0; i<n; i++)
 323     cnt[(from[i].key >> (32 - BITS)) & ((1 << BITS) - 1)]++;
 324   uns pos = 0;
 325   for (uns i=0; i<(1<<BITS); i++)
 326     {
 327       uns c = cnt[i];
 328       cnt[i] = pos;
 329       pos += c;
 330     }
 331   ASSERT(pos == n);
 332   for (uns i=0; i<n; i++)
 333     to[cnt[(from[i].key >> (32 - BITS)) & ((1 << BITS) - 1)]++] = from[i];
 334   ASSERT(cnt[(1 << BITS)-1] == n);
 335
 336   pos = 0;
 337   for (uns i=0; i<(1 << BITS); i++)
 338     {
 339       as_sort(cnt[i] - pos, alt+pos);
 340       pos = cnt[i];
 341     }
 342   ary = alt;
 343 #undef BITS
 344 }
 345
 346 static void r3_sort(void)
 347 {
 348 #define BITS 10
 349 #define LEVELS 2
 350 #define BUCKS (1 << BITS)
 351 #define THRESHOLD 5000
 352 #define ODDEVEN 0
 353
 354   auto void r3(struct elt *from, struct elt *to, uns n, uns lev);
 355   void r3(struct elt *from, struct elt *to, uns n, uns lev)
 356   {
 357     uns sh = 32 - lev*BITS;
 358     uns cnt[BUCKS];
 359     bzero(cnt, sizeof(cnt));
 360     for (uns i=0; i<n; i++)
 361       cnt[(from[i].key >> sh) & (BUCKS - 1)]++;
 362     uns pos = 0;
 363     for (uns i=0; i<BUCKS; i++)
 364       {
 365         uns c = cnt[i];
 366         cnt[i] = pos;
 367         pos += c;
 368       }
 369     ASSERT(pos == n);
 370     for (uns i=0; i<n; i++)
 371 #if 1
 372       to[cnt[(from[i].key >> sh) & (BUCKS - 1)]++] = from[i];
 373 #else
 374       sse_copy_elt(&to[cnt[(from[i].key >> sh) & (BUCKS - 1)]++], &from[i]);
 375 #endif
 376     pos = 0;
 377     for (uns i=0; i<BUCKS; i++)
 378       {
 379         uns l = cnt[i]-pos;
 380         if (lev >= LEVELS || l <= THRESHOLD)
 381           {
 382             as_sort(l, to+pos);
 383             if ((lev % 2) != ODDEVEN)
 384               memcpy(from+pos, to+pos, l * sizeof(struct elt));
 385           }
 386         else
 387           r3(to+pos, from+pos, l, lev+1);
 388         pos = cnt[i];
 389       }
 390   }
 391
 392   r3(ary, alt, n, 1);
 393   if (ODDEVEN)
 394     ary = alt;
 395
 396 #undef ODDEVEN
 397 #undef THRESHOLD
 398 #undef BUCKS
 399 #undef LEVELS
 400 #undef BITS
 401 }
 402
 403 static inline struct elt *mrg(struct elt *x, struct elt *xl, struct elt *y, struct elt *yl, struct elt *z)
 404 {
 405   for (;;)
 406     {
 407       if (x->key <= y->key)
 408         {
 409           *z++ = *x++;
 410           if (x >= xl)
 411             goto xend;
 412         }
 413       else
 414         {
 415           *z++ = *y++;
 416           if (y >= yl)
 417             goto yend;
 418         }
 419     }
 420
 421  xend:
 422   while (y < yl)
 423     *z++ = *y++;
 424   return z;
 425
 426  yend:
 427   while (x < xl)
 428     *z++ = *x++;
 429   return z;
 430 }
 431
 432 static void mergesort(void)
 433 {
 434   struct elt *from, *to;
 435   uns lev = 0;
 436   if (1)
 437     {
 438       struct elt *x = ary, *z = alt, *last = ary + (n & ~1U);
 439       while (x < last)
 440         {
 441           if (x[0].key < x[1].key)
 442             *z++ = *x++, *z++ = *x++;
 443           else
 444             {
 445               *z++ = x[1];
 446               *z++ = x[0];
 447               x += 2;
 448             }
 449         }
 450       if (n % 2)
 451         *z = *x;
 452       lev++;
 453     }
 454   for (; (1U << lev) < n; lev++)
 455     {
 456       if (lev % 2)
 457         from = alt, to = ary;
 458       else
 459         from = ary, to = alt;
 460       struct elt *x, *z, *last;
 461       x = from;
 462       z = to;
 463       last = from + n;
 464       uns step = 1 << lev;
 465       while (x + 2*step <= last)
 466         {
 467           z = mrg(x, x+step, x+step, x+2*step, z);
 468           x += 2*step;
 469         }
 470       if (x + step < last)
 471         mrg(x, x+step, x+step, last, z);
 472       else
 473         memcpy(z, x, (byte*)last - (byte*)x);
 474     }
 475   if (lev % 2)
 476     ary = alt;
 477 }
 478
 479 static void sampsort(uns n, struct elt *ar, struct elt *al, struct elt *dest, byte *wbuf)
 480 {
 481 #define WAYS 256
 482   struct elt k[WAYS];
 483   uns cnt[WAYS];
 484   bzero(cnt, sizeof(cnt));
 485   for (uns i=0; i<WAYS; i++)
 486     k[i] = ar[random() % n];
 487   as_sort(WAYS, k);
 488   for (uns i=0; i<n; i++)
 489     {
 490       uns w = 0;
 491 #define FW(delta) if (ar[i].key > k[w+delta].key) w += delta
 492       FW(128);
 493       FW(64);
 494       FW(32);
 495       FW(16);
 496       FW(8);
 497       FW(4);
 498       FW(2);
 499       FW(1);
 500       wbuf[i] = w;
 501       cnt[w]++;
 502     }
 503   struct elt *y = al, *way[WAYS], *z;
 504   for (uns i=0; i<WAYS; i++)
 505     {
 506       way[i] = y;
 507       y += cnt[i];
 508     }
 509   ASSERT(y == al+n);
 510   for (uns i=0; i<n; i++)
 511     {
 512       uns w = wbuf[i];
 513       *way[w]++ = ar[i];
 514     }
 515   y = al;
 516   z = ar;
 517   for (uns i=0; i<WAYS; i++)
 518     {
 519       if (cnt[i] >= 1000)
 520         sampsort(cnt[i], y, z, dest, wbuf);
 521       else
 522         {
 523           as_sort(cnt[i], y);
 524           if (al != dest)
 525             memcpy(z, y, cnt[i]*sizeof(struct elt));
 526         }
 527       y += cnt[i];
 528       z += cnt[i];
 529     }
 530 #undef FW
 531 #undef WAYS
 532 }
 533
 534 static void samplesort(void)
 535 {
 536   byte *aux = xmalloc(n);
 537   sampsort(n, ary, alt, ary, aux);
 538   xfree(aux);
 539 }
 540
 541 static void sampsort2(uns n, struct elt *ar, struct elt *al, struct elt *dest, byte *wbuf)
 542 {
 543 #define WAYS 256
 544   struct elt k[WAYS];
 545   uns cnt[WAYS];
 546   bzero(cnt, sizeof(cnt));
 547   for (uns i=0; i<WAYS; i++)
 548     k[i] = ar[random() % n];
 549   as_sort(WAYS, k);
 550   struct elt *k1 = ar, *k2 = ar+1, *kend = ar+n;
 551   byte *ww = wbuf;
 552   while (k2 < kend)
 553     {
 554       uns w1 = 0, w2 = 0;
 555 #define FW1(delta) if (k1->key > k[w1+delta].key) w1 += delta
 556 #define FW2(delta) if (k2->key > k[w2+delta].key) w2 += delta
 557       FW1(128); FW2(128);
 558       FW1(64);  FW2(64);
 559       FW1(32);  FW2(32);
 560       FW1(16);  FW2(16);
 561       FW1(8);   FW2(8);
 562       FW1(4);   FW2(4);
 563       FW1(2);   FW2(2);
 564       FW1(1);   FW2(1);
 565       *ww++ = w1;
 566       *ww++ = w2;
 567       cnt[w1]++;
 568       cnt[w2]++;
 569       k1 += 2;
 570       k2 += 2;
 571     }
 572   if (k1 < kend)
 573     {
 574       uns w1 = 0;
 575       FW1(128); FW1(64); FW1(32); FW1(16);
 576       FW1(8); FW1(4); FW1(2); FW1(1);
 577       *ww++ = w1;
 578       cnt[w1]++;
 579     }
 580   struct elt *y = al, *way[WAYS], *z;
 581   for (uns i=0; i<WAYS; i++)
 582     {
 583       way[i] = y;
 584       y += cnt[i];
 585     }
 586   ASSERT(y == al+n);
 587   for (uns i=0; i<n; i++)
 588     {
 589       uns w = wbuf[i];
 590       *way[w]++ = ar[i];
 591     }
 592   y = al;
 593   z = ar;
 594   for (uns i=0; i<WAYS; i++)
 595     {
 596       if (cnt[i] >= 1000)
 597         sampsort2(cnt[i], y, z, dest, wbuf);
 598       else
 599         {
 600           as_sort(cnt[i], y);
 601           if (al != dest)
 602             memcpy(z, y, cnt[i]*sizeof(struct elt));
 603         }
 604       y += cnt[i];
 605       z += cnt[i];
 606     }
 607 #undef FW1
 608 #undef FW2
 609 #undef WAYS
 610 }
 611
 612 static void samplesort2(void)
 613 {
 614   byte *aux = xmalloc(n);
 615   sampsort2(n, ary, alt, ary, aux);
 616   xfree(aux);
 617 }
 618
 619 static void heapsort(void)
 620 {
 621 #define H_LESS(_a,_b) ((_a).key > (_b).key)
 622   struct elt *heap = ary-1;
 623   HEAP_INIT(struct elt, heap, n, H_LESS, HEAP_SWAP);
 624   uns nn = n;
 625   while (nn)
 626     HEAP_DELMIN(struct elt, heap, nn, H_LESS, HEAP_SWAP);
 627 #undef H_LESS
 628 }
 629
 630 static void heapsort_ind(void)
 631 {
 632 #define H_LESS(_a,_b) ((_a)->key > (_b)->key)
 633   struct elt **heap = ind-1;
 634   HEAP_INIT(struct elt *, heap, n, H_LESS, HEAP_SWAP);
 635   uns nn = n;
 636   while (nn)
 637     HEAP_DELMIN(struct elt *, heap, nn, H_LESS, HEAP_SWAP);
 638 #undef H_LESS
 639 }
 640
 641 static void mk_ary(void)
 642 {
 643   ary = array0;
 644   alt = array1;
 645   md5_context ctx;
 646   md5_init(&ctx);
 647   u32 block[16];
 648   bzero(block, sizeof(block));
 649
 650   sum = 0;
 651   for (uns i=0; i<n; i++)
 652     {
 653 #if 1
 654       if (!(i % 4))
 655         {
 656           block[i%16] = i;
 657           md5_transform(ctx.buf, block);
 658         }
 659       ary[i].key = ctx.buf[i%4];
 660 #else
 661       ary[i].key = i*(~0U/(n-1));
 662 #endif
 663       for (uns j=1; j<sizeof(struct elt)/4; j++)
 664         ((u32*)&ary[i])[j] = ROL(ary[i].key, 3*j);
 665       sum ^= ary[i].key;
 666     }
 667 }
 668
 669 static void chk_ary(void)
 670 {
 671   u32 s = ary[0].key;
 672   for (uns i=1; i<n; i++)
 673     if (ary[i].key < ary[i-1].key)
 674       die("Missorted at %d", i);
 675     else
 676       s ^= ary[i].key;
 677   if (s != sum)
 678     die("Corrupted");
 679 }
 680
 681 static void mk_ind(void)
 682 {
 683   mk_ary();
 684   ind = xmalloc(sizeof(struct elt *) * n);
 685   for (uns i=0; i<n; i++)
 686     ind[i] = &ary[i];
 687 }
 688
 689 static void chk_ind(void)
 690 {
 691   u32 s = ind[0]->key;
 692   for (uns i=1; i<n; i++)
 693     if (ind[i]->key < ind[i-1]->key)
 694       die("Missorted at %d", i);
 695     else
 696       s ^= ind[i]->key;
 697   if (s != sum)
 698     die("Corrupted");
 699   xfree(ind);
 700 }
 701
 702 int main(int argc, char **argv)
 703 {
 704   log_init(argv[0]);
 705
 706   int opt;
 707   uns op = 0;
 708   while ((opt = cf_getopt(argc, argv, CF_SHORT_OPTS "1", CF_NO_LONG_OPTS, NULL)) >= 0)
 709     switch (opt)
 710       {
 711       case '1':
 712         op |= (1 << (opt - '0'));
 713         break;
 714       default:
 715         die("usage?");
 716       }
 717
 718   array0 = alloc_elts(n);
 719   array1 = alloc_elts(n);
 720   for (uns i=0; i<n; i++)
 721     array0[i] = array1[i] = (struct elt) { 0 };
 722
 723   msg(L_INFO, "Testing with %u elements", n);
 724
 725   mk_ary();
 726   timestamp_t timer;
 727   init_timer(&timer);
 728   for (uns i=0; i<5; i++)
 729     {
 730 #if 1
 731       memcpy(alt, ary, sizeof(struct elt) * n);
 732       memcpy(ary, alt, sizeof(struct elt) * n);
 733 #else
 734       for (uns j=0; j<n; j++)
 735         alt[j] = ary[j];
 736       for (uns j=0; j<n; j++)
 737         ary[j] = alt[j];
 738 #endif
 739     }
 740   msg(L_DEBUG, "memcpy: %d", get_timer(&timer)/10);
 741
 742 #define BENCH(type, name, func) mk_##type(); init_timer(&timer); func; msg(L_DEBUG, name ": %d", get_timer(&timer)); chk_##type()
 743
 744   BENCH(ary, "qsort", qsort(ary, n, sizeof(struct elt), comp));
 745   BENCH(ary, "arraysort", as_sort(n, ary));
 746   BENCH(ind, "indirect qsort", qsort(ind, n, sizeof(struct elt *), comp_ind));
 747   BENCH(ind, "indirect arraysort", asi_sort(n));
 748   BENCH(ary, "radix1", r1_sort());
 749   BENCH(ary, "radix1b", r1b_sort());
 750   BENCH(ary, "radix1c", r1c_sort());
 751   BENCH(ary, "radix1c-sse", r1c_sse_sort());
 752   BENCH(ary, "radix1d", r1d_sort());
 753   BENCH(ary, "radix2", r2_sort());
 754   BENCH(ary, "radix3", r3_sort());
 755   BENCH(ary, "mergesort", mergesort());
 756   BENCH(ary, "samplesort", samplesort());
 757   BENCH(ary, "samplesort2", samplesort2());
 758   BENCH(ary, "heapsort", heapsort());
 759   BENCH(ind, "indirect heapsort", heapsort_ind());
 760
 761   free_elts(array0, n);
 762   free_elts(array1, n);
 763   return 0;
 764 }