flat assembler
Message board for the users of flat assembler.

Index > Heap > Why is division sooooooo slow

Goto page 1, 2  Next
Author
Thread Post new topic Reply to topic
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
Post 21 Jul 2016, 09:57
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17271
Location: In your JS exploiting you and your system
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). Wink
Post 21 Jul 2016, 10:59
View user's profile Send private message Visit poster's website Reply with quote
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.

Wink
Post 21 Jul 2016, 13:23
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17271
Location: In your JS exploiting you and your system
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. Razz

And ultimately since the value in 'b' is never used then the whole code can be reduced to a simple 'return 0'
Post 21 Jul 2016, 13:36
View user's profile Send private message Visit poster's website Reply with quote
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. Razz
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
Post 21 Jul 2016, 16:30
View user's profile Send private message Reply with quote
AsmGuru62



Joined: 28 Jan 2004
Posts: 1409
Location: Toronto, Canada
AsmGuru62
2/3 = .666666666 (not an integer)
Post 21 Jul 2016, 16:40
View user's profile Send private message Send e-mail Reply with quote
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.

Wink


Last edited by YONG on 22 Jul 2016, 04:51; edited 1 time in total
Post 22 Jul 2016, 02:20
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17271
Location: In your JS exploiting you and your system
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.
Post 22 Jul 2016, 04:01
View user's profile Send private message Visit poster's website Reply with quote
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. Rolling Eyes
Post 22 Jul 2016, 04:54
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17271
Location: In your JS exploiting you and your system
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. Rolling Eyes
I think l4m2 understands what code the compiler will produce, but I am not so sure the YONG does. Shocked Razz
Post 22 Jul 2016, 04:59
View user's profile Send private message Visit poster's website Reply with quote
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.

Stop giving vague comments just to increase your post count.

Wink
Post 22 Jul 2016, 05:17
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17271
Location: In your JS exploiting you and your system
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:
Stop giving vague comments just to increase your post count.
I'm just following your lead. Razz
Post 22 Jul 2016, 05:54
View user's profile Send private message Visit poster's website Reply with quote
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.
Post 22 Jul 2016, 06:14
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
revolution wrote:
YONG wrote:
Stop giving vague comments just to increase your post count.
I'm just following your lead. Razz
Someone retells his/her old jokes again and again. I don't.
Post 22 Jul 2016, 06:15
View user's profile Send private message Visit poster's website Reply with quote
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!
Post 22 Jul 2016, 06:22
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17271
Location: In your JS exploiting you and your system
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.
Post 22 Jul 2016, 06:39
View user's profile Send private message Visit poster's website Reply with quote
l4m2



Joined: 15 Jan 2015
Posts: 648
l4m2
I agee that DIV goes slower than MUL, but I think 2-3times enough
Post 22 Jul 2016, 08:30
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17271
Location: In your JS exploiting you and your system
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?
Post 22 Jul 2016, 09:47
View user's profile Send private message Visit poster's website Reply with quote
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.

Wink
Post 22 Jul 2016, 13:35
View user's profile Send private message Visit poster's website Reply with quote
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.
Post 22 Jul 2016, 14:11
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page 1, 2  Next

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.