Simply avoiding the array-copy my @path=@_ makes a factor 4.5 performance boost...

Wow. I'm amazed that avoiding the copying of such a small array had such a dramatic affect on the performance. I guess it must be being copied very many times.

In mine, I tried building the hash from the array rather than carrying it around, and it produced an ~8% speed-up. Then I tried using $_[n] instead of named parameters and it leached less than 5% more. The first is worth having, the second not:

sub _findPaths3 {
    return $_[0]->( @{ $_[4] }, $_[3] ) if $_[2] eq $_[3];
    my %seen; $seen{ $_ } = 1 for @{ $_[4] }, $_[2];
    for ( grep !$seen{ $_ }, @{ $_[1]->{ $_[2] } } ) {
        _findPaths3( $_[0], $_[1], $_, $_[3], [ @{ $_[4] }, $_[2] ] ),
    }
}

sub findPaths3(&@) { _findPaths3( @_, [] ); }
[download]