GCC Code Coverage Report

Directory: ./
File: tasks/rastvorov_k_radix_sort_double_merge/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 101 101 100.0%
Functions: 8 8 100.0%
Branches: 74 96 77.1%
Line Branch Exec Source
1 #include "rastvorov_k_radix_sort_double_merge/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <array>
6 #include <bit>
7 #include <cmath>
8 #include <cstddef>
9 #include <cstdint>
10 #include <vector>
11
12 namespace rastvorov_k_radix_sort_double_merge {
13
14 namespace {
15
16 inline uint64_t DoubleToOrderedKey(double x) {
17 78 if (std::isnan(x)) {
18 return UINT64_MAX;
19 }
20 const auto bits = std::bit_cast<uint64_t>(x);
21 78 const uint64_t sign = bits >> 63U;
22
6/6
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 19 times.
✓ Branch 2 taken 5 times.
✓ Branch 3 taken 18 times.
✓ Branch 4 taken 6 times.
✓ Branch 5 taken 26 times.
 78 if (sign != 0U) {
23 15 return ~bits;
24 }
25 63 return bits ^ (1ULL << 63U);
26 }
27
28
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 12 times.
 16 void RadixSortDouble(std::vector<double> *vec) {
29 auto &a = *vec;
30 const std::size_t n = a.size();
31
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 12 times.
 16 if (n <= 1) {
32 4 return;
33 }
34
35 12 std::vector<double> out(n);
36
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<uint64_t> keys(n);
37
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<uint64_t> out_keys(n);
38
39
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 12 times.
 44 for (std::size_t i = 0; i < n; ++i) {
40
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 64 keys[i] = DoubleToOrderedKey(a[i]);
41 }
42
43
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 12 times.
 108 for (std::size_t pass = 0; pass < 8; ++pass) {
44 96 std::array<std::size_t, 256> count{};
45 96 const std::size_t shift = pass * 8;
46
47
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 96 times.
 352 for (std::size_t i = 0; i < n; ++i) {
48 256 const auto byte = static_cast<unsigned>((keys[i] >> shift) & 0xFFULL);
49 256 count.at(static_cast<std::size_t>(byte))++;
50 }
51
52 96 std::array<std::size_t, 256> pos{};
53 pos.at(0) = 0;
54
2/2
✓ Branch 0 taken 24480 times.
✓ Branch 1 taken 96 times.
 24576 for (std::size_t byte_idx = 1; byte_idx < pos.size(); ++byte_idx) {
55 24480 pos.at(byte_idx) = pos.at(byte_idx - 1) + count.at(byte_idx - 1);
56 }
57
58
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 96 times.
 352 for (std::size_t i = 0; i < n; ++i) {
59 256 const auto byte = static_cast<unsigned>((keys[i] >> shift) & 0xFFULL);
60 256 const std::size_t p = pos.at(static_cast<std::size_t>(byte))++;
61 256 out[p] = a[i];
62 256 out_keys[p] = keys[i];
63 }
64
65 a.swap(out);
66 keys.swap(out_keys);
67 }
68 }
69
70 8 std::vector<double> MergeSorted(const std::vector<double> &a, const std::vector<double> &b) {
71
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 std::vector<double> out;
72
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 out.reserve(a.size() + b.size());
73
74 std::size_t i = 0;
75 std::size_t j = 0;
76
77
4/4
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 3 times.
✓ Branch 3 taken 23 times.
 31 while (i < a.size() && j < b.size()) {
78
1/2
✓ Branch 0 taken 23 times.
✗ Branch 1 not taken.
 23 const uint64_t ka = DoubleToOrderedKey(a[i]);
79
1/2
✓ Branch 0 taken 23 times.
✗ Branch 1 not taken.
 23 const uint64_t kb = DoubleToOrderedKey(b[j]);
80
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 10 times.
 23 if (ka <= kb) {
81
1/2
✓ Branch 0 taken 13 times.
✗ Branch 1 not taken.
 13 out.push_back(a[i++]);
82 } else {
83
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 out.push_back(b[j++]);
84 }
85 }
86
87
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 8 times.
 13 while (i < a.size()) {
88
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 out.push_back(a[i++]);
89 }
90
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 8 times.
 13 while (j < b.size()) {
91
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 out.push_back(b[j++]);
92 }
93
94 8 return out;
95 }
96
97 8 std::vector<double> RecvVectorD(int src, int tag_base, MPI_Comm comm) {
98 8 int sz = 0;
99 8 MPI_Status status{};
100 8 MPI_Recv(&sz, 1, MPI_INT, src, tag_base, comm, &status);
101
102 8 std::vector<double> v(static_cast<std::size_t>(sz));
103
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 2 times.
 8 if (sz > 0) {
104
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Recv(v.data(), sz, MPI_DOUBLE, src, tag_base + 1, comm, &status);
105 }
106 8 return v;
107 }
108
109 8 void SendVectorD(int dst, int tag_base, const std::vector<double> &v, MPI_Comm comm) {
110 8 const int sz = static_cast<int>(v.size());
111 8 MPI_Send(&sz, 1, MPI_INT, dst, tag_base, comm);
112
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 2 times.
 8 if (sz > 0) {
113 6 MPI_Send(v.data(), sz, MPI_DOUBLE, dst, tag_base + 1, comm);
114 }
115 8 }
116
117 } // namespace
118
119 16 bool RastvorovKRadixSortDoubleMergeMPI::ValidationImpl() {
120 16 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank_);
121 16 MPI_Comm_size(MPI_COMM_WORLD, &world_size_);
122 16 return true;
123 }
124
125 16 bool RastvorovKRadixSortDoubleMergeMPI::PreProcessingImpl() {
126 16 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank_);
127 16 MPI_Comm_size(MPI_COMM_WORLD, &world_size_);
128
129 16 int global_size = 0;
130
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 if (world_rank_ == 0) {
131 8 global_size = static_cast<int>(GetInput().size());
132 }
133 16 MPI_Bcast(&global_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
134
135 16 counts_.assign(world_size_, 0);
136 16 displs_.assign(world_size_, 0);
137
138
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 const int base = (world_size_ > 0) ? (global_size / world_size_) : 0;
139
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 const int rem = (world_size_ > 0) ? (global_size % world_size_) : 0;
140
141
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 16 times.
 48 for (int rank_idx = 0; rank_idx < world_size_; ++rank_idx) {
142
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 6 times.
 58 counts_[rank_idx] = base + ((rank_idx < rem) ? 1 : 0);
143 }
144
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 for (int rank_idx = 1; rank_idx < world_size_; ++rank_idx) {
145 16 displs_[rank_idx] = displs_[rank_idx - 1] + counts_[rank_idx - 1];
146 }
147
148 16 local_.assign(static_cast<std::size_t>(counts_[world_rank_]), 0.0);
149
150 double *send_buf = nullptr;
151
4/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 7 times.
✓ Branch 3 taken 1 times.
 16 if (world_rank_ == 0 && global_size > 0) {
152 send_buf = GetInput().data();
153 }
154
155 16 MPI_Scatterv(send_buf, counts_.data(), displs_.data(), MPI_DOUBLE, local_.data(), counts_[world_rank_], MPI_DOUBLE, 0,
156 MPI_COMM_WORLD);
157
158 GetOutput().clear();
159 16 return true;
160 }
161
162 16 bool RastvorovKRadixSortDoubleMergeMPI::RunImpl() {
163 16 RadixSortDouble(&local_);
164
165
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 8 times.
 24 for (int step = 1; step < world_size_; step <<= 1) {
166
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 if ((world_rank_ % (2 * step)) == 0) {
167 8 const int partner = world_rank_ + step;
168
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 if (partner < world_size_) {
169 8 std::vector<double> other = RecvVectorD(partner, 2000 + step, MPI_COMM_WORLD);
170
3/6
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 16 local_ = MergeSorted(local_, other);
171 }
172 } else {
173 8 const int partner = world_rank_ - step;
174 8 SendVectorD(partner, 2000 + step, local_, MPI_COMM_WORLD);
175 8 break;
176 }
177 }
178 16 return true;
179 }
180
181 16 bool RastvorovKRadixSortDoubleMergeMPI::PostProcessingImpl() {
182 16 int out_size = 0;
183
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 if (world_rank_ == 0) {
184 8 GetOutput() = local_;
185 8 out_size = static_cast<int>(GetOutput().size());
186 }
187
188 16 MPI_Bcast(&out_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
189
190
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 if (world_rank_ != 0) {
191 8 GetOutput().assign(static_cast<std::size_t>(out_size), 0.0);
192 }
193
194
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 2 times.
 16 if (out_size > 0) {
195 14 MPI_Bcast(GetOutput().data(), out_size, MPI_DOUBLE, 0, MPI_COMM_WORLD);
196 }
197 16 return true;
198 }
199
200 } // namespace rastvorov_k_radix_sort_double_merge
201