1 /*
2 * Copyright 2018 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can
5 * be found in the LICENSE file.
6 *
7 */
8
9 //
10 // Sort 1m 64-bit keys on Intel Core i7-7820HQ
11 //
12 // std::sort(std::execution::par_unseq)() : 23 msecs
13 // std::sort() : 88 msecs
14 // qsort() : 166 msecs
15 //
16
17 #include <stdint.h>
18 #include <chrono>
19
20 //
21 // Note: Visual C++ 2017 requires the following switches:
22 //
23 // Zc:__cplusplus
24 // /std:c++17
25 //
26
27 #if 0
28 #define STRINGIZE2(x) #x
29 #define STRINGIZE(x) STRINGIZE2(x)
30 #pragma message(STRINGIZE(__cplusplus))
31 #endif
32
33 //
34 //
35 //
36
37 #if (__cplusplus >= 201703L) && !defined(HS_USE_STD_SORT) && !defined(HS_USE_QSORT)
38
39 #define HS_USE_PARALLEL_SORT
40 #include <algorithm>
41 #include <execution>
42
43 #elif (__cplusplus >= 201103L) && !defined(HS_USE_QSORT)
44
45 #undef HS_USE_PARALLEL_SORT
46 #define HS_USE_STD_SORT
47 #undef HS_USE_QSORT
48 #include <algorithm>
49
50 #else // HS_USE_QSORT
51
52 #undef HS_USE_PARALLEL_SORT
53 #undef HS_USE_STD_SORT
54 #undef HS_USE_QSORT
55 #define HS_USE_QSORT
56
57 #include <stdlib.h>
58
59 #endif
60
61 //
62 // qsort comparators
63 //
64
65 #if defined ( HS_USE_QSORT )
66
67 static
68 int
hs_qsort_compare_u32(void const * a,void const * b)69 hs_qsort_compare_u32(void const * a, void const * b)
70 {
71 if (*(uint32_t*)a == *(uint32_t*)b)
72 return 0;
73 else if (*(uint32_t*)a < *(uint32_t*)b)
74 return -1;
75 else
76 return 1;
77 }
78
79 static
80 int
hs_qsort_compare_u64(void const * a,void const * b)81 hs_qsort_compare_u64(void const * a, void const * b)
82 {
83 if (*(uint64_t*)a == *(uint64_t*)b)
84 return 0;
85 else if (*(uint64_t*)a < *(uint64_t*)b)
86 return -1;
87 else
88 return 1;
89 }
90
91 #endif
92
93 //
94 //
95 //
96
97 extern "C"
98 char const *
hs_cpu_sort_u32(uint32_t * a,uint32_t const count,double * const cpu_ns)99 hs_cpu_sort_u32(uint32_t * a, uint32_t const count, double * const cpu_ns)
100 {
101 using to_ns = std::chrono::duration<double,std::chrono::nanoseconds::period>;
102
103 auto start = std::chrono::high_resolution_clock::now();
104
105 #if defined ( HS_USE_PARALLEL_SORT )
106 std::sort(std::execution::par_unseq,a,a+count);
107 char const * const algo = "std::sort(std::execution::par_unseq)()";
108 #elif defined ( HS_USE_STD_SORT )
109 std::sort(a,a+count);
110 char const * const algo = "std:sort()";
111 #elif defined ( HS_USE_QSORT )
112 qsort(a,count,sizeof(*a),hs_qsort_compare_u32);
113 char const * const algo = "qsort()";
114 #endif
115
116 auto stop = std::chrono::high_resolution_clock::now();
117 auto duration_ns = to_ns(stop - start);
118
119 *cpu_ns = duration_ns.count();
120
121 return algo;
122 }
123
124 extern "C"
125 char const *
hs_cpu_sort_u64(uint64_t * a,uint32_t const count,double * const cpu_ns)126 hs_cpu_sort_u64(uint64_t * a, uint32_t const count, double * const cpu_ns)
127 {
128 using to_ns = std::chrono::duration<double,std::chrono::nanoseconds::period>;
129
130 auto start = std::chrono::high_resolution_clock::now();
131
132 #if defined ( HS_USE_PARALLEL_SORT )
133 std::sort(std::execution::par_unseq,a,a+count);
134 char const * const algo = "std::sort(std::execution::par_unseq)()";
135 #elif defined ( HS_USE_STD_SORT )
136 std::sort(a,a+count);
137 char const * const algo = "std::sort()";
138 #elif defined ( HS_USE_QSORT )
139 qsort(a,count,sizeof(*a),hs_qsort_compare_u64);
140 char const * const algo = "qsort()";
141 #endif
142
143 auto stop = std::chrono::high_resolution_clock::now();
144 auto duration_ns = to_ns(stop - start);
145
146 *cpu_ns = duration_ns.count();
147
148 return algo;
149 }
150
151 //
152 //
153 //
154