GCC Code Coverage Report

Directory: ./
File: tasks/karpich_i_bitwise_batcher/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 65 65 100.0%
Functions: 8 8 100.0%
Branches: 45 56 80.4%
Line Branch Exec Source
1 #include "karpich_i_bitwise_batcher/omp/include/ops_omp.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cstddef>
6 #include <cstdint>
7 #include <limits>
8 #include <random>
9 #include <utility>
10 #include <vector>
11
12 #include "karpich_i_bitwise_batcher/common/include/common.hpp"
13 #include "util/include/util.hpp"
14
15 namespace karpich_i_bitwise_batcher {
16
17 namespace {
18
19 constexpr int kBytesPerInt = 4;
20 constexpr int kBitsPerByte = 8;
21 constexpr int kRadixSize = 256;
22 constexpr uint32_t kSignBitMask = 0x80000000U;
23 constexpr uint32_t kByteMask = 0xFFU;
24
25 102 void RadixSortRange(std::vector<int> &arr, int lo, int hi) {
26 102 int n = hi - lo;
27
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 93 times.
 102 if (n <= 1) {
28 9 return;
29 }
30
31 93 std::vector<int> buf(n);
32
33
2/2
✓ Branch 0 taken 372 times.
✓ Branch 1 taken 93 times.
 465 for (int byte_idx = 0; byte_idx < kBytesPerInt; byte_idx++) {
34 372 int shift = byte_idx * kBitsPerByte;
35 372 std::array<int, kRadixSize> count{};
36
37
2/2
✓ Branch 0 taken 38856 times.
✓ Branch 1 taken 372 times.
 39228 for (int i = lo; i < hi; i++) {
38
2/2
✓ Branch 0 taken 9714 times.
✓ Branch 1 taken 29142 times.
 38856 auto val = static_cast<uint32_t>(arr[i]);
39
2/2
✓ Branch 0 taken 9714 times.
✓ Branch 1 taken 29142 times.
 38856 if (byte_idx == kBytesPerInt - 1) {
40 val ^= kSignBitMask;
41 }
42 38856 count.at((val >> shift) & kByteMask)++;
43 }
44
45 int prefix = 0;
46
2/2
✓ Branch 0 taken 95232 times.
✓ Branch 1 taken 372 times.
 95604 for (int &c : count) {
47 95232 int tmp = c;
48 95232 c = prefix;
49 95232 prefix += tmp;
50 }
51
52
2/2
✓ Branch 0 taken 38856 times.
✓ Branch 1 taken 372 times.
 39228 for (int i = lo; i < hi; i++) {
53
2/2
✓ Branch 0 taken 9714 times.
✓ Branch 1 taken 29142 times.
 38856 auto val = static_cast<uint32_t>(arr[i]);
54
2/2
✓ Branch 0 taken 9714 times.
✓ Branch 1 taken 29142 times.
 38856 if (byte_idx == kBytesPerInt - 1) {
55 val ^= kSignBitMask;
56 }
57
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 38856 times.
 38856 buf.at(count.at((val >> shift) & kByteMask)++) = arr[i];
58 }
59
60 372 std::copy(buf.begin(), buf.begin() + n, arr.begin() + lo);
61 }
62 }
63
64 86 void CompareExchange(std::vector<int> &data, int pos_a, int pos_b, int len) {
65 86 std::vector<int> merged(static_cast<size_t>(2) * len);
66 86 std::merge(data.begin() + pos_a, data.begin() + pos_a + len, data.begin() + pos_b, data.begin() + pos_b + len,
67 merged.begin());
68 86 std::copy(merged.begin(), merged.begin() + len, data.begin() + pos_a);
69
1/2
✓ Branch 0 taken 86 times.
✗ Branch 1 not taken.
 86 std::copy(merged.begin() + len, merged.end(), data.begin() + pos_b);
70 86 }
71
72 44 std::vector<std::pair<int, int>> BuildBatcherNetwork(int n) {
73 44 std::vector<std::pair<int, int>> net;
74
2/2
✓ Branch 0 taken 49 times.
✓ Branch 1 taken 44 times.
 93 for (int pw = 1; pw < n; pw *= 2) {
75
2/2
✓ Branch 0 taken 68 times.
✓ Branch 1 taken 49 times.
 117 for (int k = pw; k >= 1; k /= 2) {
76
2/2
✓ Branch 0 taken 77 times.
✓ Branch 1 taken 68 times.
 145 for (int j = k % pw; j <= n - 1 - k; j += 2 * k) {
77
2/2
✓ Branch 0 taken 86 times.
✓ Branch 1 taken 77 times.
 163 for (int i = 0; i < std::min(k, n - j - k); i++) {
78
1/2
✓ Branch 0 taken 86 times.
✗ Branch 1 not taken.
 86 if ((j + i) / (2 * pw) == (j + i + k) / (2 * pw)) {
79
1/4
✓ Branch 1 taken 86 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 86 net.emplace_back(j + i, j + i + k);
80 }
81 }
82 }
83 }
84 }
85 44 return net;
86 }
87
88 } // namespace
89
90 48 KarpichIBitwiseBatcherOMP::KarpichIBitwiseBatcherOMP(const InType &in) {
91 SetTypeOfTask(GetStaticTypeOfTask());
92 48 GetInput() = in;
93 GetOutput() = 0;
94 48 }
95
96 48 bool KarpichIBitwiseBatcherOMP::ValidationImpl() {
97
2/4
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 48 times.
 48 return GetInput() > 0 && GetOutput() == 0;
98 }
99
100 48 bool KarpichIBitwiseBatcherOMP::PreProcessingImpl() {
101 48 int n = GetInput();
102 48 data_.resize(n);
103 48 std::random_device rd;
104 48 std::mt19937 gen(rd());
105 std::uniform_int_distribution<int> dist(0, n);
106
2/2
✓ Branch 0 taken 9704 times.
✓ Branch 1 taken 48 times.
 9752 for (int i = 0; i < n; i++) {
107 9704 data_[i] = dist(gen);
108 }
109 48 return true;
110 }
111
112
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 4 times.
 48 bool KarpichIBitwiseBatcherOMP::RunImpl() {
113 48 int n = static_cast<int>(data_.size());
114
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 4 times.
 48 if (n <= 1) {
115 return true;
116 }
117
118 44 int num_thr = ppc::util::GetNumThreads();
119
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 41 times.
 44 if (num_thr > n) {
120 num_thr = 1;
121 }
122
123 44 int chunk = (n + num_thr - 1) / num_thr;
124 44 int padded = chunk * num_thr;
125 44 data_.resize(padded, std::numeric_limits<int>::max());
126
127 auto &data_ref = data_;
128 44 #pragma omp parallel for default(none) shared(data_ref, chunk, num_thr) num_threads(num_thr)
129 for (int tid = 0; tid < num_thr; tid++) {
130 RadixSortRange(data_ref, tid * chunk, (tid + 1) * chunk);
131 }
132
133 44 auto net = BuildBatcherNetwork(num_thr);
134
2/2
✓ Branch 0 taken 86 times.
✓ Branch 1 taken 44 times.
 130 for (auto &[a, b] : net) {
135
1/2
✓ Branch 1 taken 86 times.
✗ Branch 2 not taken.
 86 CompareExchange(data_, a * chunk, b * chunk, chunk);
136 }
137
138
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 44 data_.resize(n);
139 return true;
140 }
141
142 48 bool KarpichIBitwiseBatcherOMP::PostProcessingImpl() {
143
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 GetOutput() = GetInput();
144 48 return std::ranges::is_sorted(data_);
145 }
146
147 } // namespace karpich_i_bitwise_batcher
148