GCC Code Coverage Report

Directory: ./
File: tasks/karpich_i_bitwise_batcher/tbb/src/ops_tbb.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 86 87 98.9%
Functions: 9 9 100.0%
Branches: 68 100 68.0%
Line Branch Exec Source
1 #include "karpich_i_bitwise_batcher/tbb/include/ops_tbb.hpp"
2
3 #include <algorithm>
4 #include <random>
5 #include <utility>
6 #include <vector>
7
8 #include "karpich_i_bitwise_batcher/common/include/common.hpp"
9 #include "oneapi/tbb/parallel_for.h"
10 #include "oneapi/tbb/parallel_invoke.h"
11
12 namespace karpich_i_bitwise_batcher {
13
14 namespace {
15
16
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 40 times.
 160 void RadixSortPositive(std::vector<int> &arr) {
17 160 int n = static_cast<int>(arr.size());
18
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 40 times.
 160 if (n <= 1) {
19 40 return;
20 }
21
22 120 int max_val = *std::ranges::max_element(arr);
23
1/2
✓ Branch 0 taken 120 times.
✗ Branch 1 not taken.
 120 if (max_val == 0) {
24 return;
25 }
26
27 120 std::vector<int> buffer(n);
28
29
3/4
✓ Branch 0 taken 356 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 236 times.
✓ Branch 3 taken 120 times.
 356 for (int shift = 0; shift < 32 && (max_val >> shift) > 0; shift += 8) {
30
1/4
✓ Branch 1 taken 236 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 236 std::vector<int> count(256, 0);
31
2/2
✓ Branch 0 taken 19768 times.
✓ Branch 1 taken 236 times.
 20004 for (int i = 0; i < n; i++) {
32 19768 count[(arr[i] >> shift) & 0xFF]++;
33 }
34
2/2
✓ Branch 0 taken 60180 times.
✓ Branch 1 taken 236 times.
 60416 for (int i = 1; i < 256; i++) {
35 60180 count[i] += count[i - 1];
36 }
37
2/2
✓ Branch 0 taken 19768 times.
✓ Branch 1 taken 236 times.
 20004 for (int i = n - 1; i >= 0; i--) {
38 19768 buffer[--count[(arr[i] >> shift) & 0xFF]] = arr[i];
39 }
40
1/2
✓ Branch 1 taken 236 times.
✗ Branch 2 not taken.
 236 arr = buffer;
41 }
42 }
43
44
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 80 times.
 88 void RadixSort(std::vector<int> &arr) {
45 88 int n = static_cast<int>(arr.size());
46
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 80 times.
 88 if (n <= 1) {
47 8 return;
48 }
49
50 80 std::vector<int> negative;
51 80 std::vector<int> positive;
52
2/2
✓ Branch 0 taken 9920 times.
✓ Branch 1 taken 80 times.
 10000 for (int i = 0; i < n; i++) {
53
2/2
✓ Branch 0 taken 4840 times.
✓ Branch 1 taken 5080 times.
 9920 if (arr[i] < 0) {
54
1/4
✓ Branch 1 taken 4840 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 4840 negative.push_back(-arr[i]);
55 } else {
56 positive.push_back(arr[i]);
57 }
58 }
59
60
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 RadixSortPositive(positive);
61
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 RadixSortPositive(negative);
62
63 int idx = 0;
64
2/2
✓ Branch 0 taken 4840 times.
✓ Branch 1 taken 80 times.
 4920 for (int i = static_cast<int>(negative.size()) - 1; i >= 0; i--) {
65 4840 arr[idx++] = -negative[i];
66 }
67
2/2
✓ Branch 0 taken 5080 times.
✓ Branch 1 taken 80 times.
 5160 for (int x : positive) {
68 5080 arr[idx++] = x;
69 }
70 }
71
72 struct MergeTask {
73 int lo;
74 int hi;
75 int r;
76 };
77
78 44 std::vector<std::vector<std::pair<int, int>>> BuildMergeNetwork(int lo, int hi) {
79 44 std::vector<std::vector<std::pair<int, int>>> levels;
80
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 44 std::vector<MergeTask> current = {{lo, hi, 1}};
81
82
2/2
✓ Branch 0 taken 212 times.
✓ Branch 1 taken 44 times.
 256 while (!current.empty()) {
83 212 std::vector<MergeTask> next;
84 212 std::vector<std::pair<int, int>> comps;
85
86
2/2
✓ Branch 0 taken 9884 times.
✓ Branch 1 taken 212 times.
 10096 for (const auto &[tlo, thi, tr] : current) {
87 9884 int step = tr * 2;
88
2/2
✓ Branch 0 taken 4920 times.
✓ Branch 1 taken 4964 times.
 9884 if (step < thi - tlo) {
89
1/2
✓ Branch 1 taken 4920 times.
✗ Branch 2 not taken.
 4920 next.push_back({tlo, thi, step});
90
1/2
✓ Branch 1 taken 4920 times.
✗ Branch 2 not taken.
 4920 next.push_back({tlo + tr, thi, step});
91
2/2
✓ Branch 0 taken 37272 times.
✓ Branch 1 taken 4920 times.
 42192 for (int i = tlo + tr; i + tr <= thi; i += step) {
92
1/2
✓ Branch 1 taken 37272 times.
✗ Branch 2 not taken.
 37272 comps.emplace_back(i, i + tr);
93 }
94
1/2
✓ Branch 0 taken 4964 times.
✗ Branch 1 not taken.
 4964 } else if (tlo + tr <= thi) {
95
1/4
✓ Branch 1 taken 4964 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 4964 comps.emplace_back(tlo, tlo + tr);
96 }
97 }
98
99 levels.push_back(std::move(comps));
100 current = std::move(next);
101 }
102
103 44 return levels;
104 ✗ }
105
106 44 void BatcherMergeParallel(std::vector<int> &arr, int lo, int hi) {
107 44 auto levels = BuildMergeNetwork(lo, hi);
108
2/2
✓ Branch 0 taken 212 times.
✓ Branch 1 taken 44 times.
 256 for (int lvl = static_cast<int>(levels.size()) - 1; lvl >= 0; lvl--) {
109
1/2
✓ Branch 1 taken 212 times.
✗ Branch 2 not taken.
 212 const auto &level = levels[lvl];
110 212 int level_size = static_cast<int>(level.size());
111
1/2
✓ Branch 1 taken 212 times.
✗ Branch 2 not taken.
 212 tbb::parallel_for(0, level_size, [&arr, &level](int idx) {
112
2/2
✓ Branch 0 taken 21464 times.
✓ Branch 1 taken 20772 times.
 42236 auto [a, b] = level[idx];
113
2/2
✓ Branch 0 taken 21464 times.
✓ Branch 1 taken 20772 times.
 42236 if (arr[a] > arr[b]) {
114 std::swap(arr[a], arr[b]);
115 }
116 });
117 }
118 44 }
119
120 } // namespace
121
122 48 KarpichIBitwiseBatcherTBB::KarpichIBitwiseBatcherTBB(const InType &in) {
123 SetTypeOfTask(GetStaticTypeOfTask());
124 48 GetInput() = in;
125 GetOutput() = 0;
126 48 }
127
128 48 bool KarpichIBitwiseBatcherTBB::ValidationImpl() {
129 48 return GetInput() > 0;
130 }
131
132 48 bool KarpichIBitwiseBatcherTBB::PreProcessingImpl() {
133 48 int n = GetInput();
134 48 data_.resize(n);
135 48 std::mt19937 gen(static_cast<unsigned int>(n));
136 std::uniform_int_distribution<int> dist(-1000, 1000);
137
2/2
✓ Branch 0 taken 9704 times.
✓ Branch 1 taken 48 times.
 9752 for (int i = 0; i < n; i++) {
138 9704 data_[i] = dist(gen);
139 }
140 48 return true;
141 }
142
143
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 4 times.
 48 bool KarpichIBitwiseBatcherTBB::RunImpl() {
144 48 int n = static_cast<int>(data_.size());
145
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 4 times.
 48 if (n <= 1) {
146 return true;
147 }
148
149 int padded = 1;
150
2/2
✓ Branch 0 taken 212 times.
✓ Branch 1 taken 44 times.
 256 while (padded < n) {
151 212 padded *= 2;
152 }
153
154 44 int max_elem = *std::ranges::max_element(data_);
155 44 data_.resize(padded, max_elem);
156
157 44 int half = padded / 2;
158
1/2
✓ Branch 2 taken 44 times.
✗ Branch 3 not taken.
 44 std::vector<int> left(data_.begin(), data_.begin() + half);
159
1/4
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 44 std::vector<int> right(data_.begin() + half, data_.end());
160
161
2/6
✓ Branch 3 taken 44 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 44 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 176 tbb::parallel_invoke([&left]() { RadixSort(left); }, [&right]() { RadixSort(right); });
162
163 std::ranges::copy(left, data_.begin());
164 std::ranges::copy(right, data_.begin() + half);
165
166
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 44 BatcherMergeParallel(data_, 0, padded - 1);
167
168
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 44 data_.resize(n);
169 return true;
170 }
171
172 48 bool KarpichIBitwiseBatcherTBB::PostProcessingImpl() {
173 9704 for (int i = 1; std::cmp_less(i, data_.size()); i++) {
174
1/2
✓ Branch 0 taken 9656 times.
✗ Branch 1 not taken.
 9656 if (data_[i] < data_[i - 1]) {
175 return false;
176 }
177 }
178 48 GetOutput() = GetInput();
179 48 return true;
180 }
181
182 } // namespace karpich_i_bitwise_batcher
183