0

I am trying to optimize the division and modular operation to increase the overall performance of the code in C.

I have 

UINT32 quo = num / 520 ;
UINT32 rem = num % 520 ;

Most of the blogs mentioned the optimization for the power of 2 operations like

num % (2^i) = num & (2^i -1 ).

num in my code will be a fairly large number.

Please suggest an alternative ways for above piece of code.

user3555115
  • 546
  • 1
  • 4
  • 11
  • forwarding to -> `codereview.stackexchange.com` – Rizier123 Dec 30 '14 at 16:34
  • There is a function called `div` in `stdlib.h`,IIRC,but I don't know if it is efficient. Try it. – Spikatrix Dec 30 '14 at 16:38
  • 2
    Your compiler should already generate optimal code for this. – Oliver Charlesworth Dec 30 '14 at 16:39
  • There is no generic optimization for this. However, there are situations in which it's worth to optimize the context. For example, if num is the 64-bit value of your hardware real time clock, and you try to compute microseconds and a remainder, and your processor has 32 bit hardware division only and 64 bit operations are emulated in slow software, then there are possible optimizations that take into account the fact that a few milliseconds before you computed the same thing for a slightly smaller value of num. That can speed up things a lot, but it works only by optimizing the whole context. – Hans Klünder Dec 30 '14 at 16:52
  • Isn't this only a serious issue on older CPUs that have an inefficient divide instruction, or with embedded processors that lack a divide instruction? – Weather Vane Dec 30 '14 at 16:54
  • 1
    The compiler will automatically optimize this by multiplying by its multiplicative inverse, so you don't need to do anything – phuclv Dec 30 '14 at 16:55
  • the magic number for signed division by 520 is 2114445439. You can calculate it [here](http://www.hackersdelight.org/magic.htm). More information http://stackoverflow.com/questions/2033210/c-fast-division-mod-by-10x http://stackoverflow.com/questions/17113660/divisiblity-of-5-without-using-and-operator?lq=1 http://stackoverflow.com/questions/16218228/fast-division-on-gcc-arm?lq=1 – phuclv Dec 30 '14 at 17:02
  • What is the type of `num`? If the entire range of `num` is not used in this application, what is the sub-range? – chux - Reinstate Monica Dec 30 '14 at 18:12
  • Usually num varies between 64k to 128k in decimal – user3555115 Dec 30 '14 at 18:14
  • It sounds like you are trying to perform micro-optimizations. The performance gains by doing this tend to be minimal, especially since the compiler can do them for you. Posting a larger block of code to codereview.stackexchange.com will probably get you better suggestions for optimization. – Degustaf Dec 30 '14 at 19:02

2 Answers2

1

As Oliver already mentioned in the comments, the compiler should automatically optimize the division and modulo operations. But if you want to know more about optimization of division for constant divisors (say 520 as in your example), you might find this link http://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html helpful.

The trick is to find a suitable factor so that the division operation can be replaced with a multiplication-bitshift operation instead.

B.Shankar
  • 1,271
  • 7
  • 11
1

Others have commented that the compiler will optimize division by a constant - effectively performing multiplication by an inverse computed at compile time. Hardware integer division is always slower than multiplication, and the gap in the relative latencies of these instructions continues to widen.

The robust implementation for division by invariant integers in GCC was first implemented as described in this paper. A more recent paper has improved these results.

Brett Hale
  • 21,653
  • 2
  • 61
  • 90