From octave-maintainers-request at bevo dot che dot wisc dot edu Tue Mar 2 21:17:23 2004 Subject: ranges are not vectors From: Paul Kienzle To: octave-maintainers mailing list Date: Tue, 2 Mar 2004 22:16:36 -0500 --Apple-Mail-6--955134532 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; format=flowed 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 pkienzle at users dot sf dot net --Apple-Mail-6--955134532 Content-Transfer-Encoding: 7bit Content-Type: application/octet-stream; x-unix-mode=0644; name="range.diff" Content-Disposition: attachment; filename=range.diff Index: Range.cc =================================================================== RCS file: /cvs/octave/liboctave/Range.cc,v retrieving revision 1.31 diff -c -p -r1.31 Range.cc *** Range.cc 2004/02/20 18:02:59 1.31 --- Range.cc 2004/03/02 20:45:53 *************** Software Foundation, 59 Temple Place - S *** 35,41 **** #include #include "Range.h" - #include "dMatrix.h" #include "lo-mappers.h" #include "lo-utils.h" --- 35,40 ---- *************** Range::all_elements_are_ints (void) cons *** 51,67 **** } Matrix ! Range::matrix_value (void) const { ! Matrix retval; ! ! if (rng_nelem > 0) { ! retval.resize (1, rng_nelem); double b = rng_base; double increment = rng_inc; for (int i = 0; i < rng_nelem; i++) ! retval(i) = b + i * increment; // On some machines (x86 with extended precision floating point // arithmetic, for example) it is possible that we can overshoot --- 50,64 ---- } Matrix ! Range::matrix_value (void) { ! if (rng_nelem > 0 && cache.rows() == 0) { ! cache.resize (1, rng_nelem); double b = rng_base; double increment = rng_inc; for (int i = 0; i < rng_nelem; i++) ! cache(i) = b + i * increment; // On some machines (x86 with extended precision floating point // arithmetic, for example) it is possible that we can overshoot *************** Range::matrix_value (void) const *** 69,81 **** // we were very careful in our calculation of the number of // elements. ! if ((rng_inc > 0 && retval(rng_nelem-1) > rng_limit) ! || (rng_inc < 0 && retval(rng_nelem-1) < rng_limit)) ! retval(rng_nelem-1) = rng_limit; } ! return retval; } // NOTE: max and min only return useful values if nelem > 0. --- 66,92 ---- // we were very careful in our calculation of the number of // elements. ! if ((rng_inc > 0 && cache(rng_nelem-1) > rng_limit) ! || (rng_inc < 0 && cache(rng_nelem-1) < rng_limit)) ! cache(rng_nelem-1) = rng_limit; } + + return cache; + } ! Matrix ! Range::matrix_value (void) const ! { ! // Memoizing functions are semantically constant. Calling them ! // with the same values will return the same results, so it ! // doesn't matter whether the caller works from a cached return ! // value or calls the function again. Since the cache value is ! // private and not present in any inline code, we don't have to ! // worry that the caller has a stale cache pointer laying around. ! const_cast(this)->matrix_value(); ! return cache; } + // NOTE: max and min only return useful values if nelem > 0. Index: Range.h =================================================================== RCS file: /cvs/octave/liboctave/Range.h,v retrieving revision 1.21 diff -c -p -r1.21 Range.h *** Range.h 2002/11/20 16:56:48 1.21 --- Range.h 2004/03/02 20:45:53 *************** Software Foundation, 59 Temple Place - S *** 28,36 **** #endif #include - class Matrix; - class Range { --- 28,35 ---- #endif #include + #include "dMatrix.h" class Range { *************** Range *** 59,64 **** --- 58,64 ---- bool all_elements_are_ints (void) const; Matrix matrix_value (void) const; + Matrix matrix_value (void); double min (void) const; double max (void) const; *************** Range *** 76,81 **** --- 76,82 ---- private: + Matrix cache; double rng_base; double rng_limit; double rng_inc; --Apple-Mail-6--955134532 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; format=flowed --Apple-Mail-6--955134532 Content-Transfer-Encoding: 7bit Content-Type: application/octet-stream; x-unix-mode=0644; name="rangesafe.diff" Content-Disposition: attachment; filename=rangesafe.diff Index: Range.cc =================================================================== RCS file: /cvs/octave/liboctave/Range.cc,v retrieving revision 1.31 diff -c -p -r1.31 Range.cc *** Range.cc 2004/02/20 18:02:59 1.31 --- Range.cc 2004/03/02 19:57:11 *************** Software Foundation, 59 Temple Place - S *** 35,41 **** #include #include "Range.h" - #include "dMatrix.h" #include "lo-mappers.h" #include "lo-utils.h" --- 35,40 ---- *************** Range::matrix_value (void) const *** 57,62 **** --- 56,62 ---- if (rng_nelem > 0) { + if (cache.rows() != 0) return cache; retval.resize (1, rng_nelem); double b = rng_base; double increment = rng_inc; *************** Range::matrix_value (void) const *** 76,81 **** --- 76,90 ---- return retval; } + + Matrix + Range::matrix_value (void) + { + if (cache.rows () == 0) + cache = const_cast(this)->matrix_value (); + return cache; + } + // NOTE: max and min only return useful values if nelem > 0. Index: Range.h =================================================================== RCS file: /cvs/octave/liboctave/Range.h,v retrieving revision 1.21 diff -c -p -r1.21 Range.h *** Range.h 2002/11/20 16:56:48 1.21 --- Range.h 2004/03/02 19:57:11 *************** Software Foundation, 59 Temple Place - S *** 28,36 **** #endif #include - class Matrix; - class Range { --- 28,35 ---- #endif #include + #include "dMatrix.h" class Range { *************** Range *** 59,64 **** --- 58,64 ---- bool all_elements_are_ints (void) const; Matrix matrix_value (void) const; + Matrix matrix_value (void); double min (void) const; double max (void) const; *************** Range *** 76,81 **** --- 76,82 ---- private: + Matrix cache; double rng_base; double rng_limit; double rng_inc; --Apple-Mail-6--955134532 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; format=flowed --Apple-Mail-6--955134532--