Skip to content

Improve performance of MatrixIndexSet

Carsten Gräser requested to merge feature/improve-matrixindexset into master

This improves performance of MatrixIndexSet significantly by two changes:

  • Replace the std::set used to store the column indices for each rows by a std::vector based implementation. The std::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)) for std::set. However, the sorted std::vector implementation still wins for relatively large n. To avoid the worst case complexity when using very dense rows, the implementation automatically switches to std::set if the size exceeds the threshold value maxVectorSize. The default maxVectorSize=2048 was selected based on benchmark results.

  • Change the stored index type from std::size_t to uint32_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 square BCRSMatrix with 2^32 rows and two entries per row using the old MatrixIndexSet 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 of BCRSMatrix is e.g. not thread safe.)

Edited by Carsten Gräser

Merge request reports