Improve performance of MatrixIndexSet
This improves performance of MatrixIndexSet
significantly by two changes:
-
Replace the
std::set
used to store the column indices for each rows by astd::vector
based implementation. Thestd::vector
is kept sorted when inserting such that we can avoid duplicates. In the worst case (reverse order insertion) this may lead to O(n^2) complexity when inserting n entries in a row compared to O(n log(n)) forstd::set
. However, the sortedstd::vector
implementation still wins for relatively large n. To avoid the worst case complexity when using very dense rows, the implementation automatically switches tostd::set
if the size exceeds the threshold valuemaxVectorSize
. The defaultmaxVectorSize=2048
was selected based on benchmark results. -
Change the stored index type from
std::size_t
touint32_t
to reduce memory consumption and improve performance. Notice that this excludes exceptionally large matrices with more than 2^32 columns that worked before. To give an estimate on the influence of this: If you want to build a squareBCRSMatrix
with 2^32 rows and two entries per row using the oldMatrixIndexSet
implementation this alone would need more than 0.5 TB memory. One could make the index type a template parameter, but this would be a breaking interface change. -
Additionally this MR adds documentation of the thread safety of
MatrixIndexSet
. While this does not change any code, it is strictly speaking an interface change, because it introduces public guarantees that have been implementation details before. Hence you can no longer relax these guarantees (e.g. to change the implementation from row- to column-major) without breaking compatibility. However, it's IMO important to make these guarantees, because without them you cannot do multi-threaded assembly. (Notice that the 'implicit' build mode ofBCRSMatrix
is e.g. not thread safe.)