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 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 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 * 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 * 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