GCC Code Coverage Report

Directory: ./
File: tasks/kurpiakov_a_sp_comp_mat_mul/common/include/common.hpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 72 74 97.3%
Functions: 6 6 100.0%
Branches: 89 158 56.3%
Line Branch Exec Source
1 #pragma once
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <string>
7 #include <tuple>
8 #include <utility>
9 #include <vector>
10
11 #include "task/include/task.hpp"
12
13 namespace kurpiakov_a_sp_comp_mat_mul {
14
15 template <typename T>
16 class Complex {
17 public:
18 T re;
19 T im;
20
21 616 Complex() : re(T(0)), im(T(0)) {}
22
16/32
✓ Branch 2 taken 28 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 28 times.
✗ Branch 6 not taken.
✓ Branch 9 taken 28 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 28 times.
✗ Branch 13 not taken.
✓ Branch 16 taken 28 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 28 times.
✗ Branch 20 not taken.
✓ Branch 23 taken 28 times.
✗ Branch 24 not taken.
✓ Branch 26 taken 28 times.
✗ Branch 27 not taken.
✓ Branch 30 taken 28 times.
✗ Branch 31 not taken.
✓ Branch 34 taken 28 times.
✗ Branch 35 not taken.
✓ Branch 37 taken 28 times.
✗ Branch 38 not taken.
✓ Branch 41 taken 28 times.
✗ Branch 42 not taken.
✓ Branch 44 taken 28 times.
✗ Branch 45 not taken.
✓ Branch 47 taken 28 times.
✗ Branch 48 not taken.
✓ Branch 51 taken 28 times.
✗ Branch 52 not taken.
✓ Branch 54 taken 28 times.
✗ Branch 55 not taken.
 740 Complex(T r, T i) : re(r), im(i) {}
23
24 Complex operator+(const Complex &other) const {
25 return {re + other.re, im + other.im};
26 }
27
28 Complex operator-(const Complex &other) const {
29 return {re - other.re, im - other.im};
30 }
31
32 Complex operator*(const Complex &other) const {
33 504 return {(re * other.re) - (im * other.im), (re * other.im) + (im * other.re)};
34 }
35
36 Complex &operator+=(const Complex &other) {
37 504 re += other.re;
38 504 im += other.im;
39 return *this;
40 }
41
42 bool operator==(const Complex &other) const {
43 constexpr double kEps = 1e-9;
44
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 442 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 442 times.
 442 return std::abs(re - other.re) < kEps && std::abs(im - other.im) < kEps;
45 }
46
47 bool operator!=(const Complex &other) const {
48 return !(*this == other);
49 }
50 };
51
52 template <typename T>
53
1/2
✓ Branch 10 taken 280 times.
✗ Branch 11 not taken.
 6280 class CSRMatrix {
54 public:
55 int rows;
56 int cols;
57 std::vector<Complex<T>> values;
58 std::vector<int> col_indices;
59 std::vector<int> row_ptr;
60
61
1/4
✓ Branch 1 taken 1820 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 1820 CSRMatrix() : rows(0), cols(0), row_ptr(1, 0) {}
62
63
1/4
✓ Branch 1 taken 372 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 372 CSRMatrix(int r, int c) : rows(r), cols(c), row_ptr(r + 1, 0) {}
64
65 CSRMatrix(int r, int c, std::vector<Complex<T>> vals, std::vector<int> col_idx, std::vector<int> rp)
66
16/32
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 28 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 28 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 28 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 28 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 28 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 28 times.
✗ Branch 20 not taken.
✓ Branch 22 taken 28 times.
✗ Branch 23 not taken.
✓ Branch 25 taken 28 times.
✗ Branch 26 not taken.
✓ Branch 28 taken 28 times.
✗ Branch 29 not taken.
✓ Branch 31 taken 28 times.
✗ Branch 32 not taken.
✓ Branch 34 taken 28 times.
✗ Branch 35 not taken.
✓ Branch 37 taken 28 times.
✗ Branch 38 not taken.
✓ Branch 40 taken 28 times.
✗ Branch 41 not taken.
✓ Branch 43 taken 28 times.
✗ Branch 44 not taken.
✓ Branch 46 taken 28 times.
✗ Branch 47 not taken.
 672 : rows(r), cols(c), values(std::move(vals)), col_indices(std::move(col_idx)), row_ptr(std::move(rp)) {}
67
68 260 bool operator==(const CSRMatrix &other) const {
69
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 260 times.
 260 if (rows != other.rows || cols != other.cols) {
70 return false;
71 }
72
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 260 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 260 times.
 260 if (row_ptr != other.row_ptr || col_indices != other.col_indices) {
73 return false;
74 }
75
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 260 times.
 260 if (values.size() != other.values.size()) {
76 return false;
77 }
78
2/2
✓ Branch 0 taken 442 times.
✓ Branch 1 taken 260 times.
 702 for (size_t i = 0; i < values.size(); ++i) {
79 if (values[i] != other.values[i]) {
80 return false;
81 }
82 }
83 return true;
84 }
85
86 bool operator!=(const CSRMatrix &other) const {
87 return !(*this == other);
88 }
89
90 80 [[nodiscard]] CSRMatrix Multiply(const CSRMatrix &other) const {
91
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 if (cols != other.rows) {
92 ✗ return {};
93 }
94
95 80 CSRMatrix result(rows, other.cols);
96
97
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 std::vector<Complex<T>> row_acc(other.cols);
98
1/4
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 80 std::vector<bool> row_used(other.cols, false);
99
100
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 80 times.
 224 for (int i = 0; i < rows; ++i) {
101 144 std::vector<int> used_cols;
102
1/2
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
 144 used_cols.reserve(other.cols);
103
104
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 144 times.
 304 for (int ja = row_ptr[i]; ja < row_ptr[i + 1]; ++ja) {
105 160 int ka = col_indices[ja];
106 const Complex<T> &a_val = values[ja];
107
108
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 160 times.
 352 for (int jb = other.row_ptr[ka]; jb < other.row_ptr[ka + 1]; ++jb) {
109
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 192 times.
 192 int cb = other.col_indices[jb];
110 const Complex<T> &b_val = other.values[jb];
111
112
2/2
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 56 times.
 192 if (!row_used[cb]) {
113 row_used[cb] = true;
114
1/2
✓ Branch 0 taken 136 times.
✗ Branch 1 not taken.
 136 row_acc[cb] = Complex<T>();
115 used_cols.push_back(cb);
116 }
117 192 row_acc[cb] += a_val * b_val;
118 }
119 }
120
121 std::ranges::sort(used_cols);
122
123
2/2
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 144 times.
 280 for (int c : used_cols) {
124
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 128 times.
 136 result.values.push_back(row_acc[c]);
125 result.col_indices.push_back(c);
126 row_used[c] = false;
127 }
128
1/2
✓ Branch 0 taken 144 times.
✗ Branch 1 not taken.
 144 result.row_ptr[i + 1] = static_cast<int>(result.values.size());
129 }
130
131 return result;
132 80 }
133
134 private:
135 72 static void ProcessRow(int i, const CSRMatrix &self, const CSRMatrix &other, std::vector<T> &acc_re,
136 std::vector<T> &acc_im, std::vector<bool> &local_used,
137 std::vector<std::vector<Complex<T>>> &row_values,
138 std::vector<std::vector<int>> &row_col_indices) {
139 72 std::vector<int> used_cols;
140
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 used_cols.reserve(other.cols);
141
142
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 72 times.
 152 for (int ja = self.row_ptr[i]; ja < self.row_ptr[i + 1]; ++ja) {
143 80 const int ka = self.col_indices[ja];
144 80 const T a_re = self.values[ja].re;
145 80 const T a_im = self.values[ja].im;
146 80 const int jb_start = other.row_ptr[ka];
147 80 const int jb_end = other.row_ptr[ka + 1];
148
149
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 80 times.
 176 for (int jb = jb_start; jb < jb_end; ++jb) {
150
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
 96 const int cb = other.col_indices[jb];
151
2/2
✓ Branch 0 taken 68 times.
✓ Branch 1 taken 28 times.
 96 if (!local_used[cb]) {
152 local_used[cb] = true;
153
1/2
✓ Branch 0 taken 68 times.
✗ Branch 1 not taken.
 68 acc_re[cb] = T(0);
154
1/2
✓ Branch 0 taken 68 times.
✗ Branch 1 not taken.
 68 acc_im[cb] = T(0);
155 used_cols.push_back(cb);
156 }
157 96 acc_re[cb] += (a_re * other.values[jb].re) - (a_im * other.values[jb].im);
158 96 acc_im[cb] += (a_re * other.values[jb].im) + (a_im * other.values[jb].re);
159 }
160 }
161
162 std::ranges::sort(used_cols);
163
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 row_values[i].reserve(used_cols.size());
164
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 row_col_indices[i].reserve(used_cols.size());
165
166
3/4
✓ Branch 1 taken 68 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 68 times.
✓ Branch 4 taken 72 times.
 140 for (const int c : used_cols) {
167
1/2
✓ Branch 1 taken 68 times.
✗ Branch 2 not taken.
 68 row_values[i].emplace_back(acc_re[c], acc_im[c]);
168 row_col_indices[i].push_back(c);
169 local_used[c] = false;
170 }
171 72 }
172
173 public:
174 40 [[nodiscard]] CSRMatrix OMPMultiply(const CSRMatrix &other) const {
175
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40 times.
 40 if (cols != other.rows) {
176 ✗ return {};
177 }
178
179 40 CSRMatrix result(rows, other.cols);
180
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<std::vector<Complex<T>>> row_values(rows);
181
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<std::vector<int>> row_col_indices(rows);
182
183 const CSRMatrix &self = *this;
184 40 const int nrows = rows;
185 40 const int ncols = other.cols;
186
187 40 #pragma omp parallel default(none) shared(self, other, row_values, row_col_indices, nrows, ncols)
188 {
189 std::vector<T> acc_re(static_cast<std::size_t>(ncols));
190 std::vector<T> acc_im(static_cast<std::size_t>(ncols));
191 std::vector<bool> local_used(static_cast<std::size_t>(ncols), false);
192
193 #pragma omp for schedule(dynamic)
194 for (int i = 0; i < nrows; ++i) {
195 ProcessRow(i, self, other, acc_re, acc_im, local_used, row_values, row_col_indices);
196 }
197 }
198
199 int total_nnz = 0;
200
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 40 times.
 112 for (int i = 0; i < rows; ++i) {
201 72 total_nnz += static_cast<int>(row_values[i].size());
202 }
203
204
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 result.values.reserve(static_cast<std::size_t>(total_nnz));
205
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 result.col_indices.reserve(static_cast<std::size_t>(total_nnz));
206
207
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 40 times.
 112 for (int i = 0; i < rows; ++i) {
208
2/4
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 72 times.
✗ Branch 5 not taken.
 72 result.values.insert(result.values.end(), row_values[i].begin(), row_values[i].end());
209 72 result.col_indices.insert(result.col_indices.end(), row_col_indices[i].begin(), row_col_indices[i].end());
210 72 result.row_ptr[i + 1] = static_cast<int>(result.values.size());
211 }
212
213 return result;
214 40 }
215
216 [[nodiscard]] std::vector<Complex<T>> ToDense() const {
217 std::vector<Complex<T>> dense(rows * cols);
218 for (int i = 0; i < rows; ++i) {
219 for (int j = row_ptr[i]; j < row_ptr[i + 1]; ++j) {
220 dense[(i * cols) + col_indices[j]] = values[j];
221 }
222 }
223 return dense;
224 }
225 };
226
227 using ComplexD = Complex<double>;
228 using SparseMatrix = CSRMatrix<double>;
229 using InType = std::pair<SparseMatrix, SparseMatrix>;
230 using OutType = SparseMatrix;
231 using TestType = std::tuple<InType, std::string, OutType>;
232 using BaseTask = ppc::task::Task<InType, OutType>;
233
234 } // namespace kurpiakov_a_sp_comp_mat_mul
235