GCC Code Coverage Report

Directory: ./
File: tasks/trofimov_n_hoar_sort_batcher/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 62 77 80.5%
Functions: 12 13 92.3%
Branches: 40 66 60.6%
Line Branch Exec Source
1 #include "trofimov_n_hoar_sort_batcher/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <algorithm>
7 #include <utility>
8 #include <vector>
9
10 #include "oneapi/tbb/parallel_sort.h"
11 #include "trofimov_n_hoar_sort_batcher/common/include/common.hpp"
12 #include "util/include/util.hpp"
13
14 namespace trofimov_n_hoar_sort_batcher {
15
16 namespace {
17
18 constexpr int kQuickSortDepthLimit = 4;
19 constexpr int kSequentialThreshold = 1024;
20
21 struct MpiDistribution {
22 int rank = 0;
23 int size = 1;
24 int n = 0;
25 std::vector<int> counts;
26 std::vector<int> displs;
27 };
28
29 ✗ int HoarePartition(std::vector<int> &arr, int left, int right) {
30 ✗ const int pivot = arr[left + ((right - left) / 2)];
31 ✗ int i = left - 1;
32 ✗ int j = right + 1;
33
34 while (true) {
35 ✗ while (arr[++i] < pivot) {
36 }
37 ✗ while (arr[--j] > pivot) {
38 }
39 ✗ if (i >= j) {
40 ✗ return j;
41 }
42 std::swap(arr[i], arr[j]);
43 }
44 }
45
46 18 void TbbSortRange(std::vector<int> &arr, int left, int right) {
47
1/2
✓ Branch 0 taken 18 times.
✗ Branch 1 not taken.
 18 if (left >= right) {
48 return;
49 }
50 18 oneapi::tbb::parallel_sort(arr.begin() + left, arr.begin() + right + 1);
51 }
52
53 20 void QuickSortOmpTask(std::vector<int> &arr, int left, int right, int depth_limit) {
54
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 2 times.
 20 if (left >= right) {
55 return;
56 }
57
58
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 18 if ((right - left) < kSequentialThreshold || depth_limit <= 0) {
59 18 TbbSortRange(arr, left, right);
60 18 return;
61 }
62
63 ✗ const int split = HoarePartition(arr, left, right);
64
65 ✗ #pragma omp task default(none) shared(arr) \
66 ✗ firstprivate(left, split, depth_limit) if ((split - left) > kSequentialThreshold)
67 QuickSortOmpTask(arr, left, split, depth_limit - 1);
68
69 ✗ #pragma omp task default(none) shared(arr) \
70 ✗ firstprivate(split, right, depth_limit) if ((right - (split + 1)) > kSequentialThreshold)
71 QuickSortOmpTask(arr, split + 1, right, depth_limit - 1);
72
73 ✗ #pragma omp taskwait
74 }
75
76 20 MpiDistribution BuildDistribution(int n) {
77 20 MpiDistribution dist;
78 20 dist.n = n;
79
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Comm_rank(MPI_COMM_WORLD, &dist.rank);
80
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Comm_size(MPI_COMM_WORLD, &dist.size);
81
82
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 dist.counts.assign(dist.size, 0);
83
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 dist.displs.assign(dist.size, 0);
84
85 20 const int base = n / dist.size;
86 20 const int rem = n % dist.size;
87
88
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 20 times.
 60 for (int i = 0; i < dist.size; i++) {
89
4/4
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 20 times.
✓ Branch 3 taken 20 times.
 66 dist.counts[i] = base + (i < rem ? 1 : 0);
90
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 20 times.
 40 if (i > 0) {
91 20 dist.displs[i] = dist.displs[i - 1] + dist.counts[i - 1];
92 }
93 }
94
95 20 return dist;
96 ✗ }
97
98 20 std::vector<int> ScatterData(const std::vector<int> &data, const MpiDistribution &dist) {
99 20 std::vector<int> local(dist.counts[dist.rank]);
100
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Scatterv(data.data(), dist.counts.data(), dist.displs.data(), MPI_INT, local.data(), dist.counts[dist.rank],
101 MPI_INT, 0, MPI_COMM_WORLD);
102 20 return local;
103 }
104
105
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 void SortLocalChunkHybrid(std::vector<int> &local) {
106
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (local.empty()) {
107 return;
108 }
109
110 20 #pragma omp parallel num_threads(ppc::util::GetNumThreads()) default(none) shared(local)
111 {
112 #pragma omp single nowait
113 {
114 QuickSortOmpTask(local, 0, static_cast<int>(local.size()) - 1, kQuickSortDepthLimit);
115 }
116 }
117 }
118
119 20 std::vector<int> GatherChunks(const std::vector<int> &local, const MpiDistribution &dist) {
120 20 std::vector<int> gathered;
121
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (dist.rank == 0) {
122
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 gathered.resize(dist.n);
123 }
124
125
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Gatherv(local.data(), dist.counts[dist.rank], MPI_INT, gathered.data(), dist.counts.data(), dist.displs.data(),
126 MPI_INT, 0, MPI_COMM_WORLD);
127
128 20 return gathered;
129 }
130
131 20 void MergeSortedChunksOnRoot(std::vector<int> &gathered, const MpiDistribution &dist) {
132
3/4
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
 20 if (dist.rank != 0 || gathered.empty()) {
133 return;
134 }
135
136 10 int merged_size = dist.counts[0];
137
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 for (int proc = 1; proc < dist.size; proc++) {
138 10 const int right_end = merged_size + dist.counts[proc];
139 10 std::inplace_merge(gathered.begin(), gathered.begin() + merged_size, gathered.begin() + right_end);
140 merged_size = right_end;
141 }
142 }
143
144 void BroadcastResult(std::vector<int> &data, const MpiDistribution &dist) {
145
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Bcast(data.data(), dist.n, MPI_INT, 0, MPI_COMM_WORLD);
146 20 }
147
148 } // namespace
149
150
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 TrofimovNHoarSortBatcherALL::TrofimovNHoarSortBatcherALL(const InType &in) {
151 SetTypeOfTask(GetStaticTypeOfTask());
152
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GetInput() = in;
153 24 }
154
155 24 bool TrofimovNHoarSortBatcherALL::ValidationImpl() {
156 24 return true;
157 }
158
159 24 bool TrofimovNHoarSortBatcherALL::PreProcessingImpl() {
160 24 GetOutput() = GetInput();
161 24 return true;
162 }
163
164
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 4 times.
 24 bool TrofimovNHoarSortBatcherALL::RunImpl() {
165 auto &data = GetOutput();
166
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 4 times.
 24 if (data.size() <= 1) {
167 return true;
168 }
169
170 20 const auto dist = BuildDistribution(static_cast<int>(data.size()));
171
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 auto local = ScatterData(data, dist);
172
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 SortLocalChunkHybrid(local);
173
174
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 auto gathered = GatherChunks(local, dist);
175 20 MergeSortedChunksOnRoot(gathered, dist);
176
177
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (dist.rank == 0) {
178 data = std::move(gathered);
179 }
180
181 BroadcastResult(data, dist);
182 return true;
183 20 }
184
185 24 bool TrofimovNHoarSortBatcherALL::PostProcessingImpl() {
186 24 return true;
187 }
188
189 } // namespace trofimov_n_hoar_sort_batcher
190