GCC Code Coverage Report

Directory: ./
File: tasks/golovanov_d_radix_merge/tbb/src/radix_sort_tbb.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 68 71 95.8%
Functions: 5 5 100.0%
Branches: 58 76 76.3%
Line Branch Exec Source
1 #include "../include/radix_sort_tbb.hpp"
2
3 #include <tbb/blocked_range.h>
4 #include <tbb/global_control.h>
5 #include <tbb/parallel_for.h>
6
7 #include <array>
8 #include <cstddef>
9 #include <cstdint>
10 #include <cstring>
11 #include <utility>
12 #include <vector>
13
14 #include "util/include/util.hpp"
15
16 namespace {
17 constexpr int kBytes = 8;
18 constexpr std::size_t kRadix = 256;
19 constexpr std::uint64_t kSignMask = 1ULL << 63;
20 constexpr std::uint64_t kByteMask = 0xFFULL;
21
22 std::uint64_t ToSortable(std::uint64_t bits) {
23
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 44 times.
 72 return ((bits & kSignMask) != 0U) ? ~bits : (bits ^ kSignMask);
24 }
25
26 std::uint64_t FromSortable(std::uint64_t bits) {
27 72 return ((bits & kSignMask) != 0U) ? (bits ^ kSignMask) : ~bits;
28 }
29 } // namespace
30
31 30 void RadixSortTBB::SortRange(std::vector<double> &arr, std::size_t left, std::size_t right) {
32
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 30 times.
 30 if (right <= left) {
33 ✗ return;
34 }
35
36 30 std::size_t n = right - left;
37 30 std::vector<std::uint64_t> data(n);
38
39
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 30 times.
 102 for (std::size_t i = 0; i < n; ++i) {
40 std::uint64_t bits = 0;
41
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 44 times.
 72 std::memcpy(&bits, &arr[left + i], sizeof(double));
42 72 data[i] = ToSortable(bits);
43 }
44
45
1/4
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 30 std::vector<std::uint64_t> buffer(n);
46
47
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 30 times.
 270 for (int byte = 0; byte < kBytes; ++byte) {
48 240 std::array<std::size_t, kRadix> count{};
49
50
2/2
✓ Branch 0 taken 576 times.
✓ Branch 1 taken 240 times.
 816 for (std::size_t i = 0; i < n; ++i) {
51 576 auto b = static_cast<std::size_t>((data[i] >> (byte * 8)) & kByteMask);
52 576 ++count.at(b);
53 }
54
55 std::size_t sum = 0;
56
2/2
✓ Branch 0 taken 61440 times.
✓ Branch 1 taken 240 times.
 61680 for (std::size_t i = 0; i < kRadix; ++i) {
57 61440 std::size_t tmp = count.at(i);
58 61440 count.at(i) = sum;
59 61440 sum += tmp;
60 }
61
62
2/2
✓ Branch 0 taken 576 times.
✓ Branch 1 taken 240 times.
 816 for (std::size_t i = 0; i < n; ++i) {
63 576 auto b = static_cast<std::size_t>((data[i] >> (byte * 8)) & kByteMask);
64 576 buffer[count.at(b)++] = data[i];
65 }
66
67 data.swap(buffer);
68 }
69
70
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 30 times.
 102 for (std::size_t i = 0; i < n; ++i) {
71
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 28 times.
 72 std::uint64_t bits = FromSortable(data[i]);
72 72 std::memcpy(&arr[left + i], &bits, sizeof(double));
73 }
74 }
75
76 18 std::vector<double> RadixSortTBB::Merge(const std::vector<double> &a, const std::vector<double> &b) {
77
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 std::vector<double> result;
78
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 result.reserve(a.size() + b.size());
79
80 std::size_t i = 0;
81 std::size_t j = 0;
82
83
4/4
✓ Branch 0 taken 67 times.
✓ Branch 1 taken 9 times.
✓ Branch 2 taken 9 times.
✓ Branch 3 taken 58 times.
 76 while (i < a.size() && j < b.size()) {
84
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 22 times.
 58 if (a[i] <= b[j]) {
85 result.push_back(a[i]);
86 36 ++i;
87 } else {
88 result.push_back(b[j]);
89 22 ++j;
90 }
91 }
92
93
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 18 times.
 33 while (i < a.size()) {
94 result.push_back(a[i]);
95 15 ++i;
96 }
97
98
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 18 times.
 30 while (j < b.size()) {
99 result.push_back(b[j]);
100 12 ++j;
101 }
102
103 18 return result;
104 }
105
106
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 void RadixSortTBB::Sort(std::vector<double> &arr) {
107
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (arr.empty()) {
108 ✗ return;
109 }
110
111 12 int num_threads = ppc::util::GetNumThreads();
112 12 if (num_threads <= 0) {
113 num_threads = 1;
114 }
115
116
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (static_cast<std::size_t>(num_threads) > arr.size()) {
117 ✗ num_threads = static_cast<int>(arr.size());
118 }
119
120 12 tbb::global_control control(tbb::global_control::max_allowed_parallelism, num_threads);
121
122
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 std::vector<std::pair<std::size_t, std::size_t>> ranges(num_threads);
123
124 12 std::size_t base = arr.size() / static_cast<std::size_t>(num_threads);
125 12 std::size_t rem = arr.size() % static_cast<std::size_t>(num_threads);
126
127 std::size_t begin = 0;
128
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 12 times.
 42 for (std::size_t i = 0; i < ranges.size(); ++i) {
129
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 11 times.
 30 std::size_t block_size = base + (i < rem ? 1 : 0);
130 30 ranges[i] = {begin, begin + block_size};
131 begin += block_size;
132 }
133
134
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 42 tbb::parallel_for(tbb::blocked_range<std::size_t>(0, ranges.size()), [&](const tbb::blocked_range<std::size_t> &r) {
135
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 30 times.
 60 for (std::size_t i = r.begin(); i < r.end(); ++i) {
136 30 SortRange(arr, ranges[i].first, ranges[i].second);
137 }
138 30 });
139
140
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<std::vector<double>> parts(num_threads);
141
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 12 times.
 42 for (int i = 0; i < num_threads; ++i) {
142
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 parts[i] = std::vector<double>(arr.begin() + static_cast<std::ptrdiff_t>(ranges[i].first),
143
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 60 arr.begin() + static_cast<std::ptrdiff_t>(ranges[i].second));
144 }
145
146
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 12 times.
 27 while (parts.size() > 1) {
147 15 std::size_t pair_count = parts.size() / 2;
148
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 std::vector<std::vector<double>> next((parts.size() + 1) / 2);
149
150
3/4
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 12 times.
 33 tbb::parallel_for(tbb::blocked_range<std::size_t>(0, pair_count), [&](const tbb::blocked_range<std::size_t> &r) {
151
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 18 times.
 36 for (std::size_t i = r.begin(); i < r.end(); ++i) {
152 36 next[i] = Merge(parts[2 * i], parts[(2 * i) + 1]);
153 }
154 18 });
155
156
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 12 times.
 15 if (parts.size() % 2 != 0) {
157 next.back() = std::move(parts.back());
158 }
159
160 15 parts = std::move(next);
161 15 }
162
163 arr = std::move(parts[0]);
164 12 }
165