🔬47. Push-all optimisation of List.roll in Raku

Last evening, I made a commit based on my recent observation. Let me devote today’s post to that.

In the last few days, we were talking about the two methods for getting random elements from a list — pick and roll. When you pass an integer to the methods, both of them internally use an instance of the class implementing the Iterator role. Depending on the situation, either pull-one or push-all method is called on that object.

Just as a reminder, here’s the skeleton of the two methods from src/core/List.pm (the samples are not working code):

multi method roll(\number) {
    Seq.new(class :: does Iterator {
        method pull-one() is raw {
        }
    }.new(self,number.Int))
}


multi method pick(List:D: $number is copy) {
    Seq.new(class :: does Iterator {
        method pull-one() {
        }
        method push-all($target) {
        }
    }.new(self,$elems,$number))
}

The problem is that in the case of roll, Rakudo calls pull-one for each element of the list, while in the case of pick, it just gets the whole list at one go.

In this program, both methods are using pull-one:

say <a b c d e>.roll(4);
say <a b c d e>.pick(4);

Although if you change it, only pick switches to push-one, while roll makes as many pull-one calls as you need to fetch all the requested elements individually:

my @r = <a b c d e>.roll(4);
say @r;

my @p = <a b c d e>.pick(4);
say @p;

What I did, I added the push-all method to the roll method:

method push-all($target --> IterationEnd) {
    nqp::while(
        $!todo,
        nqp::stmts(
            ($target.push(nqp::atpos($!list,$!elems.rand.floor))),
            ($!todo = $!todo - 1)
        )
    )
}

Now, in the above example, pick is also using the push-all method.

Compare the speed of the program before and after the change:

$ time ./perl6 -e'my @a = "a".."z"; for ^500_000 {my @b = @a.roll(20)}'
real	0m26.321s
user	0m26.010s
sys	0m0.163s


$ time ./perl6 -e'my @a = "a".."z"; for ^500_000 {my @b = @a.roll(20)}'
real	0m20.829s
user	0m20.701s
sys	0m0.130s

With the given data, it works 20% faster. Add some more code and gain some speed 🙂

P. S. Also read Zoffix’s post (or its part) in the Rakudo.party blog with more information about the push-all method.