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 The smips-gcc toolchain does not support system calls
  12 // so printf's can only be used on a host system, not on the smips
  13 // processor simulator itself. You should not change anything except
  14 // the HOST_DEBUG and PREALLOCATE macros for your timing run.
  15
  16 #include "util.h"
  17 #include <string.h>
  18 #include <limits.h>
  19
  20 //--------------------------------------------------------------------------
  21 // Input/Reference Data
  22
  23 #define type unsigned int
  24 #include "dataset1.h"
  25
  26 #define LOG_BASE 8
  27 #define BASE (1 << LOG_BASE)
  28
  29 #if 0
  30 # define fetch_add(ptr, inc) __sync_fetch_and_add(ptr, inc)
  31 #else
  32 # define fetch_add(ptr, inc) ((*(ptr) += (inc)) - (inc))
  33 #endif
  34
  35 void sort(size_t n, type* arrIn, type* scratchIn)
  36 {
  37   size_t log_exp = 0;
  38   size_t buckets[BASE];
  39   size_t *bucket = buckets;
  40   asm("":"+r"(bucket));
  41   type *arr = arrIn, *scratch = scratchIn, *p;
  42   size_t *b;
  43
  44   while (log_exp < CHAR_BIT * sizeof(type))
  45   {
  46     for (b = bucket; b < bucket + BASE; b++)
  47       *b = 0;
  48
  49     for (p = arr; p < &arr[n-3]; p += 4)
  50     {
  51       type a0 = p[0];
  52       type a1 = p[1];
  53       type a2 = p[2];
  54       type a3 = p[3];
  55       fetch_add(&bucket[(a0 >> log_exp) % BASE], 1);
  56       fetch_add(&bucket[(a1 >> log_exp) % BASE], 1);
  57       fetch_add(&bucket[(a2 >> log_exp) % BASE], 1);
  58       fetch_add(&bucket[(a3 >> log_exp) % BASE], 1);
  59     }
  60     for ( ; p < &arr[n]; p++)
  61       bucket[(*p >> log_exp) % BASE]++;
  62
  63     size_t prev = bucket[0];
  64     prev += fetch_add(&bucket[1], prev);
  65     for (b = &bucket[2]; b < bucket + BASE; b += 2)
  66     {
  67       prev += fetch_add(&b[0], prev);
  68       prev += fetch_add(&b[1], prev);
  69     }
  70     static_assert(BASE % 2 == 0);
  71
  72     for (p = &arr[n-1]; p >= &arr[3]; p -= 4)
  73     {
  74       type a0 = p[-0];
  75       type a1 = p[-1];
  76       type a2 = p[-2];
  77       type a3 = p[-3];
  78       size_t* pb0 = &bucket[(a0 >> log_exp) % BASE];
  79       size_t* pb1 = &bucket[(a1 >> log_exp) % BASE];
  80       size_t* pb2 = &bucket[(a2 >> log_exp) % BASE];
  81       size_t* pb3 = &bucket[(a3 >> log_exp) % BASE];
  82       type* s0 = scratch + fetch_add(pb0, -1);
  83       type* s1 = scratch + fetch_add(pb1, -1);
  84       type* s2 = scratch + fetch_add(pb2, -1);
  85       type* s3 = scratch + fetch_add(pb3, -1);
  86       s0[-1] = a0;
  87       s1[-1] = a1;
  88       s2[-1] = a2;
  89       s3[-1] = a3;
  90     }
  91     for ( ; p >= &arr[0]; p--)
  92       scratch[--bucket[(*p >> log_exp) % BASE]] = *p;
  93
  94     type* tmp = arr;
  95     arr = scratch;
  96     scratch = tmp;
  97
  98     log_exp += LOG_BASE;
  99   }
 100   if (arr != arrIn)
 101     memcpy(arr, scratch, n*sizeof(type));
 102 }
 103
 104 //--------------------------------------------------------------------------
 105 // Main
 106
 107 int main( int argc, char* argv[] )
 108 {
 109   static type scratch[DATA_SIZE];
 110   // Output the input array
 111   printArray( "input", DATA_SIZE, input_data );
 112   printArray( "verify", DATA_SIZE, verify_data );
 113
 114 #if PREALLOCATE
 115   // If needed we preallocate everything in the caches
 116   sort(DATA_SIZE, verify_data, scratch);
 117   if (verify(DATA_SIZE, input_data, input_data))
 118     return 1;
 119 #endif
 120
 121   // Do the sort
 122   setStats(1);
 123   sort(DATA_SIZE, input_data, scratch);
 124   setStats(0);
 125
 126   // Print out the results
 127   printArray( "test", DATA_SIZE, input_data );
 128
 129   // Check the results
 130   return verify( DATA_SIZE, input_data, verify_data );
 131 }