flat assembler
Message board for the users of flat assembler.

 Index > Heap > Why is division sooooooo slow Goto page 1, 2  Next
Author
l4m2

Joined: 15 Jan 2015
Posts: 648
l4m2
Code:
```#include <stdio.h>
#include <time.h>

int main() {
int tmr, i, b=1000;
tmr = clock();
for (i=2; i<499999999; i++)
b ^= b * i;
printf ("MUL %f s\n", (double)(clock() - tmr)/CLK_TCK, b);

tmr = clock();
for (i=2; i<499999999; i++)
b ^= b / i;
printf ("DIV %f s\n", (double)(clock() - tmr)/CLK_TCK, b);
return 0;
}
```
Result wrote:
MUL 0.825000 s
DIV 4.330000 s
I can't stand a 5-time difference
21 Jul 2016, 09:57
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17271
revolution
l4m2 wrote:
I can't stand a 5-time difference
Your options are limited. You could try to invent a new method for division that is faster. Or perhaps instead take an easier approach and increase the execution time of the multiply (maybe by doing each multiply 5 times).
21 Jul 2016, 10:59
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
By definition, both b and i are integers.

The result of b * i must be an integer.

On the contrary, the result of b / i is not an integer most of the time.

Thus, calculating b^(b/i) would take much longer than calculating b^(b*i).

Just my two cents.

21 Jul 2016, 13:23
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17271
revolution
Another way to "fix" it is to pre-calculate the answers. Since all values used are constants then after the first run nothing changes for the second and subsequent runs so just hardcode the final values and then they will take the same time.

And besides, clearly no one here will understand your code unless you post some assembly source.

And ultimately since the value in 'b' is never used then the whole code can be reduced to a simple 'return 0'
21 Jul 2016, 13:36
l4m2

Joined: 15 Jan 2015
Posts: 648
l4m2
revolution wrote:
Another way to "fix" it is to pre-calculate the answers. Since all values used are constants then after the first run nothing changes for the second and subsequent runs so just hardcode the final values and then they will take the same time.
So it doesn't show the calculating time
revolution wrote:
And besides, clearly no one here will understand your code unless you post some assembly source.
So what to do when you don't know the most suitable way to make use of cpu?
revolution wrote:
And ultimately since the value in 'b' is never used then the whole code can be reduced to a simple 'return 0'
You lost two printf [if I don't use 'b' in the code (the last argument of printf) the calculating is optimized]
YONG wrote:
On the contrary, the result of b / i is not an integer most of the time.

Thus, calculating b^(b/i) would take much longer than calculating b^(b*i).
b/i is an integer when b and i both are
21 Jul 2016, 16:30
AsmGuru62

Joined: 28 Jan 2004
Posts: 1409
AsmGuru62
2/3 = .666666666 (not an integer)
21 Jul 2016, 16:40
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
A couple of points:

1. You need to use printf("%d", b); to print the value of an int.

2. In C, the operator ^ is Bitwise XOR. Both operands have to be the same data type, say, int.

Converting (b*i), which must be an integer, to int is easy and fast.
Converting (b/i), which is most likely a floating point number, to int is more difficult and time-consuming.
That gives rise to the difference in execution times.

Last edited by YONG on 22 Jul 2016, 04:51; edited 1 time in total
22 Jul 2016, 02:20
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17271
revolution
YONG wrote:
Converting (b/i), which is most likely a floating point number, to int is more difficult and time-consuming.
That gives rise to the difference in execution times.
Hehe, see I told you no one understands the code.
22 Jul 2016, 04:01
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
revolution wrote:
Hehe, see I told you no one understands the code.
Are you mistaken? You were talking to l4m2, not me.
22 Jul 2016, 04:54
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17271
revolution
YONG wrote:
revolution wrote:
Hehe, see I told you no one understands the code.
Are you mistaken? You were talking to l4m2, not me.
I think l4m2 understands what code the compiler will produce, but I am not so sure the YONG does.
22 Jul 2016, 04:59
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
revolution wrote:
I think l4m2 understands what code the compiler will produce ...
I doubt it. l4m2 did not even know how to properly print the value of an int.
revolution wrote:
... but I am not so sure the YONG does.
First, it should have been "that", not "the".

Second, I don't think that you have actually spent any time studying the code.

22 Jul 2016, 05:17
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17271
revolution
YONG wrote:
l4m2 did not even know how to properly print the value of an int.
l4m2 didn't want to print the value of b. l4m2 stated the reason for including b in the arguments list.
YONG wrote:
First, it should have been "that", not "the".
You are correct. I am not perfect unfortunately.
YONG wrote:
Second, I don't think that you have actually spent any time studying the code.
Your comment about floating point values being produced from (b/i) and subsequent conversion is incorrect. The compiler won't be that stupid.
YONG wrote:
22 Jul 2016, 05:54
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
revolution wrote:
Your comment about floating point values being produced from (b/i) and subsequent conversion is incorrect. The compiler won't be that stupid.
Then, enlighten me, please. How does the compiler handle (b/i) and the subsequent conversion, if needed? Please give us verifiable evidence, not just your opinion.

Thank you very much in advance.
22 Jul 2016, 06:14
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
revolution wrote:
YONG wrote:
Someone retells his/her old jokes again and again. I don't.
22 Jul 2016, 06:15
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
One more thing.

l4m2 started this thread because he/she wants to know what causes the big difference in execution times between MUL and DIV.

So, revolution, please also account for that difference. Thanks!
22 Jul 2016, 06:22
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17271
revolution
Hmm, so demanding.

If the two variables b and i are integers then the compiler simply uses the integer instruction IDIV (or maybe DIV, it depends upon the compiler). This produces an integer result. It's part of the C spec. No floats are involved.

As to why is DIV slower than MUL. Basically because no one knows how to do DIVs in the same time as MUL. I stated this all the way up in the first reply, we need a new algorithm for DIV.
22 Jul 2016, 06:39
l4m2

Joined: 15 Jan 2015
Posts: 648
l4m2
I agee that DIV goes slower than MUL, but I think 2-3times enough
22 Jul 2016, 08:30
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17271
revolution
l4m2 wrote:
I agee that DIV goes slower than MUL, but I think 2-3times enough
What do you mean "enough"? Do you mean that people are deliberately making DIV slower than they they otherwise could?
22 Jul 2016, 09:47
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
revolution wrote:
... the compiler simply uses the integer instruction IDIV (or maybe DIV, it depends upon the compiler). ... It's part of the C spec.
It is really safe for you to say so.

If you are correct, you can claim credits for it like this:

"See, I know the C specs inside out!"

If you are incorrect, you can blame the compiler like this:

"Well, it is an implementation / compiler-dependent issue."

You will never get toasted in either case. Smart!

We, the forum members, should really learn from you!

= = = = =

Back to the question.

I did some testing. Here are my findings:

MUL part:

When i = 33, the value of b becomes 0.
So, starting from i = 34, the value of b will never change again.
The loop just keeps doing "0 XOR 0" and assigns the result to b.

DIV part:

When i = 5, the old value of b = 514.
So, b/i = 514/5 = 102.8, which is not an integer.
To see how the compiler handles this, I had the value of b/i printed out.
And the value was 102.
Thus, revolution is correct on this point.
The compiler actually returns an integer value for b/i.

When i = 513, the old value of b = 512.
So, b/i = 512/513 < 1 and thus 0 is returned for b/i.
And the new value of b becomes 512.
From that point onward, the value of b will never change again.
The loop just keeps doing "512 XOR 0" and assigns the result to b.

I further tested the two loops involving only the XOR operation.
The loop with "0 XOR 0" and the one with "512 XOR 0" produced no significant difference in execution times.

In conclusion, the big difference in execution times is actually related to the speeds of the two operations MUL and DIV.

22 Jul 2016, 13:35
DimonSoft

Joined: 03 Mar 2010
Posts: 706
Location: Belarus
DimonSoft
YONG wrote:
revolution wrote:
... the compiler simply uses the integer instruction IDIV (or maybe DIV, it depends upon the compiler). ... It's part of the C spec.
It is really safe for you to say so.

If you are correct, you can claim credits for it like this:

"See, I know the C specs inside out!"

If you are incorrect, you can blame the compiler like this:

"Well, it is an implementation / compiler-dependent issue."

You will never get toasted in either case. Smart!

We, the forum members, should really learn from you!

Come on, the specs mentioned are available in just two clicks! They’re not secret. And this detail about treating division operator in C is probably one of the first things that is taught by a good teacher or book about C.

And no, this ISN’T implementation-specific, it is stated in the specs. And if you suddenly found a compiler that does otherwise, it would be a compiler that doesn’t comform to the standard. In fact, it would be a compiler of some other language very similar to C.
22 Jul 2016, 14:11
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area
Goto page 1, 2  Next

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou can attach files in this forumYou can download files in this forum