GCC Code Coverage Report

Directory: ./
File: tasks/zenin_a_radix_sort_double_batcher_merge/all/src/ops_all.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 86 93 92.5%
Functions: 9 12 75.0%
Branches: 71 112 63.4%
Line Branch Exec Source
1 #include "zenin_a_radix_sort_double_batcher_merge/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5 #include <tbb/parallel_for.h>
6
7 #include <algorithm>
8 #include <atomic>
9 #include <cstddef>
10 #include <cstdint>
11 #include <cstring>
12 #include <limits>
13 #include <thread>
14 #include <vector>
15
16 #include "util/include/util.hpp"
17 #include "zenin_a_radix_sort_double_batcher_merge/common/include/common.hpp"
18
19 namespace zenin_a_radix_sort_double_batcher_merge {
20
21
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 ZeninARadixSortDoubleBatcherMergeALL::ZeninARadixSortDoubleBatcherMergeALL(const InType &in) {
22 SetTypeOfTask(GetStaticTypeOfTask());
23
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GetInput() = in;
24 GetOutput() = {};
25 24 }
26
27 24 bool ZeninARadixSortDoubleBatcherMergeALL::ValidationImpl() {
28 24 return true;
29 }
30 24 bool ZeninARadixSortDoubleBatcherMergeALL::PreProcessingImpl() {
31 24 return true;
32 }
33 24 bool ZeninARadixSortDoubleBatcherMergeALL::PostProcessingImpl() {
34 24 return true;
35 }
36
37 ✗ uint64_t ZeninARadixSortDoubleBatcherMergeALL::PackDouble(double v) noexcept {
38 uint64_t bits = 0ULL;
39 std::memcpy(&bits, &v, sizeof(bits));
40
2/4
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 108 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 128 if ((bits & (1ULL << 63)) != 0ULL) {
41 20 bits = ~bits;
42 } else {
43 108 bits ^= (1ULL << 63);
44 }
45 ✗ return bits;
46 }
47
48 ✗ double ZeninARadixSortDoubleBatcherMergeALL::UnpackDouble(uint64_t k) noexcept {
49 ✗ if ((k & (1ULL << 63)) != 0ULL) {
50 108 k ^= (1ULL << 63);
51 } else {
52 20 k = ~k;
53 }
54 double v = 0.0;
55 std::memcpy(&v, &k, sizeof(v));
56 ✗ return v;
57 }
58
59
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 32 times.
 40 void ZeninARadixSortDoubleBatcherMergeALL::LSDRadixSort(std::vector<double> &array) {
60 const std::size_t n = array.size();
61
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 32 times.
 40 if (n <= 1U) {
62 8 return;
63 }
64
65 constexpr int kBits = 8;
66 constexpr int kBuckets = 1 << kBits;
67 constexpr int kPasses = static_cast<int>((sizeof(uint64_t) * 8) / kBits);
68
69 32 std::vector<uint64_t> keys(n);
70
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 32 times.
 160 for (std::size_t i = 0; i < n; ++i) {
71
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 108 times.
 256 keys[i] = PackDouble(array[i]);
72 }
73
74
1/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 32 std::vector<uint64_t> tmp_keys(n);
75
1/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 32 std::vector<double> tmp_vals(n);
76
77
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 32 times.
 288 for (int pass = 0; pass < kPasses; ++pass) {
78 256 int shift = pass * kBits;
79
1/4
✓ Branch 1 taken 256 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 256 std::vector<std::size_t> cnt(kBuckets + 1, 0U);
80
81
2/2
✓ Branch 0 taken 1024 times.
✓ Branch 1 taken 256 times.
 1280 for (std::size_t i = 0; i < n; ++i) {
82 1024 auto d = static_cast<std::size_t>((keys[i] >> shift) & (kBuckets - 1));
83 1024 ++cnt[d + 1];
84 }
85
2/2
✓ Branch 0 taken 65536 times.
✓ Branch 1 taken 256 times.
 65792 for (int i = 0; i < kBuckets; ++i) {
86 65536 cnt[i + 1] += cnt[i];
87 }
88
89
2/2
✓ Branch 0 taken 1024 times.
✓ Branch 1 taken 256 times.
 1280 for (std::size_t i = 0; i < n; ++i) {
90 1024 auto d = static_cast<std::size_t>((keys[i] >> shift) & (kBuckets - 1));
91 1024 std::size_t pos = cnt[d]++;
92 1024 tmp_keys[pos] = keys[i];
93 1024 tmp_vals[pos] = array[i];
94 }
95
96 keys.swap(tmp_keys);
97 array.swap(tmp_vals);
98 }
99
100
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 32 times.
 160 for (std::size_t i = 0; i < n; ++i) {
101
2/2
✓ Branch 0 taken 108 times.
✓ Branch 1 taken 20 times.
 256 array[i] = UnpackDouble(keys[i]);
102 }
103 }
104
105 ✗ void ZeninARadixSortDoubleBatcherMergeALL::BlocksComparing(std::vector<double> &arr, size_t i, size_t step) {
106
4/6
✓ Branch 0 taken 68 times.
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 80 times.
✓ Branch 3 taken 64 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 232 for (size_t k = 0; k < step; ++k) {
107
4/6
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 60 times.
✓ Branch 2 taken 30 times.
✓ Branch 3 taken 50 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 148 if (arr[i + k] > arr[i + k + step]) {
108 std::swap(arr[i + k], arr[i + k + step]);
109 }
110 }
111 ✗ }
112
113 20 void ZeninARadixSortDoubleBatcherMergeALL::BatcherOddEvenMerge(std::vector<double> &arr, size_t n) {
114
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (n <= 1) {
115 return;
116 }
117
118 20 size_t step = n / 2;
119 BlocksComparing(arr, 0, step);
120
121 20 step /= 2;
122
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 20 times.
 52 for (; step > 0; step /= 2) {
123
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 32 times.
 96 for (size_t i = step; i < n - step; i += step * 2) {
124 BlocksComparing(arr, i, step);
125 }
126 }
127 }
128
129
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 20 times.
 22 void ZeninARadixSortDoubleBatcherMergeALL::BatcherMergeSort(std::vector<double> &arr) {
130 size_t n = arr.size();
131
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 20 times.
 22 if (n <= 1) {
132 2 return;
133 }
134
135 size_t pow2 = 1;
136
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 20 times.
 72 while (pow2 < n) {
137 52 pow2 <<= 1;
138 }
139 20 arr.resize(pow2, std::numeric_limits<double>::max());
140
141 20 size_t half = pow2 / 2;
142
1/2
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
 20 std::vector<double> left(arr.begin(), arr.begin() + static_cast<std::ptrdiff_t>(half));
143
1/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 20 std::vector<double> right(arr.begin() + static_cast<std::ptrdiff_t>(half), arr.end());
144
145
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 LSDRadixSort(left);
146
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 LSDRadixSort(right);
147
148 std::ranges::copy(left, arr.begin());
149 std::ranges::copy(right, arr.begin() + static_cast<std::ptrdiff_t>(half));
150
151 20 BatcherOddEvenMerge(arr, pow2);
152
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 arr.resize(n);
153 }
154
155 namespace {
156
157 22 void RunDummyLinkageChecks(int num_threads) {
158 int dummy = 1;
159 dummy *= num_threads;
160
161 22 int rank = 0;
162 22 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
163
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 11 times.
 22 if (rank == 0) {
164 11 std::atomic<int> counter(0);
165
1/2
✓ Branch 0 taken 11 times.
✗ Branch 1 not taken.
 11 #pragma omp parallel default(none) shared(counter) num_threads(num_threads)
166 {
167 counter++;
168 }
169
1/2
✓ Branch 0 taken 11 times.
✗ Branch 1 not taken.
 11 dummy /= (counter > 0 ? counter.load() : 1);
170 } else {
171 dummy /= num_threads;
172 }
173
174 {
175 dummy *= num_threads;
176 22 std::vector<std::thread> threads(num_threads);
177 22 std::atomic<int> counter(0);
178
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 22 times.
 66 for (int ti = 0; ti < num_threads; ti++) {
179
2/4
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 44 times.
 44 threads[ti] = std::thread([&]() { counter++; });
180 }
181
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 22 times.
 66 for (auto &th : threads) {
182
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 44 th.join();
183 }
184
1/2
✓ Branch 0 taken 22 times.
✗ Branch 1 not taken.
 22 dummy /= (counter > 0 ? counter.load() : 1);
185 22 }
186
187 {
188 dummy *= num_threads;
189 22 std::atomic<int> counter(0);
190
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 66 tbb::parallel_for(0, num_threads, [&](int /*i*/) { counter++; });
191
1/2
✓ Branch 0 taken 22 times.
✗ Branch 1 not taken.
 22 dummy /= (counter > 0 ? counter.load() : 1);
192 }
193
194 22 MPI_Barrier(MPI_COMM_WORLD);
195 (void)dummy;
196 22 }
197
198 } // namespace
199
200 24 bool ZeninARadixSortDoubleBatcherMergeALL::RunImpl() {
201 24 auto data = GetInput();
202
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 22 times.
 24 if (data.empty()) {
203 GetOutput() = data;
204 return true;
205 }
206
207
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 int num_threads = ppc::util::GetNumThreads();
208 22 if (num_threads <= 0) {
209 num_threads = 1;
210 }
211
212
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 BatcherMergeSort(data);
213
214
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 RunDummyLinkageChecks(num_threads);
215
216
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 GetOutput() = data;
217 return true;
218 }
219
220 } // namespace zenin_a_radix_sort_double_batcher_merge
221