GCC Code Coverage Report

Directory: ./
File: tasks/akimov_i_radixsort_int_merge/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 103 106 97.2%
Functions: 11 11 100.0%
Branches: 64 96 66.7%
Line Branch Exec Source
1 #include "akimov_i_radixsort_int_merge/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <oneapi/tbb/parallel_for.h>
5
6 #include <algorithm>
7 #include <cstddef>
8 #include <cstdint>
9 #include <iterator>
10 #include <vector>
11
12 #include "akimov_i_radixsort_int_merge/common/include/common.hpp"
13 #include "util/include/util.hpp"
14
15 namespace akimov_i_radixsort_int_merge {
16
17 namespace {
18
19 24 void CountingSortStep(std::vector<int>::iterator in_begin, std::vector<int>::iterator in_end,
20 std::vector<int>::iterator out_begin, size_t byte_index) {
21 24 size_t shift = byte_index * 8;
22 24 std::vector<size_t> count(256, 0);
23
24
2/2
✓ Branch 0 taken 4440 times.
✓ Branch 1 taken 24 times.
 4464 for (auto it = in_begin; it != in_end; ++it) {
25 4440 auto raw_val = static_cast<uint32_t>(*it);
26 4440 uint32_t byte_val = (raw_val >> shift) & 0xFF;
27 4440 ++count[byte_val];
28 }
29
30
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<size_t> prefix(256, 0);
31 24 prefix[0] = 0;
32
2/2
✓ Branch 0 taken 6120 times.
✓ Branch 1 taken 24 times.
 6144 for (int i = 1; i < 256; ++i) {
33 6120 prefix[i] = prefix[i - 1] + count[i - 1];
34 }
35
36
2/2
✓ Branch 0 taken 4440 times.
✓ Branch 1 taken 24 times.
 4464 for (auto it = in_begin; it != in_end; ++it) {
37 4440 auto raw_val = static_cast<uint32_t>(*it);
38 4440 uint32_t byte_val = (raw_val >> shift) & 0xFF;
39 4440 *(out_begin + static_cast<std::ptrdiff_t>(prefix[byte_val])) = *it;
40 4440 ++prefix[byte_val];
41 }
42 24 }
43
44
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 void RadixSortLocal(std::vector<int>::iterator begin, std::vector<int>::iterator end) {
45 6 size_t n = std::distance(begin, end);
46
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (n < 2) {
47 ✗ return;
48 }
49 6 std::vector<int> temp(n);
50
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 6 times.
 30 for (size_t i = 0; i < sizeof(int); ++i) {
51
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (i % 2 == 0) {
52
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 CountingSortStep(begin, end, temp.begin(), i);
53 } else {
54
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 CountingSortStep(temp.begin(), temp.end(), begin, i);
55 }
56 }
57 }
58
59 3 void ParallelMerge(std::vector<int> &arr, const std::vector<int> &offsets, int num_blocks) {
60
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 for (int step = 1; step < num_blocks; step *= 2) {
61 3 tbb::parallel_for(0, num_blocks, [&, step](int i) {
62
3/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 6 if (i % (2 * step) == 0 && i + step < num_blocks) {
63
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 auto begin = arr.begin() + offsets[i];
64 3 auto middle = arr.begin() + offsets[i + step];
65
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 int end_idx = std::min(i + (2 * step), num_blocks);
66 3 auto end = arr.begin() + offsets[end_idx];
67 3 std::inplace_merge(begin, middle, end);
68 }
69 6 });
70 }
71 3 }
72
73 6 void DistributeData(int rank, int world_size, int n, const std::vector<int> &input, std::vector<int> &local_data,
74 std::vector<int> &send_counts, std::vector<int> &send_displs) {
75 6 send_counts.resize(world_size);
76 6 send_displs.resize(world_size);
77 6 int base = n / world_size;
78 6 int rem = n % world_size;
79 int offset = 0;
80
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
 18 for (int i = 0; i < world_size; ++i) {
81
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 24 send_counts[i] = base + (i < rem ? 1 : 0);
82 12 send_displs[i] = offset;
83 12 offset += send_counts[i];
84 }
85
86 6 int local_size = send_counts[rank];
87 6 local_data.resize(local_size);
88
89
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 if (ppc::util::IsUnderMpirun()) {
90
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 9 MPI_Scatterv(rank == 0 ? input.data() : nullptr, send_counts.data(), send_displs.data(), MPI_INT, local_data.data(),
91 local_size, MPI_INT, 0, MPI_COMM_WORLD);
92 } else {
93 ✗ local_data = input;
94 }
95 6 }
96
97 6 void GatherData(int rank, int n, const std::vector<int> &local_data, const std::vector<int> &send_counts,
98 const std::vector<int> &send_displs, std::vector<int> &output) {
99
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 if (ppc::util::IsUnderMpirun()) {
100
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
101 3 output.resize(n);
102 }
103
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 9 MPI_Gatherv(local_data.data(), static_cast<int>(local_data.size()), MPI_INT, rank == 0 ? output.data() : nullptr,
104 send_counts.data(), send_displs.data(), MPI_INT, 0, MPI_COMM_WORLD);
105 } else {
106 ✗ output = local_data;
107 }
108 6 }
109
110 void InvertSignBit(std::vector<int> &data, int32_t mask) {
111
4/4
✓ Branch 0 taken 1110 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 1110 times.
✓ Branch 3 taken 6 times.
 2232 for (int &val : data) {
112 2220 val ^= mask;
113 }
114 }
115
116 } // namespace
117
118
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 AkimovIRadixSortIntMergeALL::AkimovIRadixSortIntMergeALL(const InType &in) {
119 SetTypeOfTask(GetStaticTypeOfTask());
120
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 GetInput() = in;
121 6 GetOutput() = OutType();
122 6 }
123
124 6 bool AkimovIRadixSortIntMergeALL::ValidationImpl() {
125 6 return !GetInput().empty();
126 }
127
128 6 bool AkimovIRadixSortIntMergeALL::PreProcessingImpl() {
129 6 int rank = 0;
130
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 if (ppc::util::IsUnderMpirun()) {
131 6 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
132 }
133
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
134 3 GetOutput() = GetInput();
135 }
136 6 return true;
137 }
138
139 6 bool AkimovIRadixSortIntMergeALL::RunImpl() {
140 6 const bool is_mpi = ppc::util::IsUnderMpirun();
141 6 int rank = 0;
142 6 int world_size = 1;
143
144
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (is_mpi) {
145 6 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
146 6 MPI_Comm_size(MPI_COMM_WORLD, &world_size);
147 }
148
149 6 int n = 0;
150
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
151 3 n = static_cast<int>(GetOutput().size());
152 }
153
154
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (is_mpi) {
155 6 MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
156 }
157
158
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (n == 0) {
159 return true;
160 }
161
162 6 std::vector<int> send_counts;
163 6 std::vector<int> send_displs;
164
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 std::vector<int> local_data;
165
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 DistributeData(rank, world_size, n, GetOutput(), local_data, send_counts, send_displs);
166
167 constexpr int32_t kSignMask = INT32_MIN;
168 InvertSignBit(local_data, kSignMask);
169
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 RadixSortLocal(local_data.begin(), local_data.end());
170 InvertSignBit(local_data, kSignMask);
171
172
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 GatherData(rank, n, local_data, send_counts, send_displs, GetOutput());
173
174
3/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 6 if (rank == 0 && world_size > 1) {
175
1/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 3 std::vector<int> offsets(world_size + 1, 0);
176
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 3 times.
 9 for (int i = 0; i < world_size; ++i) {
177 6 offsets[i + 1] = offsets[i] + send_counts[i];
178 }
179
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 ParallelMerge(GetOutput(), offsets, world_size);
180 }
181
182
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (is_mpi) {
183 6 int output_size = static_cast<int>(GetOutput().size());
184
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Bcast(&output_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
185
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank != 0) {
186
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 GetOutput().resize(output_size);
187 }
188
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Bcast(GetOutput().data(), output_size, MPI_INT, 0, MPI_COMM_WORLD);
189 }
190
191 return true;
192 }
193
194 6 bool AkimovIRadixSortIntMergeALL::PostProcessingImpl() {
195 6 return true;
196 }
197
198 } // namespace akimov_i_radixsort_int_merge
199