Which of these functions runs faster?

Question

First case:

void lowTermReduction(int numerator, int denominator) {
    int gcd = GCD(numerator, denominator);
    numerator /= gcd;
    denominator /= gcd;
}

Second case:

void lowTermReduction(int numerator, int denominator) {
    int gcd = GCD(numerator, denominator);
    if (gcd != 1) {
        numerator /= gcd;
        denominator /= gcd;
    }
}

Which one is more efficient (fast)?
In the first case, the function always performs the division, also if this division is by 1 and doesn't change the values in numerator and denominator. I don't know if the CPU is faster in doing 12/1 or 12/2, but I think that is quite the same.
In the second case, instead, the function does the division only when the Greater Common Divisor is different by 1. But in this case it performs a logical operation if.
There are efficiency differences? And if so, are them relevan?

I doubt it will matter anyway. The time needed to reduce the GCD down to 1 is gonna dominate the run-time taken up by that final check. — Mysticial, Apr 30 '13 at 19:28
I'd say the difference is negligable, but the first division only will be fastest. — Uncle Iroh, Apr 30 '13 at 19:31
I'd prefer to avoid branching, personally. With that said, has the `lowTermReduction` function shown up as a hot-spot that you need to optimize? If so, you may want to *first* start from `GCD` and leave the micro-optimizations (nano-optimizations?) until later. — Nik Bougalis, Apr 30 '13 at 19:34
All that matter is GCD function, which will have same effect in both cases. Logical comparison vs division doesn't matter. — Rao Ehsan, Apr 30 '13 at 19:36
I suggest you combine the GCD function with the reduction. In finding the GCD, you are reducing the fraction. — Thomas Matthews, Apr 30 '13 at 19:41
As the function is written, you can optimize it further by replacing it with an empty body (unless `GCD()` is updating global variables). — jxh, Apr 30 '13 at 19:42

Jonny Dee · Accepted Answer · 2013-04-30T20:20:41.253

Without profiling on a concrete CPU architecture with typical use cases it is hard to say which one is faster.

But let's have a look at the two versions:

First version:

There is no 'if' so the two divisions will always be executed.
Also, there are always two reads and two writes to memory (or CPU registers).

Second version:

There is always a comparison operation, which also results in one memory read (or CPU register read)
However, the two divisions will only be executed in case the 'if' condition is true.
Additionally, if condition is fulfilled, there are again two reads and two writes.

So acutally it depends on how often the 'if' condition is true which in turn depends on the use cases. In general, however, I'd say the first version is faster, because most of the time the 'if' condition in the second alternative would be fulfilled anyway. As a result most of the time you will get one comparison operation and one read operation for the 'if' condition, and two read and two write operations, as well as two division operations for the 'if' block.

score 2 · Answer 2 · answered Apr 30 '13 at 19:36

The answer is dependent on the input you would typically feed to your function. If most of the time the GCD ends up being 1, then the second function will execute fewer instructions. If most of the time the GCD ends up being different from 1, then the first function will execute fewer instructions.

This function is unlikely to be the bottleneck for your system. You should profile your entire system, and only optimize the parts that are really taking the most time.

score 1 · Answer 3 · edited May 23 '17 at 11:43

1

Division in most computers is one of the slowest arithmetic operation that CPU can perform, and, on the other hand, conditional jump is pretty fast (if you forget about pipeline issues right now).

However, first you need to figure out if this is really the bottleneck in your program. Then, you need to measure times for both versions.

At the end, I guess you will not see any performance boost, as you are dividing the number by 1, so that should be pretty fast, and you may only introduce issues in speed with the jump here, so it is possible that if version become slower.

Make sure you read Bill's answer from this question.

edited May 23 '17 at 11:43

Community

1
1

answered Apr 30 '13 at 19:32

Nemanja Boric

21,627
6
67
91

1

And caching issues! With so small a program it may not be so apparent, but should the function be bigger you risk the jump ends in a piece of code that's not been loaded from main memory to the cached one, forcing the CPU to go read it whereas in unconditional division all pertinent code is already there. As you said, profile is king - and even then, I guess the answer will be different in different processors. – Joe Pineda Apr 30 '13 at 19:39

score 0 · Answer 4 · answered Apr 30 '13 at 19:34

The first case would be on average faster. The reason being, the second function will always have to do that comparison, and then the division if deemed necessary. Although if only executed once or twice you won't notice a difference, but if it is part of a greater function that will run multiple times it might be slightly more noticeable.

The first will always do 1 operation when it is called, so if called n times it will perform n operations. The second best case scenario will do n operations (if every call has a GCD of 1) but worst case scenario will do 2n operations. So I would say the safe bet would be to go with the first case

score 0 · Answer 5 · answered Apr 30 '13 at 19:38

Because the second version is performing a comparison, the second version will be slower.

The question is: How much slower?

My guess is that the time improvement is not significant.

If you want to speed up the program, figure out how to get rid of the division.

Which of these functions runs faster?

5 Answers5