4 ms·

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 ch

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): 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 ago
  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.
- mansr 16y ago
  In this context guru means "overpaid, full-of-himself cargo-culting consultant plugging his commercial vendor of choice".
  - forgotusername 16y ago
    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.
gte910h 16y ago
gcc 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 ago
  The ARM Cortex is faster than a Pentium 3 -- it's not particularly underpowered. gcc supports all three CPUs listed in that article.
  - gte910h 16y ago
    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).
- pmjordan 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. 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 ago
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?
- calloc 16y ago
  Arduino uses GCC as its compiler.
nitrogen 16y ago
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.

burgerbrain 16y ago

"embeddedgurus.com" That might be a clue.

DarkShikari 16y ago
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.
mansr 16y ago
In this context guru means "overpaid, full-of-himself cargo-culting consultant plugging his commercial vendor of choice".
- forgotusername 16y ago
  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.

gte910h 16y ago

gcc 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 ago
The ARM Cortex is faster than a Pentium 3 -- it's not particularly underpowered. gcc supports all three CPUs listed in that article.
- gte910h 16y ago
  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).
pmjordan 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. 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 ago

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?

calloc 16y ago
Arduino uses GCC as its compiler.

nitrogen 16y ago

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.