benchmarks/rsort/rsort.c

   1 // See LICENSE for license details.
   2
   3 //**************************************************************************
   4 // Quicksort benchmark
   5 //--------------------------------------------------------------------------
   6 //
   7 // This benchmark uses quicksort to sort an array of integers. The
   8 // implementation is largely adapted from Numerical Recipes for C. The
   9 // input data (and reference data) should be generated using the
  10 // qsort_gendata.pl perl script and dumped to a file named
  11 // dataset1.h
  12
  13 #include "util.h"
  14 #include <string.h>
  15 #include <limits.h>
  16
  17 //--------------------------------------------------------------------------
  18 // Input/Reference Data
  19
  20 #define type unsigned int
  21 #include "dataset1.h"
  22
  23 #define LOG_BASE 8
  24 #define BASE (1 << LOG_BASE)
  25
  26 #if 0
  27 # define fetch_add(ptr, inc) __sync_fetch_and_add(ptr, inc)
  28 #else
  29 # define fetch_add(ptr, inc) ((*(ptr) += (inc)) - (inc))
  30 #endif
  31
  32 void sort(size_t n, type* arrIn, type* scratchIn)
  33 {
  34   size_t log_exp = 0;
  35   size_t buckets[BASE];
  36   size_t *bucket = buckets;
  37   asm("":"+r"(bucket));
  38   type *arr = arrIn, *scratch = scratchIn, *p;
  39   size_t *b;
  40
  41   while (log_exp < CHAR_BIT * sizeof(type))
  42   {
  43     for (b = bucket; b < bucket + BASE; b++)
  44       *b = 0;
  45
  46     for (p = arr; p < &arr[n-3]; p += 4)
  47     {
  48       type a0 = p[0];
  49       type a1 = p[1];
  50       type a2 = p[2];
  51       type a3 = p[3];
  52       fetch_add(&bucket[(a0 >> log_exp) % BASE], 1);
  53       fetch_add(&bucket[(a1 >> log_exp) % BASE], 1);
  54       fetch_add(&bucket[(a2 >> log_exp) % BASE], 1);
  55       fetch_add(&bucket[(a3 >> log_exp) % BASE], 1);
  56     }
  57     for ( ; p < &arr[n]; p++)
  58       bucket[(*p >> log_exp) % BASE]++;
  59
  60     size_t prev = bucket[0];
  61     prev += fetch_add(&bucket[1], prev);
  62     for (b = &bucket[2]; b < bucket + BASE; b += 2)
  63     {
  64       prev += fetch_add(&b[0], prev);
  65       prev += fetch_add(&b[1], prev);
  66     }
  67     static_assert(BASE % 2 == 0);
  68
  69     for (p = &arr[n-1]; p >= &arr[3]; p -= 4)
  70     {
  71       type a0 = p[-0];
  72       type a1 = p[-1];
  73       type a2 = p[-2];
  74       type a3 = p[-3];
  75       size_t* pb0 = &bucket[(a0 >> log_exp) % BASE];
  76       size_t* pb1 = &bucket[(a1 >> log_exp) % BASE];
  77       size_t* pb2 = &bucket[(a2 >> log_exp) % BASE];
  78       size_t* pb3 = &bucket[(a3 >> log_exp) % BASE];
  79       type* s0 = scratch + fetch_add(pb0, -1);
  80       type* s1 = scratch + fetch_add(pb1, -1);
  81       type* s2 = scratch + fetch_add(pb2, -1);
  82       type* s3 = scratch + fetch_add(pb3, -1);
  83       s0[-1] = a0;
  84       s1[-1] = a1;
  85       s2[-1] = a2;
  86       s3[-1] = a3;
  87     }
  88     for ( ; p >= &arr[0]; p--)
  89       scratch[--bucket[(*p >> log_exp) % BASE]] = *p;
  90
  91     type* tmp = arr;
  92     arr = scratch;
  93     scratch = tmp;
  94
  95     log_exp += LOG_BASE;
  96   }
  97   if (arr != arrIn)
  98     memcpy(arr, scratch, n*sizeof(type));
  99 }
 100
 101 //--------------------------------------------------------------------------
 102 // Main
 103
 104 int main( int argc, char* argv[] )
 105 {
 106   static type scratch[DATA_SIZE];
 107
 108 #if PREALLOCATE
 109   // If needed we preallocate everything in the caches
 110   sort(DATA_SIZE, verify_data, scratch);
 111   if (verify(DATA_SIZE, input_data, input_data))
 112     return 1;
 113 #endif
 114
 115   // Do the sort
 116   setStats(1);
 117   sort(DATA_SIZE, input_data, scratch);
 118   setStats(0);
 119
 120   // Check the results
 121   return verify( DATA_SIZE, input_data, verify_data );
 122 }