Curiouser and curiouser!

When I run the code under 5.10, I get the sort of timings I posted above:

C:\test>1176081 -WIDTH=1000 -HEIGHT=1000
yr() took 330.252300
buk() took 1.584859
buk2() took 1.277809
buk3() took 0.226701
[download]

But if I run it under 5.22, your sub runs very much faster* and buk3() doesn't terminate at all:

(*I have an idea about the cause of the slowness in 5.10; I'll need to think of a way to verify it.)

Modifying buk3() along the lines of your modification, but taking an lvalue ref outside the while loop and using it within the loop, allows it to work again:

sub buk3{
    my $str = shift;
    my @b = map[ ( 1e99, 0 ) x 2 ], 1 .. 256;

    for my $y ( 0 .. $HEIGHT-1 ) {
        my $ref = \substr( $$str, $y * $WIDTH, $WIDTH );
        while( $$ref  =~ m[((.)\2*)]sg ) {
            my $c = ord($1); 
            $b[ $c ][ LEFT   ] = $-[0]   if  $-[0]    < $b[ $c ][ LEFT
+   ];
            $b[ $c ][ RIGHT  ] = $+[0]-1 if  $+[0]-1  > $b[ $c ][ RIGH
+T  ];
            $b[ $c ][ TOP    ] = $y      if        $y < $b[ $c ][ TOP 
+   ];
            $b[ $c ][ BOTTOM ] = $y      if        $y > $b[ $c ][ BOTT
+OM ];
        }
    }
    return \@b;
}

C:\test>\perl22\bin\perl 1176081.pl -WIDTH=1000 -HEIGHT=1000
yr() took 2.438320
buk() took 1.068071
buk2() took 0.681810
buk3() took 0.160666
[download]

Which is okay, but a strange difference.

It kinda takes the steam out of my amazing speedup figures -- 15x instead of 7000x -- but the thrill is transitory anyway :)

And now I can run your sub on a larger image, even that gain is far less:

C:\test>\perl22\bin\perl 1176081.pl -WIDTH=10000 -HEIGHT=10000
yr() took 12.714030
buk() took 110.152981
buk2() took 70.100982
buk3() took 8.158657
[download]