www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Compiler optimizations

reply "Craig Black" <cblack ara.com> writes:
So I've been playing around with the pi program.  I ported it to C++ and
I've been doing some benchmarks with MSVC.  It seems that MSVC is a little
faster when SSE2 instructions are enabled.  It is slower when they are
disabled.  Which leads me to a question.  Does the D backend make use of SSE
2 intstructions?  I think the answer is yes but perhaps the optimizer is not
quite as sophisticated as MSVC yet.

Another question for someone who knows a lot about backend optimizations.
I've noticed that integer division is faster when the the divisor is a
constant.  How does the compiler optimize this?

Another thing.  I know that integer division is essentially a floating point
operation because there is no integer division instruction.  I also read
some on the internet and learned that Intel has a library that provides
fixed-point math routines, which provides a division operation that
outperforms floating-point division.  Then I thought to myself, "Why don't
compilers just use fixed-point division for dividing integers since it's
faster?"

I know some of you out there know way more than me so please all you smart
people give me some input.

-Craig
Apr 30 2006
parent reply dennis luehring <dl.soluz gmx.net> writes:
 Another thing.  I know that integer division is essentially a floating point
 operation because there is no integer division instruction.

and what is "idiv" for you? (http://www.jegerlehner.ch/intel/opcode.html)
 I also read
 some on the internet and learned that Intel has a library that provides
 fixed-point math routines, which provides a division operation that
 outperforms floating-point division.  Then I thought to myself, "Why don't
 compilers just use fixed-point division for dividing integers since it's
 faster?"

a fixpoint floating somethimes outperforms an floating-point operating (with loss of precession) but it never outperforms an true integer division ciao dennis
Apr 30 2006
parent reply "Craig Black" <cblack ara.com> writes:
"dennis luehring" <dl.soluz gmx.net> wrote in message
news:e32c0m$1dsu$1 digitaldaemon.com...
 Another thing.  I know that integer division is essentially a floating


 operation because there is no integer division instruction.

and what is "idiv" for you? (http://www.jegerlehner.ch/intel/opcode.html)

Please anyone, correct me if I'm wrong, but I think IDIV is a pseudo-instruction. 80x86 is notorious for those (as opposed to RISC). I read on the Intel website that intel processors do not have a hardware integer division instruction. Apparently it is somehow better to use the floating point instruction instead. The benchmarks that I've done are constistent with this. I found it was faster to perform a floating-point multiplication on an integer and then convert it back to an integer than just a single integer division.
 I also read
 some on the internet and learned that Intel has a library that provides
 fixed-point math routines, which provides a division operation that
 outperforms floating-point division.  Then I thought to myself, "Why


 compilers just use fixed-point division for dividing integers since it's
 faster?"

a fixpoint floating somethimes outperforms an floating-point operating (with loss of precession) but it never outperforms an true integer division ciao dennis

Have you run benchmarks? -Craig
Apr 30 2006
parent reply dennis luehring <dl.soluz gmx.net> writes:
 Please anyone, correct me if I'm wrong, but I think IDIV is a
 pseudo-instruction.  80x86 is notorious for those (as opposed to RISC).  I
 read on the Intel website that intel processors do not have a hardware
 integer division instruction.  Apparently it is somehow better to use the
 floating point instruction instead.

i don't know the truth - but why should all the compiler vendors around us (microsoft, intel, ...) produce the slower code if there is an faster solution? what is the reason (maybe it produce lager code - it this will produce more cache problems...)
 The benchmarks that I've done are constistent with this.  I found it was
 faster to perform a floating-point multiplication on an integer and then
 convert it back to an integer than just a single integer division.

can you post your benchmark source?
 Have you run benchmarks?

no - but i can run your benchmark...
Apr 30 2006
parent reply "Craig Black" <cblack ara.com> writes:
"dennis luehring" <dl.soluz gmx.net> wrote in message
news:e32dfl$1f53$1 digitaldaemon.com...
 Please anyone, correct me if I'm wrong, but I think IDIV is a
 pseudo-instruction.  80x86 is notorious for those (as opposed to RISC).


 read on the Intel website that intel processors do not have a hardware
 integer division instruction.  Apparently it is somehow better to use


 floating point instruction instead.

i don't know the truth - but why should all the compiler vendors around us (microsoft, intel, ...) produce the slower code if there is an faster solution? what is the reason (maybe it produce lager code - it this will produce more cache problems...)

I'm not saying that there is a faster solution, but there might be. Mainly, I'm just trying to learn more so that I will be better at optimizing my code.
 The benchmarks that I've done are constistent with this.  I found it was
 faster to perform a floating-point multiplication on an integer and then
 convert it back to an integer than just a single integer division.

can you post your benchmark source?
 Have you run benchmarks?

no - but i can run your benchmark...

These two functions show the difference that I'm talking about. When benchmarking, pass in the same values for the divisor (pick a value between 2 and 30), and pass in a large enough value for total so that it will take some time for the CPU to finish. Suprisingly, the second one is faster. -Craig int divTest1(int divisor, int total) { int sum = 0; for(int i = 0; i < total; i++) { int quotient = i / divisor; sum += quotient; } } int divTest2(int divisor, int total) { int sum = 0; double idiv = 1.0 / divisor; for(int i = 0; i < total; i++) { int quotient = i * idiv; sum += quotient; } }
Apr 30 2006
next sibling parent reply James Pelcis <jpelcis gmail.com> writes:
This doesn't really surprise me.  If I am reading it correctly, the
major difference comes from only doing the division once.  If you did
the division every time, the results might not be the same.

Craig Black wrote:
 These two functions show the difference that I'm talking about.  When
 benchmarking, pass in the same values for the divisor (pick a value between
 2 and 30), and pass in a large enough value for total so that it will take
 some time for the CPU to finish.  Suprisingly, the second one is faster.
 
 -Craig
 
 int divTest1(int divisor, int total)
 {
   int sum = 0;
   for(int i = 0; i < total; i)
   {
     int quotient = i / divisor;
     sum = quotient;
   }
 }
 
 int divTest2(int divisor, int total)
 {
   int sum = 0;
   double idiv = 1.0 / divisor;
   for(int i = 0; i < total; i)
   {
     int quotient = i * idiv;
     sum = quotient;
   }
 }

Apr 30 2006
parent reply "Craig Black" <cblack ara.com> writes:
 This doesn't really surprise me.  If I am reading it correctly, the
 major difference comes from only doing the division once.  If you did
 the division every time, the results might not be the same.

I don't think you realize what is happening here ... we are dealing with integer division vs. floating point multiplication. With the floating point multiplication we have 1) conversion from int to a floating point 2) the floating point multiplication 3) convertion from floating point back to int Although CPUs have gotten faster at converting to and from floating points, the conversion is not trivial to performance. What's suprising is that these three operations are faster than a singe integer division. This is because integer division is essentially floating point division under the hood. -Craig
Apr 30 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
Craig Black wrote:
  This is
 because integer division is essentially floating point division under the
 hood.

Not exactly. What is true is that both kinds of division are based on the same 'shift and subtract' method (the same algorithm taught in 3rd grade for doing long division). If you're really interested in exactly how integer and floating point division work, get the Digital Mars CD which has complete source code to an IEEE 754 floating point emulator, as well as code to do integer division for long's. www.digitalmars.com/shop.html
May 02 2006
parent reply Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
Walter Bright wrote:
 Craig Black wrote:
  This is
 because integer division is essentially floating point division under the
 hood.

Not exactly. What is true is that both kinds of division are based on the same 'shift and subtract' method (the same algorithm taught in 3rd grade for doing long division). If you're really interested in exactly how integer and floating point division work, get the Digital Mars CD which has complete source code to an IEEE 754 floating point emulator, as well as code to do integer division for long's. www.digitalmars.com/shop.html

I ran these tests and I got basicly the same results (the int division is slower). I am very intrigued and confused. Can you (or someone else) explain briefly why this is so? One would think it would be the other way around (float being slower) or at least the same speed. -- Bruno Medeiros - CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
May 03 2006
next sibling parent Walter Bright <newshound digitalmars.com> writes:
Bruno Medeiros wrote:
 I ran these tests and I got basicly the same results (the int division 
 is slower). I am very intrigued and confused. Can you (or someone else) 
 explain briefly why this is so?
 One would think it would be the other way around (float being slower) or 
 at least the same speed.

I don't know. I'm surprised at such results. Perhaps it's because Intel has put a lot of effort into their FPU they haven't into integer math.
May 03 2006
prev sibling next sibling parent reply Thomas Kuehne <thomas-dloop kuehne.cn> writes:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Bruno Medeiros schrieb am 2006-05-03:
 Walter Bright wrote:
 Craig Black wrote:
  This is
 because integer division is essentially floating point division under the
 hood.


I ran these tests and I got basicly the same results (the int division is slower). I am very intrigued and confused. Can you (or someone else) explain briefly why this is so? One would think it would be the other way around (float being slower) or at least the same speed.

The code doesn't necessarily show that int division is slower than float multiplication. What CPU are we talking about? A naive interpretation of the "benchmark" assumes a single execution pipe that does floating point and integer operations in sequence ... Even assuming a single pipe: Why is the SSE version faster? Does the benchmark measure the speed of int division against float multiplication? Does the benchmark measure the throughput of int division against float multiplication? Does the benchmark measure the throughput of int division of a set of numbers through a constant factor against float multiplication of the same set through (1 / constant factor)? Thomas -----BEGIN PGP SIGNATURE----- iD8DBQFEWRDO3w+/yD4P9tIRAs8lAJ9q62J8zf8U0HWzxtxQmMWasuU4ngCgwA21 4M5nb9Z8ZXHevJiwylY/wGM= =QSyS -----END PGP SIGNATURE-----
May 03 2006
parent reply Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
Thomas Kuehne wrote:
 -----BEGIN PGP SIGNED MESSAGE-----
 Hash: SHA1
 
 Bruno Medeiros schrieb am 2006-05-03:
 Walter Bright wrote:
 Craig Black wrote:
  This is
 because integer division is essentially floating point division under the
 hood.


is slower). I am very intrigued and confused. Can you (or someone else) explain briefly why this is so? One would think it would be the other way around (float being slower) or at least the same speed.

The code doesn't necessarily show that int division is slower than float multiplication. What CPU are we talking about? A naive interpretation of the "benchmark" assumes a single execution pipe that does floating point and integer operations in sequence ... Even assuming a single pipe: Why is the SSE version faster? Does the benchmark measure the speed of int division against float multiplication? Does the benchmark measure the throughput of int division against float multiplication? Does the benchmark measure the throughput of int division of a set of numbers through a constant factor against float multiplication of the same set through (1 / constant factor)? Thomas -----BEGIN PGP SIGNATURE----- iD8DBQFEWRDO3w+/yD4P9tIRAs8lAJ9q62J8zf8U0HWzxtxQmMWasuU4ngCgwA21 4M5nb9Z8ZXHevJiwylY/wGM= =QSyS -----END PGP SIGNATURE-----

Hum, yes I should have been more specific. I only ran (a modified version of) the latest test, which measured the throughput of int division against double division (I hope...). Let me just put the code: #include <stdio.h> #include <time.h> //typedef double divtype; typedef int divtype; int main() { clock_t start = clock(); divtype result = 0; divtype div=1; for(int max = 100000000; div < max; div++) { result = (42 / div); } clock_t finish = clock(); double duration = (double)(finish - start) / CLOCKS_PER_SEC; printf("[%f] %2.2f seconds\n", double(result),duration); } ------------------------------------ I ran the tests with GCC, with both -O0 and -O2, on an Athlon XP, and it both cases the typedef double divtype version was about twice as fast. The assembly code I get for line 17 is the following: *** INT: .stabn 68,0,17,LM6-_main LM6: movl $42, %edx movl %edx, %eax sarl $31, %edx idivl -12(%ebp) movl %eax, -8(%ebp) *** DOUBLE: .stabn 68,0,17,LM6-_main LM6: flds LC0 fdivs -12(%ebp) fstps -8(%ebp) I have little idea what it is that it's doing. -- Bruno Medeiros - CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
May 04 2006
next sibling parent reply Don Clugston <dac nospam.com.au> writes:
Bruno Medeiros wrote:
 Thomas Kuehne wrote:
 -----BEGIN PGP SIGNED MESSAGE-----
 Hash: SHA1

 Bruno Medeiros schrieb am 2006-05-03:
 Walter Bright wrote:
 Craig Black wrote:
  This is
 because integer division is essentially floating point division 
 under the
 hood.


division is slower). I am very intrigued and confused. Can you (or someone else) explain briefly why this is so? One would think it would be the other way around (float being slower) or at least the same speed.



It's true. For Pentium, IDIV takes 46 cycles, while FDIV takes 39. For PPro, PII and PIII, DIV takes 39, while FDIV takes 38. Not much difference. However, for P4 (and probably Athlon XP is similar), FDIV has a latency of 43 cycles, while DIV has a latency of 50, plus it executes 21 microcodes! It's not quite a factor of two, but it's close. In short -- Intel killed integer division on the P4.
May 04 2006
parent pmoore <pmoore_member pathlink.com> writes:
It depends how big the dividend and divisor are. Smaller values can take much
less time than larger ones.

In article <e3cqjr$sek$1 digitaldaemon.com>, Don Clugston says...
Bruno Medeiros wrote:
 Thomas Kuehne wrote:
 -----BEGIN PGP SIGNED MESSAGE-----
 Hash: SHA1

 Bruno Medeiros schrieb am 2006-05-03:
 Walter Bright wrote:
 Craig Black wrote:
  This is
 because integer division is essentially floating point division 
 under the
 hood.


division is slower). I am very intrigued and confused. Can you (or someone else) explain briefly why this is so? One would think it would be the other way around (float being slower) or at least the same speed.



It's true. For Pentium, IDIV takes 46 cycles, while FDIV takes 39. For PPro, PII and PIII, DIV takes 39, while FDIV takes 38. Not much difference. However, for P4 (and probably Athlon XP is similar), FDIV has a latency of 43 cycles, while DIV has a latency of 50, plus it executes 21 microcodes! It's not quite a factor of two, but it's close. In short -- Intel killed integer division on the P4.

May 04 2006
prev sibling parent reply pmoore <pmoore_member pathlink.com> writes:
It looks to me that your double division is actually encoded as float division
ie 32 bits. I am not too familiar with this syntax but i believe double
precision would look like this:

fldd	LC0
fdivd	-12(%ebp)
fstpd	-8(%ebp)

I am not surprised that the FPU version is faster than the int one. You will
probably find that the Intel version is not the same as the AMD one either.


In article <e3co5o$jth$1 digitaldaemon.com>, Bruno Medeiros says...
Thomas Kuehne wrote:
 -----BEGIN PGP SIGNED MESSAGE-----
 Hash: SHA1
 
 Bruno Medeiros schrieb am 2006-05-03:
 Walter Bright wrote:
 Craig Black wrote:
  This is
 because integer division is essentially floating point division under the
 hood.


is slower). I am very intrigued and confused. Can you (or someone else) explain briefly why this is so? One would think it would be the other way around (float being slower) or at least the same speed.

The code doesn't necessarily show that int division is slower than float multiplication. What CPU are we talking about? A naive interpretation of the "benchmark" assumes a single execution pipe that does floating point and integer operations in sequence ... Even assuming a single pipe: Why is the SSE version faster? Does the benchmark measure the speed of int division against float multiplication? Does the benchmark measure the throughput of int division against float multiplication? Does the benchmark measure the throughput of int division of a set of numbers through a constant factor against float multiplication of the same set through (1 / constant factor)? Thomas -----BEGIN PGP SIGNATURE----- iD8DBQFEWRDO3w+/yD4P9tIRAs8lAJ9q62J8zf8U0HWzxtxQmMWasuU4ngCgwA21 4M5nb9Z8ZXHevJiwylY/wGM= =QSyS -----END PGP SIGNATURE-----

Hum, yes I should have been more specific. I only ran (a modified version of) the latest test, which measured the throughput of int division against double division (I hope...). Let me just put the code: #include <stdio.h> #include <time.h> //typedef double divtype; typedef int divtype; int main() { clock_t start = clock(); divtype result = 0; divtype div=1; for(int max = 100000000; div < max; div++) { result = (42 / div); } clock_t finish = clock(); double duration = (double)(finish - start) / CLOCKS_PER_SEC; printf("[%f] %2.2f seconds\n", double(result),duration); } ------------------------------------ I ran the tests with GCC, with both -O0 and -O2, on an Athlon XP, and it both cases the typedef double divtype version was about twice as fast. The assembly code I get for line 17 is the following: *** INT: .stabn 68,0,17,LM6-_main LM6: movl $42, %edx movl %edx, %eax sarl $31, %edx idivl -12(%ebp) movl %eax, -8(%ebp) *** DOUBLE: .stabn 68,0,17,LM6-_main LM6: flds LC0 fdivs -12(%ebp) fstps -8(%ebp) I have little idea what it is that it's doing. -- Bruno Medeiros - CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D

May 04 2006
parent Don Clugston <dac nospam.com.au> writes:
pmoore wrote:
 It looks to me that your double division is actually encoded as float division
 ie 32 bits. I am not too familiar with this syntax but i believe double
 precision would look like this:
 
 fldd	LC0
 fdivd	-12(%ebp)
 fstpd	-8(%ebp)

That would be faster, actually (provided it's aligned sensibly). The precision only applies to the width of the load from memory. To reduce precision of the division itself (which increases the speed), you have to set the machine status word.
 I am not surprised that the FPU version is faster than the int one. You will
 probably find that the Intel version is not the same as the AMD one either.

That's definitely true.
 
 
 In article <e3co5o$jth$1 digitaldaemon.com>, Bruno Medeiros says...
 Thomas Kuehne wrote:
 -----BEGIN PGP SIGNED MESSAGE-----
 Hash: SHA1

 Bruno Medeiros schrieb am 2006-05-03:
 Walter Bright wrote:
 Craig Black wrote:
  This is
 because integer division is essentially floating point division under the
 hood.


is slower). I am very intrigued and confused. Can you (or someone else) explain briefly why this is so? One would think it would be the other way around (float being slower) or at least the same speed.

The code doesn't necessarily show that int division is slower than float multiplication. What CPU are we talking about? A naive interpretation of the "benchmark" assumes a single execution pipe that does floating point and integer operations in sequence ... Even assuming a single pipe: Why is the SSE version faster? Does the benchmark measure the speed of int division against float multiplication? Does the benchmark measure the throughput of int division against float multiplication? Does the benchmark measure the throughput of int division of a set of numbers through a constant factor against float multiplication of the same set through (1 / constant factor)? Thomas -----BEGIN PGP SIGNATURE----- iD8DBQFEWRDO3w+/yD4P9tIRAs8lAJ9q62J8zf8U0HWzxtxQmMWasuU4ngCgwA21 4M5nb9Z8ZXHevJiwylY/wGM= =QSyS -----END PGP SIGNATURE-----

version of) the latest test, which measured the throughput of int division against double division (I hope...). Let me just put the code: #include <stdio.h> #include <time.h> //typedef double divtype; typedef int divtype; int main() { clock_t start = clock(); divtype result = 0; divtype div=1; for(int max = 100000000; div < max; div++) { result = (42 / div); } clock_t finish = clock(); double duration = (double)(finish - start) / CLOCKS_PER_SEC; printf("[%f] %2.2f seconds\n", double(result),duration); } ------------------------------------ I ran the tests with GCC, with both -O0 and -O2, on an Athlon XP, and it both cases the typedef double divtype version was about twice as fast. The assembly code I get for line 17 is the following: *** INT: .stabn 68,0,17,LM6-_main LM6: movl $42, %edx movl %edx, %eax sarl $31, %edx idivl -12(%ebp) movl %eax, -8(%ebp) *** DOUBLE: .stabn 68,0,17,LM6-_main LM6: flds LC0 fdivs -12(%ebp) fstps -8(%ebp) I have little idea what it is that it's doing. -- Bruno Medeiros - CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D


May 04 2006
prev sibling parent reply Dave <Dave_member pathlink.com> writes:
Bruno Medeiros wrote:
 Walter Bright wrote:
 Craig Black wrote:
  This is
 because integer division is essentially floating point division under 
 the
 hood.

Not exactly. What is true is that both kinds of division are based on the same 'shift and subtract' method (the same algorithm taught in 3rd grade for doing long division). If you're really interested in exactly how integer and floating point division work, get the Digital Mars CD which has complete source code to an IEEE 754 floating point emulator, as well as code to do integer division for long's. www.digitalmars.com/shop.html

I ran these tests and I got basicly the same results (the int division is slower). I am very intrigued and confused. Can you (or someone else) explain briefly why this is so? One would think it would be the other way around (float being slower) or at least the same speed.

If you take a look at the assembly for div(), idiv is being executed twice - once for the division and once for the modulo. If you replace the modulo with the explicit calculation then the perf. will improve a lot because imul & sub is faster than idiv. It'd be nice if dmd would do this optimization for us because calculating the integer quotient and subsequent remainder for the same dividend and divisor would seem to be pretty common operations.
May 03 2006
parent Dave <Dave_member pathlink.com> writes:
Dave wrote:
 Bruno Medeiros wrote:
 Walter Bright wrote:
 Craig Black wrote:
  This is
 because integer division is essentially floating point division 
 under the
 hood.

Not exactly. What is true is that both kinds of division are based on the same 'shift and subtract' method (the same algorithm taught in 3rd grade for doing long division). If you're really interested in exactly how integer and floating point division work, get the Digital Mars CD which has complete source code to an IEEE 754 floating point emulator, as well as code to do integer division for long's. www.digitalmars.com/shop.html

I ran these tests and I got basicly the same results (the int division is slower). I am very intrigued and confused. Can you (or someone else) explain briefly why this is so? One would think it would be the other way around (float being slower) or at least the same speed.

If you take a look at the assembly for div(), idiv is being executed twice - once for the division and once for the modulo. If you replace the modulo with the explicit calculation then the perf. will improve a lot because imul & sub is faster than idiv.

Obviously I was talking about the original pi.d implementation that's using the int modulo operator in the div() function: quotient = b / divisor; //remainder = b % divisor; remainder = b - quotient * divisor; // a lot faster
 It'd be nice if dmd would do this optimization for us because 
 calculating the integer quotient and subsequent remainder for the same 
 dividend and divisor would seem to be pretty common operations.

Don't get me wrong - dmd does great for integer stuff IMHO, this is just one small issue I've noticed...
May 03 2006
prev sibling next sibling parent reply dennis luehring <dl.soluz gmx.net> writes:
small change

 int divTest2(int divisor, int total)
 {
   int sum = 0;
   for(int i = 0; i < total; i++)
   {
     int quotient = i * ( 1.0 / divisor ); // !!!!!!!!
     sum += quotient;
   }
 }

Apr 30 2006
next sibling parent reply "Craig Black" <cblack ara.com> writes:
 int divTest2(int divisor, int total)
 {
   int sum = 0;
   for(int i = 0; i < total; i++)
   {
     int quotient = i * ( 1.0 / divisor ); // !!!!!!!!
     sum += quotient;
   }
 }


I don't see what you are trying to say here. -Craig
Apr 30 2006
parent reply dennis luehring <dl.soluz gmx.net> writes:
 int divTest2(int divisor, int total)
 {
   int sum = 0;
   for(int i = 0; i < total; i++)
   {
     int quotient = i * ( 1.0 / divisor ); // !!!!!!!!
     sum += quotient;
   }
 }



you say that integer devision is slower then the same division in floating point - or? but what is the problem with my benchmark then? --- sorry in c --- #include <stdio.h> #include <conio.h> #include <time.h> int main() { int result = 0; int div = 10; //(or double) !!! clock_t start, finish; double duration; start = clock(); for(int l=0; l<100000; l++) { for(int i=0; i<10000; i++) { result += (i*div) / div; } } finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf("[%i] %2.1f seconds\n",result,duration); getch(); } on 3Ghz: int: ~4.8 seconds double: ~41.7 seconds - nearly ten times slower the problem with your benchmark is that your results are not really usable try to write an "int doIntDivisionWithFloat(int Value, int Div)" and benchmark this one - not do the benchmark on the half of such an function... int IntDivUsingInt(int divisor, int value) { return value/divisor; } int IntDivUsingFloat(int divisor, int value) { return value * (1.0 / divisor); } for(int i = 0; i < longlongtime; i++) { do IntDivUsingInt( 10, i*10 ); or IntDivUsingFloat( 10, i*10 ); } is your IntDivUsingFloat still faster? ciao dennis
Apr 30 2006
next sibling parent reply dennis luehring <dl.soluz gmx.net> writes:
and if still don't understand your "optimizing"
try to write an "real" benchmark with value and divisor change every step

your tests just show us - wow! multipling is much faster then dividing - 
and that is something we all know very well (in float and int) :-)

ciao dennis
Apr 30 2006
parent "Craig Black" <cblack ara.com> writes:
 your tests just show us - wow! multipling is much faster then dividing -
 and that is something we all know very well (in float and int) :-)

No, actually it shows us that integer division can be slower than floating point division. This is because it uses floating point division under the hood and requires that the divisor be converted from int to float. -Craig
Apr 30 2006
prev sibling parent "Craig Black" <cblack ara.com> writes:
Yours used a constant divisor which allowed the compiler to optimize it
somehow.  That's one of the things that I'm trying to figure out.  How does
the compiler optimize integer division so well when the divisor is constant?
Anyway, try this one.

#include <stdio.h>
#include <conio.h>
#include <time.h>

//typedef int divtype;
typedef double divtype; // this one is faster

int Division(divtype div)
{
  int result = 0;
  for(int i=0; i<10000; i++)
  {
     result += i / div;
  }
  return result;
}

int main()
{
   int result = 0;
   int div = 10; //(or double) !!!

   clock_t start, finish;
   double  duration;

   start = clock();
   for(divtype div=1; div<10000; div++)
   {
     result = Division(div);
   }
   finish = clock();
   duration = (double)(finish - start) / CLOCKS_PER_SEC;

   printf("[%i] %2.1f seconds\n",result,duration);
}
Apr 30 2006
prev sibling parent "Craig Black" <cblack ara.com> writes:
If you want to get a direct comparison between floating point and integer
division, then use

 int divTest2(double divisor, int total)
 {
   int sum = 0;
   for(int i = 0; i < total; i++)
   {
     int quotient = i / divisor; // !!!!!!!!
     sum += quotient;
   }
 }


Apr 30 2006
prev sibling next sibling parent reply Ben Phillips <Ben_member pathlink.com> writes:
In article <e32q1p$22dv$1 digitaldaemon.com>, Craig Black says...
These two functions show the difference that I'm talking about.  When
benchmarking, pass in the same values for the divisor (pick a value between
2 and 30), and pass in a large enough value for total so that it will take
some time for the CPU to finish.  Suprisingly, the second one is faster.

-Craig

int divTest1(int divisor, int total)
{
  int sum = 0;
  for(int i = 0; i < total; i++)
  {
    int quotient = i / divisor;
    sum += quotient;
  }
}

int divTest2(int divisor, int total)
{
  int sum = 0;
  double idiv = 1.0 / divisor;
  for(int i = 0; i < total; i++)
  {
    int quotient = i * idiv;
    sum += quotient;
  }
}

The second one is faster because you cheat. You aren't testing integer division but rather floating point multiplication. The first one has to divide every time through the loop, the second one only has to multiply. Multiplication is much faster than division (even floating point multiplication vs integer division), so your results are not surprising and are not really useful.
Apr 30 2006
parent reply "Craig Black" <cblack ara.com> writes:
 The second one is faster because you cheat.

Nope. Try this one. On my computer the floating point division is twice as fast. I believe this is due to the overhead on converting the divisor from int to double before performing the division. #include <stdio.h> #include <conio.h> #include <time.h> //typedef int divtype; typedef double divtype; // this one is faster int main() { int result = 0; clock_t start, finish; double duration; start = clock(); for(divtype div=1; div<10000; div++) { for(int i=0; i<10000; i++) { result += i / div; } } finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf("[%i] %2.1f seconds\n",result,duration); }
Apr 30 2006
next sibling parent reply dennis luehring <dl.soluz gmx.net> writes:
Craig Black schrieb:
 Nope. Try this one. On my computer the floating point division is twice as

sorry but on my system int division is two times faster than floating point and by the way - the usage of the "double" in the first loop don't realy help to focus the bechmarking (incrementing int is much faster them incerenting floating points) ciao dennis
Apr 30 2006
parent reply "Craig Black" <cblack ara.com> writes:
This is probably because you have SSE optimizations disabled.
This one works even without SSE.  This shows that integer division is
slower.  Also, if you change the division to multiplication, you will notice
that integer multiplication is faster, which is what you would expect.

#include <stdio.h>
#include <conio.h>
#include <time.h>

//typedef int divtype;
typedef double divtype; // This one is faster

int main()
{
   divtype result = 0;

   clock_t start, finish;
   double  duration;

   start = clock();
   divtype max = 100000000;
   for(divtype div=1; div<max; div++)
   {
     divtype i = max - div;
     result += i / div;
   }
   finish = clock();
   duration = (double)(finish - start) / CLOCKS_PER_SEC;

   printf("[%f] %2.1f seconds\n",double(result),duration);
}
Apr 30 2006
next sibling parent reply dennis luehring <dl.soluz gmx.net> writes:
Craig Black schrieb:
 This is probably because you have SSE optimizations disabled.
 This one works even without SSE.  This shows that integer division is
 slower.  Also, if you change the division to multiplication, you will notice
 that integer multiplication is faster, which is what you would expect.

your right the double version is faster - i don't think that it can be used with integer division - because the to-float and back-to-int conversion costs too much... ciao dennis
Apr 30 2006
parent "Craig Black" <cblack ara.com> writes:
"dennis luehring" <dl.soluz gmx.net> wrote in message 
news:e34ak8$17sg$1 digitaldaemon.com...
 Craig Black schrieb:
 This is probably because you have SSE optimizations disabled.
 This one works even without SSE.  This shows that integer division is
 slower.  Also, if you change the division to multiplication, you will 
 notice
 that integer multiplication is faster, which is what you would expect.

your right the double version is faster - i don't think that it can be used with integer division - because the to-float and back-to-int conversion costs too much... ciao dennis

Not if SSE is enabled. I have actually experienced significant performance increases by doing so. -Craig
May 01 2006
prev sibling parent reply Walter Bright <newshound digitalmars.com> writes:
On my machine, integer is still faster.

int: 3.7
double: 4.2

Craig Black wrote:
 This is probably because you have SSE optimizations disabled.
 This one works even without SSE.  This shows that integer division is
 slower.  Also, if you change the division to multiplication, you will notice
 that integer multiplication is faster, which is what you would expect.
 
 #include <stdio.h>
 #include <conio.h>
 #include <time.h>
 
 //typedef int divtype;
 typedef double divtype; // This one is faster
 
 int main()
 {
    divtype result = 0;
 
    clock_t start, finish;
    double  duration;
 
    start = clock();
    divtype max = 100000000;
    for(divtype div=1; div<max; div++)
    {
      divtype i = max - div;
      result += i / div;
    }
    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
 
    printf("[%f] %2.1f seconds\n",double(result),duration);
 }
 
 

May 03 2006
parent pmoore <pmoore_member pathlink.com> writes:
I think I remember you posting a while ago that you have quite an old machine :)

In article <e3bdub$1dsu$3 digitaldaemon.com>, Walter Bright says...
On my machine, integer is still faster.

int: 3.7
double: 4.2

Craig Black wrote:
 This is probably because you have SSE optimizations disabled.
 This one works even without SSE.  This shows that integer division is
 slower.  Also, if you change the division to multiplication, you will notice
 that integer multiplication is faster, which is what you would expect.
 
 #include <stdio.h>
 #include <conio.h>
 #include <time.h>
 
 //typedef int divtype;
 typedef double divtype; // This one is faster
 
 int main()
 {
    divtype result = 0;
 
    clock_t start, finish;
    double  duration;
 
    start = clock();
    divtype max = 100000000;
    for(divtype div=1; div<max; div++)
    {
      divtype i = max - div;
      result += i / div;
    }
    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
 
    printf("[%f] %2.1f seconds\n",double(result),duration);
 }
 
 


May 04 2006
prev sibling parent Walter Bright <newshound digitalmars.com> writes:
On my machine, the int version is 1.7 seconds, the double is 3.2. I am 
unable to reproduce your results.

Craig Black wrote:
 The second one is faster because you cheat.

Nope. Try this one. On my computer the floating point division is twice as fast. I believe this is due to the overhead on converting the divisor from int to double before performing the division. #include <stdio.h> #include <conio.h> #include <time.h> //typedef int divtype; typedef double divtype; // this one is faster int main() { int result = 0; clock_t start, finish; double duration; start = clock(); for(divtype div=1; div<10000; div++) { for(int i=0; i<10000; i++) { result += i / div; } } finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf("[%i] %2.1f seconds\n",result,duration); }

May 03 2006
prev sibling parent Walter Bright <newshound digitalmars.com> writes:
Craig Black wrote:
 These two functions show the difference that I'm talking about.  When
 benchmarking, pass in the same values for the divisor (pick a value between
 2 and 30), and pass in a large enough value for total so that it will take
 some time for the CPU to finish.  Suprisingly, the second one is faster.

Multiplication is a much simpler operation than division, which is why it's faster. Secondly, the reason compilers don't do the optimization below is that it gives different results (different rounding). If you're really interested in optimization, I suggest using a disassembler on the object files, it will answer a lot of questions.
 int divTest1(int divisor, int total)
 {
   int sum = 0;
   for(int i = 0; i < total; i++)
   {
     int quotient = i / divisor;
     sum += quotient;
   }
 }
 
 int divTest2(int divisor, int total)
 {
   int sum = 0;
   double idiv = 1.0 / divisor;
   for(int i = 0; i < total; i++)
   {
     int quotient = i * idiv;
     sum += quotient;
   }
 }

May 02 2006