GCC Code Coverage Report

Directory: ./
File: tasks/balchunayte_z_shell_batcher/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 111 111 100.0%
Functions: 11 11 100.0%
Branches: 88 108 81.5%
Line Branch Exec Source
1 #include "balchunayte_z_shell_batcher/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <cstddef>
6 #include <utility>
7 #include <vector>
8
9 namespace balchunayte_z_shell_batcher {
10
11 namespace {
12
13 14 void ShellSort(std::vector<int> *vec) {
14 auto &a = *vec;
15 const std::size_t n = a.size();
16
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 14 times.
 27 for (std::size_t gap = n / 2; gap > 0; gap /= 2) {
17
2/2
✓ Branch 0 taken 33 times.
✓ Branch 1 taken 13 times.
 46 for (std::size_t i = gap; i < n; ++i) {
18 33 const int tmp = a[i];
19 std::size_t j = i;
20
4/4
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 12 times.
✓ Branch 2 taken 19 times.
✓ Branch 3 taken 21 times.
 52 while (j >= gap && a[j - gap] > tmp) {
21 19 a[j] = a[j - gap];
22 j -= gap;
23 }
24 33 a[j] = tmp;
25 }
26 }
27 14 }
28
29 struct Elem {
30 int val{};
31 bool pad{false};
32
33 46 Elem(int value, bool padding) : val(value), pad(padding) {}
34 };
35
36 inline bool Greater(const Elem &lhs, const Elem &rhs) {
37
2/2
✓ Branch 0 taken 39 times.
✓ Branch 1 taken 116 times.
 155 if (lhs.pad != rhs.pad) {
38
3/4
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 17 times.
✓ Branch 2 taken 22 times.
✗ Branch 3 not taken.
 39 return lhs.pad && !rhs.pad;
39 }
40 116 return lhs.val > rhs.val;
41 }
42
43
2/2
✓ Branch 0 taken 39 times.
✓ Branch 1 taken 116 times.
 155 inline void CompareExchange(std::vector<Elem> *arr, std::size_t i, std::size_t j) {
44
2/2
✓ Branch 0 taken 41 times.
✓ Branch 1 taken 75 times.
 116 if (Greater((*arr)[i], (*arr)[j])) {
45 std::swap((*arr)[i], (*arr)[j]);
46 }
47 155 }
48
49 std::size_t NextPow2(std::size_t x) {
50 std::size_t p = 1;
51
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 7 times.
 16 while (p < x) {
52 9 p <<= 1U;
53 }
54 return p;
55 }
56
57 31 void OddEvenMergeStep(std::vector<Elem> *arr, std::size_t k, std::size_t j) {
58 const std::size_t n = arr->size();
59
2/2
✓ Branch 0 taken 310 times.
✓ Branch 1 taken 31 times.
 341 for (std::size_t i = 0; i < n; ++i) {
60 310 const std::size_t ixj = i ^ j;
61
2/2
✓ Branch 0 taken 155 times.
✓ Branch 1 taken 155 times.
 310 if (ixj > i) {
62
2/2
✓ Branch 0 taken 113 times.
✓ Branch 1 taken 42 times.
 155 if ((i & k) == 0) {
63 113 CompareExchange(arr, i, ixj);
64 } else {
65 42 CompareExchange(arr, ixj, i);
66 }
67 }
68 }
69 31 }
70
71
1/2
✓ Branch 0 taken 7 times.
✗ Branch 1 not taken.
 7 void OddEvenMergeNetwork(std::vector<Elem> *arr) {
72 const std::size_t n = arr->size();
73
1/2
✓ Branch 0 taken 7 times.
✗ Branch 1 not taken.
 7 if (n <= 1) {
74 return;
75 }
76
77
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 7 times.
 23 for (std::size_t k = 2; k <= n; k <<= 1U) {
78
2/2
✓ Branch 0 taken 31 times.
✓ Branch 1 taken 16 times.
 47 for (std::size_t j = (k >> 1U); j > 0; j >>= 1U) {
79 31 OddEvenMergeStep(arr, k, j);
80 }
81 }
82 }
83
84
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 3 times.
 7 std::vector<int> BatcherOddEvenMerge(const std::vector<int> &a, const std::vector<int> &b) {
85 7 const std::size_t need = a.size() + b.size();
86
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 3 times.
 7 const std::size_t half = NextPow2((a.size() > b.size()) ? a.size() : b.size());
87
88 7 std::vector<Elem> buffer;
89
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 buffer.reserve(2 * half);
90
91
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 7 times.
 30 for (std::size_t i = 0; i < half; ++i) {
92
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 5 times.
 23 if (i < a.size()) {
93
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 buffer.emplace_back(a[i], false);
94 } else {
95
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 buffer.emplace_back(0, true);
96 }
97 }
98
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 7 times.
 30 for (std::size_t i = 0; i < half; ++i) {
99
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 8 times.
 23 if (i < b.size()) {
100
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 buffer.emplace_back(b[i], false);
101 } else {
102
1/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 8 buffer.emplace_back(0, true);
103 }
104 }
105
106 7 OddEvenMergeNetwork(&buffer);
107
108 7 std::vector<int> out;
109
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 out.reserve(need);
110
1/2
✓ Branch 0 taken 34 times.
✗ Branch 1 not taken.
 34 for (const auto &elem : buffer) {
111
2/2
✓ Branch 0 taken 33 times.
✓ Branch 1 taken 1 times.
 34 if (!elem.pad) {
112
1/2
✓ Branch 0 taken 33 times.
✗ Branch 1 not taken.
 33 out.push_back(elem.val);
113 }
114
2/2
✓ Branch 0 taken 27 times.
✓ Branch 1 taken 7 times.
 34 if (out.size() == need) {
115 break;
116 }
117 }
118 7 return out;
119 }
120
121 7 std::vector<int> RecvVector(int src, int tag_base, MPI_Comm comm) {
122 7 int sz = 0;
123 7 MPI_Status status{};
124 7 MPI_Recv(&sz, 1, MPI_INT, src, tag_base, comm, &status);
125
126 7 std::vector<int> v(static_cast<std::size_t>(sz));
127
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 2 times.
 7 if (sz > 0) {
128
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 MPI_Recv(v.data(), sz, MPI_INT, src, tag_base + 1, comm, &status);
129 }
130 7 return v;
131 }
132
133 7 void SendVector(int dst, int tag_base, const std::vector<int> &v, MPI_Comm comm) {
134 7 const int sz = static_cast<int>(v.size());
135 7 MPI_Send(&sz, 1, MPI_INT, dst, tag_base, comm);
136
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 2 times.
 7 if (sz > 0) {
137 5 MPI_Send(v.data(), sz, MPI_INT, dst, tag_base + 1, comm);
138 }
139 7 }
140
141 } // namespace
142
143 14 bool BalchunayteZShellBatcherMPI::ValidationImpl() {
144 14 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank_);
145 14 MPI_Comm_size(MPI_COMM_WORLD, &world_size_);
146 14 return true;
147 }
148
149 14 bool BalchunayteZShellBatcherMPI::PreProcessingImpl() {
150 14 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank_);
151 14 MPI_Comm_size(MPI_COMM_WORLD, &world_size_);
152
153 14 int global_size = 0;
154
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (world_rank_ == 0) {
155 7 global_size = static_cast<int>(GetInput().size());
156 }
157 14 MPI_Bcast(&global_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
158
159 14 counts_.assign(world_size_, 0);
160 14 displs_.assign(world_size_, 0);
161
162
1/2
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
 14 const int base = (world_size_ > 0) ? (global_size / world_size_) : 0;
163
1/2
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
 14 const int rem = (world_size_ > 0) ? (global_size % world_size_) : 0;
164
165
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 14 times.
 42 for (int rank_index = 0; rank_index < world_size_; ++rank_index) {
166
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 6 times.
 50 counts_[rank_index] = base + ((rank_index < rem) ? 1 : 0);
167 }
168
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 14 times.
 28 for (int rank_index = 1; rank_index < world_size_; ++rank_index) {
169 14 displs_[rank_index] = displs_[rank_index - 1] + counts_[rank_index - 1];
170 }
171
172 14 local_.assign(static_cast<std::size_t>(counts_[world_rank_]), 0);
173
174 int *send_buf = nullptr;
175
4/4
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 1 times.
 14 if (world_rank_ == 0 && global_size > 0) {
176 send_buf = GetInput().data();
177 }
178
179 14 MPI_Scatterv(send_buf, counts_.data(), displs_.data(), MPI_INT, local_.data(), counts_[world_rank_], MPI_INT, 0,
180 MPI_COMM_WORLD);
181
182 GetOutput().clear();
183 14 return true;
184 }
185
186 14 bool BalchunayteZShellBatcherMPI::RunImpl() {
187 14 ShellSort(&local_);
188
189
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 7 times.
 21 for (int step = 1; step < world_size_; step <<= 1) {
190
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if ((world_rank_ % (2 * step)) == 0) {
191 7 const int partner = world_rank_ + step;
192
1/2
✓ Branch 0 taken 7 times.
✗ Branch 1 not taken.
 7 if (partner < world_size_) {
193 7 std::vector<int> other = RecvVector(partner, 1000 + step, MPI_COMM_WORLD);
194
3/6
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 5 times.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 14 local_ = BatcherOddEvenMerge(local_, other);
195 }
196 } else {
197 7 const int partner = world_rank_ - step;
198 7 SendVector(partner, 1000 + step, local_, MPI_COMM_WORLD);
199 7 break;
200 }
201 }
202 14 return true;
203 }
204
205 14 bool BalchunayteZShellBatcherMPI::PostProcessingImpl() {
206 14 int out_size = 0;
207
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (world_rank_ == 0) {
208 7 GetOutput() = local_;
209 7 out_size = static_cast<int>(GetOutput().size());
210 }
211
212 14 MPI_Bcast(&out_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
213
214
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (world_rank_ != 0) {
215 7 GetOutput().assign(static_cast<std::size_t>(out_size), 0);
216 }
217
218
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 2 times.
 14 if (out_size > 0) {
219 12 MPI_Bcast(GetOutput().data(), out_size, MPI_INT, 0, MPI_COMM_WORLD);
220 }
221 14 return true;
222 }
223
224 } // namespace balchunayte_z_shell_batcher
225