GCC Code Coverage Report

Directory: ./
File: tasks/leonova_a_radix_merge_sort/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 93 97 95.9%
Functions: 13 13 100.0%
Branches: 67 104 64.4%
Line Branch Exec Source
1 #include "leonova_a_radix_merge_sort/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <cstdint>
8 #include <iterator>
9 #include <vector>
10
11 #include "leonova_a_radix_merge_sort/common/include/common.hpp"
12 #include "util/include/util.hpp"
13
14 namespace leonova_a_radix_merge_sort {
15
16 inline uint64_t LeonovaARadixMergeSortOMP::ToUnsignedValue(int64_t value) {
17
2/2
✓ Branch 0 taken 1051660 times.
✓ Branch 1 taken 304 times.
 1051964 return static_cast<uint64_t>(value) ^ kSignBitMask;
18 }
19
20 inline void LeonovaARadixMergeSortOMP::ResetLocalCounts(CounterTable &local_counts) {
21 for (auto &counter : local_counts) {
22 std::ranges::fill(counter, 0);
23 }
24 }
25
26 992 inline void LeonovaARadixMergeSortOMP::BuildThreadOffsets(const CounterTable &local_counts, size_t thread_count,
27 CounterTable &local_offsets) {
28 992 std::vector<size_t> bucket_totals(kNumCounters, 0);
29
30
2/2
✓ Branch 0 taken 2432 times.
✓ Branch 1 taken 992 times.
 3424 for (size_t thread = 0; thread < thread_count; ++thread) {
31 const auto &row = local_counts[thread];
32
2/2
✓ Branch 0 taken 622592 times.
✓ Branch 1 taken 2432 times.
 625024 for (size_t i = 0; i < kNumCounters; ++i) {
33 622592 bucket_totals[i] += row[i];
34 }
35 }
36
37 size_t prefix = 0;
38
2/2
✓ Branch 0 taken 253952 times.
✓ Branch 1 taken 992 times.
 254944 for (auto &bucket_total : bucket_totals) {
39 253952 const size_t count = bucket_total;
40 253952 bucket_total = prefix;
41 253952 prefix += count;
42 }
43
44
2/2
✓ Branch 0 taken 2432 times.
✓ Branch 1 taken 992 times.
 3424 for (size_t thread = 0; thread < thread_count; ++thread) {
45 auto &offset_row = local_offsets[thread];
46 const auto &count_row = local_counts[thread];
47 size_t bucket_index = 0;
48
2/2
✓ Branch 0 taken 622592 times.
✓ Branch 1 taken 2432 times.
 625024 for (auto &offset : offset_row) {
49 622592 offset = bucket_totals[bucket_index];
50 622592 bucket_totals[bucket_index] += count_row[bucket_index];
51 622592 ++bucket_index;
52 }
53 }
54 992 }
55
56
1/2
✓ Branch 0 taken 304 times.
✗ Branch 1 not taken.
 304 inline void LeonovaARadixMergeSortOMP::FillUnsignedKeys(const std::vector<int64_t> &arr, size_t left, size_t size,
57 std::vector<uint64_t> &keys) {
58 #pragma omp for schedule(static)
59 for (size_t index = 0; index < size; ++index) {
60
2/2
✓ Branch 0 taken 1051660 times.
✓ Branch 1 taken 304 times.
 1051964 keys[index] = ToUnsignedValue(arr[left + index]);
61 }
62 304 }
63
64 2432 inline void LeonovaARadixMergeSortOMP::CountByteValues(const std::vector<uint64_t> &keys, size_t size, int shift,
65 CounterTable &local_counts) {
66
1/2
✓ Branch 1 taken 2432 times.
✗ Branch 2 not taken.
 2432 const auto thread_id = static_cast<size_t>(omp_get_thread_num());
67 auto &row = local_counts[thread_id];
68
69 #pragma omp for schedule(static)
70 for (size_t index = 0; index < size; ++index) {
71
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8415712 times.
 8415712 const auto byte_val = static_cast<size_t>((keys[index] >> shift) & 0xFFU);
72 auto it = row.begin();
73
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8415712 times.
 8415712 std::advance(it, static_cast<std::ptrdiff_t>(byte_val));
74
2/2
✓ Branch 0 taken 8413280 times.
✓ Branch 1 taken 2432 times.
 8415712 ++(*it);
75 }
76 2432 }
77
78 2432 inline void LeonovaARadixMergeSortOMP::ScatterByte(const std::vector<uint64_t> &keys, const std::vector<int64_t> &arr,
79 size_t left, size_t size, int shift, CounterTable &local_offsets,
80 std::vector<int64_t> &temp_arr, std::vector<uint64_t> &temp_keys) {
81
1/2
✓ Branch 1 taken 2432 times.
✗ Branch 2 not taken.
 2432 const auto thread_id = static_cast<size_t>(omp_get_thread_num());
82 auto &thread_offsets = local_offsets[thread_id];
83
84 #pragma omp for schedule(static)
85 for (size_t index = 0; index < size; ++index) {
86
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8415712 times.
 8415712 const auto byte_val = static_cast<size_t>((keys[index] >> shift) & 0xFFU);
87
88 auto it = thread_offsets.begin();
89
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8415712 times.
 8415712 std::advance(it, static_cast<std::ptrdiff_t>(byte_val));
90
91 8415712 const size_t pos = (*it)++;
92
2/2
✓ Branch 0 taken 8413280 times.
✓ Branch 1 taken 2432 times.
 8415712 temp_arr[pos] = arr[left + index];
93
2/2
✓ Branch 0 taken 8413280 times.
✓ Branch 1 taken 2432 times.
 8415712 temp_keys[pos] = keys[index];
94 }
95 2432 }
96
97
2/2
✓ Branch 0 taken 992 times.
✓ Branch 1 taken 1440 times.
 2432 inline void LeonovaARadixMergeSortOMP::CopyTempToArray(std::vector<int64_t> &arr, size_t left,
98 std::vector<int64_t> &temp_arr, std::vector<uint64_t> &keys,
99 std::vector<uint64_t> &temp_keys) {
100 #pragma omp single
101 {
102 std::ranges::copy(temp_arr, arr.begin() + static_cast<std::ptrdiff_t>(left));
103 keys.swap(temp_keys);
104 }
105 2432 }
106
107
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 LeonovaARadixMergeSortOMP::LeonovaARadixMergeSortOMP(const InType &in) {
108 SetTypeOfTask(GetStaticTypeOfTask());
109
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 GetInput() = in;
110
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 GetOutput() = std::vector<int64_t>(GetInput().size());
111 128 }
112
113 256 bool LeonovaARadixMergeSortOMP::ValidationImpl() {
114 256 return !GetInput().empty();
115 }
116
117 128 bool LeonovaARadixMergeSortOMP::PreProcessingImpl() {
118 128 return true;
119 }
120
121 128 bool LeonovaARadixMergeSortOMP::RunImpl() {
122
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 if (!ValidationImpl()) {
123 return false;
124 }
125
126 128 GetOutput() = GetInput();
127
128
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 8 times.
 128 if (GetOutput().size() > 1) {
129 120 RadixMergeSort(GetOutput(), 0, GetOutput().size());
130 }
131
132 return true;
133 }
134
135 128 bool LeonovaARadixMergeSortOMP::PostProcessingImpl() {
136 128 return true;
137 }
138
139 124 void LeonovaARadixMergeSortOMP::RadixSort(std::vector<int64_t> &arr, size_t left, size_t right) {
140 124 const size_t size = right - left;
141
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 124 times.
 124 if (size <= 1) {
142 ✗ return;
143 }
144
145 124 const int requested_threads = std::max(1, ppc::util::GetNumThreads());
146
4/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 120 times.
✓ Branch 2 taken 93 times.
✓ Branch 3 taken 31 times.
 128 const int omp_threads = std::max(1, std::min(requested_threads, static_cast<int>(size)));
147 124 const auto thread_count = static_cast<size_t>(omp_threads);
148
149 124 std::vector<uint64_t> keys(size);
150
1/4
✓ Branch 1 taken 124 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 124 std::vector<int64_t> temp_arr(size);
151
1/4
✓ Branch 1 taken 124 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 124 std::vector<uint64_t> temp_keys(size);
152
153
2/6
✓ Branch 1 taken 124 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 124 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 124 CounterTable local_counts(thread_count, CounterRow(kNumCounters, 0));
154
2/4
✓ Branch 1 taken 124 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 124 times.
✗ Branch 5 not taken.
 124 CounterTable local_offsets(thread_count, CounterRow(kNumCounters, 0));
155
156 124 #pragma omp parallel default(none) shared(arr, keys, temp_arr, temp_keys, local_counts, local_offsets, left, size, \
157 omp_threads, thread_count) num_threads(omp_threads)
158 {
159 FillUnsignedKeys(arr, left, size, keys);
160
161 for (int byte_pos = 0; byte_pos < kNumBytes; ++byte_pos) {
162 const int shift = byte_pos * kByteSize;
163
164 #pragma omp single
165 {
166 ResetLocalCounts(local_counts);
167 }
168
169 #pragma omp barrier
170
171 CountByteValues(keys, size, shift, local_counts);
172
173 #pragma omp single
174 {
175 BuildThreadOffsets(local_counts, thread_count, local_offsets);
176 }
177
178 #pragma omp barrier
179
180 ScatterByte(keys, arr, left, size, shift, local_offsets, temp_arr, temp_keys);
181
182 CopyTempToArray(arr, left, temp_arr, keys, temp_keys);
183
184 #pragma omp barrier
185 }
186 }
187 124 }
188
189 4 void LeonovaARadixMergeSortOMP::SimpleMerge(std::vector<int64_t> &arr, size_t left, size_t mid, size_t right) {
190 4 const size_t left_size = mid - left;
191 4 const size_t right_size = right - mid;
192
193 4 std::vector<int64_t> merged(left_size + right_size);
194
195 size_t i = 0;
196 size_t j = 0;
197 size_t k = 0;
198
199
2/2
✓ Branch 0 taken 262148 times.
✓ Branch 1 taken 4 times.
 262152 while (i < left_size && j < right_size) {
200
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 262148 times.
 262148 if (arr[left + i] <= arr[mid + j]) {
201 ✗ merged[k++] = arr[left + i++];
202 } else {
203 262148 merged[k++] = arr[mid + j++];
204 }
205 }
206
207
2/2
✓ Branch 0 taken 262144 times.
✓ Branch 1 taken 4 times.
 262148 while (i < left_size) {
208 262144 merged[k++] = arr[left + i++];
209 }
210
211
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 while (j < right_size) {
212 ✗ merged[k++] = arr[mid + j++];
213 }
214
215 std::ranges::copy(merged, arr.begin() + static_cast<std::ptrdiff_t>(left));
216 4 }
217
218 120 void LeonovaARadixMergeSortOMP::RadixMergeSort(std::vector<int64_t> &arr, size_t left, size_t right) {
219 struct SortTask {
220 size_t left;
221 size_t right;
222 bool sorted;
223 };
224
225 120 std::vector<SortTask> stack;
226
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 120 stack.reserve(128);
227
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 120 stack.push_back({left, right, false});
228
229
2/2
✓ Branch 0 taken 132 times.
✓ Branch 1 taken 120 times.
 252 while (!stack.empty()) {
230
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 132 times.
 132 SortTask current = stack.back();
231 stack.pop_back();
232
233 132 const size_t size = current.right - current.left;
234
235
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 132 times.
 132 if (size <= 1) {
236 ✗ continue;
237 }
238
239
2/2
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 8 times.
 132 if (size <= kRadixThreshold) {
240
1/2
✓ Branch 1 taken 124 times.
✗ Branch 2 not taken.
 124 RadixSort(arr, current.left, current.right);
241 124 continue;
242 }
243
244
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (!current.sorted) {
245 4 const size_t mid = current.left + (size / 2);
246
247
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 stack.push_back({current.left, current.right, true});
248
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 stack.push_back({mid, current.right, false});
249
1/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 4 stack.push_back({current.left, mid, false});
250 } else {
251 4 const size_t mid = current.left + (size / 2);
252
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 SimpleMerge(arr, current.left, mid, current.right);
253 }
254 }
255 120 }
256
257 } // namespace leonova_a_radix_merge_sort
258