GCC Code Coverage Report

Directory: ./
File: tasks/krymova_k_lsd_sort_merge_double/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 90 103 87.4%
Functions: 11 14 78.6%
Branches: 73 120 60.8%
Line Branch Exec Source
1 #include "krymova_k_lsd_sort_merge_double/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 "krymova_k_lsd_sort_merge_double/common/include/common.hpp"
13
14 namespace krymova_k_lsd_sort_merge_double {
15
16
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 KrymovaKLsdSortMergeDoubleALL::KrymovaKLsdSortMergeDoubleALL(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GetInput() = in;
19 24 GetOutput() = OutType();
20 24 }
21
22 24 bool KrymovaKLsdSortMergeDoubleALL::ValidationImpl() {
23 24 return true;
24 }
25
26 24 bool KrymovaKLsdSortMergeDoubleALL::PreProcessingImpl() {
27 24 return true;
28 }
29
30 ✗ uint64_t KrymovaKLsdSortMergeDoubleALL::DoubleToULL(double d) {
31 uint64_t ull = 0U;
32 std::memcpy(&ull, &d, sizeof(double));
33 ✗ return ((ull & 0x8000000000000000ULL) != 0U) ? ~ull : (ull | 0x8000000000000000ULL);
34 }
35
36 ✗ double KrymovaKLsdSortMergeDoubleALL::ULLToDouble(uint64_t ull) {
37 ✗ if ((ull & 0x8000000000000000ULL) != 0U) {
38 ✗ ull &= 0x7FFFFFFFFFFFFFFFULL;
39 } else {
40 ✗ ull = ~ull;
41 }
42 double d = 0.0;
43 std::memcpy(&d, &ull, sizeof(double));
44 ✗ return d;
45 }
46
47 23 void KrymovaKLsdSortMergeDoubleALL::LSDSort(double *arr, int size) {
48
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 22 times.
 23 if (size <= 1) {
49 1 return;
50 }
51
52 const int k_bits_per_pass = 8;
53 const int k_radix = 1 << k_bits_per_pass;
54 const int k_passes = 8;
55
56 22 std::vector<uint64_t> ull_arr(size);
57
1/4
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 22 std::vector<uint64_t> ull_tmp(size);
58
1/4
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 22 std::vector<unsigned int> count(k_radix, 0U);
59
60 22 #pragma omp parallel for default(none) shared(ull_arr, arr, size)
61 for (int i = 0; i < size; ++i) {
62 ull_arr[i] = DoubleToULL(arr[i]);
63 }
64
65
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 22 times.
 198 for (int pass = 0; pass < k_passes; ++pass) {
66
1/2
✓ Branch 0 taken 176 times.
✗ Branch 1 not taken.
 176 int shift = pass * k_bits_per_pass;
67 std::ranges::fill(count, 0U);
68
69
2/2
✓ Branch 0 taken 900160 times.
✓ Branch 1 taken 176 times.
 900336 for (int i = 0; i < size; ++i) {
70 900160 unsigned int digit = (ull_arr[i] >> shift) & (k_radix - 1);
71 900160 ++count[digit];
72 }
73
74
2/2
✓ Branch 0 taken 44880 times.
✓ Branch 1 taken 176 times.
 45056 for (int i = 1; i < k_radix; ++i) {
75 44880 count[i] += count[i - 1];
76 }
77
78
2/2
✓ Branch 0 taken 900160 times.
✓ Branch 1 taken 176 times.
 900336 for (int i = size - 1; i >= 0; --i) {
79 900160 unsigned int digit = (ull_arr[i] >> shift) & (k_radix - 1);
80 900160 ull_tmp[--count[digit]] = ull_arr[i];
81 }
82
83 ull_arr.swap(ull_tmp);
84 }
85
86
1/2
✓ Branch 0 taken 22 times.
✗ Branch 1 not taken.
 22 #pragma omp parallel for default(none) shared(arr, ull_arr, size)
87 for (int i = 0; i < size; ++i) {
88 arr[i] = ULLToDouble(ull_arr[i]);
89 }
90 }
91
92 11 std::vector<double> KrymovaKLsdSortMergeDoubleALL::SimpleMerge(const std::vector<double> &a,
93 const std::vector<double> &b) {
94
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 std::vector<double> res;
95
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 res.reserve(a.size() + b.size());
96 size_t i = 0;
97 size_t j = 0;
98
4/4
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 56261 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 56260 times.
 56271 while (i < a.size() && j < b.size()) {
99
2/2
✓ Branch 0 taken 56210 times.
✓ Branch 1 taken 50 times.
 56260 res.push_back(a[i] <= b[j] ? a[i++] : b[j++]);
100 }
101
2/2
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 11 times.
 61 while (i < a.size()) {
102
1/2
✓ Branch 0 taken 50 times.
✗ Branch 1 not taken.
 50 res.push_back(a[i++]);
103 }
104
2/2
✓ Branch 0 taken 56210 times.
✓ Branch 1 taken 11 times.
 56221 while (j < b.size()) {
105
1/2
✓ Branch 0 taken 56210 times.
✗ Branch 1 not taken.
 56210 res.push_back(b[j++]);
106 }
107 11 return res;
108 }
109
110 ✗ bool KrymovaKLsdSortMergeDoubleALL::RunSmallDataset(int total_size) {
111 ✗ if (total_size > 0) {
112 ✗ GetOutput() = GetInput();
113 ✗ LSDSort(GetOutput().data(), total_size);
114 } else {
115 GetOutput().clear();
116 }
117 ✗ return true;
118 }
119
120 24 void KrymovaKLsdSortMergeDoubleALL::ComputeDistribution(int total_size, int size_comm, std::vector<int> &send_counts,
121 std::vector<int> &offsets) {
122 24 int chunk = total_size / size_comm;
123 24 int rem = total_size % size_comm;
124
125
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 24 times.
 72 for (int i = 0; i < size_comm; ++i) {
126
4/4
✓ Branch 0 taken 46 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 24 times.
 94 send_counts[i] = chunk + (i < rem ? 1 : 0);
127
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 offsets[i] = (i == 0) ? 0 : offsets[i - 1] + send_counts[i - 1];
128 }
129 24 }
130
131 24 void KrymovaKLsdSortMergeDoubleALL::ScatterData(int rank, const std::vector<int> &send_counts,
132 const std::vector<int> &offsets, std::vector<double> &local_data) {
133
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (rank == 0) {
134 12 MPI_Scatterv(GetInput().data(), send_counts.data(), offsets.data(), MPI_DOUBLE, local_data.data(),
135 send_counts[rank], MPI_DOUBLE, 0, MPI_COMM_WORLD);
136
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 1 times.
 12 } else if (send_counts[rank] > 0) {
137 11 MPI_Scatterv(nullptr, send_counts.data(), offsets.data(), MPI_DOUBLE, local_data.data(), send_counts[rank],
138 MPI_DOUBLE, 0, MPI_COMM_WORLD);
139 }
140 24 }
141
142 24 void KrymovaKLsdSortMergeDoubleALL::GatherResults(int rank, int size_comm, const std::vector<int> &send_counts,
143 std::vector<double> &local_data) {
144
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (rank == 0) {
145 12 std::vector<double> result = local_data;
146
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 for (int i = 1; i < size_comm; ++i) {
147
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 1 times.
 12 if (send_counts[i] > 0) {
148
2/6
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 11 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 11 std::vector<double> recv_buf(send_counts[i]);
149
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 MPI_Recv(recv_buf.data(), send_counts[i], MPI_DOUBLE, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
150
2/6
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 11 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 22 result = SimpleMerge(result, recv_buf);
151 }
152 }
153 GetOutput() = std::move(result);
154
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 1 times.
 12 } else if (send_counts[rank] > 0) {
155 11 MPI_Send(local_data.data(), send_counts[rank], MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);
156 }
157 24 }
158
159 24 void KrymovaKLsdSortMergeDoubleALL::BroadcastResult(int rank) {
160 24 int out_size = static_cast<int>(GetOutput().size());
161 24 MPI_Bcast(&out_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
162
163
3/4
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
 24 if ((rank != 0) && (out_size > 0)) {
164 12 GetOutput().resize(out_size);
165 12 MPI_Bcast(GetOutput().data(), out_size, MPI_DOUBLE, 0, MPI_COMM_WORLD);
166
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 } else if ((rank == 0) && (out_size > 0)) {
167 12 MPI_Bcast(GetOutput().data(), out_size, MPI_DOUBLE, 0, MPI_COMM_WORLD);
168 }
169 24 }
170
171 24 bool KrymovaKLsdSortMergeDoubleALL::RunImpl() {
172 24 int rank = 0;
173 24 int size_comm = 0;
174 24 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
175 24 MPI_Comm_size(MPI_COMM_WORLD, &size_comm);
176
177 24 int total_size = static_cast<int>(GetInput().size());
178
179 24 MPI_Bcast(&total_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
180
181
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (total_size == 0) {
182 GetOutput().clear();
183 ✗ return true;
184 }
185
186 24 std::vector<int> send_counts(size_comm);
187
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<int> offsets(size_comm);
188 24 ComputeDistribution(total_size, size_comm, send_counts, offsets);
189
190
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<double> local_data(send_counts[rank]);
191
192
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 ScatterData(rank, send_counts, offsets, local_data);
193
194
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 1 times.
 24 if (send_counts[rank] > 0) {
195
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 LSDSort(local_data.data(), send_counts[rank]);
196 }
197
198
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GatherResults(rank, size_comm, send_counts, local_data);
199
200
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 BroadcastResult(rank);
201
202 return true;
203 }
204
205
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 bool KrymovaKLsdSortMergeDoubleALL::PostProcessingImpl() {
206 const OutType &output = GetOutput();
207
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (output.empty()) {
208 return true;
209 }
210
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 225018 times.
 225042 for (size_t i = 1; i < output.size(); ++i) {
211
1/2
✓ Branch 0 taken 225018 times.
✗ Branch 1 not taken.
 225018 if (output[i] < output[i - 1]) {
212 return false;
213 }
214 }
215 return true;
216 }
217
218 } // namespace krymova_k_lsd_sort_merge_double
219