in reply to Re: Duff's Device
in thread Duff's Device

Right. The "edge case" is what fraction of the larger loop needs to be run, to emulate a smaller loop.

As an analogy, look at running tracks. One track is a loop that is 0.25 miles long. Another track is 1.00 miles in a straight line. If you want to run 1.00 miles, this is really easy to figure out where you should start and stop on either track. If you want to run 1.25 miles, it's easy on the loop track, but you have to figure out where to start or stop on the line track.

In CPU terms, leaving the track at an odd place requires more thought, more often, than entering the track at an odd place. So you calculate the fractional component once and jump into the race in the middle.

--
[ e d @ h a l l e y . c c ]

Replies are listed 'Best First'.
Re: Duff's Device
by Abigail-II (Bishop) on Feb 24, 2004 at 14:43 UTC
    I fail to understand what you are saying. Any speed gains of Duff's device aren't regarding the calculation of fractional components, or where to enter or leave the track at the odd place. That's only done once.

    It's more like running tracks where each time you pass the finish line you have to stop, and decrease the lap counter. Running 1 mile on the smaller track means having to stop 4 times to decrease the counter, while running on the longer track means stopping once. That's loop unrolling. The trick of Duff's device is doing that instead of running on big track for N miles, and a couple of runs on the small track to make up for the fractional distance, you start somewhere on the big track.

    It's the loop unrolling that saves time, it's Duff's trick of mixing switch/while that saves on tracks. Or rather, it saves on (duplicate) code.

    Abigail

[reply]

In Section Seekers of Perl Wisdom