GCC Code Coverage Report

Directory: ./
File: tasks/gonozov_l_bitwise_sorting_double_Batcher_merge/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 87 89 97.8%
Functions: 10 10 100.0%
Branches: 70 96 72.9%
Line Branch Exec Source
1 #include "gonozov_l_bitwise_sorting_double_Batcher_merge/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <cstdint>
7 #include <cstring>
8 #include <limits>
9 #include <thread>
10 #include <vector>
11
12 #include "gonozov_l_bitwise_sorting_double_Batcher_merge/common/include/common.hpp"
13 #include "util/include/util.hpp"
14
15 namespace gonozov_l_bitwise_sorting_double_batcher_merge {
16
17
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GonozovLBitSortBatcherMergeSTL::GonozovLBitSortBatcherMergeSTL(const InType &in) {
18 SetTypeOfTask(GetStaticTypeOfTask());
19
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
20 32 }
21
22 32 bool GonozovLBitSortBatcherMergeSTL::ValidationImpl() {
23 32 return !GetInput().empty();
24 }
25
26 32 bool GonozovLBitSortBatcherMergeSTL::PreProcessingImpl() {
27 32 return true;
28 }
29
30 namespace {
31
32 uint64_t DoubleToSortableInt(double d) {
33 uint64_t bits = 0;
34 std::memcpy(&bits, &d, sizeof(double));
35
36
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 208 times.
 256 if ((bits >> 63) != 0) {
37 48 return ~bits;
38 }
39
40 208 return bits | 0x8000000000000000ULL;
41 }
42
43 double SortableIntToDouble(uint64_t bits) {
44 256 if ((bits >> 63) != 0) {
45 208 bits &= ~0x8000000000000000ULL;
46 } else {
47 48 bits = ~bits;
48 }
49
50 double result = 0.0;
51 std::memcpy(&result, &bits, sizeof(double));
52
53 return result;
54 }
55
56 size_t NextPowerOfTwo(size_t n) {
57 size_t power = 1;
58
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 32 times.
 128 while (power < n) {
59 96 power <<= 1;
60 }
61 return power;
62 }
63
64
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
 72 void RadixSortDouble(std::vector<double> &data) {
65
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
 72 if (data.empty()) {
66 ✗ return;
67 }
68
69 72 std::vector<uint64_t> keys(data.size());
70
71
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 72 times.
 328 for (size_t i = 0; i < data.size(); ++i) {
72
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 208 times.
 512 keys[i] = DoubleToSortableInt(data[i]);
73 }
74
75 constexpr size_t kByteRange = 256;
76
1/4
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 72 std::vector<uint64_t> temp_keys(data.size());
77
78
2/2
✓ Branch 0 taken 576 times.
✓ Branch 1 taken 72 times.
 648 for (size_t byte_id = 0; byte_id < 8; ++byte_id) {
79
1/4
✓ Branch 1 taken 576 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 576 std::vector<size_t> count(kByteRange, 0);
80
81 576 size_t shift = byte_id * 8;
82
83
2/2
✓ Branch 0 taken 2048 times.
✓ Branch 1 taken 576 times.
 2624 for (uint64_t key : keys) {
84 2048 auto byte = static_cast<uint8_t>((key >> shift) & 0xFF);
85 2048 ++count[byte];
86 }
87
88
2/2
✓ Branch 0 taken 146880 times.
✓ Branch 1 taken 576 times.
 147456 for (size_t i = 1; i < kByteRange; ++i) {
89 146880 count[i] += count[i - 1];
90 }
91
92
2/2
✓ Branch 0 taken 2048 times.
✓ Branch 1 taken 576 times.
 2624 for (size_t i = keys.size(); i-- > 0;) {
93 2048 auto byte = static_cast<uint8_t>((keys[i] >> shift) & 0xFF);
94 2048 temp_keys[--count[byte]] = keys[i];
95 }
96
97 keys.swap(temp_keys);
98 }
99
100
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 72 times.
 328 for (size_t i = 0; i < data.size(); ++i) {
101
2/2
✓ Branch 0 taken 208 times.
✓ Branch 1 taken 48 times.
 512 data[i] = SortableIntToDouble(keys[i]);
102 }
103 }
104
105 // Сравнение и обмен блоков для сети Бэтчера
106 void CompareExchangeBlocks(double *arr, size_t i, size_t step) {
107
4/4
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 40 times.
✓ Branch 2 taken 136 times.
✓ Branch 3 taken 112 times.
 416 for (size_t k = 0; k < step; ++k) {
108
4/4
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 108 times.
✓ Branch 2 taken 80 times.
✓ Branch 3 taken 56 times.
 264 if (arr[i + k] > arr[i + k + step]) {
109 std::swap(arr[i + k], arr[i + k + step]);
110 }
111 }
112 }
113
114 // Итеративная сеть Бэтчера для диапазона [start, start + n)
115 40 void OddEvenMergeIterative(double *arr, size_t start, size_t n) {
116
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 if (n <= 1) {
117 return;
118 }
119
120 40 size_t step = n / 2;
121 CompareExchangeBlocks(arr, start, step);
122
123 40 step /= 2;
124
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 40 times.
 104 for (; step > 0; step /= 2) {
125
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 64 times.
 176 for (size_t i = step; i < n - step; i += step * 2) {
126 112 CompareExchangeBlocks(arr, start + i, step);
127 }
128 }
129 }
130
131 // Сортировка одного чанка (создание локальной копии)
132 72 void SortChunk(double *raw_data, size_t start, size_t size) {
133 72 std::vector<double> local_chunk(size);
134
135
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 72 times.
 328 for (size_t j = 0; j < size; ++j) {
136 256 local_chunk[j] = raw_data[start + j];
137 }
138
139
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 RadixSortDouble(local_chunk);
140
141
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 72 times.
 328 for (size_t j = 0; j < size; ++j) {
142 256 raw_data[start + j] = local_chunk[j];
143 }
144 72 }
145
146 // Параллельное слияние чанков сетью Бэтчера
147 32 void MergeSortedChunks(double *raw_data, size_t total_size, size_t chunk_size) {
148
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
 64 for (size_t current_size = chunk_size; current_size < total_size; current_size *= 2) {
149 32 size_t merges_count = total_size / (current_size * 2);
150
151 32 std::vector<std::thread> threads;
152
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 threads.reserve(merges_count);
153
154
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 32 times.
 72 for (size_t i = 0; i < merges_count; ++i) {
155
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 threads.emplace_back([raw_data, i, current_size]() {
156 40 size_t start = i * 2 * current_size;
157 40 OddEvenMergeIterative(raw_data, start, 2 * current_size);
158 });
159 }
160
161
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 32 times.
 72 for (auto &thread : threads) {
162
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 thread.join();
163 }
164 32 }
165 32 }
166
167
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 void ParallelHybridSort(std::vector<double> &data) {
168
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 if (data.size() <= 1) {
169 ✗ return;
170 }
171
172 size_t original_size = data.size();
173 size_t padded_size = NextPowerOfTwo(original_size);
174
175 32 data.resize(padded_size, std::numeric_limits<double>::infinity());
176
177 32 int threads_count = ppc::util::GetNumThreads();
178 32 threads_count = std::max(1, threads_count);
179
180 // Количество чанков = наибольшая степень двойки, не превышающая число потоков
181 size_t chunks_count = 1;
182
3/4
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 32 times.
✗ Branch 3 not taken.
 64 while (chunks_count * 2 <= static_cast<size_t>(threads_count) && chunks_count * 2 <= padded_size) {
183 chunks_count *= 2;
184 }
185
186
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 size_t chunk_size = padded_size / chunks_count;
187 double *raw_data = data.data();
188
189 // Параллельная сортировка чанков
190 32 std::vector<std::thread> threads;
191
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 threads.reserve(chunks_count);
192
193
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 32 times.
 104 for (size_t i = 0; i < chunks_count; ++i) {
194
1/2
✓ Branch 2 taken 72 times.
✗ Branch 3 not taken.
 144 threads.emplace_back([raw_data, i, chunk_size]() { SortChunk(raw_data, i * chunk_size, chunk_size); });
195 }
196
197
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 32 times.
 104 for (auto &thread : threads) {
198
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 thread.join();
199 }
200
201 // Параллельное слияние чанков сетью Бэтчера
202
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 MergeSortedChunks(raw_data, padded_size, chunk_size);
203
204
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 data.resize(original_size);
205 32 }
206
207 } // namespace
208
209 32 bool GonozovLBitSortBatcherMergeSTL::RunImpl() {
210 32 std::vector<double> array = GetInput();
211
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 ParallelHybridSort(array);
212
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetOutput() = array;
213 32 return true;
214 }
215
216 32 bool GonozovLBitSortBatcherMergeSTL::PostProcessingImpl() {
217 32 return true;
218 }
219
220 } // namespace gonozov_l_bitwise_sorting_double_batcher_merge
221