GCC Code Coverage Report

Directory: ./
File: tasks/popova_e_radix_sort_for_double_with_simple_merge/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 110 111 99.1%
Functions: 10 10 100.0%
Branches: 79 116 68.1%
Line Branch Exec Source
1 #include "popova_e_radix_sort_for_double_with_simple_merge/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <array>
7 #include <cstdint>
8 #include <cstring>
9 #include <random>
10 #include <utility>
11 #include <vector>
12
13 #include "popova_e_radix_sort_for_double_with_simple_merge/common/include/common.hpp"
14
15 namespace popova_e_radix_sort_for_double_with_simple_merge_threads {
16
17 namespace {
18
19 uint64_t DoubleToSortable(double value) {
20 uint64_t bits = 0;
21 std::memcpy(&bits, &value, sizeof(double));
22 bool is_negative = (bits >> 63) == 1;
23 if (is_negative) {
24 bits = ~bits;
25 } else {
26 bits ^= (1ULL << 63);
27 }
28 return bits;
29 }
30
31 double SortableToDouble(uint64_t bits) {
32 bool is_negative = (bits >> 63) == 1;
33 if (is_negative) {
34 bits ^= (1ULL << 63);
35 } else {
36 bits = ~bits;
37 }
38 double value = 0;
39 std::memcpy(&value, &bits, sizeof(double));
40 return value;
41 }
42
43
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 void RadixSortUInt(std::vector<uint64_t> &arr) {
44
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (arr.empty()) {
45 ✗ return;
46 }
47
48 const int bytes_count = 8;
49 const int base = 256;
50 24 std::vector<uint64_t> buffer(arr.size());
51
52
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 24 times.
 216 for (int byte_index = 0; byte_index < bytes_count; byte_index++) {
53 192 int sdvig = byte_index * 8;
54 192 std::array<size_t, base> count = {0};
55
56
2/2
✓ Branch 0 taken 49688 times.
✓ Branch 1 taken 192 times.
 49880 for (const auto &val : arr) {
57 49688 count.at((val >> sdvig) & 0xFF)++;
58 }
59
60 size_t offset = 0;
61
2/2
✓ Branch 0 taken 49152 times.
✓ Branch 1 taken 192 times.
 49344 for (auto &c : count) {
62 49152 size_t tmp = c;
63 49152 c = offset;
64 49152 offset += tmp;
65 }
66
67
2/2
✓ Branch 0 taken 49688 times.
✓ Branch 1 taken 192 times.
 49880 for (const auto &val : arr) {
68 49688 size_t pos = (val >> sdvig) & 0xFF;
69
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 49688 times.
 49688 buffer.at(count.at(pos)) = val;
70 49688 count.at(pos)++;
71 }
72
1/2
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
 192 arr = buffer;
73 }
74 }
75
76 12 std::vector<double> MergeSorted(const std::vector<double> &left, const std::vector<double> &right) {
77
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 std::vector<double> res;
78
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 res.reserve(left.size() + right.size());
79 size_t i = 0;
80 size_t j = 0;
81
4/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6189 times.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 6183 times.
 6195 while (i < left.size() && j < right.size()) {
82
2/2
✓ Branch 0 taken 3093 times.
✓ Branch 1 taken 3090 times.
 6183 if (left[i] <= right[j]) {
83
1/2
✓ Branch 0 taken 3093 times.
✗ Branch 1 not taken.
 3093 res.push_back(left[i++]);
84 } else {
85
1/2
✓ Branch 0 taken 3090 times.
✗ Branch 1 not taken.
 3090 res.push_back(right[j++]);
86 }
87 }
88
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 12 times.
 26 while (i < left.size()) {
89
1/2
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
 14 res.push_back(left[i++]);
90 }
91
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 12 times.
 26 while (j < right.size()) {
92
1/2
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
 14 res.push_back(right[j++]);
93 }
94 12 return res;
95 }
96
97 6211 double RandomDouble(double min_val, double max_val) {
98
4/6
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 6210 times.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
 6211 static std::random_device rd;
99
3/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 6210 times.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
 6213 static std::mt19937 gen(rd());
100 std::uniform_real_distribution<> dis(min_val, max_val);
101 6211 return dis(gen);
102 }
103
104 bool IsSorted(const std::vector<double> &arr) {
105
2/2
✓ Branch 0 taken 6199 times.
✓ Branch 1 taken 12 times.
 6211 for (size_t i = 1; i < arr.size(); i++) {
106
1/2
✓ Branch 0 taken 6199 times.
✗ Branch 1 not taken.
 6199 if (arr[i - 1] > arr[i]) {
107 return false;
108 }
109 }
110 return true;
111 }
112
113 bool SameData(const std::vector<double> &original, const std::vector<double> &result) {
114 uint64_t hash_original = 0;
115 uint64_t hash_result = 0;
116
117
2/2
✓ Branch 0 taken 6211 times.
✓ Branch 1 taken 12 times.
 6223 for (const double &value : original) {
118 uint64_t bits = 0;
119 std::memcpy(&bits, &value, sizeof(double));
120 6211 hash_original ^= bits;
121 }
122
123
2/2
✓ Branch 0 taken 6211 times.
✓ Branch 1 taken 12 times.
 6223 for (const double &value : result) {
124 uint64_t bits = 0;
125 std::memcpy(&bits, &value, sizeof(double));
126 6211 hash_result ^= bits;
127 }
128
129 12 return hash_original == hash_result;
130 }
131
132 24 void SplitMpiData(int total_elements, int size, std::vector<int> &elem_count, std::vector<int> &start_index) {
133 24 int elems_per_proc = total_elements / size;
134 24 int ostat = total_elements % size;
135 int curr_index = 0;
136
137
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 24 times.
 72 for (int i = 0; i < size; i++) {
138
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 42 times.
 48 if (i < ostat) {
139 6 elem_count[i] = elems_per_proc + 1;
140 } else {
141 42 elem_count[i] = elems_per_proc;
142 }
143 48 start_index[i] = curr_index;
144 48 curr_index += elem_count[i];
145 }
146 24 }
147
148
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 void MergeChunks(const std::vector<double> &gathered, const std::vector<int> &counts, const std::vector<int> &starts,
149 int size, std::vector<double> &output) {
150 output.clear();
151
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 12 times.
 36 for (int i = 0; i < size; i++) {
152
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<double> piece(gathered.begin() + starts[i], gathered.begin() + starts[i] + counts[i]);
153
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (!piece.empty()) {
154
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (output.empty()) {
155 output = std::move(piece);
156 } else {
157
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 output = MergeSorted(output, piece);
158 }
159 }
160 }
161 12 }
162
163 } // namespace
164
165 24 PopovaERadixSorForDoubleWithSimpleMergeALL::PopovaERadixSorForDoubleWithSimpleMergeALL(const InType &in) {
166 SetTypeOfTask(GetStaticTypeOfTask());
167 24 GetInput() = in;
168 GetOutput() = 0;
169 24 }
170
171 24 bool PopovaERadixSorForDoubleWithSimpleMergeALL::ValidationImpl() {
172 24 return GetInput() > 0;
173 }
174
175 24 bool PopovaERadixSorForDoubleWithSimpleMergeALL::PreProcessingImpl() {
176 24 int rank = 0;
177 24 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
178
179
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (rank == 0) {
180 12 int size = GetInput();
181 12 array_.resize(size);
182
2/2
✓ Branch 0 taken 6211 times.
✓ Branch 1 taken 12 times.
 6223 for (int i = 0; i < size; i++) {
183 6211 array_[i] = RandomDouble(-100.0, 100.0);
184 }
185 }
186 24 return true;
187 }
188
189 24 bool PopovaERadixSorForDoubleWithSimpleMergeALL::RunImpl() {
190 24 int rank = 0;
191 24 int size = 0;
192 24 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
193 24 MPI_Comm_size(MPI_COMM_WORLD, &size);
194
195 24 int total_elements = 0;
196
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (rank == 0) {
197 12 total_elements = static_cast<int>(array_.size());
198 }
199 24 MPI_Bcast(&total_elements, 1, MPI_INT, 0, MPI_COMM_WORLD);
200
201 24 std::vector<int> elem_count(size);
202
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<int> start_index(size);
203 24 SplitMpiData(total_elements, size, elem_count, start_index);
204
205
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 int my_elem_count = elem_count[rank];
206
2/6
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 24 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 24 std::vector<double> local_array(my_elem_count);
207
208
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 MPI_Scatterv(array_.data(), elem_count.data(), start_index.data(), MPI_DOUBLE, local_array.data(), my_elem_count,
209 MPI_DOUBLE, 0, MPI_COMM_WORLD);
210
211
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<uint64_t> local_bits(my_elem_count);
212
213 24 #pragma omp parallel default(none) shared(my_elem_count, local_bits, local_array)
214 {
215 #pragma omp for
216 for (int i = 0; i < my_elem_count; i++) {
217 local_bits[i] = DoubleToSortable(local_array[i]);
218 }
219 }
220
221
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 RadixSortUInt(local_bits);
222
223 24 #pragma omp parallel default(none) shared(my_elem_count, local_array, local_bits)
224 {
225 #pragma omp for
226 for (int i = 0; i < my_elem_count; i++) {
227 local_array[i] = SortableToDouble(local_bits[i]);
228 }
229 }
230
231 24 std::vector<double> gathered_array;
232
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (rank == 0) {
233
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 gathered_array.resize(total_elements);
234 }
235
236
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 MPI_Gatherv(local_array.data(), my_elem_count, MPI_DOUBLE, gathered_array.data(), elem_count.data(),
237 start_index.data(), MPI_DOUBLE, 0, MPI_COMM_WORLD);
238
239
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (rank == 0) {
240
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MergeChunks(gathered_array, elem_count, start_index, size, result_);
241 }
242
243 24 return true;
244 }
245
246 24 bool PopovaERadixSorForDoubleWithSimpleMergeALL::PostProcessingImpl() {
247 24 int rank = 0;
248 24 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
249
250 24 int is_ok = 0;
251
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (rank == 0) {
252 bool sorted = IsSorted(result_);
253 bool same = SameData(array_, result_);
254
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (sorted && same) {
255 12 is_ok = 1;
256 } else {
257 is_ok = 0;
258 }
259 12 GetOutput() = is_ok;
260 }
261
262 24 MPI_Bcast(&is_ok, 1, MPI_INT, 0, MPI_COMM_WORLD);
263
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (rank != 0) {
264 12 GetOutput() = is_ok;
265 }
266
267 24 MPI_Barrier(MPI_COMM_WORLD);
268 24 return true;
269 }
270
271 } // namespace popova_e_radix_sort_for_double_with_simple_merge_threads
272