bugGNU Octave - Bugs: bug #35400, Interpreter should recognize...

 
 

bug #35400: Interpreter should recognize equivalent of in-place operations for performance gain

Submitter:  Rik <rik5>
Submitted:  Mon 30 Jan 2012 01:45:07 AM UTC
   
 
Category:  Interpreter Severity:  2 - Minor
Priority:  5 - Normal Item Group:  Performance
Status:  Confirmed Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Tue 18 Apr 2023 03:42:44 PM UTC, comment #8: 

updating with octave 8.2.0 (results fairly stable over a few runs)


x = x + 1:
Elapsed time is 0.988505 seconds.

x++:
Elapsed time is 0.512677 seconds.

x += 1:
Elapsed time is 0.678747 seconds.


relative timing - 100%/51.9%/68.7%

so possibly the += operator has gotten more efficient, but the optimization mapping suggested comment #7 is still pending.

Nicholas Jankowski <nrjank>
Group Member
Wed 01 Dec 2021 12:24:58 AM UTC, comment #7: 

Good observations, but the bug report is only about performance of in-place operations.  There is no desire to change the semantics of the operators.

In particular,


A = A OP B


and


A OP= B


could be mapped to the same code because the second form is faster.  It only requires recognition by the parser that it should map to the second case.

Rik <rik5>
Group administrator
Wed 01 Dec 2021 12:10:48 AM UTC, comment #6: 

They are not the same.  x = x+1 and x += 1 do not change ans.   x++ changes ans.  Also y = x = x+1 will update both x and y but changing that to y = x++ will make y get the old value of x.

Anonymous
Tue 30 Nov 2021 10:05:46 PM UTC, comment #5: 

Go ahead and re-title.

I think it is possible, and useful, for the interpreter to recognize the pattern


A = A OP B


and optimize for it.

Rik <rik5>
Group administrator
Tue 30 Nov 2021 08:33:44 PM UTC, comment #4: 

Octave 6.4.0 on windows, the results I'm seeing from Rik's test script:

x = x + 1;
Elapsed time is 0.91841 seconds.
x++;
Elapsed time is 0.602464 seconds.
x += 1;
Elapsed time is 0.769149 seconds.

relative timing:

       Rik's c#0    Hartmut's c#2        mine
x+1         100%             100%        100%
x++         106%              43%         66%
x+=         141%              44%         84%


so... it seems the in-place operations have consistently improved since this was opened in 2012. should this remain open? should it at least be retitled to indicate the problem is now the x=x+1 performance penalty?  (is that a problem? should we expect the interpreter to be able to recognize those two operators and optimize it?)

Nicholas Jankowski <nrjank>
Group Member
Sun 20 Nov 2016 02:50:16 PM UTC, comment #3: 

This certainly could be fixed, but it will require medium to major changes to how the parser works.  This isn't necessarily a bad thing.  There is a subsasgn bug already out which would require the same change.  There have been requests to recognized true uint64 bit constants which the parser currently converts to double, etc.

Rik <rik5>
Group administrator
Sat 19 Nov 2016 08:10:48 PM UTC, comment #2: 

This issue is still (partly) present in Octave 4.2.0.

I now get the following result from the test script:

>> bm_accum

Elapsed time is 1.48891 seconds.
Elapsed time is 0.643239 seconds.
Elapsed time is 0.648474 seconds.


So we somehow improved the performance of the second command to match the third one. But the first one is still slower by a factor of two.

Would it be feasible at all, to perform the first (and most general syntax) command "x = x + 1" as an in place accumulation at all? If "no", then let's close this issue. If "yes", then let's keep it open.

Hartmut <hardy>
Mon 27 Jan 2014 02:29:54 AM UTC, comment #1: 

I get roughly the same results, still an issue in the current development version.

Mike Miller <mtmiller>
Group Member
Mon 30 Jan 2012 01:45:07 AM UTC, original submission:  

The increment operation can be coded a number of different ways in Octave.


x = x + 1;
x++;
x += 1;


After benchmarking the operations, it turns out that the third form is significantly faster (> 2X) than the others.  It is disconcerting to have the performance depend so heavily on exactly what construct the coder uses.

The reason for the performance speed-up is the work done by Jaroslav which means that the third case uses in-place accumulation rather than assigning to a temporary array.

One possible solution would be to have the parser recognize the first two forms as in-place operations and map to the existing code used in the third form.  This issue applies to any of the operators which also have in-place forms (+=, -=, *=, /=, &=, |=, ^=, etc.)

I'm attaching a benchmark script I used (bm_accum.m).  The test results are:

x = x + 1;
Elapsed time is 1.7 seconds.
x++;
Elapsed time is 1.8 seconds.
x += 1;
Elapsed time is 0.69 seconds.


Rik <rik5>
Group administrator

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #24912:  bm_accum.m added by rik5 (147B - text/x-octave)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by nrjank (Posted a comment)
  • -email is unavailable- added by hardy (Posted a comment)
  • -email is unavailable- added by rik5 (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 7 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2021-12-01 nrjank Operating SystemGNU/Linux Any
        SummaryPerformance of in-place operations Interpreter should recognize equivalent of in-place operations for performance gain
    2021-12-01 nrjank Severity3 - Normal 2 - Minor
    2021-12-01 mtmiller Carbon-CopyRemoved 80942 -
    2014-01-27 mtmiller StatusNone Confirmed
        Release3.6.0 dev
    2012-01-30 rik5 Attached File- Added bm_accum.m, #24912

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code