ranges are not vectors

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

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
[hidden email]






range.diff (3K) Download Attachment
rangesafe.diff (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

ranges are not vectors

John W. Eaton-6
On  2-Mar-2004, Paul Kienzle <[hidden email]> wrote:

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

Thanks for looking at this again.  Caching the matrix value will be a
nice improvement even if it is not the absolute most efficient
solution.

| I provide two patches.  The first, range.diff, casts away the
| const on range and caches all calls to matrix_value.

I think you can avoid the const_cast if you declare the cache variable
as mutable.

Also, you should invalidate the cache if any of the non-const
functions

  void sort (void);

  void set_base (double b) { rng_base = b;  }
  void set_limit (double l) { rng_limit = l; }
  void set_inc (double i) { rng_inc = i;   }

  void print_range (void);

are called (and actually result in a change to the range data).

I'm not sure why print_range is non-const (or at this point, why it
even exists, so I'd vote for removing it).

Would you please revise your patch to use mutable, remove the casts,
and reset the cache (if necessary) in the above functions?

Thanks,

jwe