| 88 | // In and Out cannot be the same, but In and Tmp should be same if inplace |
| 89 | template <typename SeqIn, typename Slice, typename Get_Key> |
| 90 | sequence<size_t> integer_sort_r(SeqIn const &In, Slice Out, Slice Tmp, |
| 91 | Get_Key const &g, size_t key_bits, |
| 92 | size_t num_buckets, bool inplace, |
| 93 | float parallelism = 1.0) { |
| 94 | using T = typename SeqIn::value_type; |
| 95 | size_t n = In.size(); |
| 96 | timer t("integer sort", false); |
| 97 | size_t cache_per_thread = 1000000; |
| 98 | size_t base_bits = log2_up(2 * (size_t)sizeof(T) * n / cache_per_thread); |
| 99 | // keep between 8 and 13 |
| 100 | base_bits = std::max<size_t>(8, std::min<size_t>(13, base_bits)); |
| 101 | sequence<size_t> offsets; |
| 102 | bool one_bucket; |
| 103 | bool return_offsets = (num_buckets > 0); |
| 104 | |
| 105 | if (key_bits == 0) { |
| 106 | if (!inplace) parallel_for(0, In.size(), [&](size_t i) { Out[i] = In[i]; }); |
| 107 | return sequence<size_t>(); |
| 108 | |
| 109 | // for small inputs or little parallelism use sequential radix sort |
| 110 | } else if ((n < (1 << 17) || parallelism < .0001) && !return_offsets) { |
| 111 | seq_radix_sort(In, Out, Tmp, g, key_bits, inplace); |
| 112 | return sequence<size_t>(); |
| 113 | |
| 114 | // few bits, just do a single parallel count sort |
| 115 | } else if (key_bits <= base_bits) { |
| 116 | size_t mask = (1 << key_bits) - 1; |
| 117 | auto f = [&](size_t i) { return g(In[i]) & mask; }; |
| 118 | auto get_bits = delayed_seq<size_t>(n, f); |
| 119 | size_t num_bkts = (num_buckets == 0) ? (1 << key_bits) : num_buckets; |
| 120 | // only uses one bucket optimization (last argument) if inplace |
| 121 | std::tie(offsets, one_bucket) = |
| 122 | count_sort(In.slice(), Out, get_bits, num_bkts, parallelism, inplace); |
| 123 | if (inplace && !one_bucket) |
| 124 | parallel_for(0, n, [&](size_t i) { move_uninitialized(Tmp[i], Out[i]); }); |
| 125 | if (return_offsets) |
| 126 | return offsets; |
| 127 | else |
| 128 | return sequence<size_t>(); |
| 129 | |
| 130 | // recursive case |
| 131 | } else { |
| 132 | size_t bits = 8; |
| 133 | size_t shift_bits = key_bits - bits; |
| 134 | size_t num_outer_buckets = (1 << bits); |
| 135 | size_t num_inner_buckets = return_offsets ? ((size_t)1 << shift_bits) : 0; |
| 136 | size_t mask = num_outer_buckets - 1; |
| 137 | auto f = [&](size_t i) { return (g(In[i]) >> shift_bits) & mask; }; |
| 138 | auto get_bits = delayed_seq<size_t>(n, f); |
| 139 | |
| 140 | // divide into buckets |
| 141 | std::tie(offsets, one_bucket) = |
| 142 | count_sort(In.slice(), Out, get_bits, num_outer_buckets, parallelism, |
| 143 | !return_offsets); |
| 144 | |
| 145 | // if all but one bucket are empty, try again on lower bits |
| 146 | if (one_bucket) { |
| 147 | return integer_sort_r(In, Out, Tmp, g, shift_bits, 0, inplace, |
no test coverage detected