Re: FYI: sparse indexed assignment rewritten

[Jaroslav Hajek]

On Wed, Apr 14, 2010 at 3:44 PM, John W. Eaton <address@hidden> wrote:
> On 13-Apr-2010, Jaroslav Hajek wrote:
>
> | I've nearly finished rewriting the sparse indexed assignment code.
> | The old incomprehensible quirky implementation is replaced by a shiny
> | new incomprehensible quirky implementation :)
> | Well at least I tried to comment more. And the code went down from
> | 1100 to 330 lines.
>
> Thanks for working on this big job.
>
> | 2. concatenation doesn't use the new assignment & preallocation
> | mechanism, leading to some ridiculous results:
> |
> | [...]
> |
> | produces this:
> |
> | approach 1: built-in concatenation
> | Elapsed time is 13.6298 seconds.
> | approach 2: hand-coded loop
> | Elapsed time is 0.0499048 seconds.
> |
> | i.e. a built-in operation is 270-times slower than an equivalent
> | interpreted loop (and you thought loops were sluggish? :).
> | It would be cool if sparse concatenation could take advantage of the
> | new speed-ups, but it needs some work. Help is much appreciated.
>
> Ouch, but I'm sure this can be improved.
>

And here it is
http://hg.savannah.gnu.org/hgweb/octave/rev/2dd8ea8bfd71
http://hg.savannah.gnu.org/hgweb/octave/rev/f094ac9bc93e
http://hg.savannah.gnu.org/hgweb/octave/rev/3f973f6c841c

Now the same benchmark again:

address@hidden:~/devel/octave/main> ./run-octave -q ttspc.m
approach 1: built-in concatenation
Elapsed time is 0.00847006 seconds.
approach 2: hand-coded loop
Elapsed time is 0.0498729 seconds.

i.e. the built-in operator is faster again. Compared to the previous
result, the speed-up is about 1600x.
Another item for NEWS, I guess.

Note that it is still a bit suboptimal in the sense that a fully 2D
concat with sparse matrices will be done as a sequence of horzcats +
one vertcat, but I think this is satisfactory. With dense matrices, it
will always allocate one big matrix and then position all pieces to an
appropriate place.

regards

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