1 // See LICENSE for license details.
3 //**************************************************************************
5 //--------------------------------------------------------------------------
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
17 //--------------------------------------------------------------------------
18 // Input/Reference Data
20 #define type unsigned int
24 #define BASE (1 << LOG_BASE)
27 # define fetch_add(ptr, inc) __sync_fetch_and_add(ptr, inc)
29 # define fetch_add(ptr, inc) ((*(ptr) += (inc)) - (inc))
32 void sort(size_t n
, type
* arrIn
, type
* scratchIn
)
36 size_t *bucket
= buckets
;
38 type
*arr
= arrIn
, *scratch
= scratchIn
, *p
;
41 while (log_exp
< CHAR_BIT
* sizeof(type
))
43 for (b
= bucket
; b
< bucket
+ BASE
; b
++)
46 for (p
= arr
; p
< &arr
[n
-3]; p
+= 4)
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);
57 for ( ; p
< &arr
[n
]; p
++)
58 bucket
[(*p
>> log_exp
) % BASE
]++;
60 size_t prev
= bucket
[0];
61 prev
+= fetch_add(&bucket
[1], prev
);
62 for (b
= &bucket
[2]; b
< bucket
+ BASE
; b
+= 2)
64 prev
+= fetch_add(&b
[0], prev
);
65 prev
+= fetch_add(&b
[1], prev
);
67 static_assert(BASE
% 2 == 0);
69 for (p
= &arr
[n
-1]; p
>= &arr
[3]; p
-= 4)
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);
88 for ( ; p
>= &arr
[0]; p
--)
89 scratch
[--bucket
[(*p
>> log_exp
) % BASE
]] = *p
;
98 memcpy(arr
, scratch
, n
*sizeof(type
));
101 //--------------------------------------------------------------------------
104 int main( int argc
, char* argv
[] )
106 static type scratch
[DATA_SIZE
];
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
))
117 sort(DATA_SIZE
, input_data
, scratch
);
121 return verify( DATA_SIZE
, input_data
, verify_data
);