FYI: new accumarray optimizations

[Jaroslav Hajek]

hi all,

by the following changeset
http://hg.savannah.gnu.org/hgweb/octave/rev/9a16a61ed43d

I implemented new optimizations for accumarray.
@sum, @min, and @max reductions are now handled by a fast O(N)
algorithm (in the dense case).
I also refactored the code somewhat for better general efficiency and
optimized also the @(x) {x} reduction (i.e. just collecting the values
into cells).
The following code illustrates the speed-ups.

n = 1000000;
m = 1000;
idx = ceil (m*rand (n, 1));
val = rand (n, 1);
try
  accumarray; # force parse
catch
end_try_catch

tic; accumarray (idx, val, [m, 1]); toc
tic; accumarray (idx, val, [m, 1], @min, Inf); toc
tic; accumarray (idx, val, [m, 1], @max); toc
tic; accumarray (idx, val, [m, 1], @(x){x}); toc
tic; accumarray (idx, val, [m, 1], @std); toc

m = 20;
idx = ceil (m*rand (n, 3));
val = rand (n, 1);

tic; accumarray (idx, val, [m, m, m]); toc
tic; accumarray (idx, val, [m, m, m], @min, Inf); toc
tic; accumarray (idx, val, [m, m, m], @max); toc
tic; accumarray (idx, val, [m, m, m], @(x){x}); toc
tic; accumarray (idx, val, [m, m, m], @std); toc

On Core 2 Duo @ 1.83 GHz, gcc 4.3 -O3 -march=native,
with a recent tip I get:

Elapsed time is 0.011374 seconds.
Elapsed time is 0.456557 seconds.
Elapsed time is 0.390821 seconds.
Elapsed time is 0.456975 seconds.
Elapsed time is 0.597545 seconds.
Elapsed time is 0.0489521 seconds.
Elapsed time is 0.859555 seconds.
Elapsed time is 0.874383 seconds.
Elapsed time is 1.36757 seconds.
Elapsed time is 2.39027 seconds.

with the new patch I get

Elapsed time is 0.0110469 seconds.
Elapsed time is 0.00914407 seconds.
Elapsed time is 0.00952911 seconds.
Elapsed time is 0.336586 seconds.
Elapsed time is 0.560295 seconds.
Elapsed time is 0.0400701 seconds.
Elapsed time is 0.040818 seconds.
Elapsed time is 0.0429821 seconds.
Elapsed time is 0.386366 seconds.
Elapsed time is 2.09485 seconds.

enjoy!

P.S. trying just this:

m = 100;
idx = ceil (m*rand (n, 2));
val = rand (n, 1);

tic; accumarray (idx, val, [m, m]); toc
tic; accumarray (idx, val, [m, m], [], 0, true); toc

gives

Elapsed time is 0.0295751 seconds.
Elapsed time is 0.568987 seconds.

and shows that the sparse summation significantly lags behind, so I'll
target that next.

-- 
RNDr. Jaroslav Hajek, PhD
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz