GCC Code Coverage Report

Directory: ./
File: tasks/terekhov_d_fast_sort_batch/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 123 144 85.4%
Functions: 12 13 92.3%
Branches: 84 150 56.0%
Line Branch Exec Source
1 #include "terekhov_d_fast_sort_batch/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <cstdlib>
8 #include <limits>
9 #include <stack>
10 #include <tuple>
11 #include <utility>
12 #include <vector>
13
14 #include "terekhov_d_fast_sort_batch/common/include/common.hpp"
15
16 namespace terekhov_d_fast_sort_batch {
17
18
1/2
✓ Branch 1 taken 54 times.
✗ Branch 2 not taken.
 54 TerekhovDFastSortBatchMPI::TerekhovDFastSortBatchMPI(const InType &in) {
19
1/2
✓ Branch 1 taken 54 times.
✗ Branch 2 not taken.
 54 MPI_Comm_rank(MPI_COMM_WORLD, &current_rank_);
20
1/2
✓ Branch 1 taken 54 times.
✗ Branch 2 not taken.
 54 MPI_Comm_size(MPI_COMM_WORLD, &total_processes_);
21
22 SetTypeOfTask(GetStaticTypeOfTask());
23
2/2
✓ Branch 0 taken 27 times.
✓ Branch 1 taken 27 times.
 54 if (current_rank_ == 0) {
24
1/2
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
 27 GetInput() = in;
25 }
26 54 GetOutput() = std::vector<int>();
27 54 }
28
29 54 bool TerekhovDFastSortBatchMPI::ValidationImpl() {
30 54 return GetOutput().empty();
31 }
32
33 54 bool TerekhovDFastSortBatchMPI::PreProcessingImpl() {
34 54 return true;
35 }
36
37 54 bool TerekhovDFastSortBatchMPI::RunImpl() {
38 54 size_t initial_size = 0;
39 54 size_t expanded_size = 0;
40
41 54 BroadcastArrayDimensions(initial_size, expanded_size);
42
43
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 2 times.
 54 if (initial_size == 0) {
44 return true;
45 }
46
47 52 std::vector<int> expanded_input;
48
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 26 times.
 52 if (current_rank_ == 0) {
49
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 expanded_input = GetInput();
50
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 15 times.
 26 if (expanded_size > initial_size) {
51
1/4
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 11 expanded_input.resize(expanded_size, std::numeric_limits<int>::max());
52 }
53 }
54
55 52 std::vector<int> portion_sizes;
56 52 std::vector<int> portion_starts;
57 52 std::vector<int> local_portion;
58
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 DistributeArrayElements(expanded_size, expanded_input, portion_sizes, portion_starts, local_portion);
59
60 // Локальная сортировка
61 std::ranges::sort(local_portion);
62
63 52 std::vector<std::pair<int, int>> comparator_list;
64
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 BuildComparatorSequence(comparator_list);
65
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 ExecuteComparators(portion_sizes, local_portion, comparator_list);
66
67 52 std::vector<int> collected_result;
68
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 26 times.
 52 if (current_rank_ == 0) {
69
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 collected_result.resize(expanded_size);
70 }
71
72
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 MPI_Gatherv(local_portion.data(), static_cast<int>(local_portion.size()), MPI_INT, collected_result.data(),
73 portion_sizes.data(), portion_starts.data(), MPI_INT, 0, MPI_COMM_WORLD);
74
75
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 26 times.
 52 if (current_rank_ == 0) {
76
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 collected_result.resize(initial_size);
77 GetOutput() = std::move(collected_result);
78 }
79
80
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 GetOutput().resize(initial_size);
81
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 MPI_Bcast(GetOutput().data(), static_cast<int>(initial_size), MPI_INT, 0, MPI_COMM_WORLD);
82
83 return true;
84 }
85
86 54 void TerekhovDFastSortBatchMPI::BroadcastArrayDimensions(size_t &initial_size, size_t &expanded_size) {
87
2/2
✓ Branch 0 taken 27 times.
✓ Branch 1 taken 27 times.
 54 if (current_rank_ == 0) {
88 27 initial_size = GetInput().size();
89 27 const size_t remainder = initial_size % total_processes_;
90
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 16 times.
 27 expanded_size = initial_size + (remainder == 0 ? 0 : (total_processes_ - remainder));
91 }
92
93 54 MPI_Bcast(&initial_size, 1, MPI_UNSIGNED_LONG_LONG, 0, MPI_COMM_WORLD);
94 54 MPI_Bcast(&expanded_size, 1, MPI_UNSIGNED_LONG_LONG, 0, MPI_COMM_WORLD);
95 54 }
96
97 52 void TerekhovDFastSortBatchMPI::DistributeArrayElements(const size_t &expanded_size,
98 const std::vector<int> &expanded_input,
99 std::vector<int> &portion_sizes,
100 std::vector<int> &portion_starts,
101 std::vector<int> &local_portion) const {
102 52 const int base_portion = static_cast<int>(expanded_size / total_processes_);
103
104 52 portion_sizes.resize(total_processes_);
105 52 portion_starts.resize(total_processes_);
106
107
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 52 times.
 156 for (int i = 0, offset = 0; i < total_processes_; i++) {
108 104 portion_sizes[i] = base_portion;
109 104 portion_starts[i] = offset;
110 104 offset += base_portion;
111 }
112
113 52 const int local_size = portion_sizes[current_rank_];
114 52 local_portion.resize(local_size);
115
116 52 MPI_Scatterv(expanded_input.data(), portion_sizes.data(), portion_starts.data(), MPI_INT, local_portion.data(),
117 local_size, MPI_INT, 0, MPI_COMM_WORLD);
118 52 }
119
120 52 void TerekhovDFastSortBatchMPI::BuildComparatorSequence(std::vector<std::pair<int, int>> &comparator_list) const {
121 52 std::vector<int> all_ranks(total_processes_);
122
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 52 times.
 156 for (int i = 0; i < total_processes_; i++) {
123 104 all_ranks[i] = i;
124 }
125
126
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 ConstructSortStep(all_ranks, comparator_list);
127 52 }
128
129 52 void TerekhovDFastSortBatchMPI::ConstructSortStep(const std::vector<int> &process_group,
130 std::vector<std::pair<int, int>> &comparator_list) {
131 std::stack<std::pair<std::vector<int>, bool>> task_stack;
132
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 task_stack.emplace(process_group, false);
133
134
2/2
✓ Branch 0 taken 208 times.
✓ Branch 1 taken 52 times.
 260 while (!task_stack.empty()) {
135 auto [current_group, is_merge_step] = task_stack.top();
136 task_stack.pop();
137
138
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 104 times.
 208 if (current_group.size() <= 1) {
139 104 continue;
140 }
141
142
1/2
✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
 104 auto middle = static_cast<std::vector<int>::difference_type>(current_group.size() / 2);
143
1/4
✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 104 std::vector<int> left_half(current_group.begin(), current_group.begin() + middle);
144
1/4
✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 104 std::vector<int> right_half(current_group.begin() + middle, current_group.end());
145
146
3/4
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 52 times.
✓ Branch 2 taken 52 times.
✗ Branch 3 not taken.
 156 if (is_merge_step) {
147
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 ConstructMergeStep(left_half, right_half, comparator_list);
148 continue;
149 }
150
151
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 task_stack.emplace(current_group, true);
152
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 task_stack.emplace(right_half, false);
153
2/6
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 52 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 52 task_stack.emplace(left_half, false);
154 }
155 52 }
156
157 52 void TerekhovDFastSortBatchMPI::ConstructMergeStep(const std::vector<int> &top_group,
158 const std::vector<int> &bottom_group,
159 std::vector<std::pair<int, int>> &comparator_list) {
160 std::stack<std::tuple<std::vector<int>, std::vector<int>, bool>> task_stack;
161
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 task_stack.emplace(top_group, bottom_group, false);
162
163
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 52 times.
 104 while (!task_stack.empty()) {
164 auto [upper_part, lower_part, is_merge_phase] = task_stack.top();
165 task_stack.pop();
166 52 const size_t total_count = upper_part.size() + lower_part.size();
167
168
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 52 times.
 52 if (total_count <= 1) {
169 ✗ continue;
170 }
171
1/2
✓ Branch 0 taken 52 times.
✗ Branch 1 not taken.
 52 if (total_count == 2) {
172
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 comparator_list.emplace_back(upper_part[0], lower_part[0]);
173 52 continue;
174 }
175
176 ✗ if (!is_merge_phase) {
177 ✗ auto [upper_odd, upper_even] = SplitByPosition(upper_part);
178 ✗ auto [lower_odd, lower_even] = SplitByPosition(lower_part);
179
180 ✗ task_stack.emplace(upper_part, lower_part, true);
181 ✗ task_stack.emplace(upper_even, lower_even, false);
182 ✗ task_stack.emplace(upper_odd, lower_odd, false);
183 continue;
184 ✗ }
185
186 ✗ std::vector<int> merged;
187 ✗ merged.reserve(total_count);
188 ✗ merged.insert(merged.end(), upper_part.begin(), upper_part.end());
189 ✗ merged.insert(merged.end(), lower_part.begin(), lower_part.end());
190
191 ✗ for (size_t i = 1; i < merged.size() - 1; i += 2) {
192 ✗ comparator_list.emplace_back(merged[i], merged[i + 1]);
193 }
194 }
195 52 }
196
197 ✗ std::pair<std::vector<int>, std::vector<int>> TerekhovDFastSortBatchMPI::SplitByPosition(
198 const std::vector<int> &items) {
199 ✗ std::vector<int> odd_items;
200 ✗ std::vector<int> even_items;
201 ✗ for (size_t i = 0; i < items.size(); i++) {
202 ✗ if (i % 2 == 0) {
203 even_items.push_back(items[i]);
204 } else {
205 odd_items.push_back(items[i]);
206 }
207 }
208 ✗ return std::make_pair(std::move(odd_items), std::move(even_items));
209 }
210
211 52 void TerekhovDFastSortBatchMPI::ExecuteComparators(const std::vector<int> &portion_sizes,
212 std::vector<int> &local_portion,
213 const std::vector<std::pair<int, int>> &comparator_list) const {
214 52 std::vector<int> partner_buffer;
215 52 std::vector<int> temp_buffer;
216
217
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 52 times.
 104 for (const auto &comparator : comparator_list) {
218 52 const int first_rank = comparator.first;
219 52 const int second_rank = comparator.second;
220
221
3/4
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 26 times.
 52 if (current_rank_ != first_rank && current_rank_ != second_rank) {
222 ✗ continue;
223 }
224
225
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 26 times.
 52 const int partner_rank = (current_rank_ == first_rank) ? second_rank : first_rank;
226
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 const int local_size = portion_sizes[current_rank_];
227 52 const int partner_size = portion_sizes[partner_rank];
228
229
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 partner_buffer.resize(partner_size);
230
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 temp_buffer.resize(local_size);
231
232 MPI_Status comm_status;
233
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 MPI_Sendrecv(local_portion.data(), local_size, MPI_INT, partner_rank, 0, partner_buffer.data(), partner_size,
234 MPI_INT, partner_rank, 0, MPI_COMM_WORLD, &comm_status);
235
236 52 MergePortions(local_portion, partner_buffer, temp_buffer, current_rank_ == first_rank);
237 local_portion.swap(temp_buffer);
238 }
239 52 }
240
241
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 26 times.
 52 void TerekhovDFastSortBatchMPI::MergePortions(const std::vector<int> &local_data, const std::vector<int> &partner_data,
242 std::vector<int> &result_buffer, bool take_minimal) {
243 52 const int local_size = static_cast<int>(local_data.size());
244 52 const int partner_size = static_cast<int>(partner_data.size());
245
246
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 26 times.
 52 if (take_minimal) {
247
2/2
✓ Branch 0 taken 178 times.
✓ Branch 1 taken 26 times.
 204 for (int idx = 0, local_idx = 0, partner_idx = 0; idx < local_size; idx++) {
248
2/2
✓ Branch 0 taken 94 times.
✓ Branch 1 taken 84 times.
 178 const int local_value = local_data[local_idx];
249 178 const int partner_value = partner_data[partner_idx];
250
2/2
✓ Branch 0 taken 94 times.
✓ Branch 1 taken 84 times.
 178 if (local_value < partner_value) {
251 94 result_buffer[idx] = local_value;
252 94 local_idx++;
253 } else {
254 84 result_buffer[idx] = partner_value;
255 84 partner_idx++;
256 }
257 }
258 } else {
259
2/2
✓ Branch 0 taken 178 times.
✓ Branch 1 taken 26 times.
 204 for (int idx = local_size - 1, local_idx = local_size - 1, partner_idx = partner_size - 1; idx >= 0; idx--) {
260
2/2
✓ Branch 0 taken 94 times.
✓ Branch 1 taken 84 times.
 178 const int local_value = local_data[local_idx];
261 178 const int partner_value = partner_data[partner_idx];
262
2/2
✓ Branch 0 taken 94 times.
✓ Branch 1 taken 84 times.
 178 if (local_value > partner_value) {
263 94 result_buffer[idx] = local_value;
264 94 local_idx--;
265 } else {
266 84 result_buffer[idx] = partner_value;
267 84 partner_idx--;
268 }
269 }
270 }
271 52 }
272
273 54 bool TerekhovDFastSortBatchMPI::PostProcessingImpl() {
274 54 return true;
275 }
276
277 } // namespace terekhov_d_fast_sort_batch
278