# Adding three integer sparse matrices is very slow. Adding only two is fast

Bug introduced in 9.0.0 and fixed in 10.0.0

Adding more than two sparse matrices in one step in Mathematica 9 is very slow (in fact I couldn't even wait for it to finish).

Here's an example. Let's generate a large sparse matrix:

am = AdjacencyMatrix@RandomGraph[{25000, 50000}];

am + am; // Timing (* very fast *)

(am + am) + am; // Timing (* very fast *)

am + am + am; // Timing (* so slow I didn't wait for it to finish *)


Can anyone reproduce this? I used Mathematica 9.0.0 on OS X. Mathematica 8 does not have this problem.

Does anyone have any ideas what may be going wrong here?

-
I can reproduce this on Mathematica 9.0.0 (OS X) – Nick Stranniy Jan 20 '13 at 2:32
Two people can reproduce it so tagging as bug. – Szabolcs Jan 20 '13 at 2:42
With V8 RandomGraph[{25000, 50000}] returns and error. – Mike Honeychurch Jan 20 '13 at 3:32
I am using V8.0.4 OS X 10.6.8 and am unable to evaluate am! – Mike Honeychurch Jan 20 '13 at 3:44
@Mike Precisely what error do you get? I originally had RandomGraph[{50000, 100000}] but I has to reduce the size to half of that to test on v8 as v8 returned a len32 error for the bigger graph. RandomGraph[{25000, 50000}] does work fine on 8 here, and the addition does not have the performance problem it has on 9. – Szabolcs Jan 20 '13 at 4:03

I have reported this as a bug. Having said that, here is some more info:

Note that when you use:

am = AdjacencyMatrix@RandomGraph[{25000, 50000}];//N


you do not see the issue. So this is only an integer sparse array issue. What happened until V8 internally is that there is a loop for adding each sparse array as a binary operation. E.g. something like:

res = Plus[Plus[sp1,sp2],sp3]


In version 9 this has been changed to use var args. In essence what you do with using parentheses is to enforce the old behavior. The reason this was changed is that the var args form of the code is faster and uses less memory:

am = (AdjacencyMatrix@RandomGraph[{2500, 5000}]) // N;
MaxMemoryUsed[am + am; // Timing] (*very fast*)
MaxMemoryUsed[(am + am) + am; // Timing] (*very fast*)
MaxMemoryUsed[
am + am + am; // Timing] (*so slow I didn't wait for it to finish*)


So for now you can either convert with N if that is possible, or use the parentheses.

-
A side comment, this one argument form of MaxMemoryUsed is undocumented and I didn't know about it. It looks very useful. – Szabolcs Jan 21 '13 at 1:44
For those who are not familiar with C: "var args" refers to a variadic function defined using stdarg.h. – Oleksandr R. Jan 21 '13 at 2:40
@Szabolcs, yes, that's new. The developer how does memory allocation did that for me - I need this all the time, it's so useful. It will count all allocations that go through the internal allocator. But the usual caveat for undocumented stuff applies here too. If you find issues with it let me know. – user21 Jan 21 '13 at 6:15