GCC Code Coverage Report

Directory: ./
File: tasks/chernov_t_radix_sort/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 88 93 94.6%
Functions: 8 9 88.9%
Branches: 65 108 60.2%
Line Branch Exec Source
1 #include "chernov_t_radix_sort/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <algorithm>
7 #include <cstddef>
8 #include <cstdint>
9 #include <utility>
10 #include <vector>
11
12 #include "chernov_t_radix_sort/common/include/common.hpp"
13
14 namespace chernov_t_radix_sort {
15
16
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 ChernovTRadixSortALL::ChernovTRadixSortALL(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetInput() = in;
19 GetOutput() = {};
20 16 }
21
22 16 bool ChernovTRadixSortALL::ValidationImpl() {
23 16 return true;
24 }
25
26 16 bool ChernovTRadixSortALL::PreProcessingImpl() {
27 16 GetOutput() = GetInput();
28 16 return true;
29 }
30
31 constexpr int kBitsPerDigit = 8;
32 constexpr int kRadix = 1 << kBitsPerDigit;
33 constexpr uint32_t kSignMask = 0x80000000U;
34
35
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 13 times.
 13 void ChernovTRadixSortALL::RadixSortLSDParallelOMP(std::vector<int> &data) {
36
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 13 times.
 13 if (data.empty()) {
37 ✗ return;
38 }
39 const size_t n = data.size();
40
41 13 std::vector<uint32_t> temp(n);
42 13 #pragma omp parallel for schedule(static) default(none) shared(data, temp, n)
43 for (size_t i = 0; i < n; ++i) {
44 temp[i] = static_cast<uint32_t>(data[i]) ^ kSignMask;
45 }
46
47
1/4
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 13 std::vector<uint32_t> buffer(n);
48 13 int num_threads = omp_get_max_threads();
49
50
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 13 times.
 65 for (int byte = 0; byte < 4; ++byte) {
51 52 const int shift = byte * kBitsPerDigit;
52
53
2/6
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 52 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 52 std::vector<std::vector<int>> local_counts(static_cast<size_t>(num_threads), std::vector<int>(kRadix, 0));
54
55 52 #pragma omp parallel for schedule(static) default(none) shared(temp, local_counts, n, shift)
56 for (size_t i = 0; i < n; ++i) {
57 int thread_idx = omp_get_thread_num();
58 int digit = static_cast<int>((temp[i] >> shift) & 0xFFU);
59 local_counts[static_cast<size_t>(thread_idx)][static_cast<size_t>(digit)]++;
60 }
61
62
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 std::vector<int> global_count(kRadix, 0);
63
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 52 times.
 156 for (int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
64
2/2
✓ Branch 0 taken 26624 times.
✓ Branch 1 taken 104 times.
 26728 for (int digit_idx = 0; digit_idx < kRadix; ++digit_idx) {
65 26624 global_count[digit_idx] += local_counts[static_cast<size_t>(thread_idx)][static_cast<size_t>(digit_idx)];
66 }
67 }
68
69
2/2
✓ Branch 0 taken 13260 times.
✓ Branch 1 taken 52 times.
 13312 for (int i = 1; i < kRadix; ++i) {
70 13260 global_count[i] += global_count[i - 1];
71 }
72
73
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 std::vector<int> count = global_count;
74
2/2
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 52 times.
 220 for (size_t i = n; i-- > 0;) {
75 168 int digit = static_cast<int>((temp[i] >> shift) & 0xFFU);
76 168 buffer[static_cast<size_t>(--count[static_cast<size_t>(digit)])] = temp[i];
77 }
78
79 temp.swap(buffer);
80 52 }
81
82
1/2
✓ Branch 0 taken 13 times.
✗ Branch 1 not taken.
 13 #pragma omp parallel for schedule(static) default(none) shared(data, temp, n)
83 for (size_t i = 0; i < n; ++i) {
84 data[i] = static_cast<int>(temp[i] ^ kSignMask);
85 }
86 }
87
88 6 void ChernovTRadixSortALL::SimpleMerge(const std::vector<int> &left, const std::vector<int> &right,
89 std::vector<int> &result) {
90 6 result.resize(left.size() + right.size());
91 6 std::ranges::merge(left, right, result.begin());
92 6 }
93
94 ✗ void ChernovTRadixSortALL::ComputeChunkSizes(int num_processes, size_t total_elements, std::vector<int> &recv_counts,
95 std::vector<int> &displs) {
96 7 int base = static_cast<int>(total_elements / static_cast<size_t>(num_processes));
97 7 int remainder = static_cast<int>(total_elements % static_cast<size_t>(num_processes));
98 int current_disp = 0;
99
2/4
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 21 for (int i = 0; i < num_processes; ++i) {
100
2/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 22 recv_counts[i] = base + (i < remainder ? 1 : 0);
101 14 displs[i] = current_disp;
102 14 current_disp += recv_counts[i];
103 }
104 ✗ }
105
106
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 7 times.
 7 void ChernovTRadixSortALL::MergeChunksOnRank0(const std::vector<int> &global_result,
107 const std::vector<int> &recv_counts, const std::vector<int> &displs,
108 std::vector<int> &output) {
109
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 7 times.
 7 if (global_result.empty()) {
110 output.clear();
111 ✗ return;
112 }
113
114 7 int num_processes = static_cast<int>(recv_counts.size());
115
116 int start_idx = -1;
117 int offset = 0;
118
1/2
✓ Branch 0 taken 7 times.
✗ Branch 1 not taken.
 7 for (int i = 0; i < num_processes; ++i) {
119
1/2
✓ Branch 0 taken 7 times.
✗ Branch 1 not taken.
 7 if (recv_counts[i] > 0) {
120 start_idx = i;
121 7 offset = displs[i];
122 7 break;
123 }
124 }
125
126
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 7 times.
 7 if (start_idx == -1) {
127 output.clear();
128 ✗ return;
129 }
130
131 7 std::vector<int> merged(global_result.begin() + offset, global_result.begin() + offset + recv_counts[start_idx]);
132 7 offset += recv_counts[start_idx];
133
134
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 for (int i = start_idx + 1; i < num_processes; ++i) {
135
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 1 times.
 7 if (recv_counts[i] > 0) {
136
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<int> next_part(global_result.begin() + offset, global_result.begin() + offset + recv_counts[i]);
137 6 std::vector<int> new_merged;
138
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 SimpleMerge(merged, next_part, new_merged);
139 merged = std::move(new_merged);
140
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 offset += recv_counts[i];
141 }
142 }
143
144 output = std::move(merged);
145 }
146
147 16 bool ChernovTRadixSortALL::RunImpl() {
148 auto &input_data = GetInput();
149 16 int current_rank = -1;
150 16 int num_processes = -1;
151 16 MPI_Comm_rank(MPI_COMM_WORLD, &current_rank);
152 16 MPI_Comm_size(MPI_COMM_WORLD, &num_processes);
153
154 const size_t total_elements = input_data.size();
155
156
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 14 times.
 16 if (total_elements == 0) {
157 GetOutput().clear();
158 2 return true;
159 }
160
161 14 std::vector<int> recv_counts(num_processes, 0);
162
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<int> displs(num_processes, 0);
163
164
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (current_rank == 0) {
165 7 ComputeChunkSizes(num_processes, total_elements, recv_counts, displs);
166 }
167
168
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 int local_n = 0;
169
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 MPI_Scatter(recv_counts.data(), 1, MPI_INT, &local_n, 1, MPI_INT, 0, MPI_COMM_WORLD);
170
171 14 std::vector<int> local_data;
172
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 1 times.
 14 if (local_n > 0) {
173
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 local_data.resize(static_cast<size_t>(local_n));
174
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 MPI_Scatterv(input_data.data(), recv_counts.data(), displs.data(), MPI_INT, local_data.data(), local_n, MPI_INT, 0,
175 MPI_COMM_WORLD);
176
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 RadixSortLSDParallelOMP(local_data);
177 }
178
179 14 std::vector<int> global_result;
180
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (current_rank == 0) {
181
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 global_result.resize(total_elements);
182 }
183
184
3/4
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 1 times.
✓ Branch 3 taken 14 times.
✗ Branch 4 not taken.
 27 MPI_Gatherv(local_data.empty() ? nullptr : local_data.data(), local_n, MPI_INT, global_result.data(),
185 recv_counts.data(), displs.data(), MPI_INT, 0, MPI_COMM_WORLD);
186
187
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (current_rank == 0) {
188
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 MergeChunksOnRank0(global_result, recv_counts, displs, GetOutput());
189 } else {
190 GetOutput().clear();
191 }
192
193 14 int out_size = static_cast<int>(GetOutput().size());
194
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 MPI_Bcast(&out_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
195
196
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (current_rank != 0) {
197
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 GetOutput().resize(static_cast<size_t>(out_size));
198 }
199
200
1/2
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
 14 if (out_size > 0) {
201
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 MPI_Bcast(GetOutput().data(), out_size, MPI_INT, 0, MPI_COMM_WORLD);
202 }
203
204 return true;
205 }
206
207
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 2 times.
 16 bool ChernovTRadixSortALL::PostProcessingImpl() {
208 16 return std::is_sorted(GetOutput().begin(), GetOutput().end());
209 }
210
211 } // namespace chernov_t_radix_sort
212