FWIW, here's a better single-threaded caching algorithm, which at my machine with 4 puny little cores outperforms others I checked:

use strict;
use warnings;
use feature 'say';
use Data::Dump 'dd';

use Time::HiRes 'time';
my $t = time;

my %cache = ( 1 => [ 1, 1, undef ]);
#
# [ seq_length, start_num (same as key), next_num ]
#

sub _cache_collatz {
    my $n = shift;
    return if exists $cache{ $n };
    my ( @tmp , $new_n );
    while ( !exists $cache{ $n }) {
        $new_n = $n % 2 ? 3 * $n + 1 : $n >> 1;
        push @tmp, $cache{ $n } = [ -$#tmp, $n, $new_n ];
        $n = $new_n
    }
    my $d = $#tmp + $cache{ $n }[ 0 ];
    $_-> [ 0 ] += $d for @tmp
}

sub collatz {
    my $n = shift;
    _cache_collatz( $n );
    my @a = $n;
    push @a, $n while $n = $cache{ $n }[ 2 ];
    return \@a;
}

## Demo
#
# dd collatz( 23 );
# dd \%cache;
# exit( 0 );
#
##

_cache_collatz( $_ ) for 1 .. 1e6;

say "@$_[ 1, 0 ]"
    for ( sort { $b-> [ 0 ] <=> $a-> [ 0 ]} 
               @cache{ 1 .. 1e6 })[ 0 .. 19 ];
say time - $t;

__END__

837799 525
626331 509
939497 507
704623 504
910107 476
927003 476
511935 470
767903 468
796095 468
970599 458
546681 452
818943 450
820022 450
820023 450
410011 449
615017 447
886953 445
906175 445
922524 445
922525 445
6.44625306129456
[download]

For comparison:

• laurent.pl: 30.7539658546448
• choroba.pl: 58.0188150405884
• 1nickt_orig.pl: 11.0160529613495
• 1nickt.pl: 7.18484592437744

Apparently, the last one will beat my "better caching" if run on 6 or more cores, but, like I said, I have only 4 :)