GCC Code Coverage Report

Directory: ./
File: tasks/yushkova_p_hoare_sorting_simple_merging/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 135 142 95.1%
Functions: 18 18 100.0%
Branches: 97 136 71.3%
Line Branch Exec Source
1 #include "yushkova_p_hoare_sorting_simple_merging/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <cstdint>
8 #include <exception>
9 #include <mutex>
10 #include <stack>
11 #include <thread>
12 #include <utility>
13 #include <vector>
14
15 #include "yushkova_p_hoare_sorting_simple_merging/common/include/common.hpp"
16
17 namespace yushkova_p_hoare_sorting_simple_merging {
18
19 namespace {
20
21 constexpr std::size_t kBlockSize = 64;
22
23 std::size_t GetThreadCount(std::size_t task_count) {
24 33 if (task_count == 0) {
25 return 0;
26 }
27 33 const unsigned int hardware_threads = std::thread::hardware_concurrency();
28
2/4
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 30 times.
✗ Branch 3 not taken.
 33 const std::size_t available_threads = hardware_threads == 0 ? 2 : static_cast<std::size_t>(hardware_threads);
29 return std::min(task_count, available_threads);
30 }
31
32 template <class Function>
33 void RunSequentialTasks(std::size_t task_count, Function function) {
34
4/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 27 times.
✓ Branch 3 taken 27 times.
 60 for (std::size_t task_index = 0; task_index < task_count; ++task_index) {
35 30 function(task_index);
36 }
37 }
38
39 template <class Function>
40 6 void RunThreadWorker(std::size_t thread_index, std::size_t thread_count, std::size_t task_count, Function &function,
41 std::exception_ptr &exception_ptr, std::mutex &exception_mutex) {
42 try {
43
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 6 times.
 12 for (std::size_t task_index = thread_index; task_index < task_count; task_index += thread_count) {
44
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 function(task_index);
45 }
46 ✗ } catch (...) {
47 std::scoped_lock lock(exception_mutex);
48 ✗ if (!exception_ptr) {
49 ✗ exception_ptr = std::current_exception();
50 }
51 }
52 6 }
53
54 template <class Function>
55
1/2
✓ Branch 0 taken 33 times.
✗ Branch 1 not taken.
 66 void RunInThreads(std::size_t task_count, Function function) {
56 const std::size_t thread_count = GetThreadCount(task_count);
57
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 3 times.
 66 if (thread_count <= 1) {
58 60 RunSequentialTasks(task_count, function);
59 60 return;
60 }
61
62 6 std::vector<std::thread> threads;
63
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 threads.reserve(thread_count);
64 std::exception_ptr exception_ptr;
65 6 std::mutex exception_mutex;
66
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 3 times.
 18 for (std::size_t thread_index = 0; thread_index < thread_count; ++thread_index) {
67
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 24 threads.emplace_back([thread_index, thread_count, task_count, &function, &exception_ptr, &exception_mutex]() {
68 6 RunThreadWorker(thread_index, thread_count, task_count, function, exception_ptr, exception_mutex);
69 });
70 }
71
72
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 3 times.
 18 for (auto &thread : threads) {
73
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 12 thread.join();
74 }
75
76
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 6 if (exception_ptr) {
77 ✗ std::rethrow_exception(exception_ptr);
78 }
79 6 }
80
81 64 std::vector<int> MakeIntVector(const std::vector<std::size_t> &values) {
82 64 std::vector<int> result(values.size());
83
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 64 times.
 192 for (std::size_t i = 0; i < values.size(); ++i) {
84 128 result[i] = static_cast<int>(values[i]);
85 }
86 64 return result;
87 }
88
89 32 void BuildDistribution(std::size_t total_size, int mpi_size, std::vector<std::size_t> &chunk_sizes,
90 std::vector<std::size_t> &offsets) {
91 32 const std::size_t base_size = total_size / static_cast<std::size_t>(mpi_size);
92 32 const std::size_t remainder = total_size % static_cast<std::size_t>(mpi_size);
93
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 32 times.
 96 for (int rank = 0; rank < mpi_size; ++rank) {
94 64 const auto index = static_cast<std::size_t>(rank);
95
4/4
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 12 times.
✓ Branch 2 taken 32 times.
✓ Branch 3 taken 32 times.
 116 chunk_sizes[index] = base_size + (index < remainder ? 1U : 0U);
96
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
 64 offsets[index] = rank == 0 ? 0 : offsets[index - 1] + chunk_sizes[index - 1];
97 }
98 32 }
99
100 } // namespace
101
102
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 YushkovaPHoareSortingSimpleMergingALL::YushkovaPHoareSortingSimpleMergingALL(const InType &in) {
103 SetTypeOfTask(GetStaticTypeOfTask());
104
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 GetInput() = in;
105 GetOutput().clear();
106 34 }
107
108 671 int YushkovaPHoareSortingSimpleMergingALL::HoarePartition(std::vector<int> &values, int left, int right) {
109 671 const int pivot = values[left + ((right - left) / 2)];
110 671 int i = left - 1;
111 671 int j = right + 1;
112
113 while (true) {
114 1294 ++i;
115
2/2
✓ Branch 0 taken 845 times.
✓ Branch 1 taken 1294 times.
 2139 while (values[i] < pivot) {
116 845 ++i;
117 }
118
119 1294 --j;
120
2/2
✓ Branch 0 taken 1207 times.
✓ Branch 1 taken 1294 times.
 2501 while (values[j] > pivot) {
121 1207 --j;
122 }
123
124
2/2
✓ Branch 0 taken 671 times.
✓ Branch 1 taken 623 times.
 1294 if (i >= j) {
125 671 return j;
126 }
127
128 std::swap(values[i], values[j]);
129 }
130 }
131
132 30 void YushkovaPHoareSortingSimpleMergingALL::HoareQuickSort(std::vector<int> &values, int left, int right) {
133 std::stack<std::pair<int, int>> ranges;
134 ranges.emplace(left, right);
135
136
2/2
✓ Branch 0 taken 1372 times.
✓ Branch 1 taken 30 times.
 1402 while (!ranges.empty()) {
137 auto [current_left, current_right] = ranges.top();
138 ranges.pop();
139
140
2/2
✓ Branch 0 taken 701 times.
✓ Branch 1 taken 671 times.
 1372 if (current_left >= current_right) {
141 701 continue;
142 }
143
144 671 const int partition_index = HoarePartition(values, current_left, current_right);
145
146
2/2
✓ Branch 0 taken 66 times.
✓ Branch 1 taken 605 times.
 671 if ((partition_index - current_left) > (current_right - (partition_index + 1))) {
147 ranges.emplace(current_left, partition_index);
148
1/2
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
 66 ranges.emplace(partition_index + 1, current_right);
149 } else {
150
2/4
✓ Branch 1 taken 605 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 605 times.
✗ Branch 5 not taken.
 605 ranges.emplace(partition_index + 1, current_right);
151 ranges.emplace(current_left, partition_index);
152 }
153 }
154 30 }
155
156 19 void YushkovaPHoareSortingSimpleMergingALL::SimpleMerge(const std::vector<int> &source, std::vector<int> &destination,
157 std::size_t left, std::size_t middle, std::size_t right) {
158 std::size_t left_index = left;
159 std::size_t right_index = middle;
160 std::size_t destination_index = left;
161
162
2/2
✓ Branch 0 taken 445 times.
✓ Branch 1 taken 19 times.
 464 while (left_index < middle && right_index < right) {
163
2/2
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 245 times.
 445 if (source[left_index] <= source[right_index]) {
164 200 destination[destination_index++] = source[left_index++];
165 } else {
166 245 destination[destination_index++] = source[right_index++];
167 }
168 }
169
170
2/2
✓ Branch 0 taken 348 times.
✓ Branch 1 taken 19 times.
 367 while (left_index < middle) {
171 348 destination[destination_index++] = source[left_index++];
172 }
173
174
2/2
✓ Branch 0 taken 108 times.
✓ Branch 1 taken 19 times.
 127 while (right_index < right) {
175 108 destination[destination_index++] = source[right_index++];
176 }
177 19 }
178
179
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 2 times.
 32 void YushkovaPHoareSortingSimpleMergingALL::SortLocalStlParallel(std::vector<int> &values) {
180
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 2 times.
 32 if (values.size() <= 1) {
181 return;
182 }
183
184 const std::size_t size = values.size();
185 30 const std::size_t block_count = (size + kBlockSize - 1) / kBlockSize;
186
187 30 RunInThreads(block_count, [&values, size](std::size_t block_index) {
188 33 const std::size_t block_start = block_index * kBlockSize;
189
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 3 times.
 33 const std::size_t block_end = std::min(block_start + kBlockSize, size);
190
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 3 times.
 33 if ((block_end - block_start) > 1) {
191 30 HoareQuickSort(values, static_cast<int>(block_start), static_cast<int>(block_end - 1));
192 }
193 33 });
194
195
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 30 times.
 33 for (std::size_t merge_width = kBlockSize; merge_width < size; merge_width *= 2) {
196 3 std::vector<int> merged_data(size);
197 3 const std::size_t merge_count = (size + (2 * merge_width) - 1) / (2 * merge_width);
198
199
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 RunInThreads(merge_count, [&values, size, merge_width, &merged_data](std::size_t merge_index) {
200 3 const std::size_t left = merge_index * 2 * merge_width;
201
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 const std::size_t middle = std::min(left + merge_width, size);
202 3 const std::size_t right = std::min(left + (2 * merge_width), size);
203
204
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if (middle < right) {
205 3 SimpleMerge(values, merged_data, left, middle, right);
206 } else {
207 ✗ std::copy(values.begin() + static_cast<std::ptrdiff_t>(left),
208 ✗ values.begin() + static_cast<std::ptrdiff_t>(right),
209 ✗ merged_data.begin() + static_cast<std::ptrdiff_t>(left));
210 }
211 3 });
212
213 values.swap(merged_data);
214 }
215 }
216
217 16 void YushkovaPHoareSortingSimpleMergingALL::MergeGatheredChunks(std::vector<int> &values,
218 const std::vector<std::size_t> &chunk_sizes,
219 const std::vector<std::size_t> &offsets) {
220 16 std::vector<int> merged_data(values.size());
221
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 for (std::size_t rank = 1; rank < chunk_sizes.size(); ++rank) {
222 const std::size_t left = 0;
223 16 const std::size_t middle = offsets[rank];
224 16 const std::size_t right = middle + chunk_sizes[rank];
225 16 SimpleMerge(values, merged_data, left, middle, right);
226 16 std::copy(merged_data.begin(), merged_data.begin() + static_cast<std::ptrdiff_t>(right), values.begin());
227 }
228 16 }
229
230 32 void YushkovaPHoareSortingSimpleMergingALL::BroadcastVector(std::vector<int> &values, int rank) {
231 32 auto size = static_cast<std::uint64_t>(values.size());
232 32 MPI_Bcast(&size, 1, MPI_UINT64_T, 0, MPI_COMM_WORLD);
233
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 if (rank != 0) {
234 16 values.resize(static_cast<std::size_t>(size));
235 }
236
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if (size > 0) {
237 32 MPI_Bcast(values.data(), static_cast<int>(size), MPI_INT, 0, MPI_COMM_WORLD);
238 }
239 32 }
240
241 34 bool YushkovaPHoareSortingSimpleMergingALL::ValidationImpl() {
242 34 return !GetInput().empty();
243 }
244
245 34 bool YushkovaPHoareSortingSimpleMergingALL::PreProcessingImpl() {
246 34 GetOutput() = GetInput();
247 34 return true;
248 }
249
250 34 bool YushkovaPHoareSortingSimpleMergingALL::RunImpl() {
251 34 int rank = 0;
252 34 int mpi_size = 1;
253 34 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
254 34 MPI_Comm_size(MPI_COMM_WORLD, &mpi_size);
255
256 const std::size_t total_size = GetOutput().size();
257
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 2 times.
 34 if (total_size <= 1) {
258 return true;
259 }
260
261 32 std::vector<std::size_t> chunk_sizes(static_cast<std::size_t>(mpi_size));
262
1/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 32 std::vector<std::size_t> offsets(static_cast<std::size_t>(mpi_size));
263 32 BuildDistribution(total_size, mpi_size, chunk_sizes, offsets);
264
265
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 const std::vector<int> send_counts = MakeIntVector(chunk_sizes);
266
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 const std::vector<int> send_offsets = MakeIntVector(offsets);
267
268
1/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 32 std::vector<int> local_data(chunk_sizes[static_cast<std::size_t>(rank)]);
269
3/4
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
✓ Branch 3 taken 32 times.
✗ Branch 4 not taken.
 48 MPI_Scatterv(rank == 0 ? GetOutput().data() : nullptr, send_counts.data(), send_offsets.data(), MPI_INT,
270
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 local_data.data(), send_counts[static_cast<std::size_t>(rank)], MPI_INT, 0, MPI_COMM_WORLD);
271
272
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 SortLocalStlParallel(local_data);
273
274 32 std::vector<int> gathered_data;
275
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 if (rank == 0) {
276
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 gathered_data.resize(total_size);
277 }
278
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 MPI_Gatherv(local_data.data(), static_cast<int>(local_data.size()), MPI_INT,
279
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 rank == 0 ? gathered_data.data() : nullptr, send_counts.data(), send_offsets.data(), MPI_INT, 0,
280 MPI_COMM_WORLD);
281
282
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 if (rank == 0) {
283
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 MergeGatheredChunks(gathered_data, chunk_sizes, offsets);
284 GetOutput() = std::move(gathered_data);
285 }
286
287
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 BroadcastVector(GetOutput(), rank);
288 return std::ranges::is_sorted(GetOutput());
289 }
290
291
1/2
✓ Branch 0 taken 34 times.
✗ Branch 1 not taken.
 34 bool YushkovaPHoareSortingSimpleMergingALL::PostProcessingImpl() {
292
1/2
✓ Branch 0 taken 34 times.
✗ Branch 1 not taken.
 34 return !GetOutput().empty() && std::ranges::is_sorted(GetOutput());
293 }
294
295 } // namespace yushkova_p_hoare_sorting_simple_merging
296