GCC Code Coverage Report

Directory: ./
File: tasks/sosnina_a_radix_simple_merge/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 87 90 96.7%
Functions: 10 10 100.0%
Branches: 55 74 74.3%
Line Branch Exec Source
1 #include "sosnina_a_radix_simple_merge/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cstddef>
6 #include <cstdint>
7 #include <thread>
8 #include <type_traits>
9 #include <utility>
10 #include <vector>
11
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 constexpr size_t kMinElementsPerPartSmall = 32768;
25 constexpr size_t kSmallArrayThreshold = 1'000'000;
26 constexpr size_t kLargeArrayThreshold = 20'000'000;
27
28 884 void RadixSortLSD(std::vector<int> &data, std::vector<int> &buffer) {
29 size_t idx = 0;
30
2/2
✓ Branch 0 taken 2618 times.
✓ Branch 1 taken 884 times.
 3502 for (int elem : data) {
31 2618 buffer[idx++] = static_cast<int>(static_cast<uint32_t>(elem) ^ kSignFlip);
32 }
33 std::swap(data, buffer);
34
35
2/2
✓ Branch 0 taken 3536 times.
✓ Branch 1 taken 884 times.
 4420 for (int pass = 0; pass < kNumPasses; ++pass) {
36 3536 std::array<int, kRadixSize + 1> count{};
37
38
2/2
✓ Branch 0 taken 10472 times.
✓ Branch 1 taken 3536 times.
 14008 for (auto elem : data) {
39 10472 auto digit = static_cast<uint8_t>((static_cast<uint32_t>(elem) >> (pass * kRadixBits)) & 0xFF);
40 10472 ++count.at(static_cast<size_t>(digit) + 1U);
41 }
42
43
2/2
✓ Branch 0 taken 905216 times.
✓ Branch 1 taken 3536 times.
 908752 for (int i = 1; i <= kRadixSize; ++i) {
44 905216 const auto ui = static_cast<size_t>(i);
45 905216 count.at(ui) += count.at(ui - 1U);
46 }
47
48
2/2
✓ Branch 0 taken 10472 times.
✓ Branch 1 taken 3536 times.
 14008 for (auto elem : data) {
49 10472 auto digit = static_cast<uint8_t>((static_cast<uint32_t>(elem) >> (pass * kRadixBits)) & 0xFF);
50 10472 const auto di = static_cast<size_t>(digit);
51 10472 const int write_pos = count.at(di)++;
52 10472 buffer[static_cast<size_t>(write_pos)] = elem;
53 }
54
55 std::swap(data, buffer);
56 }
57
58
2/2
✓ Branch 0 taken 2618 times.
✓ Branch 1 taken 884 times.
 3502 for (int &elem : data) {
59 2618 elem = static_cast<int>(static_cast<uint32_t>(elem) ^ kSignFlip);
60 }
61 884 }
62
63 void SimpleMerge(const std::vector<int> &left, const std::vector<int> &right, std::vector<int> &result) {
64 518 std::ranges::merge(left, right, result.begin());
65 }
66
67 /// Диапазон [begin, end) по индексам, до num_threads потоков (как грубый аналог parallel for).
68 template <typename F>
69 1432 void ParallelForRange(size_t begin, size_t end, int num_threads, F &&fn) {
70
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 716 times.
 1432 if (begin >= end) {
71 ✗ return;
72 }
73 1432 std::decay_t<F> func{std::forward<F>(fn)};
74
4/4
✓ Branch 0 taken 460 times.
✓ Branch 1 taken 256 times.
✓ Branch 2 taken 354 times.
✓ Branch 3 taken 362 times.
 2352 num_threads = std::max(1, std::min(num_threads, static_cast<int>(end - begin)));
75 1432 const size_t n = end - begin;
76 1432 const size_t chunk = (n + static_cast<size_t>(num_threads) - 1) / static_cast<size_t>(num_threads);
77 1432 std::vector<std::thread> threads;
78
2/2
✓ Branch 0 taken 1312 times.
✓ Branch 1 taken 716 times.
 4056 for (int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
79 2624 const size_t lo = begin + (static_cast<size_t>(thread_idx) * chunk);
80
1/2
✓ Branch 0 taken 1312 times.
✗ Branch 1 not taken.
 2624 if (lo >= end) {
81 break;
82 }
83
1/2
✓ Branch 1 taken 1312 times.
✗ Branch 2 not taken.
 2624 const size_t hi = std::min(end, lo + chunk);
84
1/2
✓ Branch 1 taken 1312 times.
✗ Branch 2 not taken.
 2624 threads.emplace_back([lo, hi, &func]() {
85
4/4
✓ Branch 0 taken 794 times.
✓ Branch 1 taken 794 times.
✓ Branch 2 taken 518 times.
✓ Branch 3 taken 518 times.
 2624 for (size_t i = lo; i < hi; ++i) {
86 1312 func(i);
87 }
88 });
89 }
90
2/2
✓ Branch 0 taken 1312 times.
✓ Branch 1 taken 716 times.
 4056 for (auto &th : threads) {
91
1/2
✓ Branch 1 taken 1312 times.
✗ Branch 2 not taken.
 2624 th.join();
92 }
93 1432 }
94
95 } // namespace
96
97
1/2
✓ Branch 1 taken 390 times.
✗ Branch 2 not taken.
 390 SosninaATestTaskSTL::SosninaATestTaskSTL(const InType &in) {
98 SetTypeOfTask(GetStaticTypeOfTask());
99
1/2
✓ Branch 1 taken 390 times.
✗ Branch 2 not taken.
 390 GetInput() = in;
100
1/2
✓ Branch 1 taken 390 times.
✗ Branch 2 not taken.
 390 GetOutput() = in;
101 390 }
102
103 390 bool SosninaATestTaskSTL::ValidationImpl() {
104 390 return !GetInput().empty();
105 }
106
107 390 bool SosninaATestTaskSTL::PreProcessingImpl() {
108 390 GetOutput() = GetInput();
109 390 return true;
110 }
111
112
2/2
✓ Branch 0 taken 366 times.
✓ Branch 1 taken 24 times.
 390 bool SosninaATestTaskSTL::RunImpl() {
113 std::vector<int> &data = GetOutput();
114
2/2
✓ Branch 0 taken 366 times.
✓ Branch 1 taken 24 times.
 390 if (data.size() <= 1) {
115 return true;
116 }
117
118
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 366 times.
 366 const int num_threads = ppc::util::GetNumThreads();
119 const size_t per_thread_floor = data.size() >= kLargeArrayThreshold
120
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 366 times.
 366 ? (data.size() / static_cast<size_t>(std::max(1, num_threads)))
121 366 : (data.size() / static_cast<size_t>(std::max(1, 2 * num_threads)));
122 366 size_t min_chunk_base = kMinElementsPerPart;
123
1/2
✓ Branch 0 taken 366 times.
✗ Branch 1 not taken.
 366 if (data.size() < kMinElementsPerPartSmall) {
124 366 min_chunk_base = std::max(size_t{1}, data.size() / static_cast<size_t>(std::max(1, 2 * num_threads)));
125 ✗ } else if (data.size() < kSmallArrayThreshold) {
126 ✗ min_chunk_base = kMinElementsPerPartSmall;
127 }
128 const size_t min_chunk = std::max(min_chunk_base, per_thread_floor);
129 366 const int max_parts_by_grain = std::max(1, static_cast<int>(data.size() / min_chunk));
130 366 const int num_parts = std::min({num_threads, static_cast<int>(data.size()), max_parts_by_grain});
131
132
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 276 times.
 366 if (num_parts <= 1) {
133 90 std::vector<int> buffer(data.size());
134 90 RadixSortLSD(data, buffer);
135 return std::ranges::is_sorted(data);
136 }
137
138 276 std::vector<std::vector<int>> parts(static_cast<size_t>(num_parts));
139 276 const size_t base_size = data.size() / static_cast<size_t>(num_parts);
140 276 const size_t remainder = data.size() % static_cast<size_t>(num_parts);
141 size_t pos = 0;
142
143
2/2
✓ Branch 0 taken 794 times.
✓ Branch 1 taken 276 times.
 1070 for (int i = 0; i < num_parts; ++i) {
144 794 const size_t part_size = base_size + (std::cmp_less(i, remainder) ? 1U : 0U);
145
1/2
✓ Branch 1 taken 794 times.
✗ Branch 2 not taken.
 794 parts[static_cast<size_t>(i)].assign(data.begin() + static_cast<std::ptrdiff_t>(pos),
146
1/2
✓ Branch 1 taken 794 times.
✗ Branch 2 not taken.
 794 data.begin() + static_cast<std::ptrdiff_t>(pos + part_size));
147 pos += part_size;
148 }
149
150
1/2
✓ Branch 1 taken 276 times.
✗ Branch 2 not taken.
 276 ParallelForRange(0, static_cast<size_t>(num_parts), num_threads, [&](size_t i) {
151 794 auto &part = parts[i];
152 794 std::vector<int> buffer(part.size());
153 794 RadixSortLSD(part, buffer);
154 794 });
155
156 std::vector<std::vector<int>> current = std::move(parts);
157
2/2
✓ Branch 0 taken 440 times.
✓ Branch 1 taken 276 times.
 716 while (current.size() > 1) {
158 440 const size_t half = (current.size() + 1) / 2;
159
2/4
✓ Branch 1 taken 440 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 440 times.
✗ Branch 5 not taken.
 440 std::vector<std::vector<int>> next(half);
160
161 440 const size_t pair_count = current.size() / 2;
162
3/4
✓ Branch 1 taken 440 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 86 times.
✓ Branch 4 taken 354 times.
 440 ParallelForRange(0, pair_count, num_threads, [&](size_t idx) {
163 518 auto &left = current[2 * idx];
164 auto &right = current[(2 * idx) + 1];
165 518 next[idx].resize(left.size() + right.size());
166 518 SimpleMerge(left, right, next[idx]);
167 std::vector<int>().swap(left);
168 std::vector<int>().swap(right);
169 518 });
170
2/2
✓ Branch 0 taken 86 times.
✓ Branch 1 taken 354 times.
 440 if (current.size() % 2 == 1) {
171 86 next[half - 1] = std::move(current.back());
172 }
173 440 current = std::move(next);
174 440 }
175
176 data = std::move(current[0]);
177 return std::ranges::is_sorted(data);
178 276 }
179
180 390 bool SosninaATestTaskSTL::PostProcessingImpl() {
181 390 return !GetOutput().empty();
182 }
183
184 } // namespace sosnina_a_radix_simple_merge
185