benchmarks/qsort/qsort_main.c

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