• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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