Is it better to avoid using the mod operator when possible?

Question

I assume that calculating the modulus of a number is a somewhat expensive operation, at least compared to simple arithmetic tests (such as seeing if a number exceeds the length of an array). If this is indeed the case, is it more efficient to replace, for example, the following code:

res = array[(i + 1) % len]; 

with the following? :

res = array[(i + 1 == len) ? 0 : i + 1]; 

The first one is easier on the eyes, but I wonder if the second might be more efficient. If so, might I expect an optimizing compiler to replace the first snippet with the second when a compiled language is used?

Of course, this "optimization" (if it is indeed an optimization) doesn't work in all cases (in this case, it only works if i+1 is never more than len).

Answer 1

My general advice is as follows. Use whichever version you think is easier on the eye, and then profile your entire system. Only optimize those parts of the code that the profiler flags up as bottlenecks. I'll bet my bottom dollar that the modulo operator isn't going to be among them.

As far as the specific example goes, only benchmarking can tell which is faster on your specific architecture using your specific compiler. You are potentially replacing modulo with branching, and it's anything but obvious which would be faster.

Answer 2

Some simple measurement:

#include <stdio.h> #include <stdlib.h>  int main(int argc, char *argv[]) {     int test = atoi(argv[1]);     int divisor = atoi(argv[2]);     int iterations = atoi(argv[3]);      int a = 0;      if (test == 0) {         for (int i = 0; i < iterations; i++)             a = (a + 1) % divisor;     } else if (test == 1) {         for (int i = 0; i < iterations; i++)             a = a + 1 == divisor ? 0 : a + 1;     }      printf("%d\n", a); } 

Compiling with either gcc or clang with -O3, and running time ./a.out 0 42 1000000000 (modulo version) or time ./a.out 1 42 1000000000 (comparison version) results in

• 6.25 seconds user runtime for the modulo version,
• 1.03 seconds for the comparison version.

(using gcc 5.2.1 or clang 3.6.2; Intel Core i5-4690K @ 3.50GHz; 64-bit Linux)

This means that it is probably a good idea to use the comparison version.