I've to allocate a huge sparse matrix (800.000.000 x 800.000.000) which has to be filled afterwards.
From a data inspection (Market files) the allocation per row (col) is precomputed and the required memory is allocated.
Afterwards in a first phase a big amount of inserts is done (~35.000.000.000) which ran in acceptable time (~24hrs).
In a second phase additional elements have to be added to the matrix but an overlapping with already existing entries is possible.
Hence coeffRef is used. For these elements the memory requirements are also known and pre-allocated in the first step.
Thus the matrix has after allocation the final memory consume reached. As far as I noticed there is no re-allocation done. (Maybe resorting)
It showed up that coeffRef performs extremely slow its task. (15.000 coeffs / 24 hrs)
Is there an optimization or a low effort adaptation to OpenMP available?
I think the slow down results from the search and index re-computation after an insert but I'm not really sure.

-
Martin

hm, perhaps you exceeded the physical memory available and the system allocated memory on the harddrive (swap) ? Also make sure that you compiled with optimizations ON (e.g., -O2 with gcc or clang).

Anyway, Eigen is not really tailored to handle such huge matrices which can only be properly handled by clusters through distributed storage and algorithms.

btw, when reserving memory, you must use the following version of the reserve method: http://eigen.tuxfamily.org/dox/classEig ... f2487fb596 , otherwise the memory will be allocated at the end of the entries and each insertion will trigger a copy of all elements following it.

>hm, perhaps you exceeded the physical memory available and the system allocated memory on the harddrive (swap) ?
the memory is available as RAM and the matrix seems to be allocated there. As far as you believe htop.

>Also make sure that you compiled with optimizations ON (e.g., -O2 with gcc or clang).
The optimization is switched on, but I think -O3 is used.

>Anyway, Eigen is not really tailored to handle such huge matrices which can only be properly handled by clusters through distributed storage and algorithms.
This is a necessary (last) step in processing many small matrices. Normally there are much less elements handled, only the dimensions are keppt and equal.

>btw, when reserving memory, you must use the following version of the reserve method:
Exactly this method is used, with a vector as argument. The vector stores the precomputed row-wise NNZs.
During program it's noticeable that the matrix seems to be completely allocated at the beginning. There is no big difference detectable in memory consume during run.

I only wonder that inserts (pre-sorted) run in acceptable time but coeffRef takes, compared to insert, extremely long.

that's rather strange as coeffRef is only doing a binary search within the given row before calling insert if needed. Have you tried a much smaller problem, like 1000 times smaller? In that case do you still get a very slow rate? If everything is really properly allocated in RAM, then the rate of coeffRef should be in the order of 1 million per second.

>that's rather strange as coeffRef is only doing a binary search within the given row before calling insert if needed.
I thought for an insert in an existing vector the indexes for sparse representation have to be recomputed an data has to be shifted,
even if the vector space is pre allocated.
Does this also count when an addition is done with coeffref like:
coeffref(x,y) += value;

>Have you tried a much smaller problem, like 1000 times smaller?
>In that case do you still get a very slow rate?
Not really! My experimental test-data for program testing is very small, there it work fine. but for such few data entires time its hard to measure with out instrumentation.

>If everything is really properly allocated in RAM, then the rate of coeffRef should be in the order of 1 million per second.
That's exactly the point, After reserve() HTOP shows that RAM is virtual allocated and not RES (physically).
But after the insert phase the complete matrix is physically allocated in RAM. There is no reallocation done.

I'm seeing this same symptom too. Was there ever any resolution found?

For reference, I'm accumulating values in my matrix the following way:

Code: Select all

int N = 30000;
SparseMatrix<double> A(N, N);
A.reserve(VectorXi::Constant(N, 8));
for (...) {
  A.coeffRef(i, j) += value;
}


Am I missing something?

Make sure that (1) you compile with compiler optimization ON ("release mode", or -O3), and (2) that the number of inserted coefficients per column is indeed smaller than 8, otherwise increase it to the maximal number of non-zeros per column. Finally, it is often faster to "push_back" triplets to a vector and then let Eigen does the job with setFromTriplets.