Correlation sparse array is very slow

[paulanalyst]

Correlation sparse array is very slow. Out of memory on a dense array when we have 30,000 columns. How quickly it calculated?

julia> I=int32((rand(10^7)*9999999).+1);

julia> J=int32((rand(10^7)*29999).+1);

julia> V=int8((rand(10^7)*9).+1);

julia> D=sparse(I,J,V);

julia> @time cor(D[:,1:30]);
elapsed time: 23.806328476 seconds (2458875228 bytes allocated, 0.14% gc time)

julia> @time cor(full(D[:,1:30]));
elapsed time: 4.494099126 seconds (2732042496 bytes allocated, 5.31% gc time)

Paul

[ivarne]

Previous discussion: https://groups.google.com/forum/?fromgroups=#!topic/julia-users/VacAk16jiN0

[paulanalyst]

Also very slow running sparse arrays: mean (S, 1), cov, etc functions through the column.

[ViralBShah]

We will fix all of these as soon as 0.3 is released. Thanks for reporting.

[paulanalyst]

Correlations and cov are calculated wonderfully at dense matrices, all 8
cores is always working at 100% on my win7. It would be great if it
worked for sparse the same: on all cores on full power.
Paul

W dniu 2014-08-01 14:45, Viral B. Shah pisze:

We will fix all of these as soon as 0.3 is released. Thanks for reporting.

—
Reply to this email directly or view it on GitHub
#7788 (comment).

[paulanalyst]

When this can work?

When this can work?
If it does not work, how to count to cov matrix D to finish in this life ..;)

I=int32((rand(10^7)_9999999).+1);
J=int32((rand(10^7)_29999).+1);
V=int8((rand(10^7)*9).+1);
D=sparse(I,J,V);
C=cov(D)
Paul

[ViralBShah]

I suspect that just implementing the At_mul_B and friends for sparse should suffice. Can you try for smaller problems? Basically you have to do A'*A at some point, and you can't do any faster than that. Once we have multi-threading and such, we can get a few more speedups.

[paulanalyst]

Big thx, it is short way;)

[ViralBShah]

@lindahua can you help here?

[lindahua]

I think one may just need to implement At_mul_B and friends

[paulanalyst]

It is also very slow when we do sparse mean etc ...
I=int32((rand(10^7)_9999999).+1);
J=int32((rand(10^7)_29999).+1);
V=int8((rand(10^7)*9).+1);
D=sparse(I,J,V);
mean(D,1)
looooong time...
etc...

[lindahua]

reduction along dimensions has not been specially optimized for sparse matrix.

That should not be too difficult though, since we only have to consider matrix here, rather than arrays of arbitrary dimensions.

[paulanalyst]

Dear, what about sparse statistic?
Now a have the simple sample:
@time E=mean(D,1)
after 15 min nothing, but it is posible in 0.8sek in simple while :

julia> k,l=size(D)
(6000000,30000)

julia> E=zeros(l)';

julia> @time for i=1:l
E[i]=mean(D[:,i])
#if mod(i,1000).==0 println(i);end;
end;
elapsed time: 0.838322868 seconds (794730416 bytes allocated, 48.18% gc time)

Propably is simmilary in cor, var,cov, etc

Paul

[paulanalyst]

Please, let use the parallel in this functions.

[andreasnoack]

@paulanalyst As usual: what is your versioninfo()? Also what is nnz(D)? On latest master, I get

julia> A = sprandn(6000000,30000,0.00003);

julia> @time mean(A, 1);
elapsed time: 0.13834035 seconds (166 MB allocated, 9.94% gc time in 7 pauses with 0 full sweep)

[paulanalyst]

julia> versioninfo()
Julia Version 0.3.5
Commit a05f87b* (2015-01-08 22:33 UTC)
Platform Info:
System: Windows (x86_64-w64-mingw32)
CPU: Intel(R) Core(TM) i7-2630QM CPU @ 2.00GHz
WORD_SIZE: 64
BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Sandybridge)
LAPACK: libopenblas
LIBM: libopenlibm
LLVM: libLLVM-3.3

julia> nnz(D)
99625891
Paul

[nalimilan]

I can confirm that on 0.3.5 @andreasnoack's example takes ages.

[andreasnoack]

Yes. A faster mean for sparse matrices was introduced in bde4e65 so it is not available on 0.3.x. However, the implementation is very simple, i.e. sum(A,1)/size(A,1), so you could use this method instead while waiting for 0.4.

[paulanalyst]

OK, at 0.4.0 mean is fast, like below. But for "var" I am waitng many minetes...
A fresh approach to technical computing
Documentation: http://docs.julialang.org
Type "help()" for help.

Version 0.4.0-dev+2438 (2015-01-03 12:36 UTC)
Commit b0d94dd (27 days old master)
x86_64-w64-mingw32

julia> @time E=mean(D, 1)
elapsed time: 6.035410891 seconds (1558239044 bytes allocated, 18.71% gc time)
1x30070 Array{Float64,2}:
0.0 0.0904202 0.0072963 0.00103694 0.00430618 1.68553e-7 3.37105e-7 3.37105e-7 1.68553e-7

julia> @time E=var(D, 1)
minutes....
Paul

[paulanalyst]

sum(D,1)/size(D,1) at 0.3.5 is 2 times longer then mean(D,1) at 0.4.0. , 11 ver 6 sek in my array.

julia> @time sum(D,1)/size(D,1)
elapsed time: 11.550475452 seconds (1555463276 bytes allocated, 13.28% gc time)
1x30070 Array{Float64,2}:
0.0 0.0904202 0.0072963 0.00103694 0.00430618 1.68553e-7 3.37105e-7 3.37105e-7 1.68553e-7
Paul

[andreasnoack]

I think that the reason sum in 0.4 is faster is our new garbage collector bacuase I think the implementation is the same.

The var reduction is slightly more complicated and not implemented efficiently for sparse matrices yet, but you can probably benefit from the trick we discussed last time, i.e. by using the E(XX') - EX(EX)' formulation.

[ViralBShah]

We should backport the mean.

[paulanalyst]

@ andreasnoack
E(XX') is a vecotr...

I use X'X-E(X)'*E(X)
Paul

[andreasnoack]

Then you won't get the right result.

Anyway, I'm talking about the method in the issue where you thought the was a rounding error, but it was wrong formula.

[ViralBShah]

#10536 should have fixed this one.

[simonster]

Unfortunately it doesn't look like it does, since cor is not based on mapreduce/mapreducedim.