I was playing around with optimization for C programs and used some code for (naively) calculating primes:
#include
int is_prime(int x) {
int divisor = 2;
if(x <= 1)
return(0);
if(x == 2)
return(1);
while(divisor * divisor <= x) {
if(x % divisor == 0)
return(0);
divisor++;
}
return(1);
}
int main(void) {
for(int i = 0; i <= 10000000; i++)
if(is_prime(i))
printf("%d is a prime number.\n", i);
}
I thought I could boost the performance a little bit by using a do...while
loop instead of the while
loop, so that the while condition will never be executed for an even x
. So I changed the is_prime()
function to this:
int is_prime(int x) {
int divisor = 2;
if(x <= 1)
return(0);
if(x == 2)
return(1);
do {
if(x % divisor == 0)
return(0);
divisor++;
} while(divisor * divisor <= x);
return(1);
}
When I compile both version without optimizations (gcc main.c -o main
) time ./main > /dev/null
takes about 5.5s for both, where it looks like the do..while
version performs a tiny bit better (maybe ~40ms).
When I optimize (gcc main.c -O3 -o main
), I get a strong difference between the two. time ./main > /dev/null
gives me ~5.4s for the do...while
version and ~4.9s for the while
version.
How can this be explained? Is the gcc compiler just not as well optimized for do..while
loops? Should I thus always use while
loops instead?
My CPU is an Intel i5-4300M.
My gcc version is gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0
.
I have now tested the clang compiler (clang version 6.0.0-1ubuntu2 (tags/RELEASE_600/final)
; clang main.c -O3 -o main
) as well. Here the results are as expected: time ./main > /dev/null
takes about 6.5s for the do...while
version and 6.8s for the while
version.
No comments:
Post a Comment