почему эта мемоизированная реализация Euler14 намного медленнее в Raku, чем в Python?

Недавно я играл с задачей 14 из Euler project: какое число в диапазоне 1..1_000_000 дает самый длинный последовательность Коллатца?

Мне известно о необходимости memoize, чтобы получить разумное время, и следующий фрагмент кода Python возвращает ответ относительно быстро, используя эту технику (memoize to 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)

(адаптировано из здесь; я предпочитаю эту версию, в которой не используется max, потому что я мог бы захотеть возиться с ним, чтобы вернуть самые длинные 10 последовательностей и т. д.).

Я попытался перевести это как Raku, оставаясь как можно семантически близким:

#!/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

Вот несколько раз, когда я постоянно их запускаю:

$ time <python script>
837799

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

С другой стороны, в Raku:

$ time <raku script>
837799

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

Вопрос(ы)

Я неправильно перевожу их, или разница заключается в непримиримом вопросе запуска виртуальной машины и т. д.?

Есть ли умные настройки/идиомы, которые я могу применить к коду Raku, чтобы значительно ускорить его?

В сторону

Естественно, речь идет не столько об этой конкретной Euler project проблеме; В более широком смысле меня интересует, существуют ли какие-либо магические арканы ускорения, подходящие для Raku, о которых я не знаю.


person grobber    schedule 16.11.2020    source источник
comment
Возможно, лучший способ получить волшебное ускорение Raku — это перевести его на Python :-) Извините, не удержался, я так давно не пользовался Perl, что, наверное, не могу предоставить полезный ответ, за исключением того, что вы можете вставить временные ловушки в свой код, чтобы увидеть, где находится задержка.   -  person paxdiablo    schedule 16.11.2020
comment
:-) Достаточно справедливо, но это не умаляет внутреннего интереса, который для меня представляет вопрос о том, что на самом деле здесь происходит.   -  person grobber    schedule 16.11.2020
comment
grobber, согласен, я не говорил, что ваш вопрос некорректен, он на самом деле неплох.   -  person paxdiablo    schedule 16.11.2020
comment
@paxdiablo, .@grobber Возможно, лучший способ получить волшебное ускорение Raku — это перевести его на Python... Вероятно, я не могу дать полезный ответ. :-) У тебя есть! :) Раку(до) поддерживает замечательную систему автоматического перевода. Один просто непосредственно использует существующий (или новый) код иностранного языка (нет необходимости в переводе вручную) через Inline. Используйте чужие черты, как если бы они были родными для Раку! Все данные, исключения и т. д. автоматически сортируются. Если вы нажмете на ссылку, вы увидите Inline::Python, который находится в разработке. Может, попробовать?   -  person raiph    schedule 16.11.2020
comment
Можно увидеть улучшения, используя функцию «использовать экспериментальную: кэшированную».   -  person Coke    schedule 16.11.2020


Ответы (1)


Я думаю, что большая часть дополнительного времени связана с тем, что в Raku есть проверки типов, и они не удаляются специалистом по типам во время выполнения. Или, если они удаляются, это происходит по прошествии значительного времени.

Как правило, способ оптимизации кода Raku заключается в том, чтобы сначала запустить его с помощью профилировщика:

$ raku --profile test.raku

Конечно, с этим кодом происходит сбой Segfault, поэтому мы не можем его использовать.

Я предполагаю, что большая часть времени связана с использованием хэша.

Если бы это было реализовано, использование собственных целых чисел для ключа и значения могло бы помочь:

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

Тогда объявление функций как использующих целые числа нативного размера может стать большим выигрышем.
(В настоящее время это в лучшем случае незначительное улучшение.)

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

Конечно, как я уже сказал, собственные хэши не реализованы, так что это чистое предположение.


Вы можете попробовать использовать многопроцессорные возможности Raku, но могут возникнуть проблемы с общей переменной %cllens.


Проблема также может быть из-за рекурсии. (В сочетании с вышеупомянутыми проверками типов.)

Если бы вы переписали cllen так, чтобы он использовал цикл вместо рекурсии, это могло бы помочь.


Примечание.
Ближайшим к n not in cllens, вероятно, является %cllens{$n}:!exists.
Хотя это может быть медленнее, чем простая проверка того, что значение не равно нулю.

А еще cellen какой-то ужасный. Я бы написал еще так:

sub cllen($n) {
    %cllens{$n} //= cllen(cltz($n)) + 1
}
person Brad Gilbert    schedule 16.11.2020
comment
Спасибо! RE: ваш заместитель cllen: Я бы тоже так написал! :-) Я часто использую //=, но не стремился к элегантности, попробовал самый простой перевод и опубликовал его. - person grobber; 16.11.2020
comment
Привет @grobber. разместил ... самый простой перевод, я думаю, что это помогает. Я добавил в закладки этот высококачественный SO. Я бы, наверное, тоже так написал! :-) Мне три. :) Это было первое, что я попробовал прошлой ночью. не стремился к элегантности. Одна из причин, по которой я использую op=, — эстетическая, но в целом это намного быстрее. Это вдвое сократило время работы для меня. Я решил отказаться от комментирования, потому что это был единственный успех, которого я добился, и сокращение вдвое 20-кратного замедления до 10-кратного медленнее, чем python, не было похоже на идиомы [множественное число]. Я могу применить к коду Raku, чтобы ускорить его значительно, ни магическое ускорение арканы. - person raiph; 16.11.2020
comment
@BradGilbert Конечно, [raku --profile test.raku] не работает с Segfault с этим кодом, поэтому мы не можем его использовать. Конечно, я не могу сказать, означает ли ваше «Конечно» что-то вроде «По иронии судьбы» или есть что-то очевидное, что я упускаю. :) Есть идеи, почему? Это потому, что $L установлено на миллион? Что, если он упадет, скажем, до 10? (В настоящее время я не могу получить доступ к системе с настройкой разработчика, иначе я бы попробовал сам.) - person raiph; 16.11.2020
comment
@raiph Я хотел, чтобы это звучало раздраженно. Как в «Конечно, это не работает, потому что это действительно было бы полезно». - person Brad Gilbert; 16.11.2020
comment
@BradGilbert Спасибо. Я слышал от вас о раздражении. В надежде, что мои комментарии не подпитывают его, я продолжу. Я нечасто использовал профилировщик (и вообще не могу сейчас), но в прошлом он обычно работал у меня для небольших тиражей, а не для больших. Отсюда моя мысль о снижении $L до небольшого числа, чтобы посмотреть, работает ли это и дает какое-то представление. - person raiph; 16.11.2020
comment
@raif: спасибо! Я также испытал умеренное ускорение на этой же машине, изменив cllen точно так, как предложил @Brad Gilbert (хотя и не в 2 раза; время работы сократилось до чуть менее 17 с). Уже одно это полезно знать: всегда приятно осознавать, что эстетика и производительность совпадают. - person grobber; 16.11.2020