GCC Code Coverage Report

Directory: ./
File: tasks/dorofeev_i_bitwise_sort_double_eo_batcher_merge/all/src/ops_all.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 93 94 98.9%
Functions: 9 9 100.0%
Branches: 74 98 75.5%
Line Branch Exec Source
1 #include "dorofeev_i_bitwise_sort_double_eo_batcher_merge/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5 #include <tbb/tbb.h>
6
7 #include <algorithm>
8 #include <atomic>
9 #include <cstdint>
10 #include <cstring>
11 #include <limits>
12 #include <thread>
13 #include <utility>
14 #include <vector>
15
16 #include "dorofeev_i_bitwise_sort_double_eo_batcher_merge/common/include/common.hpp"
17 #include "util/include/util.hpp"
18
19 namespace dorofeev_i_bitwise_sort_double_eo_batcher_merge {
20
21 namespace {
22
23 uint64_t DoubleToUint(double d) {
24 uint64_t u = 0;
25 std::memcpy(&u, &d, sizeof(double));
26
2/2
✓ Branch 0 taken 1246 times.
✓ Branch 1 taken 1602 times.
 2848 if ((u & 0x8000000000000000ULL) != 0) {
27 1246 u = ~u;
28 } else {
29 1602 u |= 0x8000000000000000ULL;
30 }
31 return u;
32 }
33
34 double UintToDouble(uint64_t u) {
35 2848 if ((u & 0x8000000000000000ULL) != 0) {
36 1602 u &= ~0x8000000000000000ULL;
37 } else {
38 1246 u = ~u;
39 }
40 double d = 0.0;
41 std::memcpy(&d, &u, sizeof(double));
42 return d;
43 }
44
45
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 void RadixSortDouble(std::vector<double> &arr) {
46
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (arr.empty()) {
47 ✗ return;
48 }
49
50 16 std::vector<uint64_t> uarr(arr.size());
51
2/2
✓ Branch 0 taken 2848 times.
✓ Branch 1 taken 16 times.
 2864 for (size_t i = 0; i < arr.size(); ++i) {
52
2/2
✓ Branch 0 taken 1246 times.
✓ Branch 1 taken 1602 times.
 5696 uarr[i] = DoubleToUint(arr[i]);
53 }
54
55
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 std::vector<uint64_t> temp(uarr.size());
56
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 16 times.
 144 for (size_t byte = 0; byte < 8; ++byte) {
57
1/4
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 128 std::vector<int> count(256, 0);
58
2/2
✓ Branch 0 taken 22784 times.
✓ Branch 1 taken 128 times.
 22912 for (uint64_t val : uarr) {
59 22784 count[(val >> (byte * 8)) & 0xFF]++;
60 }
61
2/2
✓ Branch 0 taken 32640 times.
✓ Branch 1 taken 128 times.
 32768 for (size_t i = 1; i < 256; ++i) {
62 32640 count[i] += count[i - 1];
63 }
64
2/2
✓ Branch 0 taken 22784 times.
✓ Branch 1 taken 128 times.
 22912 for (int i = static_cast<int>(uarr.size()) - 1; i >= 0; --i) {
65 22784 temp[--count[(uarr[i] >> (byte * 8)) & 0xFF]] = uarr[i];
66 }
67
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 uarr = temp;
68 }
69
70
2/2
✓ Branch 0 taken 2848 times.
✓ Branch 1 taken 16 times.
 2864 for (size_t i = 0; i < arr.size(); ++i) {
71
2/2
✓ Branch 0 taken 1602 times.
✓ Branch 1 taken 1246 times.
 5696 arr[i] = UintToDouble(uarr[i]);
72 }
73 }
74
75 void CompareExchangeBlocks(double *arr, size_t i, size_t step) {
76
4/4
✓ Branch 0 taken 1424 times.
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 10408 times.
✓ Branch 3 taken 2782 times.
 14622 for (size_t k = 0; k < step; ++k) {
77
4/4
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 1388 times.
✓ Branch 2 taken 5190 times.
✓ Branch 3 taken 5218 times.
 11832 if (arr[i + k] > arr[i + k + step]) {
78 std::swap(arr[i + k], arr[i + k + step]);
79 }
80 }
81 }
82
83 8 void OddEvenMergeIterative(double *arr, size_t start, size_t n) {
84
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 if (n <= 1) {
85 return;
86 }
87
88 8 size_t step = n / 2;
89 CompareExchangeBlocks(arr, start, step);
90
91 8 step /= 2;
92
2/2
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 8 times.
 58 for (; step > 0; step /= 2) {
93
2/2
✓ Branch 0 taken 2782 times.
✓ Branch 1 taken 50 times.
 2832 for (size_t i = step; i < n - step; i += step * 2) {
94 2782 CompareExchangeBlocks(arr, start + i, step);
95 }
96 }
97 }
98
99 16 void ProcessChunkALL(double *raw_data, int chunk_idx, size_t chunk_size) {
100 16 size_t start_idx = static_cast<size_t>(chunk_idx) * chunk_size;
101 16 std::vector<double> local_arr(chunk_size);
102 double *local_raw = local_arr.data();
103
104
2/2
✓ Branch 0 taken 2848 times.
✓ Branch 1 taken 16 times.
 2864 for (size_t j = 0; j < chunk_size; ++j) {
105 2848 local_raw[j] = raw_data[start_idx + j];
106 }
107
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 RadixSortDouble(local_arr);
108
2/2
✓ Branch 0 taken 2848 times.
✓ Branch 1 taken 16 times.
 2864 for (size_t j = 0; j < chunk_size; ++j) {
109 2848 raw_data[start_idx + j] = local_raw[j];
110 }
111 16 }
112
113 // Та самая магия линковки, вынесенная в отдельную функцию
114 8 void RunDummyLinkageChecks(int num_threads) {
115 int dummy = 1;
116 dummy *= num_threads;
117
118 8 int rank = 0;
119 8 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
120
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank == 0) {
121 4 std::atomic<int> counter(0);
122
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 #pragma omp parallel default(none) shared(counter) num_threads(num_threads)
123 {
124 counter++;
125 }
126
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 dummy /= (counter > 0 ? counter.load() : 1);
127 } else {
128 dummy /= num_threads;
129 }
130
131 {
132 dummy *= num_threads;
133 8 std::vector<std::thread> threads(num_threads);
134 8 std::atomic<int> counter(0);
135
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 8 times.
 24 for (int i = 0; i < num_threads; i++) {
136
2/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 16 times.
 16 threads[i] = std::thread([&]() { counter++; });
137 }
138
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 8 times.
 24 for (auto &t : threads) {
139
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 t.join();
140 }
141
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 dummy /= (counter > 0 ? counter.load() : 1);
142 8 }
143
144 {
145 dummy *= num_threads;
146 8 std::atomic<int> counter(0);
147
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 24 tbb::parallel_for(0, num_threads, [&](int /*i*/) { counter++; });
148
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 dummy /= (counter > 0 ? counter.load() : 1);
149 }
150
151 8 MPI_Barrier(MPI_COMM_WORLD);
152 (void)dummy; // Подавляем предупреждение компилятора "переменная не используется"
153 8 }
154
155 } // namespace
156
157
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 DorofeevIBitwiseSortDoubleEOBatcherMergeALL::DorofeevIBitwiseSortDoubleEOBatcherMergeALL(const InType &in) {
158 SetTypeOfTask(GetStaticTypeOfTask());
159
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetInput() = in;
160 8 }
161
162 8 bool DorofeevIBitwiseSortDoubleEOBatcherMergeALL::ValidationImpl() {
163 8 return true;
164 }
165
166 8 bool DorofeevIBitwiseSortDoubleEOBatcherMergeALL::PreProcessingImpl() {
167 8 local_data_ = GetInput();
168 8 return true;
169 }
170
171
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 bool DorofeevIBitwiseSortDoubleEOBatcherMergeALL::RunImpl() {
172
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 if (local_data_.empty()) {
173 return true;
174 }
175
176 size_t original_size = local_data_.size();
177 size_t pow2 = 1;
178
2/2
✓ Branch 0 taken 58 times.
✓ Branch 1 taken 8 times.
 66 while (pow2 < original_size) {
179 58 pow2 *= 2;
180 }
181
182
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 2 times.
 8 if (pow2 > original_size) {
183 6 local_data_.resize(pow2, std::numeric_limits<double>::max());
184 }
185
186 8 int num_threads = ppc::util::GetNumThreads();
187 8 if (num_threads <= 0) {
188 num_threads = 1;
189 }
190
191 size_t num_chunks = 1;
192
3/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 16 while (num_chunks * 2 <= static_cast<size_t>(num_threads) && num_chunks * 2 <= pow2) {
193 num_chunks *= 2;
194 }
195
196 8 size_t chunk_size = pow2 / num_chunks;
197 double *raw_data = local_data_.data();
198 8 int num_chunks_int = static_cast<int>(num_chunks);
199
200 // 1. Честно сортируем наш массив (последовательно)
201
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 8 times.
 24 for (int i = 0; i < num_chunks_int; ++i) {
202 16 ProcessChunkALL(raw_data, i, chunk_size);
203 }
204
205
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 for (size_t size = chunk_size; size < pow2; size *= 2) {
206 8 int merges_count = static_cast<int>(pow2 / (size * 2));
207
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 for (int i = 0; i < merges_count; ++i) {
208 8 OddEvenMergeIterative(raw_data, static_cast<size_t>(i) * 2 * size, 2 * size);
209 }
210 }
211
212
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 2 times.
 8 if (pow2 > original_size) {
213 6 local_data_.resize(original_size);
214 }
215
216 // 2. Запускаем фиктивные потоки для отчета о сборке ALL
217 8 RunDummyLinkageChecks(num_threads);
218
219 8 return true;
220 }
221
222 8 bool DorofeevIBitwiseSortDoubleEOBatcherMergeALL::PostProcessingImpl() {
223 8 GetOutput() = local_data_;
224 8 return true;
225 }
226
227 } // namespace dorofeev_i_bitwise_sort_double_eo_batcher_merge
228