bugGNU Octave - Bugs: bug #48736, Multiplication is thrice as fast...

 
 

bug #48736: Multiplication is thrice as fast as division

Submitted by:  Dave Goel <deego>
Submitted on:  Tue 09 Aug 2016 07:04:46 PM UTC  
 
Category:  Interpreter Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Confirmed Assigned to:  None
Originator Name:  Dave Goel Open/Closed:  Open
Release:  dev Operating System:  GNU/Linux

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

( Jump to the original submission)

Wed 29 Mar 2017 07:40:08 AM UTC, comment #11:

...gives on my x86-64 about 0.27. And you can even motivate why this is about 25% (and for specific distributions a and b are drawn from would probably be exact): 1./b is an operation, and its result gets assigned to an intermediate variable (let's call it c), aquiring up to a half eps of rounding error. Thus, the exact results of
and
differ by this up to half eps. And now you assign these results again to floating-point variables. And if you do the convolutions, you get 25% in different bins, which you can simulate like this:

In this context: https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html What Every Computer Scientist Should Know About Floating-Point Arithmetic: "The IEEE standard requires that the result of addition, subtraction, multiplication and division be exactly rounded." Octave wants to be IEEE 754 compliant, isn't it? Thus, every computer scientist should read up on floating-point arithmetic, and if he decides that in this specific application it is not necessary, he is free to do this optimization by hand. Otherwise, on octave forge there is an unmaintained fenv package listed. Perhaps this can relax the compliance, allowing octave to optimize such expressions (which would be a nice feature request -- I would definitely turn it on by default, as the only purpose of the strict compliance can be for debugging on different platforms, while if you see effects due to this in standard operation, you are probably just computing artefacts anyway).

Anonymous
Wed 29 Mar 2017 07:38:33 AM UTC, comment #10:

Next try:

Anonymous
Wed 29 Mar 2017 07:37:18 AM UTC, comment #9:

Sorry, the bug tracker got confused. My post should continue like this:

Anonymous
Wed 29 Mar 2017 07:34:14 AM UTC, comment #8:

Of course.

Anonymous
Sun 14 Aug 2016 01:36:28 AM UTC, comment #7:

Also, I am still trying to understand why the computational complexity of division should be higher.

Are there any instances of /scalars/ a and b where

a/b and a*(1/b) yield or are supposed to yield different results?

Dave Goel <deego>
Thu 11 Aug 2016 07:40:21 PM UTC, comment #6:

Thanks for pointing out (anonymous) that the computation complexity of division is higher.

Something is still funny. That is, .*= is still thrice as expensive as *=, even when RHS is a scalar. Jordigh mused on irc that's probably because it's (needlessly) going through some broadcasting in the former case.

Dave Goel <deego>
Wed 10 Aug 2016 10:47:49 PM UTC, comment #5:

The Octave in-place operators are faster.

>> tic; for i=1:50, x *= 1; end; mult_time = toc;
>> tic; for i=1:50, x /= 1; end; div_time = toc;
>> [mult_time div_time div_time/mult_time]

ans =

7.3420 27.5783 3.7562

Ceral Paquet <octavebugs>
Wed 10 Aug 2016 10:44:18 PM UTC, comment #4:

This is on a 2 core CPU, 64 bit compile, Linux Ububtu.

x = rand (1e8, 1);
tic; for i=1:50, x = x*1; end; mult_time = toc;
tic; for i=1:50, x = x/1; end; div_time = toc;
[mult_time div_time div_time/mult_time]

Matlab 2016a 64 bit:
ans =

4.7037 7.4285 1.5793

Octave 4.01 64 bit:
ans =

14.1054 31.6478 2.2437

Ceral Paquet <octavebugs>
Wed 10 Aug 2016 12:15:21 PM UTC, comment #3:

Forgot to close the last verbatim block the last past of my comment should read

as

Though I suspect this will result in a lose of precision. What as Matlab timing for these cases ?

D.

Anonymous
Wed 10 Aug 2016 12:13:08 PM UTC, comment #2:

The computational complexity of the division operator is higher than the multiplication operator. See the link

Further the link

shows that there is about a factor of 5 difference in the number of cycles for scalr division and multiplication.

Ok, perhaps Octave should be expanding

as

Anonymous
Wed 10 Aug 2016 01:27:23 AM UTC, comment #1:

I see a similar performance difference between the in-place multiplication and division by a scalar:

Mike Miller <mtmiller>
Project Administrator
Tue 09 Aug 2016 07:04:46 PM UTC, original submission:

Dear Octave,

Jordi suggested I report this. I have tested these statistics multiple times, on several versions (3.8.2 on debian stable, HG checkout version, etc).

The paste below, from the HG version, is representative of the general observation: *= is much faster than /=. And, ./= is the slowest. For developers, this might point to optimization tricks.

The practical upshot for users is to favor = over /=, .=, and ./= when RHS is a scalar.
That is, instead of using a./=33, use a*=(1/33).

octave:8> a=randn(5000,6000);
octave:9> tic; a*=2; toc ### THRICE AS FAST AS ./= BELOW.
Elapsed time is 0.133503 seconds.
octave:10> tic; a/=2; toc
Elapsed time is 0.309753 seconds.
octave:11> tic; a.*=2; toc
Elapsed time is 0.32136 seconds.
octave:12> tic; a./=2; toc
Elapsed time is 0.438965 seconds.

Dave

Dave Goel <deego>

 

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

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by octavebugs (Posted a comment)
  • -email is unavailable- added by mtmiller (Posted a comment)
  • -email is unavailable- added by deego (Submitted the item)
  • -email is unavailable- added by deego
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

     

     

    Follow 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-08-10 mtmiller CategoryNone => Interpreter
        Item GroupNone => Performance
        StatusNone => Confirmed
    2016-08-09 deego Carbon-Copy- => Added -email is unavailable-

    Back to the top


    Powered by Savane 3.4