debug/sorter/retros.c

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