Improve performance of MatrixIndexSet
This improves performance of MatrixIndexSet significantly by two changes:
-
Replace the
std::setused to store the column indices for each rows by astd::vectorbased implementation. Thestd::vectoris 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::vectorimplementation still wins for relatively large n. To avoid the worst case complexity when using very dense rows, the implementation automatically switches tostd::setif the size exceeds the threshold valuemaxVectorSize. The defaultmaxVectorSize=2048was selected based on benchmark results. -
Change the stored index type from
std::size_ttouint32_tto 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 squareBCRSMatrixwith 2^32 rows and two entries per row using the oldMatrixIndexSetimplementation 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 ofBCRSMatrixis e.g. not thread safe.)