Make qsort input size more reasonable

[riscv-tests.git] / benchmarks / qsort / qsort_main.c

diff --git a/benchmarks/qsort/qsort_main.c b/benchmarks/qsort/qsort_main.c
index 963335661e7d718039c113a84c82e33dcaad5c04..00d9560ec8749f675d042a026fc509f995f59007 100644 (file)
--- a/benchmarks/qsort/qsort_main.c
+++ b/benchmarks/qsort/qsort_main.c
@@ -12,122 +12,132 @@
 // the HOST_DEBUG and PREALLOCATE macros for your timing run.
 
 #include "util.h"
+#include <string.h>
+#include <assert.h>
 
 // The INSERTION_THRESHOLD is the size of the subarray when the
 // algorithm switches to using an insertion sort instead of
 // quick sort.
 
-#define INSERTION_THRESHOLD 7
+#define INSERTION_THRESHOLD 10
 
 // NSTACK is the required auxiliary storage.
 // It must be at least 2*lg(DATA_SIZE)
 
 #define NSTACK 50
 
-// Swap macro for swapping two values.
-
-#define SWAP(a,b) temp=(a);(a)=(b);(b)=temp;
-
 //--------------------------------------------------------------------------
 // Input/Reference Data
 
+#define type int
 #include "dataset1.h"
 
+// Swap macro for swapping two values.
+
+#define SWAP(a,b) do { typeof(a) temp=(a);(a)=(b);(b)=temp; } while (0)
+#define SWAP_IF_GREATER(a, b) do { if ((a) > (b)) SWAP(a, b); } while (0)
+
 //--------------------------------------------------------------------------
 // Quicksort function
 
-void sort( int n, int arr[] )
+static void insertion_sort(size_t n, type arr[])
 {
-  int i,j,k;
-  int ir = n;
-  int l = 1;
-  int jstack = 0;
-  int a, temp;
+  type *i, *j;
+  type value;
+  for (i = arr+1; i < arr+n; i++)
+  {
+    value = *i;
+    j = i;
+    while (value < *(j-1))
+    {
+      *j = *(j-1);
+      if (--j == arr)
+        break;
+    }
+    *j = value;
+  }
+}
 
-  int istack[NSTACK];
+static void selection_sort(size_t n, type arr[])
+{
+  for (type* i = arr; i < arr+n-1; i++)
+    for (type* j = i+1; j < arr+n; j++)
+      SWAP_IF_GREATER(*i, *j);
+}
 
-  for (;;) {
+void sort(size_t n, type arr[])
+{
+  type* ir = arr+n;
+  type* l = arr+1;
+  type* stack[NSTACK];
+  type** stackp = stack;
 
+  for (;;)
+  {
 #if HOST_DEBUG
     printArray( "", n, arr );
 #endif
 
     // Insertion sort when subarray small enough.
-    if ( ir-l < INSERTION_THRESHOLD ) {
-
-      for ( j = l+1; j <= ir; j++ ) {
-        a = arr[j-1];
-        for ( i = j-1; i >= l; i-- ) {
-          if ( arr[i-1] <= a ) break;
-          arr[i] = arr[i-1];
-        }
-        arr[i] = a;
-      }
+    if ( ir-l < INSERTION_THRESHOLD )
+    {
+      insertion_sort(ir - l + 1, l - 1);
 
-      if ( jstack == 0 ) break;
+      if ( stackp == stack ) break;
 
       // Pop stack and begin a new round of partitioning.
-      ir = istack[jstack--];
-      l = istack[jstack--];
-
+      ir = *stackp--;
+      l = *stackp--;
     }
-    else {
-
+    else
+    {
       // Choose median of left, center, and right elements as
       // partitioning element a. Also rearrange so that a[l-1] <= a[l] <= a[ir-].
-
-      k = (l+ir) >> 1;
-      SWAP(arr[k-1],arr[l])
-      if ( arr[l-1] > arr[ir-1] ) {
-        SWAP(arr[l-1],arr[ir-1])
-      }
-      if ( arr[l] > arr[ir-1] ) {
-        SWAP(arr[l],arr[ir-1])
-      }
-      if ( arr[l-1] > arr[l] ) {
-        SWAP(arr[l-1],arr[l])
-      }
+      SWAP(arr[((l-arr) + (ir-arr))/2-1], l[0]);
+      SWAP_IF_GREATER(l[-1], ir[-1]);
+      SWAP_IF_GREATER(l[0], ir[-1]);
+      SWAP_IF_GREATER(l[-1], l[0]);
 
       // Initialize pointers for partitioning.
-      i = l+1;
-      j = ir;
+      type* i = l+1;
+      type* j = ir;
 
       // Partitioning element.
-      a = arr[l];
+      type a = l[0];
 
-      for (;;) {                       // Beginning of innermost loop.
-        do i++; while (arr[i-1] < a);  // Scan up to find element > a.
-        do j--; while (arr[j-1] > a);  // Scan down to find element < a.
-        if (j < i) break;              // Pointers crossed. Partitioning complete.
-        SWAP(arr[i-1],arr[j-1]);       // Exchange elements.
-      }                                // End of innermost loop.
+      for (;;) {                    // Beginning of innermost loop.
+        while (*i++ < a);           // Scan up to find element > a.
+        while (*(j-- - 2) > a);     // Scan down to find element < a.
+        if (j < i) break;           // Pointers crossed. Partitioning complete.
+        SWAP(i[-1], j[-1]);         // Exchange elements.
+      }                             // End of innermost loop.
 
       // Insert partitioning element.
-      arr[l] = arr[j-1];
-      arr[j-1] = a;
-      jstack += 2;
+      l[0] = j[-1];
+      j[-1] = a;
+      stackp += 2;
 
       // Push pointers to larger subarray on stack,
       // process smaller subarray immediately.
 
 #if HOST_DEBUG
-      if ( jstack > NSTACK ) { printf("NSTACK too small in sort.\n"); exit(1); }
+      assert(stackp < stack+NSTACK);
 #endif
 
-      if ( ir-i+1 >= j-l ) {
-        istack[jstack]   = ir;
-        istack[jstack-1] = i;
+      if ( ir-i+1 >= j-l )
+      {
+        stackp[0] = ir;
+        stackp[-1] = i;
         ir = j-1;
       }
-      else {
-        istack[jstack]   = j-1;
-        istack[jstack-1] = l;
+      else
+      {
+        stackp[0] = j-1;
+        stackp[-1] = l;
         l = i;
       }
     }
-
   }
-
 }
 
 //--------------------------------------------------------------------------
@@ -141,7 +151,9 @@ int main( int argc, char* argv[] )
 
 #if PREALLOCATE
   // If needed we preallocate everything in the caches
-  sort( DATA_SIZE, input_data );
+  sort(DATA_SIZE, verify_data);
+  if (verify(DATA_SIZE, input_data, input_data))
+    return 1;
 #endif
 
   // Do the sort