change insert strategy

Reference issue

What does this implement/fix?

Previously, it was reported that repeatedly calling insert on a large compressed sparse matrix was slow. This is expected as the user is repeatedly performing sorted insertions. However, this appears to be a common usage pattern.

This MR changes insertAtByOuterInner , which pertains to insert and coeffRef, and will now always uncompress the matrix (a no-op if already uncompressed) and call insertUncompressedAtByOuterInner. Users may still opt to call insertCompressed() if they do not want their matrix to be uncompressed, which can still be useful if inserting a few elements or only pushing to back.

If insertUncompressedAtByOuterInner fails to find a vector with capacity, each vector's capacity will increase to a minimum of two to avoid future reallocations and reduce insertion times. This strategy can be tuned two ways:

• change kReserveSizePerVector from 2 to some other number, like 10, or a complex expression like reserve(IndexVector::AlignedMapType(outerSize(), innerNonZeroPtr()) (possibly double the reserve size of each vector!)
• instead of searching from outer to outerSize() for insertion capacity, limit the search e.g. outer + 2 to avoid lengthy searches

This may remediate some issues with users calling insert in a loop. However, it is still best to call reserve, e.g. reserve(VectorXi::Constant(10)) rather than rely on this heuristic.

Additional information