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