| 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 |