GCC Code Coverage Report

Directory: ./
File: tasks/sosnina_a_radix_simple_merge/all/src/ops_all.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 151 157 96.2%
Functions: 16 16 100.0%
Branches: 93 138 67.4%
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 1 taken 90 times.
✗ Branch 2 not taken.
 90 MPI_Scatterv(array.data(), send_counts.data(), send_displs.data(), MPI_INT, local_data.data(),
187 static_cast<int>(local_data.size()), MPI_INT, 0, MPI_COMM_WORLD);
188 90 }
189
190 90 std::vector<int> MergeTwoSorted(const std::vector<int> &left, const std::vector<int> &right) {
191 90 std::vector<int> result(left.size() + right.size());
192 size_t i = 0;
193 size_t j = 0;
194 size_t k = 0;
195
196
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()) {
197
2/2
✓ Branch 0 taken 216 times.
✓ Branch 1 taken 182 times.
 398 if (left[i] <= right[j]) {
198 216 result[k++] = left[i++];
199 } else {
200 182 result[k++] = right[j++];
201 }
202 }
203
204
2/2
✓ Branch 0 taken 108 times.
✓ Branch 1 taken 90 times.
 198 while (i < left.size()) {
205 108 result[k++] = left[i++];
206 }
207
208
2/2
✓ Branch 0 taken 142 times.
✓ Branch 1 taken 90 times.
 232 while (j < right.size()) {
209 142 result[k++] = right[j++];
210 }
211
212 90 return result;
213 }
214
215 90 void ExchangeAndMerge(int partner, std::vector<int> &merged_data) {
216 90 const size_t my_size = merged_data.size();
217 90 size_t partner_size = 0;
218
219 90 MPI_Sendrecv(&my_size, 1, MPI_UNSIGNED_LONG, partner, 0, &partner_size, 1, MPI_UNSIGNED_LONG, partner, 0,
220 MPI_COMM_WORLD, MPI_STATUS_IGNORE);
221
222 90 std::vector<int> partner_data(partner_size);
223
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 MPI_Sendrecv(merged_data.data(), static_cast<int>(my_size), MPI_INT, partner, 1, partner_data.data(),
224 static_cast<int>(partner_size), MPI_INT, partner, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
225
226
2/6
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 90 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 180 merged_data = MergeTwoSorted(merged_data, partner_data);
227 90 }
228
229 void ParallelHypercubeMerge(std::vector<int> &merged_data, int mpi_rank, int mpi_size) {
230 int step = 1;
231
232
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 90 times.
 180 while (step < mpi_size) {
233 90 const int partner = mpi_rank ^ step;
234
235
1/2
✓ Branch 0 taken 90 times.
✗ Branch 1 not taken.
 90 if (partner < mpi_size) {
236
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 ExchangeAndMerge(partner, merged_data);
237 }
238
239 90 step <<= 1;
240 }
241 }
242
243 90 void BcastSortedVector(std::vector<int> &data, int mpi_rank) {
244 90 size_t n = data.size();
245 90 MPI_Bcast(&n, 1, MPI_UNSIGNED_LONG, 0, MPI_COMM_WORLD);
246
2/2
✓ Branch 0 taken 45 times.
✓ Branch 1 taken 45 times.
 90 if (mpi_rank != 0) {
247 45 data.resize(n);
248 }
249
1/2
✓ Branch 0 taken 90 times.
✗ Branch 1 not taken.
 90 if (n > 0U) {
250 90 MPI_Bcast(data.data(), static_cast<int>(n), MPI_INT, 0, MPI_COMM_WORLD);
251 }
252 90 }
253
254 } // namespace
255
256
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 SosninaATestTaskALL::SosninaATestTaskALL(const InType &in) {
257 SetTypeOfTask(GetStaticTypeOfTask());
258
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 GetInput() = in;
259
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 GetOutput() = in;
260 96 }
261
262 96 bool SosninaATestTaskALL::ValidationImpl() {
263 96 return !GetInput().empty();
264 }
265
266 96 bool SosninaATestTaskALL::PreProcessingImpl() {
267 96 GetOutput() = GetInput();
268 96 return true;
269 }
270
271 96 bool SosninaATestTaskALL::RunImpl() {
272 96 int mpi_rank = 0;
273 96 int mpi_size = 1;
274
275 96 MPI_Comm_rank(MPI_COMM_WORLD, &mpi_rank);
276 96 MPI_Comm_size(MPI_COMM_WORLD, &mpi_size);
277
278 std::vector<int> &data = GetOutput();
279 const size_t total_size = data.size();
280
281
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 6 times.
 96 if (total_size <= 1) {
282 return true;
283 }
284
285 90 std::vector<size_t> chunk_sizes(static_cast<size_t>(mpi_size));
286
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));
287 90 ComputeChunkParams(total_size, mpi_size, chunk_sizes, offsets);
288
289
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)]);
290
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 ScatterData(data, local_data, chunk_sizes, offsets);
291
292
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 SortLocalStlParallel(local_data);
293
294
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 90 times.
 90 if (mpi_size == 1) {
295 data = std::move(local_data);
296 return std::ranges::is_sorted(data);
297 }
298
299 std::vector<int> merged_data = std::move(local_data);
300 90 ParallelHypercubeMerge(merged_data, mpi_rank, mpi_size);
301
302
2/2
✓ Branch 0 taken 45 times.
✓ Branch 1 taken 45 times.
 90 if (mpi_rank == 0) {
303 data = std::move(merged_data);
304 } else {
305 data.clear();
306 }
307
308
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 BcastSortedVector(data, mpi_rank);
309
310
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 MPI_Barrier(MPI_COMM_WORLD);
311 return std::ranges::is_sorted(data);
312 }
313
314 96 bool SosninaATestTaskALL::PostProcessingImpl() {
315 96 return !GetOutput().empty();
316 }
317
318 } // namespace sosnina_a_radix_simple_merge
319