Debian Codegraph @

dune/istl/matrixindexset.hh

raw
1 // SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root
2 // SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
3 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
4 // vi: set et ts=4 sw=2 sts=2:
5 #ifndef DUNE_ISTL_MATRIXINDEXSET_HH
6 #define DUNE_ISTL_MATRIXINDEXSET_HH
7
8 #include <algorithm>
9 #include <cstddef>
10 #include <cstdint>
11 #include <set>
12 #include <variant>
13 #include <vector>
14
15 #include <dune/common/overloadset.hh>
16
17 namespace Dune {
18
19 namespace Impl {
20
21 /**
22 * @class RowIndexSet
23 * @brief Manages a set of row indices with efficient insertion and lookup operations.
24 *
25 * This class provides a flexible and efficient way to store and manage
26 * row indices, supporting both vector and set storage types. It automatically
27 * switches between these storage types based on the number of indices to
28 * optimize performance for different use cases.
29 *
30 * @details
31 * The `RowIndexSet` class uses a `std::variant` to store row indices either as
32 * a `std::vector` or a `std::set`. The vector storage is used initially for
33 * its cache-friendly properties and efficient iteration, while the set storage
34 * is used when the number of indices exceeds a specified threshold
35 * (`maxVectorSize`), providing efficient insertion and lookup operations.
36 *
37 * This class is not thread safe in the sense that inserting several column
38 * indices leads to a data race.
39 */
40 class RowIndexSet {
41 using Index = std::uint_least32_t;
42 class Vector : public std::vector<Index> {
43 // store max size within class so that variant uses less memory
44 size_type maxVectorSize_;
45 friend class RowIndexSet;
46 };
47
48 //! \brief Maximum vector size for a given vector.
49 static Index getMaxVectorSize(const RowIndexSet::Vector& v) {
50 return v.maxVectorSize_;
51 }
52
53 public:
54 using size_type = Index;
55
56 /**
57 * \brief Default value for maxVectorSize
58 *
59 * This was selected after benchmarking for the worst case
60 * of reverse insertion of column indices. In many applications
61 * this works well. There's no need to use a different value
62 * unless you have many dense rows with more than defaultMaxVectorSize
63 * nonzero entries. Even in this case defaultMaxVectorSize may work
64 * well and a finding a better value may require careful
65 * benchmarking.
66 */
67 static constexpr size_type defaultMaxVectorSize = 2048;
68
69 /**
70 * @brief Constructs a RowIndexSet with a specified maximum vector size.
71 *
72 * @param maxVectorSize The maximum number of indices to store in a
73 * vector before switching to set storage.
74 */
75 RowIndexSet(size_type maxVectorSize = defaultMaxVectorSize) : storage_{Vector()}
76 {
77 std::get<Vector>(storage_).maxVectorSize_ = maxVectorSize;
78 }
79
80 /**
81 * @brief Inserts a column index into the row index set.
82 *
83 * This function inserts a column index into the row index set, automatically
84 * switching to set storage if the maximum vector size is exceeded.
85 *
86 * @param col The column index to insert.
87 */
88 void insert(size_type col){
89 std::visit(Dune::overload(
90 // If row is stored as set, call insert directly
91 [&](std::set<size_type>& set) {
92 set.insert(col);
93 },
94 // If row is stored as vector only insert directly
95 // if maxVectorSize_ is not reached. Otherwise switch
96 // to set storage first.
97 [&](Vector& sortedVector) {
98 auto it = std::lower_bound(sortedVector.cbegin(), sortedVector.cend(), col);
99 if (it == sortedVector.cend() or (*it != col)) {
100 if (sortedVector.size() < getMaxVectorSize(sortedVector)) {
101 sortedVector.insert(it, col);
102 } else {
103 std::set<size_type> set(sortedVector.cbegin(), sortedVector.cend());
104 set.insert(col);
105 storage_ = std::move(set);
106 }
107 }
108 }
109 ), storage_);
110 }
111
112 /**
113 * @brief Checks if the row index set contains a specific column index.
114 *
115 * @param col The column index to check.
116 * @return True if the column index is present in the row index set, false otherwise.
117 */
118 bool contains(const Index& col) const {
119 return std::visit(Dune::overload(
120 [&](const std::set<Index>& set) {
121 return set.contains(col);
122 },
123 [&](const std::vector<Index>& sortedVector) {
124 return std::binary_search(sortedVector.cbegin(), sortedVector.cend(), col);
125 }
126 ), storage_);
127 }
128
129 /**
130 * @brief Returns the current storage of row indices.
131 *
132 * @return A constant reference to the storage variant containing the row indices.
133 */
134 const auto& storage() const {
135 return storage_;
136 }
137
138 /**
139 * @brief Returns the number of row indices in the set.
140 *
141 * @return The number of row indices.
142 */
143 size_type size() const {
144 return std::visit([&](const auto& rowIndices) {
145 return rowIndices.size();
146 }, storage_);
147 }
148
149 /**
150 * @brief Clears all row indices from the set.
151 */
152 void clear() {
153 std::visit([&](auto& rowIndices) {
154 rowIndices.clear();
155 }, storage_);
156 }
157
158 private:
159 std::variant<Vector, std::set<Index>> storage_;
160 };
161 }
162
163
164 /**
165 * \brief Stores the nonzero entries for creating a sparse matrix
166 *
167 * This stores std::set-like container for the column index
168 * of each row. A sorted std::vector is used for this container
169 * up to a customizable maxVectorSize. If this size is exceeded,
170 * storage of the corresponding row is switched to std::set.
171 *
172 * The default value for maxVectorSize works well and ensures
173 * that the slow std::set fallback is only used for very
174 * dense rows.
175 *
176 * This class is thread safe in the sense that concurrent calls
177 * to all const methods and furthermore to add(row,col) with different
178 * rows in each thread are safe.
179 */
180 class MatrixIndexSet
181 {
182 public:
183 using size_type = typename Impl::RowIndexSet::size_type;
184
185 /**
186 * \brief Default value for maxVectorSize
187 *
188 * This was selected after benchmarking for the worst case
189 * of reverse insertion of column indices. In many applications
190 * this works well. There's no need to use a different value
191 * unless you have many dense rows with more than defaultMaxVectorSize
192 * nonzero entries. Even in this case defaultMaxVectorSize may work
193 * well and a finding a better value may require careful
194 * benchmarking.
195 */
196 static constexpr size_type defaultMaxVectorSize = Impl::RowIndexSet::defaultMaxVectorSize;
197
198 /**
199 * \brief Constructor with custom maxVectorSize
200 *
201 * \param maxVectorSize Maximal size for stored row vector (default is defaultMaxVectorSize).
202 */
203 MatrixIndexSet(size_type maxVectorSize=defaultMaxVectorSize) noexcept : rows_(0), cols_(0), maxVectorSize_(maxVectorSize)
204 {}
205
206 /**
207 * \brief Constructor setting the matrix size
208 *
209 * \param rows Number of matrix rows
210 * \param cols Number of matrix columns
211 * \param maxVectorSize Maximal size for stored row vector (default is defaultMaxVectorSize).
212 */
213 MatrixIndexSet(size_type rows, size_type cols, size_type maxVectorSize=defaultMaxVectorSize) : rows_(rows), cols_(cols), maxVectorSize_(maxVectorSize)
214 {
215 indices_.resize(rows_, Impl::RowIndexSet(maxVectorSize_));
216 }
217
218 /** \brief Reset the size of an index set */
219 void resize(size_type rows, size_type cols) {
220 rows_ = rows;
221 cols_ = cols;
222 indices_.resize(rows_, Impl::RowIndexSet(maxVectorSize_));
223 }
224
225 /**
226 * \brief Add an index to the index set
227 *
228 * It is safe to call add(row, col) for different rows in concurrent threads,
229 * but it is not safe to do concurrent calls for the same row, even for different
230 * columns.
231 */
232 void add(size_type row, size_type col) {
233 indices_[row].insert(col);
234 }
235
236 /** \brief Return the number of entries */
237 size_type size() const {
238 size_type entries = 0;
239 for (size_type i=0; i<rows_; i++)
240 entries += rowsize(i);
241 return entries;
242 }
243
244 /** \brief Return the number of rows */
245 size_type rows() const {return rows_;}
246
247 /** \brief Return the number of columns */
248 size_type cols() const {return cols_;}
249
250 /**
251 * \brief Return column indices of entries in given row
252 *
253 * This returns a range of all column indices
254 * that have been added for the given column.
255 * Since there are different internal implementations
256 * of this range, the result is stored in a std::variant<...>
257 * which has to be accessed using `std::visit`.
258 */
259 const auto& columnIndices(size_type row) const {
260 return indices_[row].storage();
261 }
262
263 /** \brief Return the number of entries in a given row */
264 size_type rowsize(size_type row) const {
265 return indices_[row].size();
266 }
267
268 /** \brief Import all nonzero entries of a sparse matrix into the index set
269 \tparam MatrixType Needs to be BCRSMatrix<...>
270 \param m reference to the MatrixType object
271 \param rowOffset don't write to rows<rowOffset
272 \param colOffset don't write to cols<colOffset
273 */
274 template <class MatrixType>
275 void import(const MatrixType& m, size_type rowOffset=0, size_type colOffset=0) {
276
277 typedef typename MatrixType::row_type RowType;
278 typedef typename RowType::ConstIterator ColumnIterator;
279
280 for (size_type rowIdx=0; rowIdx<m.N(); rowIdx++) {
281
282 const RowType& row = m[rowIdx];
283
284 ColumnIterator cIt = row.begin();
285 ColumnIterator cEndIt = row.end();
286
287 for(; cIt!=cEndIt; ++cIt)
288 add(rowIdx+rowOffset, cIt.index()+colOffset);
289
290 }
291
292 }
293
294 /** \brief Initializes a BCRSMatrix with the indices contained
295 in this MatrixIndexSet
296 \tparam MatrixType Needs to be BCRSMatrix<...>
297 \param matrix reference to the MatrixType object
298 */
299 template <class MatrixType>
300 void exportIdx(MatrixType& matrix) const {
301
302 matrix.setSize(rows_, cols_);
303 matrix.setBuildMode(MatrixType::random);
304
305 for (size_type row=0; row<rows_; row++)
306 matrix.setrowsize(row, rowsize(row));
307
308 matrix.endrowsizes();
309
310 for (size_type row=0; row<rows_; row++) {
311 std::visit([&](const auto& rowIndices) {
312 matrix.setIndicesNoSort(row, rowIndices.begin(), rowIndices.end());
313 }, indices_[row].storage());
314 }
315
316 matrix.endindices();
317
318 }
319
320 private:
321
322 std::vector<Impl::RowIndexSet> indices_;
323
324 size_type rows_, cols_;
325 size_type maxVectorSize_;
326
327 };
328
329
330 } // end namespace Dune
331
332 #endif