***update***
OOPS It tooks me too long to type this post, what I said here was said above while I was typing this...
***update***

In another ridiculous attempt to enhance things...
(Why am I always missing something ?)
I've tried a to 'enhance' the regex using the o modificator

So I added :

    'oregex' => sub {
                    $test_char = chr( int( rand 256 ) );
                    if ($test_char =~ /^[A..Z]$/o) {} else {}
                   },
[download]

to your code...

The result was disapointing for me...

comp: 51 wallclock secs (50.38 usr +  0.00 sys = 50.38 CPU)
exist: 50 wallclock secs (48.57 usr +  0.00 sys = 48.57 CPU)
oregex: 55 wallclock secs (54.11 usr +  0.00 sys = 54.11 CPU)
regex: 54 wallclock secs (54.10 usr +  0.00 sys = 54.10 CPU)
[download]

Could someone explain me why the optimization didn't optimize anything ?

And why my result are so different from yours ? (especially the ratio comp/regex or exist/regex ?)

I must add that I run the test several time to be sure...ANd the results were consistent...