New user self-registration is disabled due to spam. Please email eigen-core-team @ lists.tuxfamily.org if you need an account.
Before reporting a bug, please make sure that your Eigen version is up-to-date!
Bug 1443 - Repetitive calls to reserveInnerVectors in SparseMatrix::insert
Summary: Repetitive calls to reserveInnerVectors in SparseMatrix::insert
Status: CONFIRMED
Alias: None
Product: Eigen
Classification: Unclassified
Component: Sparse (show other bugs)
Version: 3.4 (development)
Hardware: All All
: Normal Performance Problem
Assignee: Nobody
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2017-06-23 15:40 UTC by Gael Guennebaud
Modified: 2019-04-04 21:56 UTC (History)
4 users (show)



Attachments

Description Gael Guennebaud 2017-06-23 15:40:59 UTC
This is an issue report by Emanuel Schmid:

****************************************

The application code uses a SparseMatrix object several times with setZero() between calculations and matrices of different size (also a small one following a big one). After setZero, reserve is called with an estimate that is at least 50% too large. The coefficients are inserted in non-linear order (sadly).

Considering the end of SparseMatrix::insert():
------------
  if(m_data.size() != m_data.allocatedSize())
  {
    // make sure the matrix is compatible to random un-compressed insertion:
    m_data.resize(m_data.allocatedSize());
    this->reserveInnerVectors(Array<StorageIndex,Dynamic,1>::Constant(m_outerSize, 2));
  }

  return insertUncompressed(row,col);
}
---------------
In the situation where a smaller matrix follows a big one, that code keeps calling reserveInnerVectors from insert, because m_data.size() is never equal to m_data.allocatedSize(). There is another m_data.resize call in reserveInnerVectors, which sets the size to what was reserved. If, however, there is more space allocated from a prior run, that is not equal to allocatedSize anymore (reserve never shrinks the allocated memory).

I added a matrix.data().squeeze() call after setZero now, what reduces the load of the algorithm by 50% (all caused by reserveInnerVectors copying data).

I'm not sure if that should be called bug or if the application is somewhat border case. But maybe someone could ponder over that if-clause above and the resize call in reserveInnerVectors, maybe they could be brought into agreement also if the matrix size is smaller that allocatedSize?

****************************************
Comment 1 Gael Guennebaud 2017-06-23 15:47:19 UTC
Indeed, the condition m_data.size() != m_data.allocatedSize() is never satisfied, and reserveInnerVectors is called every time.

One solution would be to call m_data.resize(allocatedSize()) after the call to this->reserveInnerVectors(). This is equivalent to putting all the remaining allocated space to the last column.

This is not 100% optimal if someone calls reserveInnerVectors by himself, e.g.:

SparseMatrix A;

// make A huge

A.setZero();
A.resize(small,small);
A.reserveInnerVectors(....);
A.insert(...);

In this case reserveInnerVectors will still be called at the first call to insert(), but that should be OK.
Comment 2 Jan van Dijk 2019-04-04 21:56:43 UTC
Is there any plan to implement the change that was suggested by Gael above? I stumbled on this report after finding out (using valgrind) that our simulation code spent 80% of the time in reserveInnerVectors. Our use case seems to be comparable to that of Emanuel. (And also for us triplet-based matrix assembly is not practical.)

I think that most users, like me, expect more decent performance than is presently achieved when reserve_nnz is used. At present using Eigen results in 5-10 times worse performance than obtained with other matrix-vector libraries that our code can be configured to use. The one-liner change suggested above makes Eigen shine again.

Note You need to log in before you can comment on or make changes to this bug.