4 ms·

I'm curious, is this still useful on modern architecture? I would have thought branch prediction would largely negate any performance benefit.

hythloday 14y ago
I've wanted to use things at the level of Duff's device on pre-release console hardware (SPUs and the Xenon both suck at branching, and the compiler is beyond abysmal to the point where my girlfriend can still make me wake up screaming by whispering "--target=spu-elf" in my ear while I'm asleep). On the other hand portability is a non-issue and in that circumstance there's no such thing as source-level debugging (not that I would want to step through Duff's with a source-level debugger) so everything is usually just written in assembly. I'm also not convinced I'd trust the compiler to get parallelization right, especially since as another poster mentions Duff's gives you a really unusual CFG.
kd0amg 14y ago
A superscalar machine should still be able to benefit from loop unrolling by issuing the instructions for multiple iterations in parallel (though this is more hardware-dependent than I like to think about when coding). The rollback machinery in branch speculation hardware can only handle a limited number of branches, so a loop with a very small body running on a machine with a very deep pipeline could spend a lot of time waiting on confirmations of correct branch predictions.
- Tuna-Fish 14y ago
  > by issuing the instructions for multiple iterations in parallel Unless you actually do something in the loop body, all modern superscalar HW would be bottlenecked on the writes, making multiple iterations impossible. For example, SNB has 5 main execution ports -- two agus, 3 alus, and it can do either of 2 reads or 1 read + 1 write in a single cycle. This means that if you are storing something every cycle, for each cycle you can do 3 instructions without slowing down the loop. Also, if the jump instruction is immediately preceded by the alu instruction that generates the flags for it, they get fusioned into a single instruction, meaning you don't need to count the jmp as an instruction. > The rollback machinery in branch speculation hardware can only handle a limited number of branches This used to be more of a problem before modern PRF cpus -- with PRF, recovery from branch miss is much cheaper (it's essentially the copy of 17 8-bit pointers), so Sandy Bridge and later can typically handle more in-flight branches than their pipeline length, so confirmations of branch predictions shouldn't ever stall you unless you use division to get the flags or something.
coob 14y ago
Back when I was hacking on the iPod Linux project (alternative OS for classic iPods) there was a guy (normalperson) working on optimising the FLAC decoder to run as efficiently as possible on the SoC's ARM7TDMI. IIRC he used Duff's device to squeeze a small amount of juice out of various tight loops. Then again, we were using an ancient version of GCC which didn't have great optimisation for ARM. Sorry, I've just realised this doesn't really answer your question.
stephencanon 14y ago
It is sometimes useful, but there is almost always a better way; the real virtue of duff's device is that it can sometimes give "good enough" performance while maintaining (relative) simplicity.
amalcon 14y ago
It's not so much branch prediction as the increase of CPU speed relative to bus speed. Loop unrolling increases code size. Unless you're running a lot of iterations of a very tight loop, fetching the extra code from RAM will take longer than unrolling will save you. If you are running a lot of iterations of a very tight loop, it might still be worth trying. Just remember to profile.

hythloday 14y ago

I've wanted to use things at the level of Duff's device on pre-release console hardware (SPUs and the Xenon both suck at branching, and the compiler is beyond abysmal to the point where my girlfriend can still make me wake up screaming by whispering "--target=spu-elf" in my ear while I'm asleep). On the other hand portability is a non-issue and in that circumstance there's no such thing as source-level debugging (not that I would want to step through Duff's with a source-level debugger) so everything is usually just written in assembly. I'm also not convinced I'd trust the compiler to get parallelization right, especially since as another poster mentions Duff's gives you a really unusual CFG.

kd0amg 14y ago

A superscalar machine should still be able to benefit from loop unrolling by issuing the instructions for multiple iterations in parallel (though this is more hardware-dependent than I like to think about when coding). The rollback machinery in branch speculation hardware can only handle a limited number of branches, so a loop with a very small body running on a machine with a very deep pipeline could spend a lot of time waiting on confirmations of correct branch predictions.

Tuna-Fish 14y ago
> by issuing the instructions for multiple iterations in parallel Unless you actually do something in the loop body, all modern superscalar HW would be bottlenecked on the writes, making multiple iterations impossible. For example, SNB has 5 main execution ports -- two agus, 3 alus, and it can do either of 2 reads or 1 read + 1 write in a single cycle. This means that if you are storing something every cycle, for each cycle you can do 3 instructions without slowing down the loop. Also, if the jump instruction is immediately preceded by the alu instruction that generates the flags for it, they get fusioned into a single instruction, meaning you don't need to count the jmp as an instruction. > The rollback machinery in branch speculation hardware can only handle a limited number of branches This used to be more of a problem before modern PRF cpus -- with PRF, recovery from branch miss is much cheaper (it's essentially the copy of 17 8-bit pointers), so Sandy Bridge and later can typically handle more in-flight branches than their pipeline length, so confirmations of branch predictions shouldn't ever stall you unless you use division to get the flags or something.

coob 14y ago

Back when I was hacking on the iPod Linux project (alternative OS for classic iPods) there was a guy (normalperson) working on optimising the FLAC decoder to run as efficiently as possible on the SoC's ARM7TDMI. IIRC he used Duff's device to squeeze a small amount of juice out of various tight loops. Then again, we were using an ancient version of GCC which didn't have great optimisation for ARM. Sorry, I've just realised this doesn't really answer your question.

stephencanon 14y ago

It is sometimes useful, but there is almost always a better way; the real virtue of duff's device is that it can sometimes give "good enough" performance while maintaining (relative) simplicity.

amalcon 14y ago

It's not so much branch prediction as the increase of CPU speed relative to bus speed. Loop unrolling increases code size. Unless you're running a lot of iterations of a very tight loop, fetching the extra code from RAM will take longer than unrolling will save you. If you are running a lot of iterations of a very tight loop, it might still be worth trying. Just remember to profile.