GCC Code Coverage Report

Directory: ./
File: tasks/tochilin_e_hoar_sort_sim_mer/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 96 103 93.2%
Functions: 11 12 91.7%
Branches: 60 100 60.0%
Line Branch Exec Source
1 #include "tochilin_e_hoar_sort_sim_mer/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <algorithm>
7 #include <cstddef>
8 #include <iterator>
9 #include <utility>
10 #include <vector>
11
12 #include "tochilin_e_hoar_sort_sim_mer/common/include/common.hpp"
13 #include "util/include/util.hpp"
14
15 namespace tochilin_e_hoar_sort_sim_mer {
16
17 namespace {
18
19 20 std::vector<int> BuildCounts(int total_size, int proc_count) {
20 20 std::vector<int> counts(static_cast<std::size_t>(proc_count), 0);
21
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 20 times.
 60 for (int rank = 0; rank < proc_count; ++rank) {
22 40 counts[static_cast<std::size_t>(rank)] =
23 40 (((rank + 1) * total_size) / proc_count) - ((rank * total_size) / proc_count);
24 }
25 20 return counts;
26 }
27
28 20 std::vector<int> BuildDisplacements(const std::vector<int> &counts) {
29 20 std::vector<int> displs(counts.size(), 0);
30
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 20 times.
 40 for (std::size_t i = 1; i < counts.size(); ++i) {
31 20 displs[i] = displs[i - 1] + counts[i - 1];
32 }
33 20 return displs;
34 }
35
36 10 std::vector<int> MergeLocalVectors(const std::vector<int> &a, const std::vector<int> &b) {
37
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 std::vector<int> result;
38
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 result.reserve(a.size() + b.size());
39
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 std::ranges::merge(a, b, std::back_inserter(result));
40 10 return result;
41 }
42
43 20 std::vector<int> MergeAcrossRanks(std::vector<int> local_data, int rank, int proc_count) {
44
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 10 times.
 30 for (int step = 1; step < proc_count; step *= 2) {
45
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if ((rank % (step * 2)) == step) {
46 10 const int target_rank = rank - step;
47 10 const int local_size = static_cast<int>(local_data.size());
48 10 MPI_Send(&local_size, 1, MPI_INT, target_rank, 0, MPI_COMM_WORLD);
49
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (local_size > 0) {
50 10 MPI_Send(local_data.data(), local_size, MPI_INT, target_rank, 1, MPI_COMM_WORLD);
51 }
52 break;
53 }
54
55
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 if ((rank % (step * 2)) != 0) {
56 ✗ continue;
57 }
58
59 10 const int source_rank = rank + step;
60
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 if (source_rank >= proc_count) {
61 ✗ continue;
62 }
63
64 10 int remote_size = 0;
65 10 MPI_Recv(&remote_size, 1, MPI_INT, source_rank, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
66
67 10 std::vector<int> remote_data(static_cast<std::size_t>(remote_size), 0);
68
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (remote_size > 0) {
69
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Recv(remote_data.data(), remote_size, MPI_INT, source_rank, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
70 }
71
72
2/6
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 10 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 20 local_data = MergeLocalVectors(local_data, remote_data);
73 }
74
75 20 return local_data;
76 }
77
78 } // namespace
79
80
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 TochilinEHoarSortSimMerALL::TochilinEHoarSortSimMerALL(const InType &in) {
81 SetTypeOfTask(GetStaticTypeOfTask());
82
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 GetInput() = in;
83 20 }
84
85 20 bool TochilinEHoarSortSimMerALL::ValidationImpl() {
86 20 return !GetInput().empty();
87 }
88
89 20 bool TochilinEHoarSortSimMerALL::PreProcessingImpl() {
90 20 GetOutput() = GetInput();
91 20 return true;
92 }
93
94 3304 std::pair<int, int> TochilinEHoarSortSimMerALL::Partition(std::vector<int> &arr, int l, int r) {
95 int i = l;
96 int j = r;
97 3304 const int pivot = arr[(l + r) / 2];
98
99
2/2
✓ Branch 0 taken 10138 times.
✓ Branch 1 taken 3304 times.
 16746 while (i <= j) {
100
2/2
✓ Branch 0 taken 12621 times.
✓ Branch 1 taken 10138 times.
 22759 while (arr[i] < pivot) {
101 12621 ++i;
102 }
103
2/2
✓ Branch 0 taken 14409 times.
✓ Branch 1 taken 10138 times.
 24547 while (arr[j] > pivot) {
104 14409 --j;
105 }
106
2/2
✓ Branch 0 taken 986 times.
✓ Branch 1 taken 9152 times.
 10138 if (i <= j) {
107 std::swap(arr[i], arr[j]);
108 9152 ++i;
109 9152 --j;
110 }
111 }
112
113 3304 return {i, j};
114 }
115
116 211 void TochilinEHoarSortSimMerALL::QuickSortOMP(std::vector<int> &arr, int low, int high, int depth_limit) {
117 211 std::vector<std::pair<int, int>> stack;
118
1/2
✓ Branch 1 taken 211 times.
✗ Branch 2 not taken.
 211 stack.emplace_back(low, high);
119
120
2/2
✓ Branch 0 taken 3327 times.
✓ Branch 1 taken 211 times.
 3538 while (!stack.empty()) {
121 const auto [l0, r0] = stack.back();
122 stack.pop_back();
123
124 3327 int l = l0;
125 3327 int r = r0;
126
127
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 3304 times.
 3327 if (l >= r) {
128 23 continue;
129 }
130
131 3304 const std::pair<int, int> bounds = Partition(arr, l, r);
132 3304 int i = bounds.first;
133 3304 int j = bounds.second;
134
135
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 3208 times.
 3304 if (depth_limit > 0) {
136 96 #pragma omp task default(none) shared(arr) firstprivate(l, j, depth_limit)
137 QuickSortOMP(arr, l, j, depth_limit - 1);
138
139 96 #pragma omp task default(none) shared(arr) firstprivate(i, r, depth_limit)
140 QuickSortOMP(arr, i, r, depth_limit - 1);
141 } else {
142
2/2
✓ Branch 0 taken 1534 times.
✓ Branch 1 taken 1674 times.
 3208 if (l < j) {
143
1/2
✓ Branch 1 taken 1534 times.
✗ Branch 2 not taken.
 1534 stack.emplace_back(l, j);
144 }
145
2/2
✓ Branch 0 taken 1582 times.
✓ Branch 1 taken 1626 times.
 3208 if (i < r) {
146
1/2
✓ Branch 1 taken 1582 times.
✗ Branch 2 not taken.
 1582 stack.emplace_back(i, r);
147 }
148 }
149 }
150
151
1/2
✓ Branch 0 taken 211 times.
✗ Branch 1 not taken.
 211 #pragma omp taskwait
152 211 }
153
154 ✗ std::vector<int> TochilinEHoarSortSimMerALL::MergeSortedVectors(const std::vector<int> &a, const std::vector<int> &b) {
155 ✗ std::vector<int> result;
156 ✗ result.reserve(a.size() + b.size());
157 ✗ std::ranges::merge(a, b, std::back_inserter(result));
158 ✗ return result;
159 }
160
161
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 bool TochilinEHoarSortSimMerALL::RunImpl() {
162 auto &data = GetOutput();
163
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (data.empty()) {
164 return false;
165 }
166
167 20 int rank = 0;
168 20 int proc_count = 1;
169 20 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
170 20 MPI_Comm_size(MPI_COMM_WORLD, &proc_count);
171
172 20 const int total_size = static_cast<int>(data.size());
173 20 const std::vector<int> counts = BuildCounts(total_size, proc_count);
174
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 const std::vector<int> displs = BuildDisplacements(counts);
175
176
1/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 20 std::vector<int> local_data(static_cast<std::size_t>(counts[static_cast<std::size_t>(rank)]), 0);
177
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Scatterv(data.data(), counts.data(), displs.data(), MPI_INT, local_data.data(),
178
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 counts[static_cast<std::size_t>(rank)], MPI_INT, 0, MPI_COMM_WORLD);
179
180
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 1 times.
 20 if (!local_data.empty()) {
181
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 const int thread_count = std::max(1, ppc::util::GetNumThreads());
182 19 #pragma omp parallel default(none) shared(local_data) num_threads(thread_count) if (thread_count > 1)
183 {
184 #pragma omp single
185 QuickSortOMP(local_data, 0, static_cast<int>(local_data.size()) - 1, 3);
186 }
187 }
188
189
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (rank == 0) {
190 data.clear();
191 } else {
192
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 data.assign(static_cast<std::size_t>(total_size), 0);
193 }
194
195
1/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 20 local_data = MergeAcrossRanks(std::move(local_data), rank, proc_count);
196
197
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (rank == 0) {
198 data = std::move(local_data);
199 }
200
201
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Bcast(data.data(), total_size, MPI_INT, 0, MPI_COMM_WORLD);
202
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Barrier(MPI_COMM_WORLD);
203 return true;
204 }
205
206
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 bool TochilinEHoarSortSimMerALL::PostProcessingImpl() {
207 20 return std::ranges::is_sorted(GetOutput());
208 }
209
210 } // namespace tochilin_e_hoar_sort_sim_mer
211