Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Duff's Device

by davido (Archbishop)
on Feb 24, 2004 at 06:30 UTC ( #331334=perlquestion: print w/ replies, xml ) Need Help??
davido has asked for the wisdom of the Perl Monks concerning the following question:

I've done the requisite googling on the subject of Duff's Device. Though most examples are in C, I've found one or two in Perl too. ...but they all seem fairly abstract, so I'm still struggling with how it works and where it could/should be used. I tend to do best when I see something put to practical application.

So my questions are as follows: First, why is it legal to use goto to jump into the middle of a do{....} while(); loop? (I know, that's a wired question... it's legal because it is. But the concept still seems a little odd to me). And second, what's a practical example of such a mechanism in real world Perlish use?

This is just a matter of curiosity... no homework here. ;)

Thanks in advance for any comments or pointers.


Dave

Comment on Duff's Device
Download Code
Re: Duff's Device
by arden (Curate) on Feb 24, 2004 at 06:39 UTC
      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

Re: Duff's Device
by hossman (Prior) on Feb 24, 2004 at 07:29 UTC

    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)

Re: Duff's Device
by kal (Hermit) on Feb 24, 2004 at 09:24 UTC

    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.

Re: Duff's Device
by Abigail-II (Bishop) on Feb 24, 2004 at 09:32 UTC
    From a posting of mine I made in 1998 in one of the Perl groups:
    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; }

    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
      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

Re: Duff's Device
by halley (Prior) on Feb 24, 2004 at 13:00 UTC
    When you code in machine language, there are two things which come readily apparent:
    • 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.

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

      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% --

      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


Re: Duff's Device
by hardburn (Abbot) on Feb 24, 2004 at 14:44 UTC

    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.

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

    Note: All code is untested, unless otherwise stated

      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

Re: Duff's Device
by Thelonius (Curate) on Feb 24, 2004 at 18:33 UTC
    For an interesting use of Duff's device--coroutines in C and C++ see here and here

      That is really interesting. Thx for providing the link.

Re: Duff's Device
by ambrus (Abbot) on Feb 25, 2004 at 13:31 UTC

    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__

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

Re: Duff's Device
by ambrus (Abbot) on Mar 11, 2004 at 19:29 UTC

    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.)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://331334]
Approved by arden
Front-paged by broquaint
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (5)
As of 2014-08-29 04:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (275 votes), past polls