Alternative to using % operator and / Operator in C++

Question

It is told that modulo operator "%" and divide operator "/" are very inefficient in embedded C++.

How can I alternatively achieve the following expression:

a = b % c;

I understand that this can be achieved using the following logic:

a = b - c;
while (a >= c) {
  a = a - c;
}

But my question is, is this code involving while loops efficient enough, compared to % operator?

Thanks, Kirti

Solution 1

Nothing is going to be considerably more efficient than the % operator. If there was a better way to do it, then any reasonable compiler would automatically convert it. When you're told that % and / are inefficient, that's just because those are difficult operations - if you need to perform a modulo, then do that.

There may be special cases when there are better ways - for example, mod a power of two can be written as a binary or - but those are probably optimized by your compiler.

Solution 2

Division and modulus are indeed costly hardware operations, whatever you do (this is more related to hardware architecture than to languages or compilers), perhaps ten times slower than addition.

^{However, on current laptops or servers, and on high-end microcontrollers, cache misses are often much slower than divisions!}

The GCC compiler is often able to optimize them, when the divisor is a constant.

Your naive loop is usually much more slower than using the hardware division instruction (or the library routine doing it, if not provided by hardware). I believe you are wrong in avoiding the division & replacing it with your loop.

You might tune your algorithms -e.g. by having power of twos- but I don't recommend using your code. Remember that premature optimization is evil so first try to get your program correct, then profile it to find the trouble spots.

Solution 3

That code will almost certainly be slower than however your processor/compiler decides to perform the divide/mod. Generally, shortcuts are pretty hard to come by for basic arithmetic operators, since the mcu/cpu designers and compiler programmers are pretty good at optimizing this for almost all applications.

One common shortcut in embedded devices (where every cycle/byte can make a difference) is to keep everything in terms of base-2 to use the bit shift operators to perform multiplication and division, and the bitwise and (&) to perform modulo.

Examples:

unsigned int x = 100;
unsigned int y1 = x << 4;   // same as x * 2^4 = x*16
unsigned int y2 = x >> 6;   // same as x / 2^6 = x/64
unsigned int y3 = x & 0x07; // same as x % 8

Solution 4

If the divisor is known at compile time, the operation can be transformed into a multiplication by a reciprocal, with some shifts, adds, and other fast operations. This will be faster on any modern processor, even if it implements division in hardware. Embedded targets usually have highly optimized routines for divide / modulo, since these operations are required by the standard.

Solution 5

If you have profiled your code carefully and found that a modulo operator is the major cost in an inner loop then there is an optimisation that might help. You might be already familiar with the trick for determining the sign of an integer using arithmetic left shifts (for 32 bit values):

sign = ( x >> 31 ) | 1;

This extends the sign bit across the word, so negative values yield -1 and positive values 0. Then bit 0 is set so that positive values result in 1.

If we're only incrementing values by a quantity that is less than the modulo then this same trick can be used to wrap the result:

val += inc;
val -= modulo & ( static_cast< int32_t >( ( ( modulo - 1 ) - val ) ) >> 31 );

Alternatively, if you are decrementing by values less than the modulo then the relevant code is:

int32_t signedVal = static_cast< int32_t >( val - dec );
val = signedVal + ( modulo & ( signedVal >> 31 ) );

I've added the static_cast operators because I was passing in uint32_t, but you might not find them necessary.

Does this help much as opposed to a simple % operator? That depends on your compiler and CPU architecture. I found a simple loop ran 60% faster on my i3 processor when compiled under VS2012, however on the ARM11 chip in the Raspberry Pi and compiling with GCC I only got a 20% improvement.

View more solutions

Comments

[Dan]

+1 for getting the program right before worrying about optimization. The cause of many a failed project.

[Emile Cormier]

Any decent compiler will make the same optimization for you when the right operand is a power-of-two constant. The bit-shifting/masking trick is a leftover from the early days when compiler optimization sucked, and should no longer be necessary.

[shenles]

In the embedded world you unfortunately don't always have the luxury of a decent compiler... I agree in the general case, but when in doubt, a quick check of the dissassembly will determine whether this will help or not.

[Matthieu M.]

Quotes are better when complete: We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil, good answer otherwise.