[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
ranges are not vectors
From: |
Paul Kienzle |
Subject: |
ranges are not vectors |
Date: |
Tue, 2 Mar 2004 22:16:36 -0500 |
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
- ranges are not vectors,
Paul Kienzle <=