GCC Code Coverage Report

Directory: ./
File: tasks/dorofeev_i_bitwise_sort_double_eo_batcher_merge/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 84 85 98.8%
Functions: 9 9 100.0%
Branches: 70 92 76.1%
Line Branch Exec Source
1 #include "dorofeev_i_bitwise_sort_double_eo_batcher_merge/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstdint>
5 #include <cstring>
6 #include <limits>
7 #include <thread>
8 #include <utility>
9 #include <vector>
10
11 #include "dorofeev_i_bitwise_sort_double_eo_batcher_merge/common/include/common.hpp"
12 #include "util/include/util.hpp"
13
14 namespace dorofeev_i_bitwise_sort_double_eo_batcher_merge {
15
16 namespace {
17
18 uint64_t DoubleToUint(double d) {
19 uint64_t u = 0;
20 std::memcpy(&u, &d, sizeof(double));
21
2/2
✓ Branch 0 taken 4984 times.
✓ Branch 1 taken 6408 times.
 11392 if ((u & 0x8000000000000000ULL) != 0) {
22 4984 u = ~u;
23 } else {
24 6408 u |= 0x8000000000000000ULL;
25 }
26 return u;
27 }
28
29 double UintToDouble(uint64_t u) {
30 11392 if ((u & 0x8000000000000000ULL) != 0) {
31 6408 u &= ~0x8000000000000000ULL;
32 } else {
33 4984 u = ~u;
34 }
35 double d = 0.0;
36 std::memcpy(&d, &u, sizeof(double));
37 return d;
38 }
39
40
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
 72 void RadixSortDouble(std::vector<double> &arr) {
41
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
 72 if (arr.empty()) {
42 ✗ return;
43 }
44
45 72 std::vector<uint64_t> uarr(arr.size());
46
2/2
✓ Branch 0 taken 11392 times.
✓ Branch 1 taken 72 times.
 11464 for (size_t i = 0; i < arr.size(); ++i) {
47
2/2
✓ Branch 0 taken 4984 times.
✓ Branch 1 taken 6408 times.
 22784 uarr[i] = DoubleToUint(arr[i]);
48 }
49
50
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(uarr.size());
51
2/2
✓ Branch 0 taken 576 times.
✓ Branch 1 taken 72 times.
 648 for (size_t byte = 0; byte < 8; ++byte) {
52
1/4
✓ Branch 1 taken 576 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 576 std::vector<int> count(256, 0);
53
2/2
✓ Branch 0 taken 91136 times.
✓ Branch 1 taken 576 times.
 91712 for (uint64_t val : uarr) {
54 91136 count[(val >> (byte * 8)) & 0xFF]++;
55 }
56
2/2
✓ Branch 0 taken 146880 times.
✓ Branch 1 taken 576 times.
 147456 for (size_t i = 1; i < 256; ++i) {
57 146880 count[i] += count[i - 1];
58 }
59
2/2
✓ Branch 0 taken 91136 times.
✓ Branch 1 taken 576 times.
 91712 for (int i = static_cast<int>(uarr.size()) - 1; i >= 0; --i) {
60 91136 temp[--count[(uarr[i] >> (byte * 8)) & 0xFF]] = uarr[i];
61 }
62
1/2
✓ Branch 1 taken 576 times.
✗ Branch 2 not taken.
 576 uarr = temp;
63 }
64
65
2/2
✓ Branch 0 taken 11392 times.
✓ Branch 1 taken 72 times.
 11464 for (size_t i = 0; i < arr.size(); ++i) {
66
2/2
✓ Branch 0 taken 6408 times.
✓ Branch 1 taken 4984 times.
 22784 arr[i] = UintToDouble(uarr[i]);
67 }
68 }
69
70 void CompareExchangeBlocks(double *arr, size_t i, size_t step) {
71
4/4
✓ Branch 0 taken 5696 times.
✓ Branch 1 taken 40 times.
✓ Branch 2 taken 40216 times.
✓ Branch 3 taken 11078 times.
 57030 for (size_t k = 0; k < step; ++k) {
72
4/4
✓ Branch 0 taken 742 times.
✓ Branch 1 taken 4954 times.
✓ Branch 2 taken 20344 times.
✓ Branch 3 taken 19872 times.
 45912 if (arr[i + k] > arr[i + k + step]) {
73 std::swap(arr[i + k], arr[i + k + step]);
74 }
75 }
76 }
77
78 40 void OddEvenMergeIterative(double *arr, size_t start, size_t n) {
79
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 if (n <= 1) {
80 return;
81 }
82
83 40 size_t step = n / 2;
84 CompareExchangeBlocks(arr, start, step);
85
86 40 step /= 2;
87
2/2
✓ Branch 0 taken 234 times.
✓ Branch 1 taken 40 times.
 274 for (; step > 0; step /= 2) {
88
2/2
✓ Branch 0 taken 11078 times.
✓ Branch 1 taken 234 times.
 11312 for (size_t i = step; i < n - step; i += step * 2) {
89 11078 CompareExchangeBlocks(arr, start + i, step);
90 }
91 }
92 }
93
94 72 void ProcessChunkSTL(double *raw_data, int chunk_idx, size_t chunk_size) {
95 72 size_t start_idx = static_cast<size_t>(chunk_idx) * chunk_size;
96
97 72 std::vector<double> local_arr(chunk_size);
98 double *local_raw = local_arr.data();
99
100
2/2
✓ Branch 0 taken 11392 times.
✓ Branch 1 taken 72 times.
 11464 for (size_t j = 0; j < chunk_size; ++j) {
101 11392 local_raw[j] = raw_data[start_idx + j];
102 }
103
104
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 RadixSortDouble(local_arr);
105
106
2/2
✓ Branch 0 taken 11392 times.
✓ Branch 1 taken 72 times.
 11464 for (size_t j = 0; j < chunk_size; ++j) {
107 11392 raw_data[start_idx + j] = local_raw[j];
108 }
109 72 }
110
111 32 void ExecuteSTLSort(double *raw_data, size_t pow2, size_t chunk_size, int num_chunks_int) {
112 32 std::vector<std::thread> threads;
113
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 threads.reserve(num_chunks_int);
114
115 // 1. Параллельно сортируем каждый блок, раздавая задачи сырым std::thread
116
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 32 times.
 104 for (int i = 0; i < num_chunks_int; ++i) {
117
1/2
✓ Branch 2 taken 72 times.
✗ Branch 3 not taken.
 144 threads.emplace_back([raw_data, i, chunk_size]() { ProcessChunkSTL(raw_data, i, chunk_size); });
118 }
119
120
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 32 times.
 104 for (auto &t : threads) {
121
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 t.join();
122 }
123 32 threads.clear();
124
125 // 2. Собираем отсортированные блоки вместе (Параллельное дерево слияния Бэтчера)
126
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
 64 for (size_t size = chunk_size; size < pow2; size *= 2) {
127 32 int merges_count = static_cast<int>(pow2 / (size * 2));
128
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 threads.reserve(merges_count);
129
130
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 32 times.
 72 for (int i = 0; i < merges_count; ++i) {
131 40 threads.emplace_back(
132
1/2
✓ Branch 2 taken 40 times.
✗ Branch 3 not taken.
 80 [raw_data, i, size]() { OddEvenMergeIterative(raw_data, static_cast<size_t>(i) * 2 * size, 2 * size); });
133 }
134
135
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 32 times.
 72 for (auto &t : threads) {
136
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 t.join();
137 }
138 32 threads.clear();
139 }
140 32 }
141
142 } // namespace
143
144
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 DorofeevIBitwiseSortDoubleEOBatcherMergeSTL::DorofeevIBitwiseSortDoubleEOBatcherMergeSTL(const InType &in) {
145 SetTypeOfTask(GetStaticTypeOfTask());
146
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
147 32 }
148
149 32 bool DorofeevIBitwiseSortDoubleEOBatcherMergeSTL::ValidationImpl() {
150 32 return true;
151 }
152
153 32 bool DorofeevIBitwiseSortDoubleEOBatcherMergeSTL::PreProcessingImpl() {
154 32 local_data_ = GetInput();
155 32 return true;
156 }
157
158
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 bool DorofeevIBitwiseSortDoubleEOBatcherMergeSTL::RunImpl() {
159
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if (local_data_.empty()) {
160 return true;
161 }
162
163 size_t original_size = local_data_.size();
164 size_t pow2 = 1;
165
2/2
✓ Branch 0 taken 232 times.
✓ Branch 1 taken 32 times.
 264 while (pow2 < original_size) {
166 232 pow2 *= 2;
167 }
168
169
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 if (pow2 > original_size) {
170 24 local_data_.resize(pow2, std::numeric_limits<double>::max());
171 }
172
173 32 int num_threads = ppc::util::GetNumThreads();
174 32 if (num_threads <= 0) {
175 num_threads = 1;
176 }
177
178 size_t num_chunks = 1;
179
3/4
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 32 times.
✗ Branch 3 not taken.
 64 while (num_chunks * 2 <= static_cast<size_t>(num_threads) && num_chunks * 2 <= pow2) {
180 num_chunks *= 2;
181 }
182
183 32 size_t chunk_size = pow2 / num_chunks;
184 double *raw_data = local_data_.data();
185 32 int num_chunks_int = static_cast<int>(num_chunks);
186
187 32 ExecuteSTLSort(raw_data, pow2, chunk_size, num_chunks_int);
188
189
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 if (pow2 > original_size) {
190 24 local_data_.resize(original_size);
191 }
192
193 return true;
194 }
195
196 32 bool DorofeevIBitwiseSortDoubleEOBatcherMergeSTL::PostProcessingImpl() {
197 32 GetOutput() = local_data_;
198 32 return true;
199 }
200
201 } // namespace dorofeev_i_bitwise_sort_double_eo_batcher_merge
202