Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
speeding up ACCUMARRAY

Subject: speeding up ACCUMARRAY

From: Matt J

Date: 13 Nov, 2012 17:56:14

Message: 1 of 13

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.

I'm wondering if the reason ACCUMARRAY is so slow (despite being a built-in) 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.

Subject: speeding up ACCUMARRAY

From: james bejon

Date: 13 Nov, 2012 18:27:16

Message: 2 of 13

I must admit, I've always found accumarray to be remarkably fast, e.g.,

% DATA
subs = ceil(rand(1000000,1)*10);

% ENGINE
tic
for i = 1:1000
  accumarray(subs, 1);
end
toc

% Result = 1.40 seconds

Is there a specific usage you have in mind?

Subject: speeding up ACCUMARRAY

From: Bruno Luong

Date: 13 Nov, 2012 18:42:11

Message: 3 of 13

"james bejon" wrote in message <k7u3e4$8ml$1@newscl01ah.mathworks.com>...
> I must admit, I've always found accumarray to be remarkably fast, e.g.,

Agree. However it is slow if using on small arrays or in combination with function handle.

Bruno

Subject: speeding up ACCUMARRAY

From: james bejon

Date: 13 Nov, 2012 19:07:14

Message: 4 of 13

Ah. Pity it's slow with a function handle. I find that to be its most useful feature.

Subject: speeding up ACCUMARRAY

From: Matt J

Date: 13 Nov, 2012 23:36:21

Message: 5 of 13

"james bejon" wrote in message <k7u3e4$8ml$1@newscl01ah.mathworks.com>...
> I must admit, I've always found accumarray to be remarkably fast, e.g.,
>
> % DATA
> subs = ceil(rand(1000000,1)*10);
>
> % ENGINE
> tic
> for i = 1:1000
> accumarray(subs, 1);
> end
> toc
>
> % Result = 1.40 seconds
>
> Is there a specific usage you have in mind?
================

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.

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.

   %fake data setup
    M=1e5;
    A=kron(speye(M),ones(1,16));
    N=size(A,2);
    [I,J]=find(A);
    x=rand(N,1);


    %pretend we build A from scratch
    tic;
     A=sparse(I,J,1);
    toc %Elapsed time is 0.062737 seconds.



    %Apply A
    tic
      y1=A*x;
    toc %Elapsed time is 0.006868 seconds.



    %Using accumarray
    b=x(J);
    tic
     y2=accumarray(I,b,[M,1]);
    toc %Elapsed time is 0.012236 seconds.

Subject: speeding up ACCUMARRAY

From: james bejon

Date: 13 Nov, 2012 23:53:17

Message: 6 of 13

Interesting. I've no idea why that's happening. (May as well be honest about these things).

Subject: speeding up ACCUMARRAY

From: Bruno Luong

Date: 14 Nov, 2012 07:02:10

Message: 7 of 13

"Matt J" wrote in message <k7ulhl$iod$1@newscl01ah.mathworks.com>...

>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),

There is no such step in sparse multiplication.

Bruno

Subject: speeding up ACCUMARRAY

From: Matt J

Date: 14 Nov, 2012 14:58:17

Message: 8 of 13

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k7vfli$da4$1@newscl01ah.mathworks.com>...
> "Matt J" wrote in message <k7ulhl$iod$1@newscl01ah.mathworks.com>...
>
> >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),
>
> There is no such step in sparse multiplication.
=============

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?

Subject: speeding up ACCUMARRAY

From: Matt J

Date: 14 Nov, 2012 17:40:18

Message: 9 of 13

"Matt J" wrote in message <k80bi9$isp$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k7vfli$da4$1@newscl01ah.mathworks.com>...
> > "Matt J" wrote in message <k7ulhl$iod$1@newscl01ah.mathworks.com>...
> >
> > >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),
> >
> > There is no such step in sparse multiplication.
> =============
>
> 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?
================

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.

Subject: speeding up ACCUMARRAY

From: Bruno Luong

Date: 14 Nov, 2012 19:52:13

Message: 10 of 13

"Matt J" wrote in message <k80l22$qd5$1@newscl01ah.mathworks.com>...

>
> 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.

1) Sparse internally access memory via integer indexing. Your accumarray has to cast doubles (firs input) to integers.

2) Sparse multiplication engine might benefice multi-threading, and other low-level optimization.

Accumarray is not slow. Just sparse is fast.

Bruno

Subject: speeding up ACCUMARRAY

From: Matt J

Date: 14 Nov, 2012 20:27:17

Message: 11 of 13

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k80spd$ra8$1@newscl01ah.mathworks.com>...
> "Matt J" wrote in message <k80l22$qd5$1@newscl01ah.mathworks.com>...
>
> >
> > 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.
>
> 1) Sparse internally access memory via integer indexing. Your accumarray has to cast doubles (firs input) to integers.
==================

Precasting to uint32 does seem to help!




> 2) Sparse multiplication engine might benefice multi-threading, and other low-level optimization.
>
> Accumarray is not slow. Just sparse is fast.
================

Seems like a false distinction to me. ;)

Subject: speeding up ACCUMARRAY

From: Bruno Luong

Date: 15 Nov, 2012 07:20:19

Message: 12 of 13

"Matt J" wrote in message <k80ur5$6b4$1@newscl01ah.mathworks.com>...
>
> >
> > Accumarray is not slow. Just sparse is fast.
> ================
>
> Seems like a false distinction to me. ;)

I can define exactly what can be considered as "fast" and "slow".

Bruno

Subject: speeding up ACCUMARRAY

From: Matt J

Date: 15 Nov, 2012 08:35:17

Message: 13 of 13

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k8253j$es9$1@newscl01ah.mathworks.com>...
> "Matt J" wrote in message <k80ur5$6b4$1@newscl01ah.mathworks.com>...
> >
> > >
> > > Accumarray is not slow. Just sparse is fast.
> > ================
> >
> > Seems like a false distinction to me. ;)
>
> I can define exactly what can be considered as "fast" and "slow".
============

If we're saying that there are well-known ways of making accumarray faster than it is (e.g., multi-threading), then that seems to meet the definition of "slow".

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us