http://www.mathworks.com/matlabcentral/newsreader/view_thread/324487
MATLAB Central Newsreader  speeding up ACCUMARRAY
Feed for thread: speeding up ACCUMARRAY
enus
©19942015 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Tue, 13 Nov 2012 17:56:14 +0000
speeding up ACCUMARRAY
http://www.mathworks.com/matlabcentral/newsreader/view_thread/324487#891609
Matt J
I find it strange that no FEX contributors have tried to improve upon ACCUMARRAY, since I think it's widely agreed that it is slow.<br>
<br>
I'm wondering if the reason ACCUMARRAY is so slow (despite being a builtin) is that it has to support so many different options, and whether a customized mex version, one which supported only summation accumulation, for example, could improve upon it.

Tue, 13 Nov 2012 18:27:16 +0000
Re: speeding up ACCUMARRAY
http://www.mathworks.com/matlabcentral/newsreader/view_thread/324487#891612
james bejon
I must admit, I've always found accumarray to be remarkably fast, e.g.,<br>
<br>
% DATA<br>
subs = ceil(rand(1000000,1)*10);<br>
<br>
% ENGINE<br>
tic<br>
for i = 1:1000<br>
accumarray(subs, 1);<br>
end<br>
toc<br>
<br>
% Result = 1.40 seconds<br>
<br>
Is there a specific usage you have in mind?

Tue, 13 Nov 2012 18:42:11 +0000
Re: speeding up ACCUMARRAY
http://www.mathworks.com/matlabcentral/newsreader/view_thread/324487#891613
Bruno Luong
"james bejon" wrote in message <k7u3e4$8ml$1@newscl01ah.mathworks.com>...<br>
> I must admit, I've always found accumarray to be remarkably fast, e.g.,<br>
<br>
Agree. However it is slow if using on small arrays or in combination with function handle.<br>
<br>
Bruno

Tue, 13 Nov 2012 19:07:14 +0000
Re: speeding up ACCUMARRAY
http://www.mathworks.com/matlabcentral/newsreader/view_thread/324487#891617
james bejon
Ah. Pity it's slow with a function handle. I find that to be its most useful feature.

Tue, 13 Nov 2012 23:36:21 +0000
Re: speeding up ACCUMARRAY
http://www.mathworks.com/matlabcentral/newsreader/view_thread/324487#891637
Matt J
"james bejon" wrote in message <k7u3e4$8ml$1@newscl01ah.mathworks.com>...<br>
> I must admit, I've always found accumarray to be remarkably fast, e.g.,<br>
> <br>
> % DATA<br>
> subs = ceil(rand(1000000,1)*10);<br>
> <br>
> % ENGINE<br>
> tic<br>
> for i = 1:1000<br>
> accumarray(subs, 1);<br>
> end<br>
> toc<br>
> <br>
> % Result = 1.40 seconds<br>
> <br>
> Is there a specific usage you have in mind?<br>
================<br>
<br>
I'm trying to find a way to implement a sparse matrix multiplication given I,J,S data while avoiding the overhead of actually building the sparse matrix and all of the sorting operations it requires. I have to do this for repeated sets of I,J,S data which are fairly easy/quick to generate, but if I have to load them into a sparse matrix each time, it will kill the speed.<br>
<br>
I guess one of the reasons for my suspicions about accumarray performance is the speed differences I'm seeing between an accumarray operation and an equivalent sparse matrix multiplication in the example below. The accumarray approach is about twice as slow as the sparse matrix approach even though they both have the same data to work with. In fact, the sparse matrix multiplication is probably even handicapped relative to accumarray, since it has to search through x for the appropriate x(J), whereas in the accumarray approach, I exclude the construction of b=x(J) from the tic/toc.<br>
<br>
%fake data setup<br>
M=1e5;<br>
A=kron(speye(M),ones(1,16));<br>
N=size(A,2);<br>
[I,J]=find(A);<br>
x=rand(N,1);<br>
<br>
<br>
%pretend we build A from scratch<br>
tic; <br>
A=sparse(I,J,1);<br>
toc %Elapsed time is 0.062737 seconds.<br>
<br>
<br>
<br>
%Apply A<br>
tic<br>
y1=A*x;<br>
toc %Elapsed time is 0.006868 seconds.<br>
<br>
<br>
<br>
%Using accumarray<br>
b=x(J);<br>
tic<br>
y2=accumarray(I,b,[M,1]);<br>
toc %Elapsed time is 0.012236 seconds.

Tue, 13 Nov 2012 23:53:17 +0000
Re: speeding up ACCUMARRAY
http://www.mathworks.com/matlabcentral/newsreader/view_thread/324487#891639
james bejon
Interesting. I've no idea why that's happening. (May as well be honest about these things).

Wed, 14 Nov 2012 07:02:10 +0000
Re: speeding up ACCUMARRAY
http://www.mathworks.com/matlabcentral/newsreader/view_thread/324487#891655
Bruno Luong
"Matt J" wrote in message <k7ulhl$iod$1@newscl01ah.mathworks.com>...<br>
<br>
>In fact, the sparse matrix multiplication is probably even handicapped relative to accumarray, since it has to search through x for the appropriate x(J), <br>
<br>
There is no such step in sparse multiplication.<br>
<br>
Bruno

Wed, 14 Nov 2012 14:58:17 +0000
Re: speeding up ACCUMARRAY
http://www.mathworks.com/matlabcentral/newsreader/view_thread/324487#891687
Matt J
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k7vfli$da4$1@newscl01ah.mathworks.com>...<br>
> "Matt J" wrote in message <k7ulhl$iod$1@newscl01ah.mathworks.com>...<br>
> <br>
> >In fact, the sparse matrix multiplication is probably even handicapped relative to accumarray, since it has to search through x for the appropriate x(J), <br>
> <br>
> There is no such step in sparse multiplication.<br>
=============<br>
<br>
Meaning that y=A*x is generated by looping over columns of A instead of rows? Even if so, how would that explain the speed difference?

Wed, 14 Nov 2012 17:40:18 +0000
Re: speeding up ACCUMARRAY
http://www.mathworks.com/matlabcentral/newsreader/view_thread/324487#891701
Matt J
"Matt J" wrote in message <k80bi9$isp$1@newscl01ah.mathworks.com>...<br>
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k7vfli$da4$1@newscl01ah.mathworks.com>...<br>
> > "Matt J" wrote in message <k7ulhl$iod$1@newscl01ah.mathworks.com>...<br>
> > <br>
> > >In fact, the sparse matrix multiplication is probably even handicapped relative to accumarray, since it has to search through x for the appropriate x(J), <br>
> > <br>
> > There is no such step in sparse multiplication.<br>
> =============<br>
> <br>
> Meaning that y=A*x is generated by looping over columns of A instead of rows? Even if so, how would that explain the speed difference?<br>
================<br>
<br>
Anyway, my point remains. Sparse matrix multiplication has to perform multiplications with the x(j) somewhere, whereas accumarray, in my tests, does not. So sparse mult. is further handicapped.

Wed, 14 Nov 2012 19:52:13 +0000
Re: speeding up ACCUMARRAY
http://www.mathworks.com/matlabcentral/newsreader/view_thread/324487#891705
Bruno Luong
"Matt J" wrote in message <k80l22$qd5$1@newscl01ah.mathworks.com>...<br>
<br>
> <br>
> Anyway, my point remains. Sparse matrix multiplication has to perform multiplications with the x(j) somewhere, whereas accumarray, in my tests, does not. So sparse mult. is further handicapped.<br>
<br>
1) Sparse internally access memory via integer indexing. Your accumarray has to cast doubles (firs input) to integers.<br>
<br>
2) Sparse multiplication engine might benefice multithreading, and other lowlevel optimization.<br>
<br>
Accumarray is not slow. Just sparse is fast.<br>
<br>
Bruno

Wed, 14 Nov 2012 20:27:17 +0000
Re: speeding up ACCUMARRAY
http://www.mathworks.com/matlabcentral/newsreader/view_thread/324487#891709
Matt J
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k80spd$ra8$1@newscl01ah.mathworks.com>...<br>
> "Matt J" wrote in message <k80l22$qd5$1@newscl01ah.mathworks.com>...<br>
> <br>
> > <br>
> > Anyway, my point remains. Sparse matrix multiplication has to perform multiplications with the x(j) somewhere, whereas accumarray, in my tests, does not. So sparse mult. is further handicapped.<br>
> <br>
> 1) Sparse internally access memory via integer indexing. Your accumarray has to cast doubles (firs input) to integers.<br>
==================<br>
<br>
Precasting to uint32 does seem to help!<br>
<br>
<br>
<br>
<br>
> 2) Sparse multiplication engine might benefice multithreading, and other lowlevel optimization.<br>
> <br>
> Accumarray is not slow. Just sparse is fast.<br>
================<br>
<br>
Seems like a false distinction to me. ;)

Thu, 15 Nov 2012 07:20:19 +0000
Re: speeding up ACCUMARRAY
http://www.mathworks.com/matlabcentral/newsreader/view_thread/324487#891725
Bruno Luong
"Matt J" wrote in message <k80ur5$6b4$1@newscl01ah.mathworks.com>...<br>
><br>
> > <br>
> > Accumarray is not slow. Just sparse is fast.<br>
> ================<br>
> <br>
> Seems like a false distinction to me. ;)<br>
<br>
I can define exactly what can be considered as "fast" and "slow".<br>
<br>
Bruno

Thu, 15 Nov 2012 08:35:17 +0000
Re: speeding up ACCUMARRAY
http://www.mathworks.com/matlabcentral/newsreader/view_thread/324487#891730
Matt J
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k8253j$es9$1@newscl01ah.mathworks.com>...<br>
> "Matt J" wrote in message <k80ur5$6b4$1@newscl01ah.mathworks.com>...<br>
> ><br>
> > > <br>
> > > Accumarray is not slow. Just sparse is fast.<br>
> > ================<br>
> > <br>
> > Seems like a false distinction to me. ;)<br>
> <br>
> I can define exactly what can be considered as "fast" and "slow".<br>
============<br>
<br>
If we're saying that there are wellknown ways of making accumarray faster than it is (e.g., multithreading), then that seems to meet the definition of "slow".