Hi 1nickt,

One may simulate extra CPU time to better understand the benefit of caching. I converted Laurent_R's example to consume multiple CPU cores. Laurent's example incurs extra overhead due to calling a subroutine inside the loop and returning a full list. I changed the number of iterations from 1 million to 100 thousand now that simulating extra CPU cycles.

Nick's example

use strict;
use warnings;
use feature 'say';
use MCE::Util;
use MCE::Map max_workers => MCE::Util::get_ncpu();
use Time::HiRes 'usleep';

my @output = mce_map_s {
    my $input = $_;
    my $n = $input;

    my @result = $input;

    while ( $n != 1 ) {
        $n = $n % 2 ? 3 * $n + 1 : $n / 2;
        usleep 20; # simulate extra computation
        push @result, $n;
    }

    return [ $input, scalar @result ];
} 1, 100000;

MCE::Map->finish;

@output = sort { $b->[1] <=> $a->[1] } @output;

say sprintf('%s : length %s', $_->[0], $_->[1]) for @output[0..19];
[download]

Laurent's example - no caching

use strict;
use warnings;
use feature qw/say/;
use MCE::Util;
use MCE::Map max_workers => MCE::Util::get_ncpu();
use Time::HiRes qw/usleep/;

sub collatz_seq {
    my $n = shift;
    my @result;
    while ($n != 1) {
        my $new_n = $n % 2 ? 3 * $n + 1 : $n / 2;
        usleep 20; # simulate extra computation
        push @result, $new_n;
        $n = $new_n;
    }
    return @result;
}

my @long_seqs = mce_map_s {
    my $num = $_;
    my @seq = ($num, collatz_seq $num);
    return [ $num, scalar @seq ];
} 1, 100000;

MCE::Map->finish;

@long_seqs = sort { $b->[1] <=> $a->[1] } @long_seqs;
say  "$_->[0] : length $_->[1]" for @long_seqs[0..19];
[download]

Laurent's example - with caching

use strict;
use warnings;
use feature qw/say/;
use constant MAX => 300000;
use MCE::Util;
use MCE::Map max_workers => MCE::Util::get_ncpu();
use Time::HiRes qw/usleep/;

my %cache;

sub collatz_seq {
    my $input = shift;
    my $n = $input;
    my @result;
    while ($n != 1) {
        if (exists $cache{$n}) {
            push @result, @{ $cache{$n} };
            last;
        }
        my $new_n = $n % 2 ? 3 * $n + 1 : $n / 2;
        usleep 20; # simulate extra computation
        push @result, $new_n;
        $cache{$n} = [ $new_n, @{ $cache{$new_n} } ]
            if $n < MAX && exists $cache{$new_n};
        $n = $new_n;
    }
    $cache{$input} = \@result if $n < MAX;
    return @result;
}

my @long_seqs = mce_map_s {
    my $num = $_;
    my @seq = ($num, collatz_seq $num);
    return [ $num, scalar @seq ];
} 1, 100000;

MCE::Map->finish;

@long_seqs = sort { $b->[1] <=> $a->[1] } @long_seqs;
say  "$_->[0] : length $_->[1]" for @long_seqs[0..19];
[download]

Program output

77031 : length 351
52527 : length 340
78791 : length 338
60975 : length 335
87087 : length 333
88059 : length 333
91463 : length 333
63387 : length 330
95081 : length 328
99067 : length 328
99721 : length 328
71310 : length 325
71311 : length 325
74791 : length 325
74793 : length 325
35655 : length 324
53483 : length 322
56095 : length 322
80225 : length 320
81159 : length 320
[download]

Time to run with 12 cores using a Linux VM

Notice the extra 4 seconds user time (likely function overhead inside loop), but not felt in real time (wall clock time).

   Nick's example:  1m32.958s real, 0m56.561s user - no caching
Laurent's example:  1m33.454s real, 1m00.491s user - no caching
Laurent's example:  0m18.761s real, 0m20.990s user -    caching
[download]

Caching is helpful here (5x faster) because I added sleep to simulate more CPU cycles. However, caching is not helpful when the overhead involved is greater than the computation itself as demonstrated by 1nickt's comparison above.

Regards, Mario