benchmarks/qsort/qsort_main.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 <assert.h>
  19
  20 // The INSERTION_THRESHOLD is the size of the subarray when the
  21 // algorithm switches to using an insertion sort instead of
  22 // quick sort.
  23
  24 #define INSERTION_THRESHOLD 10
  25
  26 // NSTACK is the required auxiliary storage.
  27 // It must be at least 2*lg(DATA_SIZE)
  28
  29 #define NSTACK 50
  30
  31 //--------------------------------------------------------------------------
  32 // Input/Reference Data
  33
  34 #define type int
  35 #include "dataset1.h"
  36
  37 // Swap macro for swapping two values.
  38
  39 #define SWAP(a,b) do { typeof(a) temp=(a);(a)=(b);(b)=temp; } while (0)
  40 #define SWAP_IF_GREATER(a, b) do { if ((a) > (b)) SWAP(a, b); } while (0)
  41
  42 //--------------------------------------------------------------------------
  43 // Quicksort function
  44
  45 static void insertion_sort(size_t n, type arr[])
  46 {
  47   type *i, *j;
  48   type value;
  49   for (i = arr+1; i < arr+n; i++)
  50   {
  51     value = *i;
  52     j = i;
  53     while (value < *(j-1))
  54     {
  55       *j = *(j-1);
  56       if (--j == arr)
  57         break;
  58     }
  59     *j = value;
  60   }
  61 }
  62
  63 static void selection_sort(size_t n, type arr[])
  64 {
  65   for (type* i = arr; i < arr+n-1; i++)
  66     for (type* j = i+1; j < arr+n; j++)
  67       SWAP_IF_GREATER(*i, *j);
  68 }
  69
  70 void sort(size_t n, type arr[])
  71 {
  72   type* ir = arr+n;
  73   type* l = arr+1;
  74   type* stack[NSTACK];
  75   type** stackp = stack;
  76
  77   for (;;)
  78   {
  79 #if HOST_DEBUG
  80     printArray( "", n, arr );
  81 #endif
  82
  83     // Insertion sort when subarray small enough.
  84     if ( ir-l < INSERTION_THRESHOLD )
  85     {
  86       insertion_sort(ir - l + 1, l - 1);
  87
  88       if ( stackp == stack ) break;
  89
  90       // Pop stack and begin a new round of partitioning.
  91       ir = *stackp--;
  92       l = *stackp--;
  93     }
  94     else
  95     {
  96       // Choose median of left, center, and right elements as
  97       // partitioning element a. Also rearrange so that a[l-1] <= a[l] <= a[ir-].
  98       SWAP(arr[((l-arr) + (ir-arr))/2-1], l[0]);
  99       SWAP_IF_GREATER(l[-1], ir[-1]);
 100       SWAP_IF_GREATER(l[0], ir[-1]);
 101       SWAP_IF_GREATER(l[-1], l[0]);
 102
 103       // Initialize pointers for partitioning.
 104       type* i = l+1;
 105       type* j = ir;
 106
 107       // Partitioning element.
 108       type a = l[0];
 109
 110       for (;;) {                    // Beginning of innermost loop.
 111         while (*i++ < a);           // Scan up to find element > a.
 112         while (*(j-- - 2) > a);     // Scan down to find element < a.
 113         if (j < i) break;           // Pointers crossed. Partitioning complete.
 114         SWAP(i[-1], j[-1]);         // Exchange elements.
 115       }                             // End of innermost loop.
 116
 117       // Insert partitioning element.
 118       l[0] = j[-1];
 119       j[-1] = a;
 120       stackp += 2;
 121
 122       // Push pointers to larger subarray on stack,
 123       // process smaller subarray immediately.
 124
 125 #if HOST_DEBUG
 126       assert(stackp < stack+NSTACK);
 127 #endif
 128
 129       if ( ir-i+1 >= j-l )
 130       {
 131         stackp[0] = ir;
 132         stackp[-1] = i;
 133         ir = j-1;
 134       }
 135       else
 136       {
 137         stackp[0] = j-1;
 138         stackp[-1] = l;
 139         l = i;
 140       }
 141     }
 142   }
 143 }
 144
 145 //--------------------------------------------------------------------------
 146 // Main
 147
 148 int main( int argc, char* argv[] )
 149 {
 150   // Output the input array
 151   printArray( "input", DATA_SIZE, input_data );
 152   printArray( "verify", DATA_SIZE, verify_data );
 153
 154 #if PREALLOCATE
 155   // If needed we preallocate everything in the caches
 156   sort(DATA_SIZE, verify_data);
 157   if (verify(DATA_SIZE, input_data, input_data))
 158     return 1;
 159 #endif
 160
 161   // Do the sort
 162   setStats(1);
 163   sort( DATA_SIZE, input_data );
 164   setStats(0);
 165
 166   // Print out the results
 167   printArray( "test", DATA_SIZE, input_data );
 168
 169   // Check the results
 170   return verify( DATA_SIZE, input_data, verify_data );
 171 }