Something 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):
The 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.
I'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.
That'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).
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. 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.
>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.
I think I'd probably prefer working with either ARM or MIPS assembly over x86, except for the lack of some of x86's built-in arithmetic instructions (like divide). As long as you've got an instruction set reference card handy (preferably in PDF format), it's not too difficult to work with any assembly language (I've done debugging in ARM and x86, took a class on MIPS, and wrote entire firmwares in 8-bit PIC assembly).
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.
Really? He tested and measured a few different approaches. Do you think he's advocating just using his approaches without measurement?
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.
> I'd say most of this stuff is written for people who wouldn't really learn much from a disassembly.
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.
he 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?
I 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.
Article: "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.
Many processors don't have an (integer) division instruction, however, particularly those in the embedded world. That said, I share DarkShikari's concerns.
I 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.
Agreed, 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.
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.
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.
I'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.
No 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.
26 comments
[ 2.6 ms ] story [ 66.1 ms ] threadI'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:
Without optimization: Note how neither series of instructions calls integer divide!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:
gcc uses one multiplication and some shifts/additions for div60() and two multiplications and some shifts/additions for mod60().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.