use strict;
use warnings;
use feature 'say';
use MCE::Flow;

use Inline C => Config =>
    CCFLAGSEX => '-O2 -fomit-frame-pointer', clean_after_build => 0;

use Inline C => <<'END_OF_C_CODE';

#include <stdlib.h>
#include <stdint.h>

#if defined(_WIN32)
#define strtoull _strtoui64
#endif

void collatz_count_c1( SV* _n )
{
    uint64_t n, steps = 1;  /* include 1 */
    Inline_Stack_Vars;

    #ifdef __LP64__
        n = SvUV( _n );
    #else
        n = strtoull( SvPV_nolen( _n ), NULL, 10 );
    #endif

    /* count using the T(x) notation */
    do {
        n % 2 ? ( steps += 2, n = (3 * n + 1) >> 1 )
              : ( steps += 1, n = n >> 1 );
    } while ( n != 1 );

    Inline_Stack_Reset;
    Inline_Stack_Push( sv_2mortal( newSVuv( steps ) ) );
    Inline_Stack_Done;
}

void collatz_count_c2( SV* _n )
{
    uint64_t n, steps = 1;  /* include 1 */
    Inline_Stack_Vars;

    #ifdef __LP64__
        n = SvUV( _n );
    #else
        n = strtoull( SvPV_nolen( _n ), NULL, 10 );
    #endif

    /* based on GCC compiler intrinsics demonstration by Alex Shirley */
    /* https://stackoverflow.com/questions/38114205/c-collatz-conjecture-optimization */
    /* https://www.go4expert.com/articles/builtin-gcc-functions-builtinclz-t29238 */

    if ( n % 2 == 0 ) {
        steps += __builtin_ctz(n); /* account for all evens */
        n >>= __builtin_ctz(n);    /* always returns an odd */
    }

    /* when we enter we're always working on an odd number */
    do {
        n = 3 * n + 1;
        steps += __builtin_ctz(n) + 1; /* account for odd and even */
        n >>= __builtin_ctz(n);        /* always returns an odd */
    } while ( n != 1 );

    Inline_Stack_Reset;
    Inline_Stack_Push( sv_2mortal( newSVuv( steps ) ) );
    Inline_Stack_Done;
}

END_OF_C_CODE

sub collatz_count {
    my ($n) = @_;
    my $steps = 1;  # count 1

    # count using the T(x) notation
    $n % 2 ? ( $steps += 2, $n = (3 * $n + 1) >> 1 )
           : ( $steps += 1, $n = $n >> 1 )
        while $n != 1;

    return $steps;
}

no warnings 'once';

#*collatz = \&collatz_count;     # choose collatz here
#*collatz = \&collatz_count_c1;  # using the T(x) notation
 *collatz = \&collatz_count_c2;  # using compiler intrinsics

my $m = shift || 1e6;
my ( @sizes, $chunk_size );

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

MCE::Flow->init(
    max_workers => MCE::Util::get_ncpu(),
    chunk_size  => $chunk_size,
    gather      => \@sizes,
    bounds_only => 1,
);

mce_flow_s sub {
    my ( $start, $end ) = @{ $_[1] }; my @ret;

    for ( $start .. $end ) {
        push @ret, [ $_, collatz($_) ];
        @ret = ( sort { $b->[1] <=> $a->[1] } @ret )[ 0..19 ]
           if @ret > 100;
    }

    ( @ret > 20 )
        ? MCE->gather( ( sort { $b->[1] <=> $a->[1] } @ret )[ 0..19 ] )
        : MCE->gather( @ret );
}, 1, $m;

MCE::Flow->finish;

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