6 ms·
Efficient C Tip – use the modulus (%) operator with caution
- DarkShikari 16y agoSomething about this article bugs me. Division and modulus by constants can be done very quickly with multiply, shift, and add (Hacker's Delight has a whole chapter on how this works). Furthermore, the compiler generally does this automatically in most cases. The clock timings here look rather extreme -- as if the compiler-builtin integer divide/modulus function was being called (many of these chips don't have integer divide units). I'm not one at all to generally trust compilers, but in this case, either these compilers are very very bad or the author didn't have optimization turned on. Of course, the author doesn't post disassembly or even what compilers he's using, so we'll never know! Edit: in fact, even without optimization, GCC uses this trick. Here's how gcc 4.3.4 compiles unsigned int foo(unsigned int a) {return a%60UL;} on x86_32, for example (I don't have an ARM cross-compiler handy): With optimization: movl 4(%esp), %ecx movl $-2004318071, %edx movl %ecx, %eax mull %edx shrl $5, %edx imull $60, %edx, %edx subl %edx, %ecx movl %ecx, %eax ret Without optimization: subl $8, %esp movl 12(%esp), %ecx movl $-2004318071, (%esp) movl (%esp), %eax mull %ecx movl %edx, %eax shrl $5, %eax movl %eax, 4(%esp) movl 4(%esp), %eax leal 0(,%eax,4), %edx movl %edx, %eax sall $4, %eax subl %edx, %eax movl %ecx, %edx subl %eax, %edx movl %edx, 4(%esp) movl 4(%esp), %eax addl $8, %esp ret Note how neither series of instructions calls integer divide!
- burgerbrain 16y ago"embeddedgurus.com" That might be a clue.
- DarkShikari 16y agoThe entire point of my above post was that integer divide is typically slow on embedded CPUs -- most of which don't have integer divide units. I'm quite aware of the domain name.
- mansr 16y agoIn this context guru means "overpaid, full-of-himself cargo-culting consultant plugging his commercial vendor of choice".
- forgotusername 16y agoI'm not sure how you arrived at that. This guy's advice is generally good (division can be slow, even on modern desktop CPUs - particularly if a constant divisor is not available to the compiler), it's just his reasoning that's a bit flawed. More importantly he at least tried to test his reasoning than assuming it was correct (even though he didn't do so quite thoroughly enough). If he's managed to survive in a reasonably hard core industry for 20 years and his advice has at least some truth in it, then I'd say you're being a little harsh with that description.
- gte910h 16y agogcc is a much better compiler than many embedded compilers. Many of the chips he's talking about are pretty tiny little underpowered things with bad-middling compilers.
- DarkShikari 16y agoThe ARM Cortex is faster than a Pentium 3 -- it's not particularly underpowered. gcc supports all three CPUs listed in that article.
- gte910h 16y agoThat's why I said "many". It also got very little in the way of speedups from these changes. Additionally, the manufactures compilers are often setup inside crappy IDEs with integrated debuggers. IAR was included with at least the middle chip he's talking about. The people doing this aren't necessarily the type of folks who use vim + gcc + unix command line stuff to get them onto the boards. Why do they do this instead of using gcc? No clue. Probably they think they can make more money or are afraid of china stealing their silicon (seriously).
- pmjordan 16y agoIf that's the case the whole thing becomes a game of figuring out what optimisations the compiler does make, and doing the rest yourself. Even in this light, there's not an awful lot to be learned from the article - no disassembly in sight, and no mention from which operations the division is synthesized. This is cargo cult optimisation of the worst kind.
- gte910h 16y ago>If that's the case the whole thing becomes a game of figuring out what optimisations the compiler does make, and doing the rest yourself. You just described much of embedded programming there. >This is cargo cult optimisation of the worst kind. Really? He tested and measured a few different approaches. Do you think he's advocating just using his approaches without measurement? >no disassembly in sight, and no mention from which operations the division is synthesized I'd say most of this stuff is written for people who wouldn't really learn much from a disassembly. They may work with 3-5 different families of chips, all with very different (and sometimes moderately strange) instruction sets. They mostly chose the chip due to cost or power consumption, and it's a tiny tiny portion of their design. They're trained in EE, not programming, and do enough to get through their design. Debugging arm or mips assembler is considerably different than x86.
- bigiain 16y agohe does say: "In all three cases I used an IAR compiler with full speed optimization" While this sort of optimization is way-out-on-the-edge-case for most of the code discussed here, I'm going to have to go home tonight and see if a particular bit of AVR code I've been wondering how to speed up is suffering this problem. I wonder if the Arduino environment does any better here?
- calloc 16y agoArduino uses GCC as its compiler.
- nitrogen 16y agoI had to do quite a lot of optimization by hand to get gcc for ARM 4.3.3 (the Sourcery customized version) with -march=armv5te to stop calling the software divide routines, even when dividing by constants. Gcc's performance and conformance can vary widely across supported architectures.
- tspiteri 16y agoArticle: "Well a little thought shows that C = A % B is equivalent to C = A - B * (A / B). In other words the modulus operator is functionally equivalent to three operations." The integer divide instruction returns both the quotient and the remainder on the processors I know of. I can't see what sense it makes to have a modulo operator that is more expensive than a division operator.
- pmjordan 16y agoMany processors don't have an (integer) division instruction, however, particularly those in the embedded world. That said, I share DarkShikari's concerns.
- tspiteri 16y agoI am not saying that division is not expensive, or that the modulo operator is not just as expensive. I am only pointing out that the modulo operator is not more expensive that division.
- pmjordan 16y agoAgreed, if there is a dedicated instruction available[1], and if the expression can't be reduced to multiplications/shifts/addition due to division by a constant. None of the 3 architectures mentioned in the article have a division instruction, and the denominators are constant. So this is probably the least of the problems with this article, considering the audience is embedded programmers whose code probably never runs on x86, POWER or SPARC processors. Where you're not using the division instruction, modulo can actually be faster than division itself. The extreme case are powers of 2 of course; on x86, a right shift is vastly more expensive than a bitwise AND, for example. Other denominators don't produce quite so drastic differences. In any case, once you've done the division, the remainder is practically free; the article is basically an illustration of how bad the compilers in question are at spotting this fact. (though not mentioning which compilers and with which flags are affected makes it pretty useless) [1] It's technically conceivable that a superscalar, microcoded processor might actually detect whether the quotient, the remainder or both are actually used later in the code during the dependency check, and produce 3 different sets of microcode for these situations. I'd be surprised if any actually did this, though.
- spc476 16y agoI'm surprised he didn't look into the use of the div() function (it's a standard C function) that returns both the quotient and remainder, since he's using both results anyway.
- georgecmu 16y agoNo that isn’t a misprint. The ARM was nearly two orders of magnitude more cycle efficient than the MSP430 and AVR. Thus my claim that the modulus operator can be very inefficient is true for some architectures – but not all. The first thing a real embedded guru would do is look at the assembly listing. My guess is that ARM actually provides operations for integer division and modulus, while for AVR they're implemented as low-level gcc library routines.