GCC Code Coverage Report

Directory: ./
File: tasks/dorofeev_i_bitwise_sort_double_eo_batcher_merge/tbb/src/ops_tbb.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 80 81 98.8%
Functions: 12 12 100.0%
Branches: 62 80 77.5%
Line Branch Exec Source
1 #include "dorofeev_i_bitwise_sort_double_eo_batcher_merge/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/tbb.h>
4
5 #include <algorithm>
6 #include <cstdint>
7 #include <cstring>
8 #include <limits>
9 #include <utility>
10 #include <vector>
11
12 #include "dorofeev_i_bitwise_sort_double_eo_batcher_merge/common/include/common.hpp"
13 #include "util/include/util.hpp"
14
15 namespace dorofeev_i_bitwise_sort_double_eo_batcher_merge {
16
17 namespace {
18
19 uint64_t DoubleToUint(double d) {
20 uint64_t u = 0;
21 std::memcpy(&u, &d, sizeof(double));
22
2/2
✓ Branch 0 taken 2492 times.
✓ Branch 1 taken 3204 times.
 5696 if ((u & 0x8000000000000000ULL) != 0) {
23 2492 u = ~u;
24 } else {
25 3204 u |= 0x8000000000000000ULL;
26 }
27 return u;
28 }
29
30 double UintToDouble(uint64_t u) {
31 5696 if ((u & 0x8000000000000000ULL) != 0) {
32 3204 u &= ~0x8000000000000000ULL;
33 } else {
34 2492 u = ~u;
35 }
36 double d = 0.0;
37 std::memcpy(&d, &u, sizeof(double));
38 return d;
39 }
40
41
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 36 times.
 36 void RadixSortDouble(std::vector<double> &arr) {
42
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 36 times.
 36 if (arr.empty()) {
43 ✗ return;
44 }
45
46 36 std::vector<uint64_t> uarr(arr.size());
47
2/2
✓ Branch 0 taken 5696 times.
✓ Branch 1 taken 36 times.
 5732 for (size_t i = 0; i < arr.size(); ++i) {
48
2/2
✓ Branch 0 taken 2492 times.
✓ Branch 1 taken 3204 times.
 11392 uarr[i] = DoubleToUint(arr[i]);
49 }
50
51
1/4
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 36 std::vector<uint64_t> temp(uarr.size());
52
2/2
✓ Branch 0 taken 288 times.
✓ Branch 1 taken 36 times.
 324 for (size_t byte = 0; byte < 8; ++byte) {
53
1/4
✓ Branch 1 taken 288 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 288 std::vector<int> count(256, 0);
54
2/2
✓ Branch 0 taken 45568 times.
✓ Branch 1 taken 288 times.
 45856 for (uint64_t val : uarr) {
55 45568 count[(val >> (byte * 8)) & 0xFF]++;
56 }
57
2/2
✓ Branch 0 taken 73440 times.
✓ Branch 1 taken 288 times.
 73728 for (size_t i = 1; i < 256; ++i) {
58 73440 count[i] += count[i - 1];
59 }
60
2/2
✓ Branch 0 taken 45568 times.
✓ Branch 1 taken 288 times.
 45856 for (int i = static_cast<int>(uarr.size()) - 1; i >= 0; --i) {
61 45568 temp[--count[(uarr[i] >> (byte * 8)) & 0xFF]] = uarr[i];
62 }
63
1/2
✓ Branch 1 taken 288 times.
✗ Branch 2 not taken.
 288 uarr = temp;
64 }
65
66
2/2
✓ Branch 0 taken 5696 times.
✓ Branch 1 taken 36 times.
 5732 for (size_t i = 0; i < arr.size(); ++i) {
67
2/2
✓ Branch 0 taken 3204 times.
✓ Branch 1 taken 2492 times.
 11392 arr[i] = UintToDouble(uarr[i]);
68 }
69 }
70
71 void CompareExchangeBlocks(double *arr, size_t i, size_t step) {
72
4/4
✓ Branch 0 taken 2848 times.
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 20108 times.
✓ Branch 3 taken 5539 times.
 28515 for (size_t k = 0; k < step; ++k) {
73
4/4
✓ Branch 0 taken 371 times.
✓ Branch 1 taken 2477 times.
✓ Branch 2 taken 10172 times.
✓ Branch 3 taken 9936 times.
 22956 if (arr[i + k] > arr[i + k + step]) {
74 std::swap(arr[i + k], arr[i + k + step]);
75 }
76 }
77 }
78
79 20 void OddEvenMergeIterative(double *arr, size_t start, size_t n) {
80
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (n <= 1) {
81 return;
82 }
83
84 20 size_t step = n / 2;
85 CompareExchangeBlocks(arr, start, step);
86
87 20 step /= 2;
88
2/2
✓ Branch 0 taken 117 times.
✓ Branch 1 taken 20 times.
 137 for (; step > 0; step /= 2) {
89
2/2
✓ Branch 0 taken 5539 times.
✓ Branch 1 taken 117 times.
 5656 for (size_t i = step; i < n - step; i += step * 2) {
90 5539 CompareExchangeBlocks(arr, start + i, step);
91 }
92 }
93 }
94
95 // Вынесли обработку отдельного чанка, чтобы снизить когнитивную сложность
96 36 void ProcessChunkTBB(double *raw_data, int chunk_idx, size_t chunk_size) {
97 36 size_t start_idx = static_cast<size_t>(chunk_idx) * chunk_size;
98
99 36 std::vector<double> local_arr(chunk_size);
100 double *local_raw = local_arr.data();
101
102
2/2
✓ Branch 0 taken 5696 times.
✓ Branch 1 taken 36 times.
 5732 for (size_t j = 0; j < chunk_size; ++j) {
103 5696 local_raw[j] = raw_data[start_idx + j];
104 }
105
106
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 RadixSortDouble(local_arr);
107
108
2/2
✓ Branch 0 taken 5696 times.
✓ Branch 1 taken 36 times.
 5732 for (size_t j = 0; j < chunk_size; ++j) {
109 5696 raw_data[start_idx + j] = local_raw[j];
110 }
111 36 }
112
113 // Вынесли всю логику TBB арены в отдельную функцию
114
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 void ExecuteTBBSort(double *raw_data, size_t pow2, size_t chunk_size, int num_chunks_int, int num_threads) {
115 tbb::task_arena arena(num_threads);
116
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 arena.execute([&]() {
117 // 1. Параллельно сортируем каждый блок
118 52 tbb::parallel_for(tbb::blocked_range<int>(0, num_chunks_int), [&](const tbb::blocked_range<int> &r) {
119
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 36 times.
 72 for (int i = r.begin(); i != r.end(); ++i) {
120 36 ProcessChunkTBB(raw_data, i, chunk_size);
121 }
122 36 });
123
124 // 2. Собираем отсортированные блоки вместе (Параллельное дерево слияния Бэтчера)
125
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 for (size_t size = chunk_size; size < pow2; size *= 2) {
126 16 int merges_count = static_cast<int>(pow2 / (size * 2));
127
128 36 tbb::parallel_for(tbb::blocked_range<int>(0, merges_count), [&](const tbb::blocked_range<int> &r) {
129
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 20 times.
 40 for (int i = r.begin(); i != r.end(); ++i) {
130 20 OddEvenMergeIterative(raw_data, static_cast<size_t>(i) * 2 * size, 2 * size);
131 }
132 20 });
133 }
134 16 });
135 16 }
136
137 } // namespace
138
139
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 DorofeevIBitwiseSortDoubleEOBatcherMergeTBB::DorofeevIBitwiseSortDoubleEOBatcherMergeTBB(const InType &in) {
140 SetTypeOfTask(GetStaticTypeOfTask());
141
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetInput() = in;
142 16 }
143
144 16 bool DorofeevIBitwiseSortDoubleEOBatcherMergeTBB::ValidationImpl() {
145 16 return true;
146 }
147
148 16 bool DorofeevIBitwiseSortDoubleEOBatcherMergeTBB::PreProcessingImpl() {
149 16 local_data_ = GetInput();
150 16 return true;
151 }
152
153 // Теперь метод RunImpl читается как легкая история без страшной вложенности
154
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 bool DorofeevIBitwiseSortDoubleEOBatcherMergeTBB::RunImpl() {
155
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 if (local_data_.empty()) {
156 return true;
157 }
158
159 size_t original_size = local_data_.size();
160 size_t pow2 = 1;
161
2/2
✓ Branch 0 taken 116 times.
✓ Branch 1 taken 16 times.
 132 while (pow2 < original_size) {
162 116 pow2 *= 2;
163 }
164
165
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 if (pow2 > original_size) {
166 12 local_data_.resize(pow2, std::numeric_limits<double>::max());
167 }
168
169 16 int num_threads = ppc::util::GetNumThreads();
170 16 if (num_threads <= 0) {
171 num_threads = 1;
172 }
173
174 size_t num_chunks = 1;
175
3/4
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 16 times.
✗ Branch 3 not taken.
 32 while (num_chunks * 2 <= static_cast<size_t>(num_threads) && num_chunks * 2 <= pow2) {
176 num_chunks *= 2;
177 }
178
179 16 size_t chunk_size = pow2 / num_chunks;
180 double *raw_data = local_data_.data();
181 16 int num_chunks_int = static_cast<int>(num_chunks);
182
183 // Запускаем инкапсулированную логику TBB
184 16 ExecuteTBBSort(raw_data, pow2, chunk_size, num_chunks_int, num_threads);
185
186
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 if (pow2 > original_size) {
187 12 local_data_.resize(original_size);
188 }
189
190 return true;
191 }
192
193 16 bool DorofeevIBitwiseSortDoubleEOBatcherMergeTBB::PostProcessingImpl() {
194 16 GetOutput() = local_data_;
195 16 return true;
196 }
197
198 } // namespace dorofeev_i_bitwise_sort_double_eo_batcher_merge
199