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 #define HS_USE_QSORT
55
56 #include <stdlib.h>
57
58 #endif
59
60 //
61 // qsort comparators
62 //
63
64 #if defined ( HS_USE_QSORT )
65
66 static
67 int
hs_qsort_compare_u32(void const * a,void const * b)68 hs_qsort_compare_u32(void const * a, void const * b)
69 {
70 if (*(uint32_t*)a == *(uint32_t*)b)
71 return 0;
72 else if (*(uint32_t*)a < *(uint32_t*)b)
73 return -1;
74 else
75 return 1;
76 }
77
78 static
79 int
hs_qsort_compare_u64(void const * a,void const * b)80 hs_qsort_compare_u64(void const * a, void const * b)
81 {
82 if (*(uint64_t*)a == *(uint64_t*)b)
83 return 0;
84 else if (*(uint64_t*)a < *(uint64_t*)b)
85 return -1;
86 else
87 return 1;
88 }
89
90 #endif
91
92 //
93 //
94 //
95
96 extern "C"
97 char const *
hs_cpu_sort_u32(uint32_t * a,uint32_t const count,double * const cpu_ns)98 hs_cpu_sort_u32(uint32_t * a, uint32_t const count, double * const cpu_ns)
99 {
100 using to_ns = std::chrono::duration<double,std::chrono::nanoseconds::period>;
101
102 auto start = std::chrono::high_resolution_clock::now();
103
104 #if defined ( HS_USE_PARALLEL_SORT )
105 std::sort(std::execution::par_unseq,a,a+count);
106 char const * const algo = "std::sort(std::execution::par_unseq)()";
107 #elif defined ( HS_USE_STD_SORT )
108 std::sort(a,a+count);
109 char const * const algo = "std:sort()";
110 #elif defined ( HS_USE_QSORT )
111 qsort(a,count,sizeof(*a),hs_qsort_compare_u32);
112 char const * const algo = "qsort()";
113 #endif
114
115 auto stop = std::chrono::high_resolution_clock::now();
116 auto duration_ns = to_ns(stop - start);
117
118 *cpu_ns = duration_ns.count();
119
120 return algo;
121 }
122
123 extern "C"
124 char const *
hs_cpu_sort_u64(uint64_t * a,uint32_t const count,double * const cpu_ns)125 hs_cpu_sort_u64(uint64_t * a, uint32_t const count, double * const cpu_ns)
126 {
127 using to_ns = std::chrono::duration<double,std::chrono::nanoseconds::period>;
128
129 auto start = std::chrono::high_resolution_clock::now();
130
131 #if defined ( HS_USE_PARALLEL_SORT )
132 std::sort(std::execution::par_unseq,a,a+count);
133 char const * const algo = "std::sort(std::execution::par_unseq)()";
134 #elif defined ( HS_USE_STD_SORT )
135 std::sort(a,a+count);
136 char const * const algo = "std::sort()";
137 #elif defined ( HS_USE_QSORT )
138 qsort(a,count,sizeof(*a),hs_qsort_compare_u64);
139 char const * const algo = "qsort()";
140 #endif
141
142 auto stop = std::chrono::high_resolution_clock::now();
143 auto duration_ns = to_ns(stop - start);
144
145 *cpu_ns = duration_ns.count();
146
147 return algo;
148 }
149
150 //
151 //
152 //
153