GCC Code Coverage Report

Directory: ./
File: tasks/papulina_y_radix_sort/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 78 89 87.6%
Functions: 8 10 80.0%
Branches: 61 104 58.7%
Line Branch Exec Source
1 #include "papulina_y_radix_sort/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <algorithm>
7 #include <array>
8 #include <cmath>
9 #include <cstdint>
10 #include <cstring>
11 #include <vector>
12
13 #include "papulina_y_radix_sort/common/include/common.hpp"
14
15 namespace papulina_y_radix_sort {
16
17
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 PapulinaYRadixSortALL::PapulinaYRadixSortALL(const InType &in) {
18 SetTypeOfTask(GetStaticTypeOfTask());
19
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 GetInput() = in;
20 14 GetOutput() = std::vector<double>();
21 14 }
22
23 14 bool PapulinaYRadixSortALL::ValidationImpl() {
24 14 return true;
25 }
26
27 14 bool PapulinaYRadixSortALL::PreProcessingImpl() {
28 14 return true;
29 }
30 7 std::vector<double> PapulinaYRadixSortALL::SimpleMerge(const std::vector<double> &a, const std::vector<double> &b) {
31
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 std::vector<double> res;
32
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 res.reserve(a.size() + b.size());
33 size_t i = 0;
34 size_t j = 0;
35
4/4
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 41 times.
✓ Branch 2 taken 5 times.
✓ Branch 3 taken 36 times.
 43 while (i < a.size() && j < b.size()) {
36
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 17 times.
 36 if (a[i] <= b[j]) {
37
1/2
✓ Branch 0 taken 19 times.
✗ Branch 1 not taken.
 19 res.push_back(a[i++]);
38 } else {
39
1/2
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
 17 res.push_back(b[j++]);
40 }
41 }
42
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 while (i < a.size()) {
43
1/2
✓ Branch 0 taken 7 times.
✗ Branch 1 not taken.
 7 res.push_back(a[i++]);
44 }
45
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 while (j < b.size()) {
46
1/2
✓ Branch 0 taken 7 times.
✗ Branch 1 not taken.
 7 res.push_back(b[j++]);
47 }
48 7 return res;
49 }
50
51 14 bool PapulinaYRadixSortALL::RunImpl() {
52 14 int rank = 0;
53 14 int size_comm = 0;
54 14 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
55 14 MPI_Comm_size(MPI_COMM_WORLD, &size_comm);
56
57 14 int total_size = 0;
58
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (rank == 0) {
59 7 total_size = static_cast<int>(GetInput().size());
60 }
61 14 MPI_Bcast(&total_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
62
63
1/2
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
 14 if (total_size == 0) {
64 return true;
65 }
66
67 14 std::vector<int> send_counts(size_comm);
68
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<int> offsets(size_comm);
69 14 int chunk = total_size / size_comm;
70 14 int remainder = total_size % size_comm;
71
72
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 14 times.
 42 for (int i = 0; i < size_comm; ++i) {
73
4/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 14 times.
✓ Branch 3 taken 14 times.
 52 send_counts[i] = chunk + (i < remainder ? 1 : 0);
74
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 14 times.
 28 offsets[i] = (i == 0) ? 0 : offsets[i - 1] + send_counts[i - 1];
75 }
76
77
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<double> local_data(send_counts[rank]);
78
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 double *in_ptr = (rank == 0) ? GetInput().data() : nullptr;
79
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 MPI_Scatterv(in_ptr, send_counts.data(), offsets.data(), MPI_DOUBLE, local_data.data(), send_counts[rank], MPI_DOUBLE,
80 0, MPI_COMM_WORLD);
81
82
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 RadixSort(local_data.data(), send_counts[rank]);
83
84
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (rank == 0) {
85
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 std::vector<double> final_res = local_data;
86
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 for (int i = 1; i < size_comm; ++i) {
87
1/2
✓ Branch 0 taken 7 times.
✗ Branch 1 not taken.
 7 if (send_counts[i] > 0) {
88
1/4
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 7 std::vector<double> recv_buf(send_counts[i]);
89
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 MPI_Recv(recv_buf.data(), send_counts[i], MPI_DOUBLE, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
90
2/6
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 7 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 14 final_res = SimpleMerge(final_res, recv_buf);
91 }
92 }
93
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 GetOutput() = final_res;
94
1/2
✓ Branch 0 taken 7 times.
✗ Branch 1 not taken.
 7 } else if (send_counts[rank] > 0) {
95
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 MPI_Send(local_data.data(), send_counts[rank], MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);
96 }
97
98
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 GetOutput().resize(total_size);
99
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 MPI_Bcast(GetOutput().data(), total_size, MPI_DOUBLE, 0, MPI_COMM_WORLD);
100
101 return true;
102 }
103
104 14 bool PapulinaYRadixSortALL::PostProcessingImpl() {
105 14 return true;
106 }
107 112 void PapulinaYRadixSortALL::SortByByte(uint64_t *bytes, uint64_t *out, int byte, int size) {
108 auto *byte_view = reinterpret_cast<unsigned char *>(bytes);
109 112 std::array<int, 256> counter = {0};
110
111
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 112 times.
 512 for (int i = 0; i < size; i++) {
112 400 int index = byte_view[(8 * i) + byte];
113 400 *(counter.data() + index) += 1;
114 }
115
116 int tmp = 0;
117
2/2
✓ Branch 0 taken 28672 times.
✓ Branch 1 taken 112 times.
 28784 for (int j = 0; j < 256; j++) {
118 28672 int a = *(counter.data() + j);
119 28672 *(counter.data() + j) = tmp;
120 28672 tmp += a;
121 }
122
123
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 112 times.
 512 for (int i = 0; i < size; i++) {
124 400 int index = byte_view[(8 * i) + byte];
125 400 out[*(counter.data() + index)] = bytes[i];
126 400 *(counter.data() + index) += 1;
127 }
128 112 }
129
130 ✗ uint64_t PapulinaYRadixSortALL::InBytes(double d) {
131 uint64_t bits = 0;
132 memcpy(&bits, &d, sizeof(double));
133 ✗ if ((bits & kMask) != 0) {
134 ✗ bits = ~bits;
135 } else {
136 ✗ bits = bits ^ kMask;
137 }
138 ✗ return bits;
139 }
140
141 ✗ double PapulinaYRadixSortALL::FromBytes(uint64_t bits) {
142 double d = NAN;
143 ✗ if ((bits & kMask) != 0) {
144 ✗ bits = bits ^ kMask;
145 } else {
146 ✗ bits = ~bits;
147 }
148 memcpy(&d, &bits, sizeof(double));
149 ✗ return d;
150 }
151
152 14 void PapulinaYRadixSortALL::RadixSort(double *arr, int size) {
153
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 14 times.
 14 if (size <= 1) {
154 ✗ return;
155 }
156 14 std::vector<uint64_t> bytes(size);
157
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<uint64_t> out(size);
158
159 14 #pragma omp parallel for default(none) shared(bytes, arr, size)
160 for (int i = 0; i < size; i++) {
161 bytes[i] = InBytes(arr[i]);
162 }
163
164 14 uint64_t *src_ptr = bytes.data();
165 uint64_t *dst_ptr = out.data();
166
167
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 14 times.
 126 for (int byte = 0; byte < 8; byte++) {
168 112 SortByByte(src_ptr, dst_ptr, byte, size);
169 std::swap(src_ptr, dst_ptr);
170 }
171
172
1/2
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
 14 #pragma omp parallel for default(none) shared(arr, src_ptr, size)
173 for (int i = 0; i < size; i++) {
174 arr[i] = FromBytes(src_ptr[i]);
175 }
176 }
177 } // namespace papulina_y_radix_sort
178