Change your fib sub to the following. You'll be amazed at the speedup you get:

my %cache;
sub fib {
    my $n = shift;
    return $n if $n < 2;
    return ( $cache{ $n - 1 } ||= fib($n - 1) )
         + ( $cache{ $n - 2 } ||= fib($n - 2) );
}
[download]

With your fib(), 1 .. 50 takes 10 100 minutes and counting. With the above, 1 .. 100 takes less than 1 millisecond.

Once you're done being amazed, see Memoize for the explanation of what it does and why it works.