GCC Code Coverage Report

Directory: ./
File: tasks/vasiliev_m_shell_sort_batcher_merge/all/src/ops_all.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 139 141 98.6%
Functions: 15 15 100.0%
Branches: 114 176 64.8%
Line Branch Exec Source
1 #include "vasiliev_m_shell_sort_batcher_merge/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <tbb/blocked_range.h>
5 #include <tbb/parallel_for.h>
6
7 #include <algorithm>
8 #include <cstddef>
9 #include <vector>
10
11 #include "util/include/util.hpp"
12 #include "vasiliev_m_shell_sort_batcher_merge/common/include/common.hpp"
13
14 namespace vasiliev_m_shell_sort_batcher_merge {
15
16
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 VasilievMShellSortBatcherMergeALL::VasilievMShellSortBatcherMergeALL(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GetInput() = in;
19 12 GetOutput() = OutType{};
20 12 }
21
22 12 bool VasilievMShellSortBatcherMergeALL::ValidationImpl() {
23 12 return !GetInput().empty();
24 }
25
26
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 bool VasilievMShellSortBatcherMergeALL::PreProcessingImpl() {
27 GetOutput().clear();
28 12 return true;
29 }
30
31 12 bool VasilievMShellSortBatcherMergeALL::RunImpl() {
32 12 int rank = 0;
33 12 int process_count = 1;
34 12 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
35 12 MPI_Comm_size(MPI_COMM_WORLD, &process_count);
36
37 auto &vec = GetInput();
38 12 int n = static_cast<int>(vec.size());
39
40 12 std::vector<int> counts(process_count);
41
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<int> displs(process_count);
42
43
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
44 6 CalcCountsAndDispls(n, process_count, counts, displs);
45 }
46
47
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Bcast(counts.data(), process_count, MPI_INT, 0, MPI_COMM_WORLD);
48
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Bcast(displs.data(), process_count, MPI_INT, 0, MPI_COMM_WORLD);
49
50
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<ValType> local_data(static_cast<size_t>(counts[rank]));
51
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Scatterv(vec.data(), counts.data(), displs.data(), MPI_INT, local_data.data(), counts[rank], MPI_INT, 0,
52 MPI_COMM_WORLD);
53
54
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 const int threads = std::max(1, ppc::util::GetNumThreads());
55
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 std::vector<size_t> bounds = ChunkBoundaries(static_cast<size_t>(counts[rank]), threads);
56 12 size_t chunk_count = bounds.size() - 1;
57
58
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 ShellSort(local_data, bounds);
59
60
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<ValType> buffer(static_cast<size_t>(counts[rank]));
61
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 12 times.
 23 for (size_t size = 1; size < chunk_count; size *= 2) {
62
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 CycleMerge(local_data, buffer, bounds, size);
63 local_data.swap(buffer);
64 }
65
66
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
67
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 GetOutput().resize(static_cast<size_t>(n));
68 }
69
70
3/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
✓ Branch 3 taken 12 times.
✗ Branch 4 not taken.
 18 MPI_Gatherv(local_data.data(), counts[rank], MPI_INT, rank == 0 ? GetOutput().data() : nullptr, counts.data(),
71 displs.data(), MPI_INT, 0, MPI_COMM_WORLD);
72
73
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
74
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 auto root_bounds = BoundsFromCounts(counts);
75 6 size_t root_chunk_count = root_bounds.size() - 1;
76
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<ValType> root_buffer(static_cast<size_t>(n));
77
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 for (size_t size = 1; size < root_chunk_count; size *= 2) {
78
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 CycleMerge(GetOutput(), root_buffer, root_bounds, size);
79 GetOutput().swap(root_buffer);
80 }
81 }
82
83
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank != 0) {
84
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 GetOutput().resize(static_cast<size_t>(n));
85 }
86
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Bcast(GetOutput().data(), n, MPI_INT, 0, MPI_COMM_WORLD);
87
88 12 return true;
89 }
90
91 12 bool VasilievMShellSortBatcherMergeALL::PostProcessingImpl() {
92 12 return true;
93 }
94
95 6 void VasilievMShellSortBatcherMergeALL::CalcCountsAndDispls(int n, int process_count, std::vector<int> &counts,
96 std::vector<int> &displs) {
97 6 int chunk = n / process_count;
98 6 int remainder = n % process_count;
99
100
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
 18 for (int i = 0; i < process_count; i++) {
101
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 2 times.
 22 counts[i] = chunk + (i < remainder ? 1 : 0);
102 }
103
104 6 displs[0] = 0;
105
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 for (int i = 1; i < process_count; i++) {
106 6 displs[i] = displs[i - 1] + counts[i - 1];
107 }
108 6 }
109
110 6 std::vector<size_t> VasilievMShellSortBatcherMergeALL::BoundsFromCounts(const std::vector<int> &counts) {
111
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 std::vector<size_t> bounds;
112
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 bounds.reserve(counts.size() + 1);
113
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 bounds.push_back(0);
114
3/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 12 times.
✓ Branch 4 taken 6 times.
 18 for (int c : counts) {
115
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 bounds.push_back(bounds.back() + static_cast<size_t>(c));
116 }
117 6 return bounds;
118 }
119
120 12 std::vector<size_t> VasilievMShellSortBatcherMergeALL::ChunkBoundaries(size_t vec_size, int threads) {
121
4/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 11 times.
✓ Branch 2 taken 11 times.
✓ Branch 3 taken 1 times.
 13 size_t chunks = static_cast<size_t>(std::max(1, std::min(threads, static_cast<int>(vec_size))));
122 12 std::vector<size_t> bounds;
123
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 bounds.reserve(chunks + 1);
124
125 12 size_t chunk_size = vec_size / chunks;
126 12 size_t remainder = vec_size % chunks;
127
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 bounds.push_back(0);
128
129
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 12 times.
 35 for (size_t i = 0; i < chunks; i++) {
130
3/6
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 7 times.
✓ Branch 3 taken 23 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 39 bounds.push_back(bounds.back() + chunk_size + (i < remainder ? 1 : 0));
131 }
132 12 return bounds;
133 }
134
135 12 void VasilievMShellSortBatcherMergeALL::ShellSort(std::vector<ValType> &vec, std::vector<size_t> &bounds) {
136 12 size_t chunk_count = bounds.size() - 1;
137
138 35 tbb::parallel_for(tbb::blocked_range<size_t>(0, chunk_count), [&](const tbb::blocked_range<size_t> &range) {
139
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 23 times.
 46 for (size_t chunk = range.begin(); chunk < range.end(); chunk++) {
140 23 size_t first = bounds[chunk];
141 23 size_t last = bounds[chunk + 1];
142 23 size_t n = last - first;
143
144
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 23 times.
 38 for (size_t gap = n / 2; gap > 0; gap /= 2) {
145
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 15 times.
 34 for (size_t i = first + gap; i < last; i++) {
146 19 ValType tmp = vec[i];
147 size_t j = i;
148
4/4
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 14 times.
 25 while (j >= first + gap && vec[j - gap] > tmp) {
149 6 vec[j] = vec[j - gap];
150 j -= gap;
151 }
152 19 vec[j] = tmp;
153 }
154 }
155 }
156 23 });
157 12 }
158
159 17 void VasilievMShellSortBatcherMergeALL::CycleMerge(std::vector<ValType> &vec, std::vector<ValType> &buffer,
160 std::vector<size_t> &bounds, size_t size) {
161 17 const size_t chunk_count = bounds.size() - 1;
162 17 const size_t merge_count = (chunk_count + (2 * size) - 1) / (2 * size);
163
164 34 tbb::parallel_for(tbb::blocked_range<size_t>(0, merge_count), [&](const tbb::blocked_range<size_t> &range) {
165
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 17 times.
 34 for (size_t idx = range.begin(); idx < range.end(); idx++) {
166 17 const size_t l = idx * 2 * size;
167
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 17 times.
 17 const size_t mid = std::min(l + size, chunk_count);
168
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 17 times.
 17 const size_t r = std::min(l + (2 * size), chunk_count);
169
170
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 17 times.
 17 const size_t start = bounds[l];
171 17 const size_t middle = bounds[mid];
172 17 const size_t end = bounds[r];
173
174
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 17 times.
 17 if (mid == r) {
175 ✗ std::copy(vec.begin() + static_cast<std::ptrdiff_t>(start), vec.begin() + static_cast<std::ptrdiff_t>(end),
176 ✗ buffer.begin() + static_cast<std::ptrdiff_t>(start));
177 } else {
178 std::vector<ValType> l_vect(vec.begin() + static_cast<std::ptrdiff_t>(start),
179 17 vec.begin() + static_cast<std::ptrdiff_t>(middle));
180 std::vector<ValType> r_vect(vec.begin() + static_cast<std::ptrdiff_t>(middle),
181
1/4
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 17 vec.begin() + static_cast<std::ptrdiff_t>(end));
182
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 std::vector<ValType> merged = BatcherMerge(l_vect, r_vect);
183
2/2
✓ Branch 0 taken 83 times.
✓ Branch 1 taken 17 times.
 100 for (size_t i = 0; i < merged.size(); i++) {
184 83 buffer[start + i] = merged[i];
185 }
186 }
187 }
188 17 });
189 17 }
190
191 17 std::vector<ValType> VasilievMShellSortBatcherMergeALL::BatcherMerge(std::vector<ValType> &l, std::vector<ValType> &r) {
192 17 std::vector<ValType> even_l;
193 17 std::vector<ValType> odd_l;
194 17 std::vector<ValType> even_r;
195 17 std::vector<ValType> odd_r;
196
197
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 SplitEvenOdd(l, even_l, odd_l);
198
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 SplitEvenOdd(r, even_r, odd_r);
199
200
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 std::vector<ValType> even = Merge(even_l, even_r);
201
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 std::vector<ValType> odd = Merge(odd_l, odd_r);
202
203
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 std::vector<ValType> res;
204
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 res.reserve(l.size() + r.size());
205
206
3/4
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 51 times.
✓ Branch 2 taken 17 times.
✗ Branch 3 not taken.
 68 for (size_t i = 0; i < even.size() || i < odd.size(); i++) {
207
1/2
✓ Branch 0 taken 51 times.
✗ Branch 1 not taken.
 51 if (i < even.size()) {
208 res.push_back(even[i]);
209 }
210
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 19 times.
 51 if (i < odd.size()) {
211 res.push_back(odd[i]);
212 }
213 }
214
215
2/2
✓ Branch 0 taken 29 times.
✓ Branch 1 taken 17 times.
 46 for (size_t i = 1; i + 1 < res.size(); i += 2) {
216
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 12 times.
 29 if (res[i] > res[i + 1]) {
217 std::swap(res[i], res[i + 1]);
218 }
219 }
220
221 17 return res;
222 }
223
224 34 void VasilievMShellSortBatcherMergeALL::SplitEvenOdd(std::vector<ValType> &vec, std::vector<ValType> &even,
225 std::vector<ValType> &odd) {
226 34 even.reserve(even.size() + (vec.size() / 2) + 1);
227 34 odd.reserve(odd.size() + (vec.size() / 2));
228
229
2/2
✓ Branch 0 taken 51 times.
✓ Branch 1 taken 34 times.
 85 for (size_t i = 0; i < vec.size(); i += 2) {
230 even.push_back(vec[i]);
231
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 19 times.
 51 if (i + 1 < vec.size()) {
232 odd.push_back(vec[i + 1]);
233 }
234 }
235 34 }
236
237 34 std::vector<ValType> VasilievMShellSortBatcherMergeALL::Merge(std::vector<ValType> &a, std::vector<ValType> &b) {
238
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 std::vector<ValType> merged;
239
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 merged.reserve(a.size() + b.size());
240 size_t i = 0;
241 size_t j = 0;
242
243
4/4
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 61 times.
✓ Branch 2 taken 15 times.
✓ Branch 3 taken 46 times.
 80 while (i < a.size() && j < b.size()) {
244
2/2
✓ Branch 0 taken 29 times.
✓ Branch 1 taken 17 times.
 46 if (a[i] <= b[j]) {
245
1/2
✓ Branch 0 taken 29 times.
✗ Branch 1 not taken.
 29 merged.push_back(a[i++]);
246 } else {
247
1/2
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
 17 merged.push_back(b[j++]);
248 }
249 }
250
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 34 times.
 51 while (i < a.size()) {
251
1/2
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
 17 merged.push_back(a[i++]);
252 }
253
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 34 times.
 54 while (j < b.size()) {
254
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 merged.push_back(b[j++]);
255 }
256
257 34 return merged;
258 }
259
260 } // namespace vasiliev_m_shell_sort_batcher_merge
261