7ffc12a41c73f801c19beb216a5b2db10335cb9e
[riscv-tests.git] / 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 }