ranges are not vectors

[Paul Kienzle]

I'm sure this issue was raised a number of years ago,
but it occasionally bites people:  most operations
on ranges convert the range to a vector first.  This
can lead to bad benchmark results, since the syntactic
difference is subtle.

Compare matrix indexing (linear):

octave:12> for N=[10,100,1000,10000], total=0; tic; x=[1:N]; for i=1:N, 
total+=x(i); end; N,toc end
N = 10
ans = 0.0050050
N = 100
ans = 0.017255
N = 1000
ans = 0.14234
N = 10000
ans = 1.3797

with range indexing (quadratic?):

octave:13> for N=[10,100,1000,10000], total=0; tic; x=1:N; for i=1:N, 
total+=x(i); end; N,toc end
N = 10
ans = 0.0048410
N = 100
ans = 0.019801
N = 1000
ans = 0.23843
N = 10000
ans = 7.9764

I'm not convinced this problem is worth fixing since
it only shows up on benchmarks ;-)

However, it is pretty bad worst case performance.  Fixing
it 'properly' would require quite a bit of work in
liboctave/Range.{cc,h} and src/ov-range.cc so that the
full matrix is never created.

A much simpler solution is to create the full matrix, but
cache the result so that the penalty is only paid once.

In creating a patch I ran into a small problem: a good
place to cache the result is in the range itself, but range
is frequently a const variable, so I needed const
and non-const forms of the matrix_value() method.
Fortunately octave_value::do_index_op is not a const
method, so the above case can be optimized.  On the
other hand, caching the result of matrix_value doesn't
really change the value of the range, so it should be
okay to cast away the const.  This would allow us to
benefit from caching on all octave_range ops.

I provide two patches.  The first, range.diff, casts away the
const on range and caches all calls to matrix_value.  The
second, rangesafe.diff, only caches matrix_values for
non-const ranges.  Both work for me in Debian Linux
for octave-2.1.55 CVS.

Paul Kienzle
address@hidden

range.diff
Description: Binary data

rangesafe.diff
Description: Binary data