GCC Code Coverage Report

Directory: ./
File: tasks/kolotukhin_a_merge_sort_doubles/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 115 116 99.1%
Functions: 12 12 100.0%
Branches: 83 120 69.2%
Line Branch Exec Source
1 #include "kolotukhin_a_merge_sort_doubles/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <cmath>
6 #include <cstddef>
7 #include <cstdint>
8 #include <cstring>
9 #include <vector>
10
11 #include "kolotukhin_a_merge_sort_doubles/common/include/common.hpp"
12
13 namespace kolotukhin_a_merge_sort_doubles {
14
15 namespace {
16
17 10 std::vector<std::uint64_t> ConvertDoublesToKeys(const std::vector<double> &data) {
18 const std::size_t data_size = data.size();
19 10 std::vector<std::uint64_t> keys(data_size);
20
21
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 10 times.
 42 for (std::size_t i = 0; i < data_size; i++) {
22 std::uint64_t u = 0;
23 std::memcpy(&u, &data[i], sizeof(double));
24
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 23 times.
 32 if ((u & 0x8000000000000000ULL) != 0U) {
25 9 u = ~u;
26 } else {
27 23 u |= 0x8000000000000000ULL;
28 }
29 32 keys[i] = u;
30 }
31
32 10 return keys;
33 }
34
35 10 void ConvertKeysToDoubles(const std::vector<std::uint64_t> &keys, std::vector<double> &data) {
36 const std::size_t data_size = data.size();
37
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 10 times.
 42 for (std::size_t i = 0; i < data_size; ++i) {
38 32 std::uint64_t u = keys[i];
39
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 9 times.
 32 if ((u & 0x8000000000000000ULL) != 0U) {
40 23 u &= ~0x8000000000000000ULL;
41 } else {
42 9 u = ~u;
43 }
44 std::memcpy(&data[i], &u, sizeof(double));
45 }
46 10 }
47
48
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 void RadixSortUint64(std::vector<std::uint64_t> &keys) {
49 const std::size_t data_size = keys.size();
50
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 if (data_size <= 1) {
51 ✗ return;
52 }
53
54 const int radix_size = 256;
55 10 std::vector<std::uint64_t> temp(data_size);
56
57
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 10 times.
 90 for (int shift = 0; shift < 64; shift += 8) {
58
1/4
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 80 std::vector<std::size_t> count(radix_size + 1, 0);
59
60
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 80 times.
 336 for (std::size_t i = 0; i < data_size; i++) {
61 256 const auto digit = static_cast<std::uint8_t>((keys[i] >> shift) & 0xFF);
62 256 ++count[digit + 1];
63 }
64
65
2/2
✓ Branch 0 taken 20480 times.
✓ Branch 1 taken 80 times.
 20560 for (int i = 0; i < radix_size; ++i) {
66 20480 count[i + 1] += count[i];
67 }
68
69
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 80 times.
 336 for (std::size_t i = 0; i < data_size; ++i) {
70 256 const auto digit = static_cast<std::uint8_t>((keys[i] >> shift) & 0xFF);
71 256 const std::size_t pos = count[digit];
72 256 temp[pos] = keys[i];
73 256 count[digit] = pos + 1;
74 }
75
76
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 if (!temp.empty()) {
77
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 80 times.
 336 for (std::size_t i = 0; i < data_size; ++i) {
78 256 keys[i] = temp[i];
79 }
80 }
81 }
82 }
83
84
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 10 times.
 12 void RadixSortDoubles(std::vector<double> &data) {
85 const std::size_t data_size = data.size();
86
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 10 times.
 12 if (data_size <= 1) {
87 2 return;
88 }
89
90 10 std::vector<std::uint64_t> keys = ConvertDoublesToKeys(data);
91
92
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 RadixSortUint64(keys);
93
94 10 ConvertKeysToDoubles(keys, data);
95 }
96
97 5 std::vector<double> MergeSortedArrays(const std::vector<double> &a, const std::vector<double> &b) {
98
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 std::vector<double> result;
99
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 result.reserve(a.size() + b.size());
100 std::size_t i = 0;
101 std::size_t j = 0;
102
4/4
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 21 times.
✓ Branch 2 taken 3 times.
✓ Branch 3 taken 18 times.
 23 while (i < a.size() && j < b.size()) {
103
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 10 times.
 18 if (a[i] < b[j]) {
104
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 result.push_back(a[i++]);
105 } else {
106
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 result.push_back(b[j++]);
107 }
108 }
109
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 5 times.
 15 while (i < a.size()) {
110
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 result.push_back(a[i++]);
111 }
112
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 5 times.
 9 while (j < b.size()) {
113
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 result.push_back(b[j++]);
114 }
115 5 return result;
116 }
117
118 6 void HandleMergeAsReceiver(int rank, int step, int world_size, std::vector<double> &local_data) {
119 6 int source_rank = rank + step;
120
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (source_rank < world_size) {
121 6 int remote_size = 0;
122 6 MPI_Recv(&remote_size, 1, MPI_INT, source_rank, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
123
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 times.
 6 if (remote_size > 0) {
124 5 std::vector<double> remote_data(remote_size);
125
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 MPI_Recv(remote_data.data(), remote_size, MPI_DOUBLE, source_rank, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
126
2/6
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 10 local_data = MergeSortedArrays(local_data, remote_data);
127 }
128 }
129 6 }
130
131 6 void HandleMergeAsSender(int rank, int step, std::vector<double> &local_data) {
132 6 int dest_rank = rank - step;
133 6 int send_size = static_cast<int>(local_data.size());
134 6 MPI_Send(&send_size, 1, MPI_INT, dest_rank, 0, MPI_COMM_WORLD);
135
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 times.
 6 if (send_size > 0) {
136 5 MPI_Send(local_data.data(), send_size, MPI_DOUBLE, dest_rank, 1, MPI_COMM_WORLD);
137 }
138 local_data.clear();
139 6 }
140
141 } // namespace
142
143
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 KolotukhinAMergeSortDoublesMPI::KolotukhinAMergeSortDoublesMPI(const InType &in) {
144 SetTypeOfTask(GetStaticTypeOfTask());
145
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 GetInput() = in;
146 14 std::get<0>(GetOutput()) = std::vector<double>();
147 14 std::get<1>(GetOutput()) = -1;
148 14 }
149
150 14 bool KolotukhinAMergeSortDoublesMPI::ValidationImpl() {
151 14 int mpi_initialized = 0;
152 14 MPI_Initialized(&mpi_initialized);
153 14 return (mpi_initialized != 0);
154 }
155
156
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 14 times.
 14 bool KolotukhinAMergeSortDoublesMPI::PreProcessingImpl() {
157 std::get<0>(GetOutput()).clear();
158 14 return true;
159 }
160
161 14 bool KolotukhinAMergeSortDoublesMPI::RunImpl() {
162 14 int rank = 0;
163 14 int world_size = 0;
164 14 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
165 14 MPI_Comm_size(MPI_COMM_WORLD, &world_size);
166
167 const auto &input = GetInput();
168
169 14 int data_size = static_cast<int>(input.size());
170 14 MPI_Bcast(&data_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
171
172
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 12 times.
 14 if (data_size == 0) {
173 2 std::get<0>(GetOutput()) = std::vector<double>();
174 2 std::get<1>(GetOutput()) = rank;
175 2 return true;
176 }
177
178 12 std::vector<int> displs(world_size, 0);
179
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<int> recv_counts(world_size, 0);
180 12 int local_size = data_size / world_size;
181
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 7 times.
 12 if (rank < data_size % world_size) {
182 5 local_size++;
183 }
184
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<double> local_data(local_size);
185
186
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
187 int offset = 0;
188
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
 18 for (int i = 0; i < world_size; ++i) {
189
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 5 times.
 19 recv_counts[i] = (data_size / world_size) + (i < (data_size % world_size) ? 1 : 0);
190 12 displs[i] = offset;
191 12 offset += recv_counts[i];
192 }
193 }
194
195
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Bcast(recv_counts.data(), world_size, MPI_INT, 0, MPI_COMM_WORLD);
196
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Bcast(displs.data(), world_size, MPI_INT, 0, MPI_COMM_WORLD);
197
3/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
✓ Branch 3 taken 12 times.
✗ Branch 4 not taken.
 18 MPI_Scatterv(rank == 0 ? input.data() : nullptr, recv_counts.data(), displs.data(), MPI_DOUBLE, local_data.data(),
198 local_size, MPI_DOUBLE, 0, MPI_COMM_WORLD);
199
200
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 RadixSortDoubles(local_data);
201
202 int step = 1;
203
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 while (step < world_size) {
204
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if ((rank % (2 * step)) == 0) {
205
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 HandleMergeAsReceiver(rank, step, world_size, local_data);
206
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 } else if (((rank - step) % (2 * step)) == 0) {
207
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 HandleMergeAsSender(rank, step, local_data);
208 }
209 step *= 2;
210
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Barrier(MPI_COMM_WORLD);
211 }
212
213
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 std::get<0>(GetOutput()) = local_data;
214
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 1 times.
 12 std::get<1>(GetOutput()) = rank;
215
216 return true;
217 }
218
219 14 bool KolotukhinAMergeSortDoublesMPI::PostProcessingImpl() {
220 14 return true;
221 }
222
223 } // namespace kolotukhin_a_merge_sort_doubles
224