I don't know that modifing Benchmark's cmpthese/timethese current behavior is neccessary, but a new method that supports interleaving might be usefull...

package Benchmark;
use List::Util qw(shuffle);

sub interleavethese{
    # based on timethese, but it merges the results from several small
    # iterations with the order shuffled each time.
    my($n, $iters, $alt, $style) = @_;
    die "usage: interleavethese(count, iters, { 'Name1'=>'code1', ... 
+}\n"
                unless ref $alt eq 'HASH';
    my @names = sort keys %$alt;
    $style = "" unless defined $style;
    print "Benchmark: " unless $style eq 'none';
    if ( $n > 0 ) {
        croak "non-integer loopcount $n, stopped" if int($n)<$n;
        print "timing $iters sets of $n iterations of" unless $style e
+q 'none';
    } else {
        print "running" unless $style eq 'none';
    }
    print " ", join(', ',@names) unless $style eq 'none';
    unless ( $n > 0 ) {
        my $for = n_to_for( $n );
        print ", each for $iters iterations of at least $for CPU secon
+ds" unless $style eq 'none';
    }
    print "...\n" unless $style eq 'none';

    my %results;
    for (my $i = 0; $i < $iters; $i++) {
    my @tasks = shuffle @names;
    foreach my $name (@tasks) {
        my $t = timethis ($n, $alt -> {$name}, $name, $style);
        $results{$name} = exists $results{$name} ?
        timesum($results{$name}, $t) : $t;
    }
    }

    return \%results;
}

package main;

#use it like this...
use Benchmark qw[ cmpthese interleasethese ];
cmpthese(interleavethese(5, 3, {
    Atest => \&test,
    Btest => \&test,
    Ctest => \&test,
}));
cmpthese(interleavethese(-5, 3, {
    Atest => \&test,
    Btest => \&test,
    Ctest => \&test,
}));
[download]

Here is a hack which implement's simonm's suggestion, which was also made independently to me by Gary Benson of Perl Seminar New York over a fine Indian meal at Angon on East 6 Street in Manhattan.

The hack involves three separate files and is probably modularizable, at least in part. To add/modify subroutines to be tested, add them to the third file below.