GCC Code Coverage Report

Directory: ./
File: tasks/sosnina_a_radix_simple_merge/tbb/src/ops_tbb.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 41 67 61.2%
Functions: 6 8 75.0%
Branches: 23 50 46.0%
Line Branch Exec Source
1 #include "sosnina_a_radix_simple_merge/tbb/include/ops_tbb.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cstddef>
6 #include <cstdint>
7 #include <utility>
8 #include <vector>
9
10 #include "oneapi/tbb/parallel_for.h"
11 #include "oneapi/tbb/partitioner.h"
12 #include "sosnina_a_radix_simple_merge/common/include/common.hpp"
13 #include "util/include/util.hpp"
14
15 namespace sosnina_a_radix_simple_merge {
16
17 namespace {
18
19 constexpr int kRadixBits = 8;
20 constexpr int kRadixSize = 1 << kRadixBits;
21 constexpr int kNumPasses = sizeof(int) / sizeof(uint8_t);
22 constexpr uint32_t kSignFlip = 0x80000000U;
23 constexpr size_t kMinElementsPerPart = 4096;
24 /// На n < порога — крупнее части, меньше уровней merge (лучше E на малых входах).
25 constexpr size_t kMinElementsPerPartSmall = 32768;
26 constexpr size_t kSmallArrayThreshold = 1'000'000;
27 /// От этого размера — «крупный» вход: целимся в ~не больше одной части на поток, глубже merge дороже.
28 constexpr size_t kLargeArrayThreshold = 20'000'000;
29
30 186 void RadixSortLSD(std::vector<int> &data, std::vector<int> &buffer) {
31 size_t idx = 0;
32
2/2
✓ Branch 0 taken 1322 times.
✓ Branch 1 taken 186 times.
 1508 for (int elem : data) {
33 1322 buffer[idx++] = static_cast<int>(static_cast<uint32_t>(elem) ^ kSignFlip);
34 }
35 std::swap(data, buffer);
36
37
2/2
✓ Branch 0 taken 744 times.
✓ Branch 1 taken 186 times.
 930 for (int pass = 0; pass < kNumPasses; ++pass) {
38 744 std::array<int, kRadixSize + 1> count{};
39
40
2/2
✓ Branch 0 taken 5288 times.
✓ Branch 1 taken 744 times.
 6032 for (auto elem : data) {
41 5288 auto digit = static_cast<uint8_t>((static_cast<uint32_t>(elem) >> (pass * kRadixBits)) & 0xFF);
42 5288 ++count.at(static_cast<size_t>(digit) + 1U);
43 }
44
45
2/2
✓ Branch 0 taken 190464 times.
✓ Branch 1 taken 744 times.
 191208 for (int i = 1; i <= kRadixSize; ++i) {
46 190464 const auto ui = static_cast<size_t>(i);
47 190464 count.at(ui) += count.at(ui - 1U);
48 }
49
50
2/2
✓ Branch 0 taken 5288 times.
✓ Branch 1 taken 744 times.
 6032 for (auto elem : data) {
51 5288 auto digit = static_cast<uint8_t>((static_cast<uint32_t>(elem) >> (pass * kRadixBits)) & 0xFF);
52 5288 const auto di = static_cast<size_t>(digit);
53 5288 const int write_pos = count.at(di)++;
54 5288 buffer[static_cast<size_t>(write_pos)] = elem;
55 }
56
57 std::swap(data, buffer);
58 }
59
60
2/2
✓ Branch 0 taken 1322 times.
✓ Branch 1 taken 186 times.
 1508 for (int &elem : data) {
61 1322 elem = static_cast<int>(static_cast<uint32_t>(elem) ^ kSignFlip);
62 }
63 186 }
64
65 void SimpleMerge(const std::vector<int> &left, const std::vector<int> &right, std::vector<int> &result) {
66 ✗ std::ranges::merge(left, right, result.begin());
67 }
68
69 } // namespace
70
71
1/2
✓ Branch 1 taken 198 times.
✗ Branch 2 not taken.
 198 SosninaATestTaskTBB::SosninaATestTaskTBB(const InType &in) {
72 SetTypeOfTask(GetStaticTypeOfTask());
73
1/2
✓ Branch 1 taken 198 times.
✗ Branch 2 not taken.
 198 GetInput() = in;
74
1/2
✓ Branch 1 taken 198 times.
✗ Branch 2 not taken.
 198 GetOutput() = in;
75 198 }
76
77 198 bool SosninaATestTaskTBB::ValidationImpl() {
78 198 return !GetInput().empty();
79 }
80
81 198 bool SosninaATestTaskTBB::PreProcessingImpl() {
82 198 GetOutput() = GetInput();
83 198 return true;
84 }
85
86
2/2
✓ Branch 0 taken 186 times.
✓ Branch 1 taken 12 times.
 198 bool SosninaATestTaskTBB::RunImpl() {
87 std::vector<int> &data = GetOutput();
88
2/2
✓ Branch 0 taken 186 times.
✓ Branch 1 taken 12 times.
 198 if (data.size() <= 1) {
89 return true;
90 }
91
92
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 186 times.
 186 const int num_threads = ppc::util::GetNumThreads();
93
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 186 times.
 186 const size_t min_chunk_base = (data.size() < kSmallArrayThreshold) ? kMinElementsPerPartSmall : kMinElementsPerPart;
94 // На больших массивах — не мельче ~ n/T (меньше лишних уровней merge, толще radix-куски).
95 // На малых — оставляем запас n/(2T), чтобы не раздувать число частей.
96 const size_t per_thread_floor = data.size() >= kLargeArrayThreshold
97
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 186 times.
 186 ? (data.size() / static_cast<size_t>(std::max(1, num_threads)))
98 186 : (data.size() / static_cast<size_t>(std::max(1, 2 * num_threads)));
99 const size_t min_chunk = std::max(min_chunk_base, per_thread_floor);
100 186 const int max_parts_by_grain = std::max(1, static_cast<int>(data.size() / min_chunk));
101 186 const int num_parts = std::min({num_threads, static_cast<int>(data.size()), max_parts_by_grain});
102
103
1/2
✓ Branch 0 taken 186 times.
✗ Branch 1 not taken.
 186 if (num_parts <= 1) {
104 186 std::vector<int> buffer(data.size());
105 186 RadixSortLSD(data, buffer);
106 return std::ranges::is_sorted(data);
107 }
108
109 ✗ std::vector<std::vector<int>> parts(static_cast<size_t>(num_parts));
110 ✗ const size_t base_size = data.size() / static_cast<size_t>(num_parts);
111 ✗ const size_t remainder = data.size() % static_cast<size_t>(num_parts);
112 size_t pos = 0;
113
114 ✗ for (int i = 0; i < num_parts; ++i) {
115 ✗ const size_t part_size = base_size + (std::cmp_less(i, remainder) ? 1U : 0U);
116 ✗ parts[static_cast<size_t>(i)].assign(data.begin() + static_cast<std::ptrdiff_t>(pos),
117 ✗ data.begin() + static_cast<std::ptrdiff_t>(pos + part_size));
118 pos += part_size;
119 }
120
121 ✗ tbb::parallel_for(0, num_parts, [&](int i) {
122 ✗ std::vector<int> buffer(parts[static_cast<size_t>(i)].size());
123 ✗ RadixSortLSD(parts[static_cast<size_t>(i)], buffer);
124 ✗ }, tbb::simple_partitioner{});
125
126 std::vector<std::vector<int>> current = std::move(parts);
127 ✗ while (current.size() > 1) {
128 ✗ const size_t half = (current.size() + 1) / 2;
129 ✗ std::vector<std::vector<int>> next(half);
130
131 ✗ const size_t pair_count = current.size() / 2;
132 ✗ tbb::parallel_for(static_cast<size_t>(0), pair_count, [&](size_t idx) {
133 ✗ std::vector<int> &left = current[2 * idx];
134 std::vector<int> &right = current[(2 * idx) + 1];
135 ✗ next[idx].resize(left.size() + right.size());
136 ✗ SimpleMerge(left, right, next[idx]);
137 std::vector<int>().swap(left);
138 std::vector<int>().swap(right);
139 ✗ }, tbb::simple_partitioner{});
140 ✗ if (current.size() % 2 == 1) {
141 ✗ next[half - 1] = std::move(current.back());
142 }
143 ✗ current = std::move(next);
144 ✗ }
145
146 data = std::move(current[0]);
147 return std::ranges::is_sorted(data);
148 ✗ }
149
150 198 bool SosninaATestTaskTBB::PostProcessingImpl() {
151 198 return !GetOutput().empty();
152 }
153
154 } // namespace sosnina_a_radix_simple_merge
155