GCC Code Coverage Report

Directory: ./
File: tasks/krymova_k_lsd_sort_merge_double/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 72 79 91.1%
Functions: 11 13 84.6%
Branches: 51 78 65.4%
Line Branch Exec Source
1 #include "krymova_k_lsd_sort_merge_double/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/blocked_range.h>
4 #include <tbb/parallel_for.h>
5 #include <tbb/task_arena.h>
6
7 #include <algorithm>
8 #include <cstdint>
9 #include <cstring>
10 #include <vector>
11
12 #include "krymova_k_lsd_sort_merge_double/common/include/common.hpp"
13
14 namespace krymova_k_lsd_sort_merge_double {
15
16
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 KrymovaKLsdSortMergeDoubleTBB::KrymovaKLsdSortMergeDoubleTBB(const InType &in)
17
2/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 48 times.
✗ Branch 5 not taken.
 48 : num_threads_(tbb::this_task_arena::max_concurrency()) {
18 SetTypeOfTask(GetStaticTypeOfTask());
19
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput() = in;
20 48 GetOutput() = OutType();
21 48 }
22
23 48 bool KrymovaKLsdSortMergeDoubleTBB::ValidationImpl() {
24 48 return !GetInput().empty();
25 }
26
27 48 bool KrymovaKLsdSortMergeDoubleTBB::PreProcessingImpl() {
28 48 GetOutput() = GetInput();
29 48 return true;
30 }
31
32 ✗ uint64_t KrymovaKLsdSortMergeDoubleTBB::DoubleToULL(double d) {
33 uint64_t ull = 0;
34 std::memcpy(&ull, &d, sizeof(double));
35
36
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 450080 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 450080 if ((ull & 0x8000000000000000ULL) != 0U) {
37 ✗ ull = ~ull;
38 } else {
39 450080 ull |= 0x8000000000000000ULL;
40 }
41
42 ✗ return ull;
43 }
44
45 ✗ double KrymovaKLsdSortMergeDoubleTBB::ULLToDouble(uint64_t ull) {
46
1/4
✓ Branch 0 taken 450080 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 450080 if ((ull & 0x8000000000000000ULL) != 0U) {
47 450080 ull &= 0x7FFFFFFFFFFFFFFFULL;
48 } else {
49 ✗ ull = ~ull;
50 }
51
52 double d = 0.0;
53 std::memcpy(&d, &ull, sizeof(double));
54 ✗ return d;
55 }
56
57 184 void KrymovaKLsdSortMergeDoubleTBB::LSDSortDouble(double *arr, int size) {
58
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 184 times.
 184 if (size <= 1) {
59 ✗ return;
60 }
61
62 const int k_bits_per_pass = 8;
63 const int k_radix = 1 << k_bits_per_pass;
64 const int k_passes = static_cast<int>(sizeof(double)) * 8 / k_bits_per_pass;
65
66 184 std::vector<uint64_t> ull_arr(size);
67
1/4
✓ Branch 1 taken 184 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 184 std::vector<uint64_t> ull_tmp(size);
68
69
2/2
✓ Branch 0 taken 450080 times.
✓ Branch 1 taken 184 times.
 450264 for (int i = 0; i < size; ++i) {
70
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 450080 times.
 900160 ull_arr[i] = DoubleToULL(arr[i]);
71 }
72
73
1/4
✓ Branch 1 taken 184 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 184 std::vector<unsigned int> count(k_radix, 0U);
74
75
2/2
✓ Branch 0 taken 1472 times.
✓ Branch 1 taken 184 times.
 1656 for (int pass = 0; pass < k_passes; ++pass) {
76
1/2
✓ Branch 0 taken 1472 times.
✗ Branch 1 not taken.
 1472 int shift = pass * k_bits_per_pass;
77
78 std::ranges::fill(count, 0U);
79
80
2/2
✓ Branch 0 taken 3600640 times.
✓ Branch 1 taken 1472 times.
 3602112 for (int i = 0; i < size; ++i) {
81 3600640 unsigned int digit = (ull_arr[i] >> shift) & (k_radix - 1);
82 3600640 ++count[digit];
83 }
84
85
2/2
✓ Branch 0 taken 375360 times.
✓ Branch 1 taken 1472 times.
 376832 for (int i = 1; i < k_radix; ++i) {
86 375360 count[i] += count[i - 1];
87 }
88
89
2/2
✓ Branch 0 taken 3600640 times.
✓ Branch 1 taken 1472 times.
 3602112 for (int i = size - 1; i >= 0; --i) {
90 3600640 unsigned int digit = (ull_arr[i] >> shift) & (k_radix - 1);
91 3600640 ull_tmp[--count[digit]] = ull_arr[i];
92 }
93
94 ull_arr.swap(ull_tmp);
95 }
96
97
2/2
✓ Branch 0 taken 450080 times.
✓ Branch 1 taken 184 times.
 450264 for (int i = 0; i < size; ++i) {
98
1/2
✓ Branch 0 taken 450080 times.
✗ Branch 1 not taken.
 900160 arr[i] = ULLToDouble(ull_arr[i]);
99 }
100 }
101
102 140 void KrymovaKLsdSortMergeDoubleTBB::MergeSections(double *left, const double *right, int left_size, int right_size) {
103
1/2
✓ Branch 1 taken 140 times.
✗ Branch 2 not taken.
 140 std::vector<double> temp(left_size);
104
1/2
✓ Branch 0 taken 140 times.
✗ Branch 1 not taken.
 140 std::ranges::copy(left, left + left_size, temp.begin());
105
106 int left_index = 0;
107 int right_index = 0;
108 int dest_index = 0;
109
110
2/2
✓ Branch 0 taken 450128 times.
✓ Branch 1 taken 140 times.
 450268 while (left_index < left_size && right_index < right_size) {
111
2/2
✓ Branch 0 taken 449728 times.
✓ Branch 1 taken 400 times.
 450128 if (temp[left_index] <= right[right_index]) {
112 449728 left[dest_index++] = temp[left_index++];
113 } else {
114 400 left[dest_index++] = right[right_index++];
115 }
116 }
117
118
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 140 times.
 540 while (left_index < left_size) {
119 400 left[dest_index++] = temp[left_index++];
120 }
121 140 }
122
123 44 void KrymovaKLsdSortMergeDoubleTBB::SortSectionsParallel(double *arr, int size, int portion) {
124 44 int num_blocks = (size + portion - 1) / portion;
125 const size_t grain_size = 1;
126 228 tbb::parallel_for(tbb::blocked_range<int>(0, num_blocks, grain_size), [&](const tbb::blocked_range<int> &range) {
127
2/2
✓ Branch 0 taken 184 times.
✓ Branch 1 taken 184 times.
 368 for (int block_index = range.begin(); block_index != range.end(); ++block_index) {
128 184 int start = block_index * portion;
129
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 184 times.
 184 int current_size = std::min(portion, size - start);
130 184 LSDSortDouble(arr + start, current_size);
131 }
132 184 });
133 44 }
134
135 44 void KrymovaKLsdSortMergeDoubleTBB::IterativeMergeSort(double *arr, int size, int portion) {
136
1/2
✓ Branch 0 taken 44 times.
✗ Branch 1 not taken.
 44 if (size <= 1) {
137 return;
138 }
139
140 44 SortSectionsParallel(arr, size, portion);
141
142
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 44 times.
 140 for (int merge_size = portion; merge_size < size; merge_size *= 2) {
143 96 int num_pairs = (size + 2 * merge_size - 1) / (2 * merge_size);
144 const size_t grain_size = 16;
145 192 tbb::parallel_for(tbb::blocked_range<int>(0, num_pairs, grain_size), [&](const tbb::blocked_range<int> &range) {
146
2/2
✓ Branch 0 taken 156 times.
✓ Branch 1 taken 96 times.
 252 for (int pair_index = range.begin(); pair_index != range.end(); ++pair_index) {
147 156 int start = pair_index * 2 * merge_size;
148 int left_size = merge_size;
149
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 132 times.
 156 int right_size = std::min(merge_size, size - (start + merge_size));
150
2/2
✓ Branch 0 taken 140 times.
✓ Branch 1 taken 16 times.
 156 if (right_size > 0) {
151 140 MergeSections(arr + start, arr + start + left_size, left_size, right_size);
152 }
153 }
154 96 });
155 }
156 }
157
158
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 4 times.
 48 bool KrymovaKLsdSortMergeDoubleTBB::RunImpl() {
159 OutType &output = GetOutput();
160 48 int size = static_cast<int>(output.size());
161
162
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 4 times.
 48 if (size <= 1) {
163 return true;
164 }
165
166 44 int portion = std::max(1, size / num_threads_);
167 portion = std::min(portion, 1000000);
168
169 44 IterativeMergeSort(output.data(), size, portion);
170
171 return true;
172 }
173
174 48 bool KrymovaKLsdSortMergeDoubleTBB::PostProcessingImpl() {
175 const OutType &output = GetOutput();
176
177
2/2
✓ Branch 0 taken 450036 times.
✓ Branch 1 taken 48 times.
 450084 for (size_t i = 1; i < output.size(); ++i) {
178
1/2
✓ Branch 0 taken 450036 times.
✗ Branch 1 not taken.
 450036 if (output[i] < output[i - 1]) {
179 return false;
180 }
181 }
182
183 return true;
184 }
185
186 } // namespace krymova_k_lsd_sort_merge_double
187