GCC Code Coverage Report

Directory: ./
File: tasks/akhmetov_daniil_strassen_dense_double/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 70 183 38.3%
Functions: 9 21 42.9%
Branches: 46 200 23.0%
Line Branch Exec Source
1 #include "akhmetov_daniil_strassen_dense_double/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <future>
6 #include <vector>
7
8 #include "akhmetov_daniil_strassen_dense_double/common/include/common.hpp"
9 #include "util/include/util.hpp"
10
11 namespace akhmetov_daniil_strassen_dense_double {
12
13 namespace {
14
15 constexpr std::size_t kCutoff = 256;
16 constexpr std::size_t kBlockSize = 64;
17 constexpr std::size_t kThreshold = 64;
18
19 std::size_t NextPow2(std::size_t x) {
20 if (x <= 1) {
21 return 1;
22 }
23 std::size_t p = 1;
24
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 16 times.
 136 while (p < x) {
25 120 p <<= 1;
26 }
27 return p;
28 }
29
30 void ZeroMatrix(double *dst, std::size_t stride, std::size_t n) {
31
2/2
✓ Branch 0 taken 3072 times.
✓ Branch 1 taken 16 times.
 3088 for (std::size_t i = 0; i < n; ++i) {
32 3072 std::fill_n(dst + (i * stride), n, 0.0);
33 }
34 }
35
36 ✗ void AddToBuffer(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *dst,
37 std::size_t n, double b_coeff) {
38 ✗ for (std::size_t i = 0; i < n; ++i) {
39 ✗ const double *a_row = a + (i * a_stride);
40 ✗ const double *b_row = b + (i * b_stride);
41 ✗ double *dst_row = dst + (i * n);
42 ✗ for (std::size_t j = 0; j < n; ++j) {
43 ✗ dst_row[j] = a_row[j] + (b_coeff * b_row[j]);
44 }
45 }
46 ✗ }
47
48 void MulMicroBlock(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *c,
49 std::size_t c_stride, std::size_t i_begin, std::size_t i_end, std::size_t k_begin, std::size_t k_end,
50 std::size_t j_begin, std::size_t j_end) {
51
2/2
✓ Branch 0 taken 36864 times.
✓ Branch 1 taken 576 times.
 37440 for (std::size_t i = i_begin; i < i_end; ++i) {
52 36864 double *c_row = c + (i * c_stride);
53 36864 const double *a_row = a + (i * a_stride);
54
2/2
✓ Branch 0 taken 2359296 times.
✓ Branch 1 taken 36864 times.
 2396160 for (std::size_t k = k_begin; k < k_end; ++k) {
55 2359296 const double aik = a_row[k];
56 2359296 const double *b_row = b + (k * b_stride);
57
2/2
✓ Branch 0 taken 150994944 times.
✓ Branch 1 taken 2359296 times.
 153354240 for (std::size_t j = j_begin; j < j_end; ++j) {
58 150994944 c_row[j] += aik * b_row[j];
59 }
60 }
61 }
62 }
63
64 160 void MulJBlocks(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *c,
65 std::size_t c_stride, std::size_t n, std::size_t ii, std::size_t i_end, std::size_t kk,
66 std::size_t k_end) {
67
2/2
✓ Branch 0 taken 576 times.
✓ Branch 1 taken 160 times.
 736 for (std::size_t jj = 0; jj < n; jj += kBlockSize) {
68 576 const std::size_t j_end = std::min(jj + kBlockSize, n);
69 MulMicroBlock(a, a_stride, b, b_stride, c, c_stride, ii, i_end, kk, k_end, jj, j_end);
70 }
71 160 }
72
73 void MulKBlocks(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *c,
74 std::size_t c_stride, std::size_t n, std::size_t ii, std::size_t i_end) {
75
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 48 times.
 208 for (std::size_t kk = 0; kk < n; kk += kBlockSize) {
76 160 const std::size_t k_end = std::min(kk + kBlockSize, n);
77 160 MulJBlocks(a, a_stride, b, b_stride, c, c_stride, n, ii, i_end, kk, k_end);
78 }
79 }
80
81 16 void NaiveMulBlocked(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *c,
82 std::size_t c_stride, std::size_t n) {
83 16 ZeroMatrix(c, c_stride, n);
84
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 for (std::size_t ii = 0; ii < n; ii += kBlockSize) {
85 48 const std::size_t i_end = std::min(ii + kBlockSize, n);
86 MulKBlocks(a, a_stride, b, b_stride, c, c_stride, n, ii, i_end);
87 }
88 16 }
89
90 ✗ void CombineQuadrants(const std::vector<double> &m1, const std::vector<double> &m2, const std::vector<double> &m3,
91 const std::vector<double> &m4, const std::vector<double> &m5, const std::vector<double> &m6,
92 const std::vector<double> &m7, double *c, std::size_t c_stride, std::size_t half) {
93 ✗ for (std::size_t i = 0; i < half; ++i) {
94 ✗ double *c11 = c + (i * c_stride);
95 double *c12 = c11 + half;
96 ✗ double *c21 = c + ((i + half) * c_stride);
97 double *c22 = c21 + half;
98
99 ✗ const double *m1_row = m1.data() + (i * half);
100 const double *m2_row = m2.data() + (i * half);
101 const double *m3_row = m3.data() + (i * half);
102 const double *m4_row = m4.data() + (i * half);
103 const double *m5_row = m5.data() + (i * half);
104 const double *m6_row = m6.data() + (i * half);
105 const double *m7_row = m7.data() + (i * half);
106
107 ✗ for (std::size_t j = 0; j < half; ++j) {
108 ✗ c11[j] = m1_row[j] + m4_row[j] - m5_row[j] + m7_row[j];
109 ✗ c12[j] = m3_row[j] + m5_row[j];
110 ✗ c21[j] = m2_row[j] + m4_row[j];
111 ✗ c22[j] = m1_row[j] - m2_row[j] + m3_row[j] + m6_row[j];
112 }
113 }
114 ✗ }
115
116 using StrassenFn = void (*)(const double *, std::size_t, const double *, std::size_t, double *, std::size_t,
117 std::size_t);
118 void StrassenSeqImpl(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *c,
119 std::size_t c_stride, std::size_t n);
120 constexpr StrassenFn kStrassenSeqFn = &StrassenSeqImpl;
121
122 ✗ void ComputeProduct(const double *a1, std::size_t a1_stride, const double *a2, std::size_t a2_stride, double a2_coeff,
123 const double *b1, std::size_t b1_stride, const double *b2, std::size_t b2_stride, double b2_coeff,
124 std::vector<double> &out, std::size_t n) {
125 ✗ std::vector<double> lhs(n * n);
126 ✗ std::vector<double> rhs(n * n);
127 ✗ AddToBuffer(a1, a1_stride, a2, a2_stride, lhs.data(), n, a2_coeff);
128 ✗ AddToBuffer(b1, b1_stride, b2, b2_stride, rhs.data(), n, b2_coeff);
129 ✗ out.assign(n * n, 0.0);
130 ✗ kStrassenSeqFn(lhs.data(), n, rhs.data(), n, out.data(), n, n);
131 ✗ }
132
133 ✗ void ComputeProductSingle(const double *a, std::size_t a_stride, const double *b1, std::size_t b1_stride,
134 const double *b2, std::size_t b2_stride, double b2_coeff, std::vector<double> &out,
135 std::size_t n) {
136 ✗ std::vector<double> rhs(n * n);
137 ✗ AddToBuffer(b1, b1_stride, b2, b2_stride, rhs.data(), n, b2_coeff);
138 ✗ out.assign(n * n, 0.0);
139 ✗ kStrassenSeqFn(a, a_stride, rhs.data(), n, out.data(), n, n);
140 ✗ }
141
142 ✗ void ComputeProductSingleLeft(const double *a1, std::size_t a1_stride, const double *a2, std::size_t a2_stride,
143 double a2_coeff, const double *b, std::size_t b_stride, std::vector<double> &out,
144 std::size_t n) {
145 ✗ std::vector<double> lhs(n * n);
146 ✗ AddToBuffer(a1, a1_stride, a2, a2_stride, lhs.data(), n, a2_coeff);
147 ✗ out.assign(n * n, 0.0);
148 ✗ kStrassenSeqFn(lhs.data(), n, b, b_stride, out.data(), n, n);
149 ✗ }
150
151 16 void StrassenTopStl(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *c,
152 std::size_t c_stride, std::size_t n) {
153
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 if (n <= kCutoff || ppc::util::GetNumThreads() <= 1) {
154 16 kStrassenSeqFn(a, a_stride, b, b_stride, c, c_stride, n);
155 16 return;
156 }
157
158 ✗ const std::size_t half = n / 2;
159
160 ✗ const double *a11 = a;
161 ✗ const double *a12 = a + half;
162 ✗ const double *a21 = a + (half * a_stride);
163 ✗ const double *a22 = a21 + half;
164
165 ✗ const double *b11 = b;
166 ✗ const double *b12 = b + half;
167 ✗ const double *b21 = b + (half * b_stride);
168 ✗ const double *b22 = b21 + half;
169
170 ✗ std::vector<double> m1;
171 ✗ std::vector<double> m2;
172 ✗ std::vector<double> m3;
173 ✗ std::vector<double> m4;
174 ✗ std::vector<double> m5;
175 ✗ std::vector<double> m6;
176 ✗ std::vector<double> m7;
177
178 ✗ auto f1 = std::async(std::launch::async, [&] {
179 ✗ ComputeProduct(a11, a_stride, a22, a_stride, 1.0, b11, b_stride, b22, b_stride, 1.0, m1, half);
180 ✗ });
181 auto f2 = std::async(std::launch::async,
182 ✗ [&] { ComputeProductSingleLeft(a21, a_stride, a22, a_stride, 1.0, b11, b_stride, m2, half); });
183 auto f3 = std::async(std::launch::async,
184 ✗ [&] { ComputeProductSingle(a11, a_stride, b12, b_stride, b22, b_stride, -1.0, m3, half); });
185 auto f4 = std::async(std::launch::async,
186 ✗ [&] { ComputeProductSingle(a22, a_stride, b21, b_stride, b11, b_stride, -1.0, m4, half); });
187 auto f5 = std::async(std::launch::async,
188 ✗ [&] { ComputeProductSingleLeft(a11, a_stride, a12, a_stride, 1.0, b22, b_stride, m5, half); });
189 ✗ auto f6 = std::async(std::launch::async, [&] {
190 ✗ ComputeProduct(a21, a_stride, a11, a_stride, -1.0, b11, b_stride, b12, b_stride, 1.0, m6, half);
191 ✗ });
192 ✗ auto f7 = std::async(std::launch::async, [&] {
193 ✗ ComputeProduct(a12, a_stride, a22, a_stride, -1.0, b21, b_stride, b22, b_stride, 1.0, m7, half);
194 ✗ });
195
196 ✗ f1.get();
197 ✗ f2.get();
198 ✗ f3.get();
199 ✗ f4.get();
200 ✗ f5.get();
201 ✗ f6.get();
202 ✗ f7.get();
203
204 ✗ CombineQuadrants(m1, m2, m3, m4, m5, m6, m7, c, c_stride, half);
205 }
206
207 16 void StrassenSeqImpl(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *c,
208 std::size_t c_stride, std::size_t n) {
209
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 if (n <= kCutoff) {
210 16 NaiveMulBlocked(a, a_stride, b, b_stride, c, c_stride, n);
211 16 return;
212 }
213
214 ✗ const std::size_t half = n / 2;
215
216 const double *a11 = a;
217 ✗ const double *a12 = a + half;
218 ✗ const double *a21 = a + (half * a_stride);
219 ✗ const double *a22 = a21 + half;
220
221 const double *b11 = b;
222 ✗ const double *b12 = b + half;
223 ✗ const double *b21 = b + (half * b_stride);
224 ✗ const double *b22 = b21 + half;
225
226 ✗ std::vector<double> m1(half * half);
227 ✗ std::vector<double> m2(half * half);
228 ✗ std::vector<double> m3(half * half);
229 ✗ std::vector<double> m4(half * half);
230 ✗ std::vector<double> m5(half * half);
231 ✗ std::vector<double> m6(half * half);
232 ✗ std::vector<double> m7(half * half);
233 ✗ std::vector<double> lhs(half * half);
234 ✗ std::vector<double> rhs(half * half);
235
236 ✗ AddToBuffer(a11, a_stride, a22, a_stride, lhs.data(), half, 1.0);
237 ✗ AddToBuffer(b11, b_stride, b22, b_stride, rhs.data(), half, 1.0);
238 ✗ kStrassenSeqFn(lhs.data(), half, rhs.data(), half, m1.data(), half, half);
239
240 ✗ AddToBuffer(a21, a_stride, a22, a_stride, lhs.data(), half, 1.0);
241 ✗ kStrassenSeqFn(lhs.data(), half, b11, b_stride, m2.data(), half, half);
242
243 ✗ AddToBuffer(b12, b_stride, b22, b_stride, rhs.data(), half, -1.0);
244 ✗ kStrassenSeqFn(a11, a_stride, rhs.data(), half, m3.data(), half, half);
245
246 ✗ AddToBuffer(b21, b_stride, b11, b_stride, rhs.data(), half, -1.0);
247 ✗ kStrassenSeqFn(a22, a_stride, rhs.data(), half, m4.data(), half, half);
248
249 ✗ AddToBuffer(a11, a_stride, a12, a_stride, lhs.data(), half, 1.0);
250 ✗ kStrassenSeqFn(lhs.data(), half, b22, b_stride, m5.data(), half, half);
251
252 ✗ AddToBuffer(a21, a_stride, a11, a_stride, lhs.data(), half, -1.0);
253 ✗ AddToBuffer(b11, b_stride, b12, b_stride, rhs.data(), half, 1.0);
254 ✗ kStrassenSeqFn(lhs.data(), half, rhs.data(), half, m6.data(), half, half);
255
256 ✗ AddToBuffer(a12, a_stride, a22, a_stride, lhs.data(), half, -1.0);
257 ✗ AddToBuffer(b21, b_stride, b22, b_stride, rhs.data(), half, 1.0);
258 ✗ kStrassenSeqFn(lhs.data(), half, rhs.data(), half, m7.data(), half, half);
259
260 ✗ CombineQuadrants(m1, m2, m3, m4, m5, m6, m7, c, c_stride, half);
261 }
262
263 } // namespace
264
265
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 AkhmetovDStrassenDenseDoubleSTL::AkhmetovDStrassenDenseDoubleSTL(const InType &in) {
266 SetTypeOfTask(GetStaticTypeOfTask());
267
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GetInput() = in;
268 24 }
269
270
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 bool AkhmetovDStrassenDenseDoubleSTL::ValidationImpl() {
271 const auto &input = GetInput();
272
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (input.empty()) {
273 return false;
274 }
275 24 const size_t n = format::GetN(input);
276
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (n == 0) {
277 return false;
278 }
279 24 const size_t expected_size = 1 + (2 * n * n);
280 24 return input.size() == expected_size;
281 }
282
283 24 bool AkhmetovDStrassenDenseDoubleSTL::PreProcessingImpl() {
284 const auto &input = GetInput();
285 24 const size_t n = format::GetN(input);
286 24 GetOutput().assign(n * n, 0.0);
287 24 return true;
288 }
289
290 24 bool AkhmetovDStrassenDenseDoubleSTL::RunImpl() {
291 const auto &input = GetInput();
292 auto &output = GetOutput();
293
294 24 const std::size_t n = format::GetN(input);
295 24 const Matrix a = format::GetA(input);
296
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 const Matrix b = format::GetB(input);
297
298
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 16 times.
 24 if (n <= kThreshold) {
299
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 output = Matrix(n * n, 0.0);
300
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 8 times.
 520 for (std::size_t i = 0; i < n; ++i) {
301
2/2
✓ Branch 0 taken 32768 times.
✓ Branch 1 taken 512 times.
 33280 for (std::size_t k = 0; k < n; ++k) {
302
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32768 times.
 32768 const double aik = a.at((i * n) + k);
303
2/2
✓ Branch 0 taken 2097152 times.
✓ Branch 1 taken 32768 times.
 2129920 for (std::size_t j = 0; j < n; ++j) {
304
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 2097152 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2097152 times.
 2097152 output.at((i * n) + j) += aik * b.at((k * n) + j);
305 }
306 }
307 }
308 return true;
309 }
310
311
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if ((n % 2U) != 0U) {
312 ✗ output.assign(n * n, 0.0);
313 ✗ NaiveMulBlocked(a.data(), n, b.data(), n, output.data(), n, n);
314 ✗ return true;
315 }
316
317 const std::size_t padded = NextPow2(n);
318
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 Matrix a_pad(padded * padded, 0.0);
319
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 Matrix b_pad(padded * padded, 0.0);
320
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 Matrix c_pad(padded * padded, 0.0);
321
322
2/2
✓ Branch 0 taken 3072 times.
✓ Branch 1 taken 16 times.
 3088 for (std::size_t i = 0; i < n; ++i) {
323 3072 std::copy_n(a.data() + (i * n), n, a_pad.data() + (i * padded));
324 3072 std::copy_n(b.data() + (i * n), n, b_pad.data() + (i * padded));
325 }
326
327
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 StrassenTopStl(a_pad.data(), padded, b_pad.data(), padded, c_pad.data(), padded, padded);
328
329
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 output.assign(n * n, 0.0);
330
2/2
✓ Branch 0 taken 3072 times.
✓ Branch 1 taken 16 times.
 3088 for (std::size_t i = 0; i < n; ++i) {
331 3072 std::copy_n(c_pad.data() + (i * padded), n, output.data() + (i * n));
332 }
333
334 return true;
335 }
336
337 24 bool AkhmetovDStrassenDenseDoubleSTL::PostProcessingImpl() {
338 const auto &input = GetInput();
339 24 const size_t n = format::GetN(input);
340 24 return GetOutput().size() == n * n;
341 }
342
343 } // namespace akhmetov_daniil_strassen_dense_double
344