bugGNU Octave - Bugs: bug #31709, simple routine which runs 20 times...

 
 

bug #31709: simple routine which runs 20 times slower on octave vs. matlab!

Submitter:  kody law <kodo>
Submitted:  Fri 19 Nov 2010 10:52:14 PM UTC
   
 
Category:  None Severity:  3 - Normal
Priority:  5 - Normal Item Group:  None
Status:  None Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * 3.2.3 Operating System:  * Mac OS
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Mon 22 Nov 2010 12:20:09 AM UTC, comment #8: 

WOW! This is fantastic stuff, Rik!  I stand corrected.

Many thanks for all your help.  Indeed, this routine now runs in 2.5 s. just like in matlab!  I am impressed. 

I find the row/column reversal particularly curious.

Thanks for the information about profiling too - I did not think of this and I only ever used it in matlab, where there is a command for it.

OK, thanks again and have a great night, best, Kody.

kody law <kodo>
Sun 21 Nov 2010 10:12:40 PM UTC, comment #7: 


>>I am afraid you did not read my submission


Please do not tell me what I did or did not do.  I know exactly what I did.  Your code has some typical issues which hinder speed which I identified.  Only after those are corrected, and the speed does not improve, can one can start looking at whether the Octave core needs to be changed. 

>>iii) pre-allocation will not help here either.


This is a scientific/engineering question rather than one of opinion.  Don't tell me that pre-allocation won't help, just demonstrate that it doesn't with some code.  I will happily accept that sort of evidence.

Profiling isn't all that hard, it just involves putting tic/toc combinations around various blocks and narrowing things down.  On my machine I find the following times for the slow calculation:

Outer While Loop : 14.55 seconds
Inner While Loop : 1.093

So, somewhat surprisingly, it is not the tightest inner loop.  Keep profiling.

le, lens block : 0.9601
cy assignments : 12.311

Okay, now the hot spot is clear.  85% of the execution time is being spent in just two cy assignments.  For optimization purposes I will time both of them.

cy assignment #1 : 6.600
cy assignment #2 : 5.978

cy assignment #2 is

cy(i,N^3+1)=le;
why not keep cy square (N^3,N^3) and use a single row vector to keep track of le?  I added/changed
cy=sparse(N^3,N^3);
cyle = sparse (N^3,1);
and assignment #2 is now
cyle(i,1) = le;


cy assignment #2 w/cyle : 1.384

From ~6 seconds to 1.4 seconds or a little over 400% speedup.  But I notice that cyle always uses 100% of it's entries.  Why not pre-allocate the storage for the sparse array since it will be used?  Second change:

cyle = spalloc (N^3, 1, N^3);


cy assignment #2 w/cyle & spalloc : 0.3957
cy assignment #2 w/cyle & full matrix : 0.3461

This speeds things up another 3X.  Since 100% of the cyle entries were filled I tried using a regular full matrix rather than a sparse matrix.  As you can see, this change only nets about 10% improvement.

With the improvements above as a guide I tried allocating storage for cy as well.

cy=spalloc(N^3,N^3,N^3);


cy assignment #1 w/spalloc : 3.1131

This halves the time, but that still looks a little long.  Why not try reversing the answer space and using column vectors instead of row vectors?  The change in calculation can easily be undone by transposing the matrix cy at the end of the run.


cy(1:le,i)=v';


cy assignment #1 w/spalloc & reversed row/cols : 0.82021

This is an 8x speed-up overall.  I agree that Octave really should treat sparse column and row vectors equivalently and will file an optimization bug about this on the bug tracker.  Nevertheless, you can easily code around it.

Finally, I went back and took a look at the original inner while loop.  With all of the changes above incorporated the original benchmarking time has changed.  This is not unusual.  Optimization involves repeatedly finding the hotspot in the code, dealing with it, which in turn reveals another hotspot.

Inner While Loop : 0.7633

The while loop test condition checks the variable flag every single time which is unnecessary.  If you want a loop body to always execute once, use a do/until loop.  If you're programming in Matlab, which doesn't offer this construct, then you can extract the body of the loop and execute it once before starting the while loop.  Changed code:

v=i;
first = pp(i);
pp(i) = 0;
while (first ~=i)


Inner While Loop w/o flag : 0.37611
Outer While Loop after optimization : 1.79 seconds

Overall improvement was 14.55/1.79 or 8.1X.  Your 40 second code should take about 5 seconds with these changes.  It also yielded the same answer for cy compared to the original code.

Rik <rik5>
Group administrator
Sun 21 Nov 2010 06:37:04 PM UTC, comment #6: 

Such is life I suppose .... thanks for the info.  I am a little surprised, since even matlab does not come close to competing with lower level languages such as Fortran/C for loops.  Guess that means if I'm doing something simple with lots of loops I better use one of them 8)

Cheers,
Kody

kody law <kodo>
Sun 21 Nov 2010 05:20:47 AM UTC, comment #5: 

The thing is, most of us are in a similar situation to you: we want things to improve but lack the resources :-(

Anyway, you're not going to see specific routines being made faster by a JIT. Rather you are going to see loops being faster. So, if your code contains loops where the body is relatively cheap to evaluate, chances are that a JIT would help.

Cheers
Søren

Søren Hauberg <hauberg>
Sun 21 Nov 2010 02:14:44 AM UTC, comment #4: 

Please pardon my loud text :-) ... I was somehow under the impression clarity might have been lacking without...  No intention of rudeness at all.  Everyone here has been really more than helpful and I understand you are all volunteers.

Unfortunately, I am a starving scientist and neither software development nor funding are areas of expertise, so I'm afraid I cannot help with this issue, as much as I would like to.

For reference, is there somewhere a list of routines which are significantly sped up by JIT ?

Thanks again, cheers,
Kody.

kody law <kodo>
Sat 20 Nov 2010 09:34:05 PM UTC, comment #3: 

The problem is that Octave does not have a Just-in-Time (JIT) compiler; Matlab does. It is well-known that Octave is lagging in this regard. The basic problem is that it is a fairly large project to implement this and none of the core developers have the resources to do this project.

So, unless funding for this project appears or new contributors appear, I doubt that Octave will get a JIT in the near future. Feel free to prove me wrong, though :-)

Søren

P.S. The really is no reason to shout, we can read perfectly well without the capital letters :-)

Søren Hauberg <hauberg>
Sat 20 Nov 2010 06:33:07 PM UTC, comment #2: 

Many thanks for your prompt response and cursory glance, Rik!

I appreciate the suggestions and pointer to matlab's page.  I know about the loop deficiency with both matlab and octave, and this might be the thing that drives me to a lower level language.
Sometimes loops are absolutely necessary.

I am afraid you did not read my submission, so let me try to clarify a few points.

i) this routine cannot be vectorized, to my knowledge (and I am something of an expert at optimizing and vectorizing code and using matlab as well).

ii) I am talking about an ORDER OF MAGNITUDE difference BETWEEN MATLAB AND OCTAVE!

iii) pre-allocation will not help here either.

iv) there are no optimized library functions I know of to replace anything here.

It is necessary to follow the path of each site through its cycle of permutations.  There is no other way.  There IS a MAJOR problem with octave hidden here.

This submission should NOT be closed.

Thanks

kody law <kodo>
Sat 20 Nov 2010 05:23:06 PM UTC, comment #1: 

See Appendix C.2 "Tips for Making Code Run Faster" in the Octave documentation.  In general, you should avoid loops and vectorize the code.  Matlab itself also has a very good reference on getting code to run faster (http://www.mathworks.com/help/techdoc/matlab_prog/f8-784135.html). 

From a cursory glance, I would try the following
1) Vectorize the inner loop.
2) Pre-allocate return arrays such as v to avoid repeated memory allocations.
3) Use optimized library functions, such as find, rather than writing your own code to search through vectors.

Rik <rik5>
Group administrator
Fri 19 Nov 2010 10:52:14 PM UTC, original submission:  

The peculiarity is attached.  Any suggestions about how to speed it up would be greatly appreciated.  Thanks a lot for all your help!

A takes about 2.5 seconds on matlab, while B takes 2 seconds.  On octave the difference is more than an order of magnitude!

%%%% when A is uncommented and B is commented,
%%%% the routine takes 40 secs!

%%%% when B is uncommented and A is commented,
%%%% the routine takes 2 secs!

%%%% each time, the program sorts a permutation into
%%%% cycles, going through each element.  'lens' lists
%%%% the number of elements in permutations of each length

%%%% longer permutations =
%%%% fewer entries into while loop =
%%%% faster -- too much faster!

Thanks again, best

kody law <kodo>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #22064:  per.tar added by kodo (103KiB - application/x-tar)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by hauberg (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by kodo (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2010-11-20 rik5 Open/ClosedOpen Closed
    2010-11-19 kodo Attached File- Added per.tar, #22064

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code