GCC Code Coverage Report

Directory: ./
File: tasks/leonova_a_radix_merge_sort/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 150 154 97.4%
Functions: 14 15 93.3%
Branches: 100 154 64.9%
Line Branch Exec Source
1 #include "leonova_a_radix_merge_sort/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <cstdint>
8 #include <future>
9 #include <utility>
10 #include <vector>
11
12 #include "leonova_a_radix_merge_sort/common/include/common.hpp"
13 #include "util/include/util.hpp"
14
15 static_assert(sizeof(int64_t) == sizeof(std::int64_t));
16
17 namespace leonova_a_radix_merge_sort {
18
19
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 LeonovaARadixMergeSortALL::LeonovaARadixMergeSortALL(const InType &in) {
20 SetTypeOfTask(GetStaticTypeOfTask());
21
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 GetInput() = in;
22
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 GetOutput() = std::vector<int64_t>(GetInput().size());
23 64 }
24
25 128 bool LeonovaARadixMergeSortALL::ValidationImpl() {
26 128 int rank = 0;
27 128 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
28
29 128 int is_valid = 1;
30
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 64 times.
 128 if (rank == 0) {
31
1/2
✓ Branch 0 taken 64 times.
✗ Branch 1 not taken.
 128 is_valid = GetInput().empty() ? 0 : 1;
32 }
33
34 128 MPI_Bcast(&is_valid, 1, MPI_INT, 0, MPI_COMM_WORLD);
35 128 return is_valid == 1;
36 }
37
38 64 bool LeonovaARadixMergeSortALL::PreProcessingImpl() {
39 64 return true;
40 }
41
42 64 bool LeonovaARadixMergeSortALL::PostProcessingImpl() {
43 64 return true;
44 }
45
46 namespace {
47
48 void MpiSendInt64(const std::vector<int64_t> &buf, int count, int dest, int tag) {
49 30 MPI_Send(static_cast<const void *>(buf.data()), count, MPI_INT64_T, dest, tag, MPI_COMM_WORLD);
50 30 }
51
52 void MpiRecvInt64(std::vector<int64_t> &buf, int count, int src, int tag) {
53
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 MPI_Recv(static_cast<void *>(buf.data()), count, MPI_INT64_T, src, tag, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
54 30 }
55
56 void MpiBcastInt64(std::vector<int64_t> &buf, int count) {
57 64 MPI_Bcast(static_cast<void *>(buf.data()), count, MPI_INT64_T, 0, MPI_COMM_WORLD);
58 }
59
60 void MpiScattervInt64(const std::vector<int64_t> &sendbuf, const std::vector<int> &counts,
61 const std::vector<int> &displs, std::vector<int64_t> &recvbuf, int recv_count, int root) {
62 const void *send_ptr = static_cast<const void *>(sendbuf.data());
63 void *recv_ptr = static_cast<void *>(recvbuf.data());
64
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 MPI_Scatterv(send_ptr, counts.data(), displs.data(), MPI_INT64_T, recv_ptr, recv_count, MPI_INT64_T, root,
65 MPI_COMM_WORLD);
66 64 }
67
68 } // namespace
69
70 inline uint64_t LeonovaARadixMergeSortALL::ToUnsignedValue(int64_t value) {
71 262987 return static_cast<uint64_t>(value) ^ kSignBitMask;
72 }
73
74 ✗ void LeonovaARadixMergeSortALL::FillKeys(const std::vector<int64_t> &arr, size_t left, size_t size,
75 std::vector<uint64_t> &keys) {
76
2/4
✓ Branch 0 taken 262987 times.
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 263099 for (size_t i = 0; i < size; ++i) {
77 262987 keys[i] = ToUnsignedValue(arr[left + i]);
78 }
79 ✗ }
80
81
1/2
✓ Branch 0 taken 896 times.
✗ Branch 1 not taken.
 896 void LeonovaARadixMergeSortALL::CountBytes(const std::vector<uint64_t> &keys, size_t begin, size_t end, int shift,
82 std::vector<size_t> &counts) {
83 std::ranges::fill(counts, 0);
84
2/2
✓ Branch 0 taken 2103896 times.
✓ Branch 1 taken 896 times.
 2104792 for (size_t i = begin; i < end; ++i) {
85 2103896 ++counts[(keys[i] >> shift) & 0xFFU];
86 }
87 896 }
88
89 896 void LeonovaARadixMergeSortALL::ScatterBytes(const std::vector<uint64_t> &src_keys, const std::vector<int64_t> &src_arr,
90 size_t left, size_t begin, size_t end, int shift,
91 std::vector<size_t> &offsets, std::vector<int64_t> &dst_arr,
92 std::vector<uint64_t> &dst_keys) {
93
2/2
✓ Branch 0 taken 2103896 times.
✓ Branch 1 taken 896 times.
 2104792 for (size_t i = begin; i < end; ++i) {
94 2103896 const size_t bucket = (src_keys[i] >> shift) & 0xFFU;
95 2103896 const size_t pos = offsets[bucket]++;
96 2103896 dst_arr[pos] = src_arr[left + i];
97 2103896 dst_keys[pos] = src_keys[i];
98 }
99 896 }
100
101 56 void LeonovaARadixMergeSortALL::ParallelRadixSort(std::vector<int64_t> &arr, size_t left, size_t right) {
102 56 const size_t size = right - left;
103
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 if (size <= 1) {
104 ✗ return;
105 }
106
107 56 const auto hw = static_cast<size_t>(std::max(1, ppc::util::GetNumThreads()));
108 const size_t num_threads = std::min(hw, size);
109 56 const size_t chunk = (size + num_threads - 1) / num_threads;
110
111 56 std::vector<size_t> boundaries(num_threads + 1);
112
2/2
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 56 times.
 224 for (size_t tndex = 0; tndex <= num_threads; ++tndex) {
113 168 boundaries[tndex] = left + std::min(tndex * chunk, size);
114 }
115
116 112 auto sort_chunk = [&](size_t cl, size_t cr) {
117 112 const size_t sz = cr - cl;
118 112 std::vector<uint64_t> keys(sz);
119
1/4
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 112 std::vector<int64_t> tmp_arr(sz);
120
1/4
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 112 std::vector<uint64_t> tmp_keys(sz);
121
1/4
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 112 std::vector<size_t> counts(kNumCounters);
122
1/4
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 112 std::vector<size_t> offsets(kNumCounters);
123
124 112 FillKeys(arr, cl, sz, keys);
125
126
2/2
✓ Branch 0 taken 896 times.
✓ Branch 1 taken 112 times.
 1008 for (int byte_pos = 0; byte_pos < kNumBytes; ++byte_pos) {
127 896 const int shift = byte_pos * kByteSize;
128
129 896 CountBytes(keys, 0, sz, shift, counts);
130
131 size_t sum = 0;
132
2/2
✓ Branch 0 taken 229376 times.
✓ Branch 1 taken 896 times.
 230272 for (size_t bndex = 0; bndex < kNumCounters; ++bndex) {
133 229376 offsets[bndex] = sum;
134 229376 sum += counts[bndex];
135 }
136
137 896 ScatterBytes(keys, arr, cl, 0, sz, shift, offsets, tmp_arr, tmp_keys);
138
139 std::ranges::copy(tmp_arr, arr.begin() + static_cast<std::ptrdiff_t>(cl));
140 keys.swap(tmp_keys);
141 }
142 112 };
143
144 56 std::vector<std::future<void>> futures;
145
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 futures.reserve(num_threads);
146
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 56 times.
 168 for (size_t tndex = 0; tndex < num_threads; ++tndex) {
147
1/2
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
 224 futures.push_back(std::async(std::launch::async, sort_chunk, boundaries[tndex], boundaries[tndex + 1]));
148 }
149
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 56 times.
 168 for (auto &f : futures) {
150
1/2
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
 112 f.get();
151 }
152
153
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 MergeChunks(arr, boundaries);
154 56 }
155
156 56 void LeonovaARadixMergeSortALL::SimpleMerge(std::vector<int64_t> &arr, size_t left, size_t mid, size_t right) {
157 56 std::vector<int64_t> merged(right - left);
158
159 size_t i = left;
160 size_t j = mid;
161 size_t k = 0;
162
163
2/2
✓ Branch 0 taken 131501 times.
✓ Branch 1 taken 56 times.
 131557 while (i < mid && j < right) {
164
2/2
✓ Branch 0 taken 79 times.
✓ Branch 1 taken 131422 times.
 131501 merged[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
165 }
166
2/2
✓ Branch 0 taken 131426 times.
✓ Branch 1 taken 56 times.
 131482 while (i < mid) {
167 131426 merged[k++] = arr[i++];
168 }
169
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 56 times.
 116 while (j < right) {
170 60 merged[k++] = arr[j++];
171 }
172
173 std::ranges::copy(merged, arr.begin() + static_cast<std::ptrdiff_t>(left));
174 56 }
175
176
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 void LeonovaARadixMergeSortALL::MergeChunks(std::vector<int64_t> &arr, const std::vector<size_t> &boundaries) {
177 56 const size_t num_chunks = boundaries.size() - 1;
178
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 if (num_chunks <= 1) {
179 return;
180 }
181
182 size_t step = 1;
183
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 56 times.
 112 while (step < num_chunks) {
184 56 const size_t double_step = step * 2;
185 size_t t = 0;
186
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 56 times.
 112 while (t < num_chunks) {
187
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 const size_t mid_idx = std::min(t + step, num_chunks);
188 56 const size_t right_idx = std::min(t + double_step, num_chunks);
189
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 if (mid_idx < right_idx) {
190 56 SimpleMerge(arr, boundaries[t], boundaries[mid_idx], boundaries[right_idx]);
191 }
192 t += double_step;
193 }
194 step = double_step;
195 }
196 }
197
198 30 void LeonovaARadixMergeSortALL::MergeSortedVectors(std::vector<int64_t> &local, const std::vector<int64_t> &incoming) {
199
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 std::vector<int64_t> merged;
200
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 merged.reserve(local.size() + incoming.size());
201
202 size_t i = 0;
203 size_t j = 0;
204
205
4/4
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 131530 times.
✓ Branch 2 taken 18 times.
✓ Branch 3 taken 131512 times.
 131542 while (i < local.size() && j < incoming.size()) {
206
2/2
✓ Branch 0 taken 82 times.
✓ Branch 1 taken 131430 times.
 131512 merged.push_back((local[i] <= incoming[j]) ? local[i++] : incoming[j++]);
207 }
208
2/2
✓ Branch 0 taken 131421 times.
✓ Branch 1 taken 30 times.
 131451 while (i < local.size()) {
209
1/2
✓ Branch 0 taken 131421 times.
✗ Branch 1 not taken.
 131421 merged.push_back(local[i++]);
210 }
211
2/2
✓ Branch 0 taken 58 times.
✓ Branch 1 taken 30 times.
 88 while (j < incoming.size()) {
212
1/2
✓ Branch 0 taken 58 times.
✗ Branch 1 not taken.
 58 merged.push_back(incoming[j++]);
213 }
214
215 local = std::move(merged);
216 30 }
217
218 64 void LeonovaARadixMergeSortALL::HierarchicalMerge(std::vector<int64_t> &local_data, int rank, int world_size) {
219 int step = 1;
220
221
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 64 times.
 128 while (step < world_size) {
222 64 const int mask = step * 2;
223
224
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
 64 if ((rank & (mask - 1)) == 0) {
225 32 const int partner = rank + step;
226
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if (partner < world_size) {
227 32 int incoming_size = 0;
228 32 MPI_Recv(&incoming_size, 1, MPI_INT, partner, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
229
230
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 2 times.
 32 if (incoming_size > 0) {
231 30 std::vector<int64_t> incoming(static_cast<size_t>(incoming_size));
232
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 MpiRecvInt64(incoming, incoming_size, partner, 1);
233
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 MergeSortedVectors(local_data, incoming);
234 }
235 }
236
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 } else if ((rank & (mask - 1)) == step) {
237 32 const int partner = rank - step;
238 32 const int send_size = static_cast<int>(local_data.size());
239 32 MPI_Send(&send_size, 1, MPI_INT, partner, 0, MPI_COMM_WORLD);
240
241
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 2 times.
 32 if (send_size > 0) {
242 MpiSendInt64(local_data, send_size, partner, 1);
243 }
244
245 local_data.clear();
246 local_data.shrink_to_fit();
247 }
248
249 64 MPI_Barrier(MPI_COMM_WORLD);
250 step *= 2;
251 }
252 64 }
253
254 64 void LeonovaARadixMergeSortALL::BroadcastResult(std::vector<int64_t> &local_data, int rank, int total) {
255
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
 64 int result_size = (rank == 0) ? static_cast<int>(local_data.size()) : 0;
256 64 MPI_Bcast(&result_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
257
258
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
 64 if (rank != 0) {
259 32 local_data.resize(static_cast<size_t>(total));
260 }
261
262 64 MpiBcastInt64(local_data, result_size);
263 64 }
264
265 64 bool LeonovaARadixMergeSortALL::RunImpl() {
266
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 if (!ValidationImpl()) {
267 return false;
268 }
269
270 64 int rank = 0;
271 64 int world_size = 1;
272 64 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
273 64 MPI_Comm_size(MPI_COMM_WORLD, &world_size);
274
275 64 const auto total = static_cast<int>(GetInput().size());
276
277 64 std::vector<int> send_counts(static_cast<size_t>(world_size), 0);
278
1/4
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 64 std::vector<int> send_displs(static_cast<size_t>(world_size), 0);
279
280
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
 64 if (rank == 0) {
281 32 const int base = total / world_size;
282 32 const int remainder = total % world_size;
283
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 32 times.
 96 for (int pndex = 0; pndex < world_size; ++pndex) {
284
2/2
✓ Branch 0 taken 47 times.
✓ Branch 1 taken 17 times.
 111 send_counts[static_cast<size_t>(pndex)] = base + (pndex < remainder ? 1 : 0);
285 }
286 int offset = 0;
287
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 32 times.
 96 for (int pndex = 0; pndex < world_size; ++pndex) {
288 64 send_displs[static_cast<size_t>(pndex)] = offset;
289 64 offset += send_counts[static_cast<size_t>(pndex)];
290 }
291 }
292
293
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 MPI_Bcast(send_counts.data(), world_size, MPI_INT, 0, MPI_COMM_WORLD);
294
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 MPI_Bcast(send_displs.data(), world_size, MPI_INT, 0, MPI_COMM_WORLD);
295
296
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 const int recv_count = send_counts[static_cast<size_t>(rank)];
297
1/4
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 64 std::vector<int64_t> local_data(static_cast<size_t>(recv_count));
298
299
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 64 times.
 64 if (world_size == 1) {
300 ✗ local_data = GetInput();
301 } else {
302 MpiScattervInt64(GetInput(), send_counts, send_displs, local_data, recv_count, 0);
303 }
304
305
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 8 times.
 64 if (recv_count > 1) {
306
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 ParallelRadixSort(local_data, 0, static_cast<size_t>(recv_count));
307 }
308
309
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 HierarchicalMerge(local_data, rank, world_size);
310
311
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 BroadcastResult(local_data, rank, total);
312
313 GetOutput() = std::move(local_data);
314
315 return true;
316 }
317
318 } // namespace leonova_a_radix_merge_sort
319