And you can do that in Perl as well:

my $n = int (($count + 7) / 8);

goto (qw !LABEL0 LABEL1 LABEL2 LABEL3
          LABEL4 LABEL5 LABEL6 LABEL7!) [$count % 8];

{
    LABEL0:  print "0\n";
    LABEL7:  print "7\n";
    LABEL6:  print "6\n";
    LABEL5:  print "5\n";
    LABEL4:  print "4\n";
    LABEL3:  print "3\n";
    LABEL2:  print "2\n";
    LABEL1:  print "1\n";
    redo if -- $n > 0;
}
[download]

It's certainly legal to jump into a bare block, and bare blocks are looping constructs as well.

Abigail

I wanted to play with this (and the other examples) in the debugger. Apparently the debugger has problems with goto jumping into blocks while single stepping. Depending on the variation, I get a Windows error (running inside a "Dos Shell"), or the debugger just exits.

Here is the version:

This is perl, v5.8.0 built for MSWin32-x86-multi-thread
(with 1 registered patch, see perl -V for more detail)

Copyright 1987-2002, Larry Wall

Binary build 806 provided by ActiveState Corp. http://www.ActiveState.
+com
Built 00:45:44 Mar 31 2003
[download]

Running normally (no debugger) doesn't have this problem. In the debugger, staying within a block or jumping outside of a block is OK too. [I only tried bare blocks, nothing fancy.]

Hrmm....

-QM
--
Quantum Mechanics: The dreams stuff is made of

- - arden.

Yeah, it was actually the obfu that got me thinking of Duff's Device again. I read the FAQ links too. I guess I just need to see it in action somewhere to gain a better appreciation for it. It's definately one of the more demonic constructs I've seen in the computer world. Not yet sure if it's from the light side or the dark side of the force.

What I truly hope never to see is a regex version of Duff's Device. haha




Dave

• there's no instruction like while () {...} or for (;;) {...}
• the processor likes to cruise ahead and doesn't like jumping

In CompSci 100, you'll learn that there are three components to a loop: an initial condition, a body of work, and a test against the work. In CompEng 100, you'll learn that there is really only one construct at the lowest level: if a simple condition is met, jump elsewhere. All the fussy academics of loop structure are just abstractions to which you can adhere for safety.

Almost every hardware instruction processor suffers a performance hit when they're told in one instruction that they won't in fact be running the NEXT instruction next. Today's processors do a lot of thinking ahead, and predicting what registers or memory locations they'll have to start fetching, even before they've reached the instruction. All that thinking ahead is moot if the condition requires a jump.

Duff's Device is just another way of writing a loop, using the barest features of the processor: jump to new locations, but minimize how often that happens.

It's meaningless in Perl, except as an anecdote, because the virtual machine has so many branches at the machine code level no matter what code you write, and no additional expensive penalty for jumping around in Perl code.

It's meaningless in Perl, except as an anecdote, because the virtual machine has so many branches at the machine code level no matter what code you write, and no additional expensive penalty for jumping around in Perl code.

It's not just the jumping you save on, it's also the reduced testing. Duff's device does two things: it does loop unrolling, and it uses a neat/tricky way of dealing with the border case of a loop unrolling technique. Loop unrolling pays because of not having to evaluate a condition. Here's a benchmark showing duff's device to be significant faster than a plain loop (yes, the work done is contrived, but that's not the point):

#!/usr/bin/perl

use strict;
use warnings;

use Benchmark qw /timethese cmpthese/;

our ($x, $y);
our  $N = shift || 100;

cmpthese -1  => {
    noduff   => '$x = 0;
                 my $n = $N;
                 while ($n --) {$x ++}',
    duff     => '$y = 0;
                 my $n = int (($N + 7) / 8);
                 goto "LABEL" . ($N % 8);
                 {   LABEL0: $y ++;
                     LABEL7: $y ++;
                     LABEL6: $y ++;
                     LABEL5: $y ++;
                     LABEL4: $y ++;
                     LABEL3: $y ++;
                     LABEL2: $y ++;
                     LABEL1: $y ++;
                     redo if -- $n > 0
                  }',
};

die "Unequal \$N == $N; \$x == $x; \$y == $y.\n" unless $N == $x && $N
+ == $y;

__END__
          Rate noduff   duff
noduff 39384/s     --   -42%
duff   68267/s    73%     --
[download]

Abigail

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 ]

So the important point here is that we only have to evaluate if (--$n > 0) one eighth of the time?



---
demerphq


First they ignore you, then they laugh at you, then they fight you, then you win.
-- Gandhi

It made almost no sense to me when i first saw it, but as with most algorithms, I found that the best way to make sense of it was to step through it in my mind based on a couple of different input scenerios.

In the case of Duff's Device in particular, the real key for me was to keep in mind exactly what it was designed to optimize. If you look at other (more straightforward) loop unwinding optimizations, then this one doesn't seem quite as insane.

(The recent obfu is probably not the best thing to study when trying to make sense of it)

Have you read the original posting by Duff? (Well, semi-original ;) http://www.lysator.liu.se/c/duffs-device.html.

I don't think there is a valid use for this in Perl. It was designed for extreme reasons of speed; whereas it's likely something you would code in Perl wouldn't have those concerns.

That is really interesting. Thx for providing the link.

First, why is it legal to use goto to jump into the middle of a do{....} while(); loop?

Because goto is stupid :) Seriously, goto LABEL and goto EXPR can jump anywhere (except where they can't). It is bizzare because it's bizzare, so stay away.

I wouldn't say gotos are stupid, dangerous maybe but not stupid. I think it's a more natural way to move around as it's closer to english. However, it can get you into quite a bit of trouble so it is recommended that you not use them. So much so that many people are afraid of using a goto and refuse to use them under any circumstance. I've never really had a need to use them as most of the time a nice loop with some if/then/else statements will do and makes debugging easier but I wouldn't not use a goto just because they are bad. I would just triple check that portion of the code.

So why is it bizzare and stupid? You never really gave an explanation other than it can jump anywhere.... well yeah, that's kindof the point. Kindof like if we need to start over and reinit stuff goto the beginning. If we are in the middle of a program that is not designed to do something like this would you rather 1) rewrite your code and put a bunch of checks to see if we need to start or 2) put in a goto BEGINING:? Of course where you run into trouble is if something is open and you don't properly close it etc... but if you clean up before jumping it's not a problem.

I thought he meant it was stupid as in not smart, as in it jumps anywhere regardless and doesn't do anything thinking about it.

___________
Eric Hodges

It's bizzare, particularly in the goto EXPR form, because there is no way to calculate the jump until runtime. Depending on the complexity of EXPR, code maintnance could be hopeless. Also, this causes a linear scan of your code, so your jump will be slower (in the worst case) if your code base is larger. Lord forbid if Hitler had ever discovered the sinister power behind goto EXPR (I claim exemption from Godwin's law).

Of course, goto &SUB is a totally different matter.

----
: () { :|:& };:

Note: All code is untested, unless otherwise stated

I'd think that Duff's device is never useful in Perl.

It is certainly not useful in my obfu, I could have finished the obfu like this as well:

tie @b, &^Px$^P;
# without duff's device I can copy array very efficently
push @b,$_ for@a;
# oh, I nearly forgot magical subs, so here they are
sub DESTROY { }
sub AUTOLOAD {
        ($#, %c)= qw(%c $#);
        print $_[1];
        bless [];
        }
__END__
[download]

This would be as good as the original, just not as obfuscated.

You may find the jump into the while loop more legal, if you think about it like this: you could omit the braces completely, and change the while (or redo) to an if-goto construct. The C version with the case statement is still wierd, as the C switch statement is misused, but the Perl version does not use this strange idiom. (Well, maybe you could write a case-based version in perl too, I'm not sure. The postfix when will have fall-through in perl6.)