GCC Code Coverage Report

Directory: ./
File: tasks/sosnina_a_radix_simple_merge/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 162 169 95.9%
Functions: 16 16 100.0%
Branches: 100 152 65.8%
Line Branch Exec Source
1 #include "sosnina_a_radix_simple_merge/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <array>
7 #include <cstddef>
8 #include <cstdint>
9 #include <thread>
10 #include <type_traits>
11 #include <utility>
12 #include <vector>
13
14 #include "sosnina_a_radix_simple_merge/common/include/common.hpp"
15 #include "util/include/util.hpp"
16
17 namespace sosnina_a_radix_simple_merge {
18
19 namespace {
20
21 constexpr int kRadixBits = 8;
22 constexpr int kRadixSize = 1 << kRadixBits;
23 constexpr int kNumPasses = sizeof(int) / sizeof(uint8_t);
24 constexpr uint32_t kSignFlip = 0x80000000U;
25 constexpr size_t kMinElementsPerPart = 4096;
26 constexpr size_t kMinElementsPerPartSmall = 32768;
27 constexpr size_t kSmallArrayThreshold = 1'000'000;
28 constexpr size_t kLargeArrayThreshold = 20'000'000;
29
30 160 void RadixSortLSD(std::vector<int> &data, std::vector<int> &buffer) {
31 size_t idx = 0;
32
2/2
✓ Branch 0 taken 314 times.
✓ Branch 1 taken 160 times.
 474 for (int elem : data) {
33 314 buffer[idx++] = static_cast<int>(static_cast<uint32_t>(elem) ^ kSignFlip);
34 }
35 std::swap(data, buffer);
36
37
2/2
✓ Branch 0 taken 640 times.
✓ Branch 1 taken 160 times.
 800 for (int pass = 0; pass < kNumPasses; ++pass) {
38 640 std::array<int, kRadixSize + 1> count{};
39
40
2/2
✓ Branch 0 taken 1256 times.
✓ Branch 1 taken 640 times.
 1896 for (auto elem : data) {
41 1256 auto digit = static_cast<uint8_t>((static_cast<uint32_t>(elem) >> (pass * kRadixBits)) & 0xFF);
42 1256 ++count.at(static_cast<size_t>(digit) + 1U);
43 }
44
45
2/2
✓ Branch 0 taken 163840 times.
✓ Branch 1 taken 640 times.
 164480 for (int i = 1; i <= kRadixSize; ++i) {
46 163840 const auto ui = static_cast<size_t>(i);
47 163840 count.at(ui) += count.at(ui - 1U);
48 }
49
50
2/2
✓ Branch 0 taken 1256 times.
✓ Branch 1 taken 640 times.
 1896 for (auto elem : data) {
51 1256 auto digit = static_cast<uint8_t>((static_cast<uint32_t>(elem) >> (pass * kRadixBits)) & 0xFF);
52 1256 const auto di = static_cast<size_t>(digit);
53 1256 const int write_pos = count.at(di)++;
54 1256 buffer[static_cast<size_t>(write_pos)] = elem;
55 }
56
57 std::swap(data, buffer);
58 }
59
60
2/2
✓ Branch 0 taken 314 times.
✓ Branch 1 taken 160 times.
 474 for (int &elem : data) {
61 314 elem = static_cast<int>(static_cast<uint32_t>(elem) ^ kSignFlip);
62 }
63 160 }
64
65 void SimpleMerge(const std::vector<int> &left, const std::vector<int> &right, std::vector<int> &result) {
66 80 std::ranges::merge(left, right, result.begin());
67 }
68
69 template <typename F>
70 320 void ParallelForRange(size_t begin, size_t end, int num_threads, F &&fn) {
71
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 160 times.
 320 if (begin >= end) {
72 ✗ return;
73 }
74 320 std::decay_t<F> func{std::forward<F>(fn)};
75
4/4
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 80 times.
✓ Branch 2 taken 80 times.
✓ Branch 3 taken 80 times.
 480 num_threads = std::max(1, std::min(num_threads, static_cast<int>(end - begin)));
76 320 const size_t n = end - begin;
77 320 const size_t chunk = (n + static_cast<size_t>(num_threads) - 1) / static_cast<size_t>(num_threads);
78 320 std::vector<std::thread> threads;
79
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 160 times.
 800 for (int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
80 480 const size_t lo = begin + (static_cast<size_t>(thread_idx) * chunk);
81
1/2
✓ Branch 0 taken 240 times.
✗ Branch 1 not taken.
 480 if (lo >= end) {
82 break;
83 }
84
1/2
✓ Branch 1 taken 240 times.
✗ Branch 2 not taken.
 480 const size_t hi = std::min(end, lo + chunk);
85
1/2
✓ Branch 1 taken 240 times.
✗ Branch 2 not taken.
 480 threads.emplace_back([lo, hi, &func]() {
86
4/4
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 160 times.
✓ Branch 2 taken 80 times.
✓ Branch 3 taken 80 times.
 480 for (size_t i = lo; i < hi; ++i) {
87 240 func(i);
88 }
89 });
90 }
91
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 160 times.
 800 for (auto &th : threads) {
92
1/2
✓ Branch 1 taken 240 times.
✗ Branch 2 not taken.
 480 th.join();
93 }
94 320 }
95
96 /// Локальная параллельная radix + merge (как STL): потоки внутри MPI-процесса.
97
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 10 times.
 90 void SortLocalStlParallel(std::vector<int> &data) {
98
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 10 times.
 90 if (data.size() <= 1) {
99 10 return;
100 }
101
102
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 80 times.
 80 const int num_threads = ppc::util::GetNumThreads();
103 const size_t per_thread_floor = data.size() >= kLargeArrayThreshold
104
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 ? (data.size() / static_cast<size_t>(std::max(1, num_threads)))
105 80 : (data.size() / static_cast<size_t>(std::max(1, 2 * num_threads)));
106 80 size_t min_chunk_base = kMinElementsPerPart;
107
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 if (data.size() < kMinElementsPerPartSmall) {
108 80 min_chunk_base = std::max(size_t{1}, data.size() / static_cast<size_t>(std::max(1, 2 * num_threads)));
109 ✗ } else if (data.size() < kSmallArrayThreshold) {
110 ✗ min_chunk_base = kMinElementsPerPartSmall;
111 }
112 const size_t min_chunk = std::max(min_chunk_base, per_thread_floor);
113 80 const int max_parts_by_grain = std::max(1, static_cast<int>(data.size() / min_chunk));
114 80 const int num_parts = std::min({num_threads, static_cast<int>(data.size()), max_parts_by_grain});
115
116
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 if (num_parts <= 1) {
117 ✗ std::vector<int> buffer(data.size());
118 ✗ RadixSortLSD(data, buffer);
119 return;
120 }
121
122 80 std::vector<std::vector<int>> parts(static_cast<size_t>(num_parts));
123 80 const size_t base_size = data.size() / static_cast<size_t>(num_parts);
124 80 const size_t remainder = data.size() % static_cast<size_t>(num_parts);
125 size_t pos = 0;
126
127
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 80 times.
 240 for (int i = 0; i < num_parts; ++i) {
128 160 const size_t part_size = base_size + (std::cmp_less(i, remainder) ? 1U : 0U);
129
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 parts[static_cast<size_t>(i)].assign(data.begin() + static_cast<std::ptrdiff_t>(pos),
130
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 data.begin() + static_cast<std::ptrdiff_t>(pos + part_size));
131 pos += part_size;
132 }
133
134
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 ParallelForRange(0, static_cast<size_t>(num_parts), num_threads, [&](size_t i) {
135 160 auto &part = parts[i];
136 160 std::vector<int> buffer(part.size());
137 160 RadixSortLSD(part, buffer);
138 160 });
139
140 std::vector<std::vector<int>> current = std::move(parts);
141
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 80 times.
 160 while (current.size() > 1) {
142 80 const size_t half = (current.size() + 1) / 2;
143
2/4
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 80 times.
✗ Branch 5 not taken.
 80 std::vector<std::vector<int>> next(half);
144
145 80 const size_t pair_count = current.size() / 2;
146
2/4
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 80 times.
 80 ParallelForRange(0, pair_count, num_threads, [&](size_t idx) {
147 80 auto &left = current[2 * idx];
148 auto &right = current[(2 * idx) + 1];
149 80 next[idx].resize(left.size() + right.size());
150 80 SimpleMerge(left, right, next[idx]);
151 std::vector<int>().swap(left);
152 std::vector<int>().swap(right);
153 80 });
154
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 if (current.size() % 2 == 1) {
155 ✗ next[half - 1] = std::move(current.back());
156 }
157 80 current = std::move(next);
158 80 }
159
160 data = std::move(current[0]);
161 80 }
162
163 90 void ComputeChunkParams(size_t total_size, int mpi_size, std::vector<size_t> &chunk_sizes,
164 std::vector<size_t> &offsets) {
165 90 const size_t base_chunk = total_size / static_cast<size_t>(mpi_size);
166 90 const size_t remainder = total_size % static_cast<size_t>(mpi_size);
167
168
2/2
✓ Branch 0 taken 180 times.
✓ Branch 1 taken 90 times.
 270 for (int i = 0; i < mpi_size; ++i) {
169
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 90 times.
 180 chunk_sizes[static_cast<size_t>(i)] = base_chunk + (std::cmp_less(i, remainder) ? 1U : 0U);
170 180 offsets[static_cast<size_t>(i)] =
171
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 90 times.
 180 (i == 0) ? 0 : offsets[static_cast<size_t>(i - 1)] + chunk_sizes[static_cast<size_t>(i - 1)];
172 }
173 90 }
174
175 90 void ScatterData(const std::vector<int> &array, std::vector<int> &local_data, const std::vector<size_t> &chunk_sizes,
176 const std::vector<size_t> &offsets) {
177 90 const int mpi_size = static_cast<int>(chunk_sizes.size());
178 90 std::vector<int> send_counts(mpi_size);
179
1/4
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 90 std::vector<int> send_displs(mpi_size);
180
181
2/2
✓ Branch 0 taken 180 times.
✓ Branch 1 taken 90 times.
 270 for (int i = 0; i < mpi_size; ++i) {
182 180 send_counts[i] = static_cast<int>(chunk_sizes[static_cast<size_t>(i)]);
183 180 send_displs[i] = static_cast<int>(offsets[static_cast<size_t>(i)]);
184 }
185
186
1/2
✓ Branch 0 taken 90 times.
✗ Branch 1 not taken.
 90 int recv_dummy = 0;
187
1/2
✓ Branch 0 taken 90 times.
✗ Branch 1 not taken.
 90 int *const recv_buf = local_data.empty() ? &recv_dummy : local_data.data();
188
1/2
✓ Branch 0 taken 90 times.
✗ Branch 1 not taken.
 90 const int *const send_buf = array.empty() ? &recv_dummy : array.data();
189
190
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 MPI_Scatterv(send_buf, send_counts.data(), send_displs.data(), MPI_INT, recv_buf, static_cast<int>(local_data.size()),
191 MPI_INT, 0, MPI_COMM_WORLD);
192 90 }
193
194 90 std::vector<int> MergeTwoSorted(const std::vector<int> &left, const std::vector<int> &right) {
195 90 std::vector<int> result(left.size() + right.size());
196 size_t i = 0;
197 size_t j = 0;
198 size_t k = 0;
199
200
4/4
✓ Branch 0 taken 435 times.
✓ Branch 1 taken 53 times.
✓ Branch 2 taken 37 times.
✓ Branch 3 taken 398 times.
 488 while (i < left.size() && j < right.size()) {
201
2/2
✓ Branch 0 taken 216 times.
✓ Branch 1 taken 182 times.
 398 if (left[i] <= right[j]) {
202 216 result[k++] = left[i++];
203 } else {
204 182 result[k++] = right[j++];
205 }
206 }
207
208
2/2
✓ Branch 0 taken 108 times.
✓ Branch 1 taken 90 times.
 198 while (i < left.size()) {
209 108 result[k++] = left[i++];
210 }
211
212
2/2
✓ Branch 0 taken 142 times.
✓ Branch 1 taken 90 times.
 232 while (j < right.size()) {
213 142 result[k++] = right[j++];
214 }
215
216 90 return result;
217 }
218
219 90 void ExchangeAndMerge(int partner, std::vector<int> &merged_data) {
220 90 const auto my_size_u64 = static_cast<uint64_t>(merged_data.size());
221 90 uint64_t partner_size_u64 = 0;
222
223 90 MPI_Sendrecv(&my_size_u64, 1, MPI_UINT64_T, partner, 0, &partner_size_u64, 1, MPI_UINT64_T, partner, 0,
224 MPI_COMM_WORLD, MPI_STATUS_IGNORE);
225
226 const size_t my_size = merged_data.size();
227 90 const auto partner_size = static_cast<size_t>(partner_size_u64);
228
229
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 90 times.
 90 if (my_size == 0 && partner_size == 0) {
230 ✗ return;
231 }
232
233 90 std::vector<int> partner_data(partner_size);
234 90 int send_dummy = 0;
235 90 int recv_dummy = 0;
236
1/2
✓ Branch 0 taken 90 times.
✗ Branch 1 not taken.
 90 int *const send_buf = (my_size > 0) ? merged_data.data() : &send_dummy;
237
1/2
✓ Branch 0 taken 90 times.
✗ Branch 1 not taken.
 90 int *const recv_buf = (partner_size > 0) ? partner_data.data() : &recv_dummy;
238
239
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 MPI_Sendrecv(send_buf, static_cast<int>(my_size), MPI_INT, partner, 1, recv_buf, static_cast<int>(partner_size),
240 MPI_INT, partner, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
241
242
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 90 times.
 90 if (my_size == 0) {
243 merged_data = std::move(partner_data);
244
1/2
✓ Branch 0 taken 90 times.
✗ Branch 1 not taken.
 90 } else if (partner_size > 0) {
245
1/4
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 180 merged_data = MergeTwoSorted(merged_data, partner_data);
246 }
247 }
248
249 void ParallelHypercubeMerge(std::vector<int> &merged_data, int mpi_rank, int mpi_size) {
250 int step = 1;
251
252
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 90 times.
 180 while (step < mpi_size) {
253 90 const int partner = mpi_rank ^ step;
254
255
1/2
✓ Branch 0 taken 90 times.
✗ Branch 1 not taken.
 90 if (partner < mpi_size) {
256
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 ExchangeAndMerge(partner, merged_data);
257 }
258
259 90 step <<= 1;
260 }
261 }
262
263 90 void BcastSortedVector(std::vector<int> &data, int mpi_rank) {
264 90 auto n_u64 = static_cast<uint64_t>(data.size());
265 90 MPI_Bcast(&n_u64, 1, MPI_UINT64_T, 0, MPI_COMM_WORLD);
266 90 const auto n = static_cast<size_t>(n_u64);
267
2/2
✓ Branch 0 taken 45 times.
✓ Branch 1 taken 45 times.
 90 if (mpi_rank != 0) {
268 45 data.resize(n);
269 }
270
1/2
✓ Branch 0 taken 90 times.
✗ Branch 1 not taken.
 90 if (n > 0U) {
271 90 MPI_Bcast(data.data(), static_cast<int>(n), MPI_INT, 0, MPI_COMM_WORLD);
272 }
273 90 }
274
275 } // namespace
276
277
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 SosninaATestTaskALL::SosninaATestTaskALL(const InType &in) {
278 SetTypeOfTask(GetStaticTypeOfTask());
279
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 GetInput() = in;
280
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 GetOutput() = in;
281 96 }
282
283 96 bool SosninaATestTaskALL::ValidationImpl() {
284 96 return !GetInput().empty();
285 }
286
287 96 bool SosninaATestTaskALL::PreProcessingImpl() {
288 96 GetOutput() = GetInput();
289 96 return true;
290 }
291
292 96 bool SosninaATestTaskALL::RunImpl() {
293 96 int mpi_rank = 0;
294 96 int mpi_size = 1;
295
296 96 MPI_Comm_rank(MPI_COMM_WORLD, &mpi_rank);
297 96 MPI_Comm_size(MPI_COMM_WORLD, &mpi_size);
298
299 std::vector<int> &data = GetOutput();
300 const size_t total_size = data.size();
301
302
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 6 times.
 96 if (total_size <= 1) {
303 return true;
304 }
305
306 90 std::vector<size_t> chunk_sizes(static_cast<size_t>(mpi_size));
307
1/4
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 90 std::vector<size_t> offsets(static_cast<size_t>(mpi_size));
308 90 ComputeChunkParams(total_size, mpi_size, chunk_sizes, offsets);
309
310
1/4
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 90 std::vector<int> local_data(chunk_sizes[static_cast<size_t>(mpi_rank)]);
311
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 ScatterData(data, local_data, chunk_sizes, offsets);
312
313
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 SortLocalStlParallel(local_data);
314
315
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 90 times.
 90 if (mpi_size == 1) {
316 data = std::move(local_data);
317 return std::ranges::is_sorted(data);
318 }
319
320 std::vector<int> merged_data = std::move(local_data);
321 90 ParallelHypercubeMerge(merged_data, mpi_rank, mpi_size);
322
323
2/2
✓ Branch 0 taken 45 times.
✓ Branch 1 taken 45 times.
 90 if (mpi_rank == 0) {
324 data = std::move(merged_data);
325 } else {
326 data.clear();
327 }
328
329
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 BcastSortedVector(data, mpi_rank);
330
331
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 MPI_Barrier(MPI_COMM_WORLD);
332 return std::ranges::is_sorted(data);
333 }
334
335 96 bool SosninaATestTaskALL::PostProcessingImpl() {
336 96 return !GetOutput().empty();
337 }
338
339 } // namespace sosnina_a_radix_simple_merge
340