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

 
 

bug #48736: Multiplication is thrice as fast as division

Submitter:  deego <deego>
Submitted:  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
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

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

a./b

and

a.*c

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:


a=rand(1000000,1);
b=rand(1000000,1);
mean(round(a)!=round(a+b-.5))


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:

...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 +verbatim+ a./b -verbatim- and +verbatim+ a.*c -verbatim- 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:


a=rand(1000000,1);
b=rand(1000000,1);
mean(round(a)!=round(a+b-.5))


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:37:18 AM UTC, comment #9: 

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

...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 +verbatim+a./b-verbatim- and +verbatim+a.*c-verbatim- 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:


a=rand(1000000,1);
b=rand(1000000,1);
mean(round(a)!=round(a+b-.5))


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:34:14 AM UTC, comment #8: 

Of course.


a=rand(1000000,1);
b=rand(1000000,1);
mean(a./b!=a.*(1./b))


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 +verbatim+a./b-verbatim- and +verbatim+a.*c-verbatim- 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:


a=rand(1000000,1);
b=rand(1000000,1);
mean(round(a)!=round(a+b-.5))


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
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?

deego <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.



deego <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


x /= n


as


x *= 1/n


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


https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations


Further the link


https://gmplib.org/~tege/x86-timing.pdf


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


x /= n


as

x *= 1/n
-varbatim-

but I suspect that this would not be as accurate. What as the matlab times in this case ?

D.

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:


>> x = rand (1e8, 1);
>> tic; for i=1:10, x *= 1; endfor; mult_time = toc;
>> tic; for i=1:10, x /= 1; endfor; div_time = toc;
>> div_time / mult_time
ans =  2.5274


Mike Miller <mtmiller>
Group Member
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

deego <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
  •  

    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 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.13-f8d8.
    Corresponding source code