| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "titaev_m_sortirovka_betchera/all/include/ops_all.hpp" | ||
| 2 | |||
| 3 | #include <omp.h> | ||
| 4 | |||
| 5 | #include <algorithm> | ||
| 6 | #include <cstdint> | ||
| 7 | #include <cstring> | ||
| 8 | #include <vector> | ||
| 9 | |||
| 10 | #include "titaev_m_sortirovka_betchera/common/include/common.hpp" | ||
| 11 | |||
| 12 | namespace titaev_m_sortirovka_betchera { | ||
| 13 | |||
| 14 | namespace { | ||
| 15 | |||
| 16 | uint64_t DoubleToOrderedUint(double value) { | ||
| 17 | uint64_t bits = 0; | ||
| 18 | std::memcpy(&bits, &value, sizeof(double)); | ||
| 19 | constexpr uint64_t kSignMask = (1ULL << 63); | ||
| 20 | if ((bits & kSignMask) != 0ULL) { | ||
| 21 | bits = ~bits; | ||
| 22 | } else { | ||
| 23 | bits ^= kSignMask; | ||
| 24 | } | ||
| 25 | return bits; | ||
| 26 | } | ||
| 27 | |||
| 28 | double OrderedUintToDouble(uint64_t bits) { | ||
| 29 | constexpr uint64_t kSignMask = (1ULL << 63); | ||
| 30 | if ((bits & kSignMask) != 0ULL) { | ||
| 31 | bits ^= kSignMask; | ||
| 32 | } else { | ||
| 33 | bits = ~bits; | ||
| 34 | } | ||
| 35 | double result = 0.0; | ||
| 36 | std::memcpy(&result, &bits, sizeof(double)); | ||
| 37 | return result; | ||
| 38 | } | ||
| 39 | |||
| 40 | } // namespace | ||
| 41 | |||
| 42 |
1/2✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
|
16 | TitaevSortirovkaBetcheraALL::TitaevSortirovkaBetcheraALL(const InType &in) { |
| 43 | SetTypeOfTask(GetStaticTypeOfTask()); | ||
| 44 |
1/2✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
|
16 | GetInput() = in; |
| 45 | GetOutput().clear(); | ||
| 46 | 16 | } | |
| 47 | |||
| 48 | 16 | bool TitaevSortirovkaBetcheraALL::ValidationImpl() { | |
| 49 | 16 | return !GetInput().empty(); | |
| 50 | } | ||
| 51 | |||
| 52 | 16 | bool TitaevSortirovkaBetcheraALL::PreProcessingImpl() { | |
| 53 | 16 | GetOutput() = GetInput(); | |
| 54 | 16 | return true; | |
| 55 | } | ||
| 56 | |||
| 57 | 14 | void TitaevSortirovkaBetcheraALL::ConvertToKeys(const InType &input, std::vector<uint64_t> &keys) { | |
| 58 | const auto n = static_cast<int64_t>(input.size()); | ||
| 59 | 14 | #pragma omp parallel for default(none) shared(input, keys, n) | |
| 60 | for (int64_t i = 0; i < n; i++) { | ||
| 61 | keys[i] = DoubleToOrderedUint(input[i]); | ||
| 62 | } | ||
| 63 | 14 | } | |
| 64 | |||
| 65 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 14 times.
|
14 | void TitaevSortirovkaBetcheraALL::RadixSort(std::vector<uint64_t> &keys) { |
| 66 | const std::size_t n = keys.size(); | ||
| 67 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 14 times.
|
14 | if (n <= 1) { |
| 68 | ✗ | return; | |
| 69 | } | ||
| 70 | |||
| 71 | constexpr int kBits = 8; | ||
| 72 | constexpr int kBuckets = 1 << kBits; | ||
| 73 | constexpr int kPasses = 64 / kBits; | ||
| 74 | |||
| 75 | 14 | std::vector<uint64_t> tmp(n); | |
| 76 | const auto signed_n = static_cast<int64_t>(n); | ||
| 77 | |||
| 78 |
2/2✓ Branch 0 taken 112 times.
✓ Branch 1 taken 14 times.
|
126 | for (int pass = 0; pass < kPasses; pass++) { |
| 79 |
1/4✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
|
112 | std::vector<std::size_t> count(kBuckets, 0); |
| 80 | 112 | const int num_threads = omp_get_max_threads(); | |
| 81 |
2/6✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 112 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
|
112 | std::vector<std::vector<std::size_t>> local_count(num_threads, std::vector<std::size_t>(kBuckets, 0)); |
| 82 | |||
| 83 | 112 | #pragma omp parallel default(none) shared(keys, local_count, signed_n, pass) | |
| 84 | { | ||
| 85 | const int tid = omp_get_thread_num(); | ||
| 86 | auto &lc = local_count[tid]; | ||
| 87 | #pragma omp for | ||
| 88 | for (int64_t i = 0; i < signed_n; i++) { | ||
| 89 | const std::size_t bucket = (keys[i] >> (pass * kBits)) & (kBuckets - 1); | ||
| 90 | lc[bucket]++; | ||
| 91 | } | ||
| 92 | } | ||
| 93 | |||
| 94 |
2/2✓ Branch 0 taken 28672 times.
✓ Branch 1 taken 112 times.
|
28784 | for (int bucket_idx = 0; bucket_idx < kBuckets; bucket_idx++) { |
| 95 |
2/2✓ Branch 0 taken 57344 times.
✓ Branch 1 taken 28672 times.
|
86016 | for (int thr = 0; thr < num_threads; thr++) { |
| 96 | 57344 | count[bucket_idx] += local_count[thr][bucket_idx]; | |
| 97 | } | ||
| 98 | } | ||
| 99 | |||
| 100 |
2/2✓ Branch 0 taken 28560 times.
✓ Branch 1 taken 112 times.
|
28672 | for (int i = 1; i < kBuckets; i++) { |
| 101 | 28560 | count[i] += count[i - 1]; | |
| 102 | } | ||
| 103 | |||
| 104 |
2/2✓ Branch 0 taken 2704 times.
✓ Branch 1 taken 112 times.
|
2816 | for (std::size_t i = n; i-- > 0;) { |
| 105 | 2704 | const std::size_t bucket = (keys[i] >> (pass * kBits)) & (kBuckets - 1); | |
| 106 | 2704 | tmp[--count[bucket]] = keys[i]; | |
| 107 | } | ||
| 108 | |||
| 109 | keys.swap(tmp); | ||
| 110 | 112 | } | |
| 111 | } | ||
| 112 | |||
| 113 | 14 | void TitaevSortirovkaBetcheraALL::ConvertFromKeys(const std::vector<uint64_t> &keys, OutType &output) { | |
| 114 | const auto n = static_cast<int64_t>(keys.size()); | ||
| 115 | 14 | output.resize(keys.size()); | |
| 116 | 14 | #pragma omp parallel for default(none) shared(keys, output, n) | |
| 117 | for (int64_t i = 0; i < n; i++) { | ||
| 118 | output[i] = OrderedUintToDouble(keys[i]); | ||
| 119 | } | ||
| 120 | 14 | } | |
| 121 | |||
| 122 | ✗ | void TitaevSortirovkaBetcheraALL::BatcherStage(OutType &result, std::size_t array_size, std::size_t block, | |
| 123 | std::size_t step) { | ||
| 124 | ✗ | const auto signed_size = static_cast<int64_t>(array_size); | |
| 125 | 70 | #pragma omp parallel for default(none) shared(result, signed_size, block, step) | |
| 126 | for (int64_t i = 0; i < signed_size; i++) { | ||
| 127 | const auto idx = static_cast<std::size_t>(i); | ||
| 128 | const std::size_t partner = idx ^ step; | ||
| 129 | if (partner <= idx) { | ||
| 130 | continue; | ||
| 131 | } | ||
| 132 | const bool ascending = ((idx & block) == 0); | ||
| 133 | const bool need_swap = ascending ? (result[idx] > result[partner]) : (result[idx] < result[partner]); | ||
| 134 | if (need_swap) { | ||
| 135 | std::swap(result[idx], result[partner]); | ||
| 136 | } | ||
| 137 | } | ||
| 138 | ✗ | } | |
| 139 | |||
| 140 |
1/2✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
|
10 | void TitaevSortirovkaBetcheraALL::BatcherSort() { |
| 141 | auto &result = GetOutput(); | ||
| 142 | const std::size_t n = result.size(); | ||
| 143 |
1/2✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
|
10 | if (n < 2) { |
| 144 | return; | ||
| 145 | } | ||
| 146 |
2/2✓ Branch 0 taken 30 times.
✓ Branch 1 taken 10 times.
|
40 | for (std::size_t block = 2; block <= n; block <<= 1) { |
| 147 |
2/2✓ Branch 0 taken 70 times.
✓ Branch 1 taken 30 times.
|
100 | for (std::size_t step = block >> 1; step > 0; step >>= 1) { |
| 148 | BatcherStage(result, n, block, step); | ||
| 149 | } | ||
| 150 | } | ||
| 151 | } | ||
| 152 | |||
| 153 |
2/2✓ Branch 0 taken 14 times.
✓ Branch 1 taken 2 times.
|
16 | bool TitaevSortirovkaBetcheraALL::RunImpl() { |
| 154 | auto &input = GetInput(); | ||
| 155 | const std::size_t n = input.size(); | ||
| 156 |
2/2✓ Branch 0 taken 14 times.
✓ Branch 1 taken 2 times.
|
16 | if (n <= 1) { |
| 157 | return true; | ||
| 158 | } | ||
| 159 | 14 | std::vector<uint64_t> keys(n); | |
| 160 | 14 | ConvertToKeys(input, keys); | |
| 161 |
1/2✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
|
14 | RadixSort(keys); |
| 162 |
1/2✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
|
14 | ConvertFromKeys(keys, GetOutput()); |
| 163 |
2/2✓ Branch 0 taken 10 times.
✓ Branch 1 taken 4 times.
|
14 | if ((n & (n - 1)) == 0) { |
| 164 | 10 | BatcherSort(); | |
| 165 | } | ||
| 166 | return true; | ||
| 167 | } | ||
| 168 | |||
| 169 | 16 | bool TitaevSortirovkaBetcheraALL::PostProcessingImpl() { | |
| 170 | 16 | return true; | |
| 171 | } | ||
| 172 | |||
| 173 | } // namespace titaev_m_sortirovka_betchera | ||
| 174 |