debug/sorter/retros.c

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