Efficient C Tip – use the modulus (%) operator with caution
embeddedgurus.com
embeddedgurus.com
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
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
That might be a clue.
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.
Many of the chips he's talking about are pretty tiny little underpowered things with bad-middling compilers.
gcc supports all three CPUs listed in that article.
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).
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.
I was hunting through disassembled ARM code for performance bottlenecks and managed to speed things up quite a bit by manually removing divides that should've been caught by the optimizer from my C code. I didn't find it any more or less difficult than any other assembly language.
The problem, to me, is that he's not explained why the faster versions are faster (we don't know, because there's no disassembly), and the whole thing isn't reproducible because we don't know which compilers were used. For all we know, another compiler does better with the "slower" code.
They're trained in EE, not programming, and do enough to get through their design.
My EE friends definitely know assembly language. They also know that many chips don't have divide instructions, and at the very least, that the compiler can use other ops to work around that. Even for EEs who don't know, I don't think showing them the decomposition of the division would make their brains explode.
Debugging arm or mips assembler is considerably different than x86.
[citation needed]. I'll admit I've not done any work with MIPS, but I didn't have any trouble with ARM. Sure, there's Thumb mode, but that's pretty much it.
Even so, I find that a lot of the advice is misleading. As mentioned elsewhere, the reason modulus is slow is not that you can write it three arithmetic operations, but because division is slow. And especiall any kind of 32bit arithmetic on 8bit and 16bit processors. Even though he used narrower integer types, he did not explain why that was better.
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?
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.
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.
Ah, I missed that. Even on normal processors, for the following:
int div60(int i) { return i / 60; }
int mod60(int i) { return i % 60; }
This is probably the rationale behind the standard div() function, that calculates division and modulus together - it should make it easier for less sophisticated compilers to take advantage of this.
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.