help-octave
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

extreme slowness in Nd array FORTRAN indexing fixed using a colon


From: John W. Eaton
Subject: extreme slowness in Nd array FORTRAN indexing fixed using a colon
Date: Fri, 11 Nov 2005 13:19:42 -0500

On 15-Oct-2005, Mike Miller wrote:

| I found this quite stunning.  The upshot is that use of FORTRAN indexing 
| is almost 9,000 times faster (in my examples) when a colon "(:)" is used 
| in a 3-d array as when the colon is not used.  If this is a "known issue," 
| let me apologize in advance, but it needs to be more widely known, and if 
| there is a way to fix this inside the Octave code, it probably should be 
| fixed.
| 
| We are using Octave 2.1.71 with Octave-Forge on Red Hat Linux.
| 
| We are working on some m-files where we grab elements of an array and 
| assign them to elements of another array.  The way to do this quickly 
| seems to be with FORTRAN indexing.  It was conveninent to work with a 3-d 
| array of size N x M x 2 (FYI, this is for N subjects by M genetic markers 
| by 2 parents).  In the following Octave commands, I'm just making a new 
| matrix M1 or M2 by grabbing random elements of array H:
| 
| 
| octave:1> H=rand(500,500,2);
| octave:2> I=ceil(500000*rand(100,100));
| 
| octave:3> tic; M1=H(I); toc
| ans = 38.849
| 
| octave:4> tic; M2=H(:)(I); toc
| ans = 0.0044010
| 
| octave:5> sum(sum(M1==M2))
| ans = 10000
| 
| octave:6> 38.849/0.0044010
| ans = 8827.3
| 
| 
| In other words, the same indexing operation on the same data data gave the 
| same result but was 8827 times as fast when the colon operator was used. 
| Since the output is the same with and without the colon, doesn't that mean 
| that the colon is gratuitous?  Isn't there a way to change the Octave 
| program so that it provides the faster speed even when the colon is 
| absent?
| 
| By the way, the colon still has a small effect when the array is a matrix 
| instead of a 3-d array.  For example, 0.00678 seconds without colon versus 
| 0.00481 seconds with colon (41% longer without the colon).  That might be 
| important sometimes but it's nothing compared to an 8000-fold speed up!

Please try the following patch.

BTW, it is generally better to send bug reports to the address@hidden
list.

Thanks,

jwe


liboctave/ChangeLog:

2005-11-11  John W. Eaton  <address@hidden>

        * Array.cc (Array<T>::indexN): Simplify.


Index: liboctave/Array.cc
===================================================================
RCS file: /cvs/octave/liboctave/Array.cc,v
retrieving revision 1.138
diff -u -r1.138 Array.cc
--- liboctave/Array.cc  29 Oct 2005 04:31:25 -0000      1.138
+++ liboctave/Array.cc  11 Nov 2005 18:08:26 -0000
@@ -2221,10 +2221,6 @@
 
          octave_idx_type n = result_dims.numel ();
 
-         int r_dims = result_dims.length ();
-
-         Array<octave_idx_type> iidx (r_dims, 0);
-
          octave_idx_type k = 0;
 
          for (octave_idx_type i = 0; i < n; i++)
@@ -2232,15 +2228,9 @@
              octave_idx_type ii = ra_idx.elem (k++);
 
              if (ii >= orig_len)
-               retval.elem (iidx) = rfv;
+               retval.elem (i) = rfv;
              else
-               {
-                 Array<int> temp = get_ra_idx (ii, dv);
-
-                 retval.elem (iidx) = elem (temp);
-               }
-             if (i != n - 1)
-               increment_index (iidx, result_dims);
+               retval.elem (i) = elem (ii);
            }
        }
     }



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------



reply via email to

[Prev in Thread] Current Thread [Next in Thread]