GCC Code Coverage Report

Directory: ./
File: tasks/akimov_i_radix_sort_double_batcher_merge/mpi/src/ops_mpi.cpp
Date: 2026-01-10 02:40:41
Exec Total Coverage
Lines: 136 161 84.5%
Functions: 12 17 70.6%
Branches: 104 176 59.1%
Line Branch Exec Source
1 #include "akimov_i_radix_sort_double_batcher_merge/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <cstdint>
8 #include <cstring>
9 #include <utility>
10 #include <vector>
11
12 #include "akimov_i_radix_sort_double_batcher_merge/common/include/common.hpp"
13
14 namespace akimov_i_radix_sort_double_batcher_merge {
15
16
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 AkimovIRadixBatcherSortMPI::AkimovIRadixBatcherSortMPI(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 GetInput() = in;
19 GetOutput() = {};
20 30 }
21
22 30 bool AkimovIRadixBatcherSortMPI::ValidationImpl() {
23 30 return true;
24 }
25 30 bool AkimovIRadixBatcherSortMPI::PreProcessingImpl() {
26 30 return true;
27 }
28 30 bool AkimovIRadixBatcherSortMPI::PostProcessingImpl() {
29 30 return true;
30 }
31
32 ✗ uint64_t AkimovIRadixBatcherSortMPI::PackDouble(double v) noexcept {
33 uint64_t bits = 0ULL;
34 std::memcpy(&bits, &v, sizeof(bits));
35 // transform IEEE-754 double to lexicographically sortable integer
36
2/4
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 58 if ((bits & (1ULL << 63)) != 0ULL) { // negative numbers
37 16 bits = ~bits;
38 } else { // positive numbers
39 42 bits ^= (1ULL << 63);
40 }
41 ✗ return bits;
42 }
43
44 ✗ double AkimovIRadixBatcherSortMPI::UnpackDouble(uint64_t k) noexcept {
45 ✗ if ((k & (1ULL << 63)) != 0ULL) {
46 42 k ^= (1ULL << 63);
47 } else {
48 16 k = ~k;
49 }
50 double value = 0.0;
51 std::memcpy(&value, &k, sizeof(value));
52 ✗ return value;
53 }
54
55
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 22 times.
 28 void AkimovIRadixBatcherSortMPI::LsdRadixSort(std::vector<double> &arr) {
56 const std::size_t n = arr.size();
57
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 22 times.
 28 if (n <= 1U) {
58 6 return;
59 }
60
61 constexpr int kBits = 8;
62 constexpr int kBuckets = 1 << kBits;
63 constexpr int kPasses = static_cast<int>((sizeof(uint64_t) * 8) / kBits);
64
65 22 std::vector<uint64_t> keys;
66
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 keys.resize(n);
67
2/2
✓ Branch 0 taken 58 times.
✓ Branch 1 taken 22 times.
 80 for (std::size_t i = 0; i < n; ++i) {
68
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 42 times.
 116 keys[i] = PackDouble(arr[i]);
69 }
70
71 22 std::vector<uint64_t> tmp_keys;
72
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 tmp_keys.resize(n);
73 22 std::vector<double> tmp_vals;
74
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 tmp_vals.resize(n);
75
76
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 22 times.
 198 for (int pass = 0; pass < kPasses; ++pass) {
77 176 int shift = pass * kBits;
78 176 std::vector<std::size_t> count;
79
1/4
✓ Branch 1 taken 176 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 176 count.assign(kBuckets + 1, 0U);
80
81
2/2
✓ Branch 0 taken 464 times.
✓ Branch 1 taken 176 times.
 640 for (std::size_t i = 0; i < n; ++i) {
82 464 auto digit = static_cast<std::size_t>((keys[i] >> shift) & (kBuckets - 1));
83 464 ++count[digit + 1];
84 }
85
86
2/2
✓ Branch 0 taken 45056 times.
✓ Branch 1 taken 176 times.
 45232 for (int i = 0; i < kBuckets; ++i) {
87 45056 count[i + 1] += count[i];
88 }
89
90
2/2
✓ Branch 0 taken 464 times.
✓ Branch 1 taken 176 times.
 640 for (std::size_t i = 0; i < n; ++i) {
91 464 auto digit = static_cast<std::size_t>((keys[i] >> shift) & (kBuckets - 1));
92 464 std::size_t pos = count[digit]++;
93 464 tmp_keys[pos] = keys[i];
94 464 tmp_vals[pos] = arr[i];
95 }
96
97 keys.swap(tmp_keys);
98 arr.swap(tmp_vals);
99 }
100
101
2/2
✓ Branch 0 taken 58 times.
✓ Branch 1 taken 22 times.
 80 for (std::size_t i = 0; i < n; ++i) {
102
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 16 times.
 116 arr[i] = UnpackDouble(keys[i]);
103 }
104 }
105
106 ✗ void AkimovIRadixBatcherSortMPI::CmpSwap(std::vector<double> &arr, int i, int j) noexcept {
107 ✗ const int sz = static_cast<int>(arr.size());
108 ✗ if (i < sz && j < sz && arr[i] > arr[j]) {
109 std::swap(arr[i], arr[j]);
110 }
111 ✗ }
112
113 // NOLINTNEXTLINE(misc-no-recursion)
114 ✗ void AkimovIRadixBatcherSortMPI::OddEvenMergeRec(std::vector<double> &arr, int start, int len, int stride) {
115 ✗ int step = stride * 2;
116 ✗ if (step < len) {
117 ✗ OddEvenMergeRec(arr, start, len, step);
118 ✗ OddEvenMergeRec(arr, start + stride, len, step);
119 ✗ for (int i = start + stride; i + stride < start + len; i += step) {
120 CmpSwap(arr, i, i + stride);
121 }
122 } else {
123 ✗ CmpSwap(arr, start, start + stride);
124 }
125 ✗ }
126
127 // NOLINTNEXTLINE(misc-no-recursion)
128 ✗ void AkimovIRadixBatcherSortMPI::OddEvenMergeSortRec(std::vector<double> &arr, int start, int len) {
129 ✗ if (len > 1) {
130 ✗ int mid = len / 2;
131 ✗ OddEvenMergeSortRec(arr, start, mid);
132 ✗ OddEvenMergeSortRec(arr, start + mid, len - mid);
133 ✗ OddEvenMergeRec(arr, start, len, 1);
134 }
135 ✗ }
136
137 28 std::vector<std::pair<int, int>> AkimovIRadixBatcherSortMPI::BuildOddEvenPhasePairs(int procs) {
138 28 std::vector<std::pair<int, int>> comparators;
139
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 if (procs <= 1) {
140 return comparators;
141 }
142
143 28 int num_phases = procs * 2;
144
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 28 times.
 140 for (int phase = 0; phase < num_phases; ++phase) {
145
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 56 times.
 112 if ((phase % 2) == 0) {
146
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 56 times.
 112 for (int i = 0; i + 1 < procs; i += 2) {
147
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 comparators.emplace_back(i, i + 1);
148 }
149 } else {
150
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 for (int i = 1; i + 1 < procs; i += 2) {
151 ✗ comparators.emplace_back(i, i + 1);
152 }
153 }
154 }
155
156 return comparators;
157 }
158
159 56 void AkimovIRadixBatcherSortMPI::ExchangeAndSelect(std::vector<double> &local, int partner, int /*rank*/,
160 bool keep_lower) {
161 56 int local_size = static_cast<int>(local.size());
162 56 int partner_size = 0;
163
164 56 MPI_Sendrecv(&local_size, 1, MPI_INT, partner, 0, &partner_size, 1, MPI_INT, partner, 0, MPI_COMM_WORLD,
165 MPI_STATUS_IGNORE);
166
167 56 std::vector<double> partner_data;
168
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 partner_data.resize(static_cast<std::size_t>(partner_size));
169
170
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 MPI_Sendrecv(local.data(), local_size, MPI_DOUBLE, partner, 1, partner_data.data(), partner_size, MPI_DOUBLE, partner,
171 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
172
173
3/4
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 54 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
 56 if (local_size == 0 && partner_size == 0) {
174 return;
175 }
176
177 56 std::vector<double> merged;
178
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 merged.reserve(static_cast<std::size_t>(local_size) + static_cast<std::size_t>(partner_size));
179
180 std::size_t i = 0U;
181 std::size_t j = 0U;
182
4/4
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 176 times.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 152 times.
 208 while (i < local.size() && j < partner_data.size()) {
183
2/2
✓ Branch 0 taken 83 times.
✓ Branch 1 taken 69 times.
 152 if (local[i] <= partner_data[j]) {
184
1/2
✓ Branch 0 taken 83 times.
✗ Branch 1 not taken.
 83 merged.push_back(local[i++]);
185 } else {
186
1/2
✓ Branch 0 taken 69 times.
✗ Branch 1 not taken.
 69 merged.push_back(partner_data[j++]);
187 }
188 }
189
2/2
✓ Branch 0 taken 43 times.
✓ Branch 1 taken 56 times.
 99 while (i < local.size()) {
190
1/2
✓ Branch 0 taken 43 times.
✗ Branch 1 not taken.
 43 merged.push_back(local[i++]);
191 }
192
2/2
✓ Branch 0 taken 57 times.
✓ Branch 1 taken 56 times.
 113 while (j < partner_data.size()) {
193
1/2
✓ Branch 0 taken 57 times.
✗ Branch 1 not taken.
 57 merged.push_back(partner_data[j++]);
194 }
195
196
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 28 times.
 56 if (keep_lower) {
197
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 auto mid_it = merged.begin() + static_cast<std::vector<double>::difference_type>(local_size);
198 28 local.assign(merged.begin(), mid_it);
199 } else {
200
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 auto start_it = merged.end() - static_cast<std::vector<double>::difference_type>(local_size);
201 28 local.assign(start_it, merged.end());
202 }
203 }
204
205 28 void AkimovIRadixBatcherSortMPI::ComputeCountsDispls(int total, int world, std::vector<int> &counts,
206 std::vector<int> &displs) {
207 28 int base_count = total / world;
208 28 int remainder = total % world;
209
210
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 28 times.
 84 for (int i = 0; i < world; ++i) {
211
4/4
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 28 times.
✓ Branch 3 taken 28 times.
 98 counts[i] = base_count + ((i < remainder) ? 1 : 0);
212
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 28 times.
 56 displs[i] = (i == 0) ? 0 : (displs[i - 1] + counts[i - 1]);
213 }
214 28 }
215
216 28 void AkimovIRadixBatcherSortMPI::ScatterData(int total, int world, int rank, std::vector<double> &data,
217 std::vector<int> &counts, std::vector<int> &displs,
218 std::vector<double> &local_data) {
219 28 ComputeCountsDispls(total, world, counts, displs);
220 28 local_data.resize(static_cast<std::size_t>(counts[rank]));
221 28 MPI_Scatterv(data.data(), counts.data(), displs.data(), MPI_DOUBLE, local_data.data(), counts[rank], MPI_DOUBLE, 0,
222 MPI_COMM_WORLD);
223 28 }
224
225 28 void AkimovIRadixBatcherSortMPI::PerformNetworkMerge(std::vector<double> &local_data, int world_size, int rank) {
226 28 auto comparators = BuildOddEvenPhasePairs(world_size);
227
228
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 28 times.
 84 for (const auto &pr : comparators) {
229 56 int proc1 = pr.first;
230 56 int proc2 = pr.second;
231
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 28 times.
 56 if (rank == proc1) {
232
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 ExchangeAndSelect(local_data, proc2, rank, true);
233
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 } else if (rank == proc2) {
234
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 ExchangeAndSelect(local_data, proc1, rank, false);
235 }
236
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 MPI_Barrier(MPI_COMM_WORLD);
237 }
238 28 }
239
240 28 void AkimovIRadixBatcherSortMPI::GatherData(std::vector<double> &local_data, int total_size, int world_size, int rank,
241 std::vector<double> &sorted_data) {
242
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 14 times.
 28 if (rank == 0) {
243 14 sorted_data.resize(static_cast<std::size_t>(total_size));
244 }
245
246 28 int new_local_size = static_cast<int>(local_data.size());
247 28 std::vector<int> new_counts;
248
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 new_counts.resize(static_cast<std::size_t>(world_size));
249
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 MPI_Gather(&new_local_size, 1, MPI_INT, new_counts.data(), 1, MPI_INT, 0, MPI_COMM_WORLD);
250
251 28 std::vector<int> new_displs;
252
1/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 28 new_displs.assign(static_cast<std::size_t>(world_size), 0);
253
254
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 14 times.
 28 if (rank == 0) {
255
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 14 times.
 28 for (int i = 1; i < world_size; ++i) {
256 14 new_displs[i] = new_displs[i - 1] + new_counts[i - 1];
257 }
258 }
259
260
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 MPI_Gatherv(local_data.data(), new_local_size, MPI_DOUBLE, sorted_data.data(), new_counts.data(), new_displs.data(),
261 MPI_DOUBLE, 0, MPI_COMM_WORLD);
262 28 }
263
264 30 bool AkimovIRadixBatcherSortMPI::RunImpl() {
265 30 int rank = 0;
266 30 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
267 30 int world_size = 0;
268 30 MPI_Comm_size(MPI_COMM_WORLD, &world_size);
269
270 30 int total_size = 0;
271 30 std::vector<double> data;
272
273
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 15 times.
 30 if (rank == 0) {
274
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 data = GetInput();
275 15 total_size = static_cast<int>(data.size());
276 }
277
278
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 MPI_Bcast(&total_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
279
280
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 28 times.
 30 if (total_size == 0) {
281
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 if (rank == 0) {
282 GetOutput() = {};
283 }
284 2 return true;
285 }
286
287 28 std::vector<int> counts;
288
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 counts.resize(static_cast<std::size_t>(world_size));
289 28 std::vector<int> displs;
290
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 displs.resize(static_cast<std::size_t>(world_size));
291 28 std::vector<double> local_data;
292
293
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 ScatterData(total_size, world_size, rank, data, counts, displs, local_data);
294
295
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 LsdRadixSort(local_data);
296
297
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 PerformNetworkMerge(local_data, world_size, rank);
298
299 28 std::vector<double> sorted_data;
300
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 GatherData(local_data, total_size, world_size, rank, sorted_data);
301
302
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 14 times.
 28 if (rank == 0) {
303
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 GetOutput() = sorted_data;
304 }
305
306 return true;
307 }
308
309 } // namespace akimov_i_radix_sort_double_batcher_merge
310