why is this memoized Euler14 implementation so much slower in Raku than Python?

Question

I was recently playing with problem 14 of the Euler project: which number in the range 1..1_000_000 produces the longest Collatz sequence?

I'm aware of the issue of having to memoize to get reasonable times, and the following piece of Python code returns an answer relatively quickly using that technique (memoize to a dict):

#!/usr/bin/env python

L = 1_000_000
cllens={1:1}

cltz = lambda n: 3*n + 1 if n%2 else n//2

def cllen(n):
    if n not in cllens: cllens[n] = cllen(cltz(n)) + 1
    return cllens[n]

maxn=1
for i in range(1,L+1):
    ln=cllen(i)
    if (ln > cllens[maxn]): maxn=i

print(maxn)

(adapted from here; I prefer this version that doesn't use max, because I might want to fiddle with it to return the longest 10 sequences, etc.).

I have tried to translate it to Raku staying as semantically close as I could:

#!/usr/bin/env perl6
use v6;

my $L=1_000_000;
my %cllens = (1 => 1);

sub cltz($n) { ($n %% 2) ?? ($n div 2) !! (3*$n+1) }

sub cllen($n) {
    (! %cllens{$n}) && (%cllens{$n} = 1+cllen($n.&cltz));
    %cllens{$n};
}

my $maxn=1;
for (1..$L) {
    my $ln = cllen($_);
    ($ln > %cllens{$maxn}) && ($maxn = $_)
}
say $maxn

Here are the sorts of times I am consistently getting running these:

$ time <python script>
837799

real    0m1.244s
user    0m1.179s
sys     0m0.064s

On the other hand, in Raku:

$ time <raku script>
837799

real    0m21.828s
user    0m21.677s
sys     0m0.228s

Question(s)

Am I mistranslating between the two, or is the difference an irreconcilable matter of starting up a VM, etc.?

Are there clever tweaks / idioms I can apply to the Raku code to speed it up considerably past this?

Aside

Naturally, it's not so much about this specific Euler project problem; I'm more broadly interested in whether there are any magical speedup arcana appropriate to Raku I am not aware of.

Answer 1

I think the majority of the extra time is because Raku has type checks, and they aren't getting removed by the runtime type specializer. Or if they are getting removed it is after a significant amount of time.

Generally the way to optimize Raku code is first to run it with the profiler:

$ raku --profile test.raku

Of course that fails with a Segfault with this code, so we can't use it.

My guess would be that much of the time is related to using the Hash.

If it was implemented, using native ints for the key and value might have helped:

 my int %cllens{int} = (1 => 1);

Then declaring the functions as using native-sized ints could be a bigger win.
(Currently this is a minor improvement at best.)

sub cltz ( int $n --> int ) {…}
sub cllen( int $n --> int ) {…}
for (1..$L) -> int $_ {…}

Of course like I said native hashes aren't implemented, so that is pure speculation.

---

You could try to use the multi-process abilities of Raku, but there may be issues with the shared %cllens variable.

---

The problem could also be because of recursion. (Combined with the aforementioned type checks.)

If you rewrote cllen so that it used a loop instead of recursion that might help.

---

Note:
The closest to n not in cllens is probably %cllens{$n}:!exists.
Though that might be slower than just checking that the value is not zero.

Also cellen is kinda terrible. I would have written it more like this:

sub cllen($n) {
    %cllens{$n} //= cllen(cltz($n)) + 1
}