#!/usr/bin/env perl
use strict;
use warnings;

use File::Map qw/map_anonymous unmap/;
use Time::HiRes qw/usleep/;
use MCE::Flow;
use MCE::Candy;

my $size = shift || 1e6;

$size = 1e6 if $size < 1e6;  # minimum
$size = 1e9 if $size > 1e9;  # maximum

map_anonymous my $cache, $size * 2 + 2, 'shared';

# fill cache with zeroes
substr($cache, 0, $size * 2 + 2, pack('s', 0) x ( $size + 1 ));

# local to workers and the manager process
my @seqs;

sub collatz_seq {
    my ( $chunk_id, $seq_beg, $seq_end ) = @_;
    my ( $n, $steps, $tmp );

    for my $input ( $seq_beg..$seq_end ) {
        $n = $input, $steps = 0;

        $n % 2 ? ( $steps += 2, $n = (3 * $n + 1) >> 1 )
               : ( $steps += 1, $n = $n >> 1 )
            while $n != 1 && $n >= $input;

        $tmp = unpack('s', substr($cache, $n * 2, 2));

        # another worker with a lesser chunk_id is not yet
        # completed processing $n, so pause a little

        # if ( $tmp == 0 && $chunk_id > 1 ) {
        #     do {
        #         usleep 100;
        #         $tmp = unpack('s', substr($cache, $n * 2, 2));
        #     } while ( $tmp == 0 );
        # }

        # do this instead (faster): compute $n if cache miss
        $tmp = _collatz($n) if $tmp == 0 && $chunk_id > 1;

        substr($cache, $input * 2, 2, pack('s', $steps += $tmp));
        push @seqs, [ $input, $steps + 1 ] if $steps > 400;
    }
}

sub _collatz {
    my ( $input ) = @_;
    my ( $n, $steps ) = ( $input, 0 );

    $n % 2 ? ( $steps += 2, $n = (3 * $n + 1) >> 1 )
           : ( $steps += 1, $n = $n >> 1 )
        while $n != 1 && $n >= $input;

    my $tmp = unpack('s', substr($cache, $n * 2, 2));

    $tmp = _collatz($n) if $tmp == 0;
    substr($cache, $input * 2, 2, pack('s', $steps += $tmp));

    return $steps
}

my $chunk_size;

$chunk_size  = int( $size / MCE::Util::get_ncpu() / 80 + 1 );
$chunk_size += 1 if $chunk_size % 2;

MCE::Flow->init(
    max_workers => MCE::Util::get_ncpu(),
    chunk_size  => $chunk_size,  # specify 2500 if pausing above
    bounds_only => 1,
    gather      => MCE::Candy::out_iter_array(\@seqs),
);

mce_flow_s sub {
    my ( $mce, $chunk_ref, $chunk_id ) = @_;
    collatz_seq($chunk_id, @{ $chunk_ref });
    @seqs > 20
        ? MCE->gather($chunk_id, ( sort { $b->[1] <=> $a->[1] } @seqs )[ 0..19 ])
        : MCE->gather($chunk_id, @seqs);
    @seqs = ();
}, 2, $size;

MCE::Flow->finish; unmap $cache;
@seqs = ( sort { $b->[1] <=> $a->[1]} @seqs )[ 0..19 ];

printf "Collatz(%5d) has sequence length of %3d steps\n", @$_
    for @seqs;


##</code><code>##

#!/usr/bin/env perl
use strict;
use warnings;

use File::Map qw/map_anonymous unmap/;
use Time::HiRes qw/usleep/;
use MCE::Flow;
use MCE::Candy;

use Inline C => Config => CCFLAGSEX => '-O2 -fomit-frame-pointer';
use Inline C => <<'END_OF_C_CODE';

#include <stdint.h>

void num_steps_c( SV* _n, SV* _s )
{
    uint64_t n, input;
    int steps = 0;

    n = input = SvUV(_n);

    while ( n != 1 && n >= input ) {
        n % 2 ? ( steps += 2, n = (3 * n + 1) >> 1 )
              : ( steps += 1, n = n >> 1 );
    }

    sv_setuv(_n, n);
    sv_setiv(_s, steps);

    return;
}

END_OF_C_CODE

my $size = shift || 1e6;

$size = 1e6 if $size < 1e6;  # minimum
$size = 1e9 if $size > 1e9;  # maximum

map_anonymous my $cache, $size * 2 + 2, 'shared';

# fill cache with zeroes
substr($cache, 0, $size * 2 + 2, pack('s', 0) x ( $size + 1 ));

# local to workers and the manager process
my @seqs;

sub collatz_seq {
    my ( $chunk_id, $seq_beg, $seq_end ) = @_;
    my ( $n, $steps, $tmp );

    for my $input ( $seq_beg..$seq_end ) {
        num_steps_c($n = $input, $steps);

        $tmp = unpack('s', substr($cache, $n * 2, 2));

        # another worker with a lesser chunk_id is not yet
        # completed processing $n, so pause a little

        # if ( $tmp == 0 && $chunk_id > 1 ) {
        #     do {
        #         usleep 100;
        #         $tmp = unpack('s', substr($cache, $n * 2, 2));
        #     } while ( $tmp == 0 );
        # }

        # do this instead (faster): compute $n if cache miss
        $tmp = _collatz($n) if $tmp == 0 && $chunk_id > 1;

        substr($cache, $input * 2, 2, pack('s', $steps += $tmp));
        push @seqs, [ $input, $steps + 1 ] if $steps > 400;
    }
}

sub _collatz {
    my ( $input ) = @_;

    num_steps_c( my $n = $input, my $steps );
    my $tmp = unpack('s', substr($cache, $n * 2, 2));

    $tmp = _collatz($n) if $tmp == 0;
    substr($cache, $input * 2, 2, pack('s', $steps += $tmp));

    return $steps
}

my $chunk_size;

$chunk_size  = int( $size / MCE::Util::get_ncpu() / 80 + 1 );
$chunk_size += 1 if $chunk_size % 2;

MCE::Flow->init(
    max_workers => MCE::Util::get_ncpu(),
    chunk_size  => $chunk_size,  # specify 2500 if pausing above
    bounds_only => 1,
    gather      => MCE::Candy::out_iter_array(\@seqs),
);

mce_flow_s sub {
    my ( $mce, $chunk_ref, $chunk_id ) = @_;
    collatz_seq($chunk_id, @{ $chunk_ref });
    @seqs > 20
        ? MCE->gather($chunk_id, ( sort { $b->[1] <=> $a->[1] } @seqs )[ 0..19 ])
        : MCE->gather($chunk_id, @seqs);
    @seqs = ();
}, 2, $size;

MCE::Flow->finish; unmap $cache;
@seqs = ( sort { $b->[1] <=> $a->[1]} @seqs )[ 0..19 ];

printf "Collatz(%5d) has sequence length of %3d steps\n", @$_
    for @seqs;


##</code><code>##

1e9, 32 cores
  collatz_seq_before     0m34.211s
  collatz_seq_final      0m26.340s
  collatz_seq_inline_c   0m15.673s

Collatz(670617279) has sequence length of 987 steps
Collatz(848749995) has sequence length of 977 steps
Collatz(954843745) has sequence length of 972 steps
Collatz(954843751) has sequence length of 972 steps
Collatz(716132809) has sequence length of 969 steps
Collatz(537099606) has sequence length of 966 steps
Collatz(537099607) has sequence length of 966 steps
Collatz(268549803) has sequence length of 965 steps
Collatz(805649409) has sequence length of 964 steps
Collatz(805649410) has sequence length of 964 steps
Collatz(805649411) has sequence length of 964 steps
Collatz(805649415) has sequence length of 964 steps
Collatz(402824705) has sequence length of 963 steps
Collatz(604237057) has sequence length of 961 steps
Collatz(604237058) has sequence length of 961 steps
Collatz(604237059) has sequence length of 961 steps
Collatz(302118529) has sequence length of 960 steps
Collatz(906355586) has sequence length of 959 steps
Collatz(906355587) has sequence length of 959 steps
Collatz(906355588) has sequence length of 959 steps