GCC Code Coverage Report

Directory: ./
File: tasks/akimov_i_radixsort_int_merge/tbb/src/ops_tbb.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 69 70 98.6%
Functions: 9 9 100.0%
Branches: 43 54 79.6%
Line Branch Exec Source
1 #include "akimov_i_radixsort_int_merge/tbb/include/ops_tbb.hpp"
2
3 #include <oneapi/tbb/parallel_for.h>
4 #include <tbb/tbb.h>
5
6 #include <algorithm>
7 #include <array>
8 #include <cstddef>
9 #include <cstdint>
10 #include <iterator>
11 #include <vector>
12
13 #include "akimov_i_radixsort_int_merge/common/include/common.hpp"
14 #include "util/include/util.hpp"
15
16 namespace akimov_i_radixsort_int_merge {
17
18 namespace {
19 72 void CountingSortStep(std::vector<int>::iterator in_begin, std::vector<int>::iterator in_end,
20 std::vector<int>::iterator out_begin, size_t byte_index) {
21 72 size_t shift = byte_index * 8;
22 72 std::array<size_t, 256> count = {0};
23
24
2/2
✓ Branch 0 taken 17760 times.
✓ Branch 1 taken 72 times.
 17832 for (auto it = in_begin; it != in_end; ++it) {
25 17760 auto raw_val = static_cast<unsigned int>(*it);
26 17760 unsigned int byte_val = (raw_val >> shift) & 0xFF;
27
28
2/2
✓ Branch 0 taken 4440 times.
✓ Branch 1 taken 13320 times.
 17760 if (byte_index == sizeof(int) - 1) {
29 4440 byte_val ^= 128;
30 }
31 17760 count.at(byte_val)++;
32 }
33
34 72 std::array<size_t, 256> prefix{};
35 prefix[0] = 0;
36
2/2
✓ Branch 0 taken 18360 times.
✓ Branch 1 taken 72 times.
 18432 for (int i = 1; i < 256; ++i) {
37 18360 prefix.at(i) = prefix.at(i - 1) + count.at(i - 1);
38 }
39
40
2/2
✓ Branch 0 taken 17760 times.
✓ Branch 1 taken 72 times.
 17832 for (auto it = in_begin; it != in_end; ++it) {
41 17760 auto raw_val = static_cast<unsigned int>(*it);
42 17760 unsigned int byte_val = (raw_val >> shift) & 0xFF;
43
44
2/2
✓ Branch 0 taken 4440 times.
✓ Branch 1 taken 13320 times.
 17760 if (byte_index == sizeof(int) - 1) {
45 4440 byte_val ^= 128;
46 }
47
48 17760 *(out_begin + static_cast<int64_t>(prefix.at(byte_val))) = *it;
49 17760 prefix.at(byte_val)++;
50 }
51 72 }
52
53
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
 18 void RadixSortLocal(std::vector<int>::iterator begin, std::vector<int>::iterator end) {
54 18 size_t n = std::distance(begin, end);
55
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
 18 if (n < 2) {
56 ✗ return;
57 }
58
59 18 std::vector<int> temp(n);
60
61
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 18 times.
 90 for (size_t i = 0; i < sizeof(int); ++i) {
62
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 36 times.
 72 if (i % 2 == 0) {
63 36 CountingSortStep(begin, end, temp.begin(), i);
64 } else {
65 36 CountingSortStep(temp.begin(), temp.end(), begin, i);
66 }
67 }
68 }
69 } // namespace
70
71
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 AkimovIRadixSortIntMergeTBB::AkimovIRadixSortIntMergeTBB(const InType &in) {
72 SetTypeOfTask(GetStaticTypeOfTask());
73
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GetInput() = in;
74 12 GetOutput() = OutType();
75 12 }
76
77 12 bool AkimovIRadixSortIntMergeTBB::ValidationImpl() {
78 12 return !GetInput().empty();
79 }
80
81 12 bool AkimovIRadixSortIntMergeTBB::PreProcessingImpl() {
82 12 GetOutput() = GetInput();
83 12 return true;
84 }
85
86
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 bool AkimovIRadixSortIntMergeTBB::RunImpl() {
87 auto &arr = GetOutput();
88 12 int n = static_cast<int>(arr.size());
89
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (n == 0) {
90 return true;
91 }
92
93 12 int num_threads = ppc::util::GetNumThreads();
94
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 5 times.
 12 if (n < num_threads * 100) {
95 7 num_threads = 1;
96 }
97
98
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 3 times.
 12 if (num_threads == 1) {
99 9 RadixSortLocal(arr.begin(), arr.end());
100 9 return true;
101 }
102
103 // Разбиваем массив на блоки
104 3 std::vector<int> offsets(num_threads + 1);
105 3 int chunk = n / num_threads;
106 3 int rem = n % num_threads;
107 int curr = 0;
108
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 3 times.
 12 for (int i = 0; i < num_threads; ++i) {
109
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 1 times.
 9 offsets[i] = curr;
110
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 1 times.
 17 curr += chunk + (i < rem ? 1 : 0);
111 }
112
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 offsets[num_threads] = n;
113
114 // Параллельная сортировка блоков
115
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 tbb::parallel_for(0, num_threads, [&](int i) {
116 9 auto begin = arr.begin() + offsets[i];
117 9 auto end = arr.begin() + offsets[i + 1];
118 9 RadixSortLocal(begin, end);
119 9 });
120
121 // Слияние блоков
122
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 3 times.
 8 for (int step = 1; step < num_threads; step *= 2) {
123
1/4
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 5 tbb::parallel_for(0, num_threads, [&](int i) {
124
4/4
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 9 times.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 1 times.
 16 if (i % (2 * step) == 0 && i + step < num_threads) {
125
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 5 times.
 6 auto begin = arr.begin() + offsets[i];
126 6 auto middle = arr.begin() + offsets[i + step];
127
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 5 times.
 6 int end_idx = std::min(i + (2 * step), num_threads);
128 6 auto end = arr.begin() + offsets[end_idx];
129 6 std::inplace_merge(begin, middle, end);
130 }
131 16 });
132 }
133
134 return true;
135 }
136
137 12 bool AkimovIRadixSortIntMergeTBB::PostProcessingImpl() {
138 12 return true;
139 }
140
141 } // namespace akimov_i_radixsort_int_merge
142