benchmark mistery

bm

# The most common approach, and probably the simplest solution to this challenge
# is to create an array of men, and then keep taking two from the front and putting the first of 
# them to the back of the array until it has only one member left.
#
# A concise version of this looks like

sub take-two-push-one 
{
    given my @men = 1..50 { .push( .splice(0,2).first ) while .elems > 1 };
    @men.first;
}

# This is a straightforward and easy to understand solution. But is it the fastest?
# Let's look at some other possibilities.

# The following two solutions look at the number of men in each round
# of killing and then use rotor(2) to split them up into killer / victim tuples,
# from which only the survivors will be shoved into the next round.
#
# The first one uses recursion, while the second one does the work iteratively.
#
# Apart from that it's basically the same code in both cases. It should perform similarly.
# If anything the recursive version should be slower since it has the additional overhead of 
# multiple subroutine calls. Or so one would think.

multi sub recursive-rotor
{
    recursive-rotor( 1..50 );
}

multi sub recursive-rotor( @men ) 
{
    given @men
    {
        return .first if .elems == 1;
    
        if .elems %% 2 
        {
            # When the number of men is even, we know the last man will die and 
            # we can start the next round at the beginning.
            recursive-rotor( .rotor(2).map: *.first );
        } else 
        {
            # When the number of men is odd, the last man will have killed the 
            # former first man, so we need to skip over the poor fellow.
            recursive-rotor( .rotor(2, :partial).skip.map: *.first );
        }
    }
}

sub rotor
{
    my @men = 1..50;
    
    while @men.elems > 1
    {
        if @men.elems %% 2 
        {
            @men = @men.rotor(2).map: *.first;
        } else {
            @men = @men.rotor(2, :partial).skip.map: *.first;
        }
    }
    @men.first;
}

# O-------------------O--------O-----------------O-------O-------------------O
# |                   | Rate   | recursive-rotor | rotor | take-two-push-one |
# O===================O========O=================O=======O===================O
# | recursive-rotor   | 3968/s | --              | -9%   | -22%              |
# | rotor             | 3661/s | 10%             | --    | -14%              |
# | take-two-push-one | 3198/s | 28%             | 16%   | --                |
# O-------------------O--------O-----------------O-------O-------------------O
#
# So in reality the recursive version is faster than the iterative. Why is that?
# 
# I assume it because the iterative version has to operate on Arrays, since it 
# has to assign to @men. The recursive function however can operate solely on Lists.
#  
# Both variants are faster than the naive approach. But one fifth speedup is not 
# a huge win. Surely there is room for improvement. 
#
# In an attempt to do less work the following solution does not keep and transform 
# a list of numbers that represent each man. Instead it keeps a list of dead and
# alive states, manipulating them. Since the array does not get transformed it can 
# use the index of the array to identify the survivor.

sub c-style 
{
    my @men    = True xx 50;
    my $killed = 0;
    my $skip   = False;
    my $to-kill   = 1;
    
    loop 
    {
        if @men[$to-kill]
        {
            if ( $skip )
            {
                return $to-kill + 1
                    if $killed == 49;

                $skip = False;
            }
            else
            {
                $killed++;
                @men[$to-kill] = False;
                $skip = True;
            }
        }

        $to-kill = $to-kill > 49 ?? 0 !! $to-kill + 1;
    }
   
}

#How does this compare?
# 
# O-------------------O--------O---------O-----------------O-------------------O
# |                   | Rate   | c-style | recursive-rotor | take-two-push-one |
# O===================O========O=========O=================O===================O
# | c-style           | 3794/s | --      | 5%              | -23%              |
# | recursive-rotor   | 3976/s | -5%     | --              | -27%              |
# | take-two-push-one | 2983/s | 31%     | 38%             | --                |
# O-------------------O--------O---------O-----------------O-------------------O
#
# This too is faster than the original, in about the same ballpark as the recursive rotor
# variant. Again, not great. It's also quite ugly code.

# The problem naturally lends itself to be expressed in terms of a circular linked list,
# a data structure most young people don't learn about in school anymore.
#
# In the following solution, I'm using Rakus ability to ad hoc mixin roles to first create a circular linked list of 
# Integers, then I start cutting out (or killing) every second man from the list, starting at the first man.
#
# While the raw killing part here is very efficient (linear complexity), 
# the ad-hoc mixing in of the Linked role will cost. 

role Linked { has $.next is rw; }

sub linked-list 
{
    my $first = my $killer = 1 but Linked;
    
    for 2..50 
    { 
        my $man = $_ but Linked; 
        $killer.next = $man; 
        $killer = $man; 
    }
    
    $killer.next = $first;
    $killer = $first;

    while $killer != $killer.next {
      $killer = $killer.next = $killer.next.next;
    }

    $killer;
}

# O-------------------O--------O-------------O-----------------O-------------------O
# |                   | Rate   | linked-list | recursive-rotor | take-two-push-one |
# O===================O========O=============O=================O===================O
# | linked-list       | 1056/s | --          | 349%            | 230%              |
# | recursive-rotor   | 4077/s | -78%        | --              | -27%              |
# | take-two-push-one | 3145/s | -70%        | 36%             | --                |
# O-------------------O--------O-------------O-----------------O-------------------O
#
# Bummer. 3 to 4 times slower. That's bad. Apparenly ad-hoc roles are really costly.
# What happens when a class is used instead?



class LinkedInt is Int does Linked { };

sub linked-list-class 
{
    my $first = LinkedInt.new(1);
    my $killer  = $first;

    for 2..50 
    { 
        my $man = LinkedInt.new($_); 
        $killer.next = $man; 
        $killer = $man; 
    }
    
    $killer.next = $first;
    $killer = $first;

    while $killer != $killer.next {
      $killer = $killer.next = $killer.next.next;
    }

    $killer;
}


use Bench;

#Bench.new.cmpthese( 5000, { :&take-two-push-one, :&recursive-rotor, :&linked-list } );
Bench.new.cmpthese( 5000, { :&take-two-push-one, :&recursive-rotor, :&linked-list-class } );


#Bench.new.cmpthese( 5000, { :&take-two-push-one, :&linked-list-class } );
#Bench.new.cmpthese( 5000, { :&take-two-push-one, :&recursive-rotor, :&rotor } );
#Bench.new.cmpthese( 5000, { :&take-two-push-one, :&recursive-rotor, :&c-style } );
#Bench.new.cmpthese( 5000, { :&take-two-push-one, :&rotor, } );
#Bench.new.cmpthese( 5000, { :&take-two-push-one, :& } );
#Bench.new.cmpthese( 5000, { :&take-two-push-one, :&linked-list, :&linked-list-class, :&recursive-rotor, :&c-style, :&rotor, } );