debug/sorter/retros.c

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