GCC Code Coverage Report

Directory: ./
File: tasks/golovanov_d_radix_merge/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 82 86 95.3%
Functions: 11 11 100.0%
Branches: 56 98 57.1%
Line Branch Exec Source
1 #include "golovanov_d_radix_merge/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <algorithm>
7 #include <cstdint>
8 #include <cstring>
9 #include <utility>
10 #include <vector>
11
12 #include "golovanov_d_radix_merge/common/include/common.hpp"
13 #include "util/include/util.hpp"
14
15 namespace {
16
17 inline std::uint64_t DoubleToSortableUint64(double val) {
18 std::uint64_t bits = 0;
19 std::memcpy(&bits, &val, sizeof(double));
20 const std::uint64_t sign_mask = std::uint64_t{1} << 63;
21
17/38
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✓ Branch 16 taken 1 times.
✓ Branch 17 taken 5 times.
✓ Branch 18 taken 3 times.
✓ Branch 19 taken 3 times.
✗ Branch 20 not taken.
✓ Branch 21 taken 4 times.
✓ Branch 22 taken 1 times.
✓ Branch 23 taken 3 times.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✓ Branch 28 taken 3 times.
✓ Branch 29 taken 3 times.
✓ Branch 30 taken 2 times.
✓ Branch 31 taken 4 times.
✓ Branch 32 taken 1 times.
✓ Branch 33 taken 1 times.
✓ Branch 34 taken 5 times.
✓ Branch 35 taken 8 times.
✓ Branch 36 taken 6 times.
✓ Branch 37 taken 7 times.
 31 return ((bits & sign_mask) != 0U) ? ~bits : bits ^ sign_mask;
22 }
23
24
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 void RadixSortStable(std::vector<double> &data, int /*num_threads*/) {
25
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (data.size() < 2) {
26 return;
27 }
28 std::ranges::stable_sort(data,
29 [](double a, double b) { return DoubleToSortableUint64(a) < DoubleToSortableUint64(b); });
30 }
31
32
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 void MergeSortedVectors(std::vector<double> &left, const std::vector<double> &right) {
33
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if (right.empty()) {
34 ✗ return;
35 }
36
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (left.empty()) {
37 ✗ left = right;
38 ✗ return;
39 }
40 3 std::vector<double> merged(left.size() + right.size());
41 3 std::ranges::merge(left, right, merged.begin(),
42 [](double a, double b) { return DoubleToSortableUint64(a) < DoubleToSortableUint64(b); });
43 left.swap(merged);
44 }
45
46 struct DistributionParams {
47 std::vector<int> send_counts;
48 std::vector<int> displs;
49 int global_size_int{};
50 };
51
52 6 DistributionParams ComputeDistribution(int world_size, uint64_t global_size) {
53 6 DistributionParams params;
54 6 params.global_size_int = static_cast<int>(global_size);
55
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 params.send_counts.resize(world_size, 0);
56
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 params.displs.resize(world_size, 0);
57
58 6 const int base_count = params.global_size_int / world_size;
59 6 const int remainder = params.global_size_int % world_size;
60 int offset = 0;
61
62
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
 18 for (int proc = 0; proc < world_size; ++proc) {
63
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
 20 params.send_counts[proc] = base_count + (proc < remainder ? 1 : 0);
64 12 params.displs[proc] = offset;
65 12 offset += params.send_counts[proc];
66 }
67
68 6 return params;
69 ✗ }
70
71 6 bool PerformMergeStep(std::vector<double> &local_data, int rank, int step, int world_size) {
72 6 const int group_size = step << 1;
73
74
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if ((rank % group_size) == 0) {
75 3 const int src = rank + step;
76
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if (src < world_size) {
77 3 int recv_count = 0;
78 3 MPI_Recv(&recv_count, 1, MPI_INT, src, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
79
80
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if (recv_count > 0) {
81 3 std::vector<double> received_data(recv_count);
82
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 MPI_Recv(received_data.data(), recv_count, MPI_DOUBLE, src, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
83
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 MergeSortedVectors(local_data, received_data);
84 }
85 }
86 3 return true;
87 }
88
89 3 const int dst = rank - step;
90 3 const int send_count = static_cast<int>(local_data.size());
91 3 MPI_Send(&send_count, 1, MPI_INT, dst, 0, MPI_COMM_WORLD);
92
93
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if (send_count > 0) {
94 3 MPI_Send(local_data.data(), send_count, MPI_DOUBLE, dst, 1, MPI_COMM_WORLD);
95 }
96 local_data.clear();
97 return false;
98 }
99
100 6 void ParallelMergeSort(std::vector<double> &local_data, int rank, int world_size, int num_threads) {
101 6 RadixSortStable(local_data, num_threads);
102
103
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 3 times.
 9 for (int step = 1; step < world_size; step <<= 1) {
104
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 3 times.
 6 if (!PerformMergeStep(local_data, rank, step, world_size)) {
105 break;
106 }
107 }
108 6 }
109
110 6 void GatherResults(std::vector<double> &local_data, int rank, int global_size, std::vector<double> &result) {
111 6 result.resize(global_size);
112
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
113 result.swap(local_data);
114 }
115 6 MPI_Bcast(result.data(), global_size, MPI_DOUBLE, 0, MPI_COMM_WORLD);
116 6 }
117
118 } // namespace
119
120 namespace golovanov_d_radix_merge {
121
122
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 GolovanovDRadixMergeALL::GolovanovDRadixMergeALL(const InType &in) {
123 SetTypeOfTask(GetStaticTypeOfTask());
124
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 GetInput() = in;
125 GetOutput() = {};
126 6 }
127
128 6 bool GolovanovDRadixMergeALL::ValidationImpl() {
129 6 int rank = 0;
130 6 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
131 6 int is_valid = 1;
132
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
133
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 is_valid = !GetInput().empty() ? 1 : 0;
134 }
135 6 MPI_Bcast(&is_valid, 1, MPI_INT, 0, MPI_COMM_WORLD);
136 6 return is_valid != 0;
137 }
138
139 6 bool GolovanovDRadixMergeALL::PreProcessingImpl() {
140 6 return true;
141 }
142
143 6 bool GolovanovDRadixMergeALL::RunImpl() {
144 6 int rank = 0;
145 6 int world_size = 1;
146 6 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
147 6 MPI_Comm_size(MPI_COMM_WORLD, &world_size);
148 6 const int num_threads = ppc::util::GetNumThreads();
149
150 6 uint64_t global_size = 0;
151
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
152 3 global_size = GetInput().size();
153 }
154 6 MPI_Bcast(&global_size, 1, MPI_UINT64_T, 0, MPI_COMM_WORLD);
155
156 6 DistributionParams dist_params = ComputeDistribution(world_size, global_size);
157
158
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 std::vector<double> local_data(dist_params.send_counts[rank]);
159
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 double *send_buffer = (rank == 0) ? GetInput().data() : nullptr;
160
161
2/4
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
 12 MPI_Scatterv(send_buffer, dist_params.send_counts.data(), dist_params.displs.data(), MPI_DOUBLE,
162
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 local_data.empty() ? nullptr : local_data.data(), dist_params.send_counts[rank], MPI_DOUBLE, 0,
163 MPI_COMM_WORLD);
164
165
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 ParallelMergeSort(local_data, rank, world_size, num_threads);
166
167 6 std::vector<double> result;
168
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 GatherResults(local_data, rank, dist_params.global_size_int, result);
169
170 GetOutput() = std::move(result);
171 6 return true;
172 6 }
173
174 6 bool GolovanovDRadixMergeALL::PostProcessingImpl() {
175 6 return true;
176 }
177
178 } // namespace golovanov_d_radix_merge
179