Thanks++, that explains it. After seeing your post, I vaguely recall having seen a "Benchmark gotcha" somewhere that had a similar explanation, but I can't place it.

I normally use subs when I do benchamrks, but this time I figured that the operations being benchmarked were so fast and the differences between them potentially so slight, that the overhead of calling the subs would significantly distort the results. Therefore, I repeated the tests, still using eval'ed strings, but replacing the relevant lexicals with package variables. Here are the results:

# input length: 7
          Rate ?<!Y  ?!X ?<!X  ?!Y
?<!Y  613304/s   -- -32% -50% -52%
?!X   908420/s  48%   -- -27% -29%
?<!X 1236528/s 102%  36%   --  -4%
?!Y  1286220/s 110%  42%   4%   --
[download]

use strict;
use warnings;

use Benchmark 'cmpthese';

my $sz      = ( shift || 10 ) - 4;
our $X = 'N' . 'x' x $sz . '001';
our $Y = 'N' . 'x' x $sz . '000';

print '# input length: ', length( $X ), $/;

cmpthese( -1,
          {
           '?!X'  => '$main::X =~ /^N(?!.*00$).*$/',
           '?!Y'  => '$main::Y =~ /^N(?!.*00$).*$/',
           '?<!X' => '$main::X =~ /^N.*(?<!00$)$/',
           '?<!Y' => '$main::Y =~ /^N.*(?<!00$)$/',
           }
        );
__END__
[download]