GCC Code Coverage Report

Directory: ./
File: tasks/tochilin_e_hoar_sort_sim_mer/tbb/src/ops_tbb.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 72 80 90.0%
Functions: 13 14 92.9%
Branches: 47 82 57.3%
Line Branch Exec Source
1 #include "tochilin_e_hoar_sort_sim_mer/tbb/include/ops_tbb.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <iterator>
6 #include <utility>
7 #include <vector>
8
9 #include "oneapi/tbb/enumerable_thread_specific.h"
10 #include "oneapi/tbb/global_control.h"
11 #include "oneapi/tbb/parallel_for.h"
12 #include "oneapi/tbb/parallel_invoke.h"
13 #include "tochilin_e_hoar_sort_sim_mer/common/include/common.hpp"
14 #include "util/include/util.hpp"
15
16 namespace tochilin_e_hoar_sort_sim_mer {
17
18 namespace {
19
20 constexpr int kMinSequentialCutoff = 2048;
21
22 int ResolveConcurrency() {
23 40 return std::max(1, ppc::util::GetNumThreads());
24 }
25
26 } // namespace
27
28
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 TochilinEHoarSortSimMerTBB::TochilinEHoarSortSimMerTBB(const InType &in) {
29 SetTypeOfTask(GetStaticTypeOfTask());
30
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetInput() = in;
31 40 }
32
33 40 bool TochilinEHoarSortSimMerTBB::ValidationImpl() {
34 40 return !GetInput().empty();
35 }
36
37 40 bool TochilinEHoarSortSimMerTBB::PreProcessingImpl() {
38 40 GetOutput() = GetInput();
39 40 return true;
40 }
41
42 13216 std::pair<int, int> TochilinEHoarSortSimMerTBB::Partition(std::vector<int> &arr, int l, int r) {
43 int i = l;
44 int j = r;
45 13216 const int pivot = arr[(l + r) / 2];
46
47
2/2
✓ Branch 0 taken 40552 times.
✓ Branch 1 taken 13216 times.
 66984 while (i <= j) {
48
2/2
✓ Branch 0 taken 50484 times.
✓ Branch 1 taken 40552 times.
 91036 while (arr[i] < pivot) {
49 50484 ++i;
50 }
51
2/2
✓ Branch 0 taken 57636 times.
✓ Branch 1 taken 40552 times.
 98188 while (arr[j] > pivot) {
52 57636 --j;
53 }
54
2/2
✓ Branch 0 taken 3944 times.
✓ Branch 1 taken 36608 times.
 40552 if (i <= j) {
55 std::swap(arr[i], arr[j]);
56 36608 ++i;
57 36608 --j;
58 }
59 }
60
61 13216 return {i, j};
62 }
63
64 64 void TochilinEHoarSortSimMerTBB::QuickSortSequential(std::vector<int> &arr, int low, int high) {
65
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 64 times.
 64 if (low >= high) {
66 ✗ return;
67 }
68
69 64 std::vector<std::pair<int, int>> stack;
70
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 stack.emplace_back(low, high);
71
72
2/2
✓ Branch 0 taken 13216 times.
✓ Branch 1 taken 64 times.
 13280 while (!stack.empty()) {
73 const auto [l, r] = stack.back();
74 stack.pop_back();
75
76
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 13216 times.
 13216 if (l >= r) {
77 ✗ continue;
78 }
79
80 13216 const auto [i, j] = Partition(arr, l, r);
81
82
2/2
✓ Branch 0 taken 6484 times.
✓ Branch 1 taken 6732 times.
 13216 if (l < j) {
83
1/2
✓ Branch 1 taken 6484 times.
✗ Branch 2 not taken.
 6484 stack.emplace_back(l, j);
84 }
85
2/2
✓ Branch 0 taken 6668 times.
✓ Branch 1 taken 6548 times.
 13216 if (i < r) {
86
1/2
✓ Branch 1 taken 6668 times.
✗ Branch 2 not taken.
 6668 stack.emplace_back(i, r);
87 }
88 }
89 }
90
91
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 64 times.
 64 bool TochilinEHoarSortSimMerTBB::ProcessRange(std::vector<int> &arr, std::pair<int, int> range, int serial_cutoff,
92 std::vector<std::pair<int, int>> &next_ranges) {
93 const auto [left, right] = range;
94
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 64 times.
 64 if (left >= right) {
95 return false;
96 }
97
98 64 const int range_size = right - left + 1;
99
1/2
✓ Branch 0 taken 64 times.
✗ Branch 1 not taken.
 64 if (range_size <= serial_cutoff) {
100 64 QuickSortSequential(arr, left, right);
101 64 return false;
102 }
103
104 ✗ const auto [i, j] = Partition(arr, left, right);
105 ✗ if (left < j) {
106 ✗ next_ranges.emplace_back(left, j);
107 }
108 ✗ if (i < right) {
109 ✗ next_ranges.emplace_back(i, right);
110 }
111
112 return true;
113 }
114
115 80 void TochilinEHoarSortSimMerTBB::QuickSortParallel(std::vector<int> &arr, int low, int high, int serial_cutoff) {
116
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 64 times.
 80 if (low >= high) {
117 16 return;
118 }
119
120 64 std::vector<std::pair<int, int>> current_ranges;
121
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 current_ranges.emplace_back(low, high);
122
123
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 64 times.
 128 while (!current_ranges.empty()) {
124
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 tbb::enumerable_thread_specific<std::vector<std::pair<int, int>>> next_ranges_local;
125
126 64 tbb::parallel_for(tbb::blocked_range<std::size_t>(0, current_ranges.size()),
127
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 [&](const tbb::blocked_range<std::size_t> &range) {
128 64 auto &local_next = next_ranges_local.local();
129
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 64 times.
 128 for (std::size_t idx = range.begin(); idx != range.end(); ++idx) {
130 64 ProcessRange(arr, current_ranges[idx], serial_cutoff, local_next);
131 }
132 64 });
133
134 64 std::vector<std::pair<int, int>> next_ranges;
135 for (auto &local_ranges : next_ranges_local) {
136 64 next_ranges.insert(next_ranges.end(), local_ranges.begin(), local_ranges.end());
137 }
138 current_ranges = std::move(next_ranges);
139 64 }
140 }
141
142 ✗ int TochilinEHoarSortSimMerTBB::ResolveSerialCutoff(std::size_t size) {
143 const int concurrency = ResolveConcurrency();
144 40 const std::size_t per_worker = size / static_cast<std::size_t>(concurrency * 4);
145 40 return std::max(kMinSequentialCutoff, static_cast<int>(per_worker));
146 }
147
148 40 std::vector<int> TochilinEHoarSortSimMerTBB::MergeSortedVectors(const std::vector<int> &a, const std::vector<int> &b) {
149
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<int> result;
150
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 result.reserve(a.size() + b.size());
151
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::ranges::merge(a, b, std::back_inserter(result));
152 40 return result;
153 }
154
155
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 bool TochilinEHoarSortSimMerTBB::RunImpl() {
156 auto &data = GetOutput();
157
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 if (data.empty()) {
158 return false;
159 }
160
161 const tbb::global_control control(tbb::global_control::max_allowed_parallelism,
162 40 static_cast<std::size_t>(ResolveConcurrency()));
163
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 const auto mid = static_cast<std::vector<int>::difference_type>(data.size() / 2);
164
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 const int serial_cutoff = ResolveSerialCutoff(data.size());
165
166
2/4
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 40 times.
✗ Branch 5 not taken.
 40 std::vector<int> left(data.begin(), data.begin() + mid);
167
1/4
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 40 std::vector<int> right(data.begin() + mid, data.end());
168
169 40 tbb::parallel_invoke([&]() { QuickSortParallel(left, 0, static_cast<int>(left.size()) - 1, serial_cutoff); },
170
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 80 [&]() { QuickSortParallel(right, 0, static_cast<int>(right.size()) - 1, serial_cutoff); });
171
172
2/6
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 40 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 80 data = MergeSortedVectors(left, right);
173
174 return true;
175 }
176
177
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 bool TochilinEHoarSortSimMerTBB::PostProcessingImpl() {
178 40 return std::ranges::is_sorted(GetOutput());
179 }
180
181 } // namespace tochilin_e_hoar_sort_sim_mer
182