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 | [reply] [d/l] |
|
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
| [reply] [d/l] [select] |
Re: Duff's Device
by arden (Curate) on Feb 24, 2004 at 06:39 UTC
|
| [reply] |
|
| [reply] |
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 ]
| [reply] [d/l] [select] |
|
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 | [reply] [d/l] |
|
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 ]
| [reply] |
|
|
| [reply] [d/l] [select] |
|
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)
| [reply] |
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.
| [reply] |
Re: Duff's Device
by Thelonius (Priest) 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 | [reply] |
|
| [reply] |
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
| [reply] [d/l] [select] |
|
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.
| [reply] |
|
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.
| [reply] |
|
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
| [reply] [d/l] [select] |
|
|
|
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.
| [reply] [d/l] |
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.)
| [reply] |