Pourquoi Raku fonctionne-t-il si mal avec des tableaux multidimensionnels?

10

Je suis curieux de savoir pourquoi Raku exécute si mal les tableaux multidimensionnels de manipulation. J'ai fait un test rapide en initialisant une matrice à 2 dimensions en Python, C # et Raku et le temps écoulé est étonnamment élevé pour la dernière.

Pour Raku

my @grid[4000;4000] = [[0 xx 4000] xx 4000];
# Elapsed time 42 seconds !!

Pour Python

table= [ [ 0 for i in range(4000) ] for j in range(4000) ]
# Elapsed time 0.51 seconds

C #

int [,]matrix = new int[4000,4000];
//Just for mimic same behaviour
for(int i=0;i<4000;i++)
   for(int j=0;j<4000;j++)
       matrix[i,j] = 0;
# Elapsed time 0.096 seconds

Suis-je mal? Cela semble beaucoup trop de différence.

Javi
la source
5
Ce n'est que lent pour les tableaux multidimensionnels façonnés (EG celui où vous le définissez @grid[4000;4000]), le code python n'utilise pas un tableau façonné et vous essayez de même dans Raku, vous obtenez un bien meilleur retour: my @grid = [[0 xx 4000] xx 4000]; cela signifie que vous devez accéder avec @grid[0][0]non @grid[0;0]. Je pense que c'est principalement parce que les tableaux en forme sont toujours en cours de réalisation.
Scimon Proctor
1
Sur ma machine a @grid[1000;1000] = [[0 xx 1000]xx1000]pris 12 secondes. @grid = [[0 xx 1000]xx1000]a pris 0,6 donc ... ouais. J'éviterais les tableaux en forme.
Scimon Proctor
5
@Scimon, vous pouvez toujours utiliser l'accesseur [;] pour les tableaux non mis en forme. my @grid = [[$++ xx 100] xx 100]; say @grid[0;1]; say @grid[1;1]renvoie respectivement 1 et 101
user0721090601
Impressionnant! Cela rend les choses plus faciles.
Scimon Proctor du
2
Les tableaux multidimensionnels en forme n'ont pas encore reçu la qualité d'optimisation que de nombreux autres domaines de Rakudo ont reçus.
Elizabeth Mattijsen

Réponses:

13

Une première comparaison directe

Je vais commencer par un code qui est beaucoup plus aligné avec votre code Python que votre propre traduction. Je pense que le code Raku qui est le plus directement équivalent à votre Python est:

my \table = [ [ 0 for ^4000 ] for ^4000 ];
say table[3999;3999]; # 0

Ce code déclare un identifiant sans sceau 1 . Il:

  • Goutte "mise en forme" ( [4000;4000]dans my @table[4000;4000]). Je l'ai laissé tomber parce que votre code Python ne le fait pas. La mise en forme confère des avantages mais a des implications en termes de performances. 2

  • Utilise la liaison au lieu de l' affectation . Je suis passé à la liaison parce que votre code Python fait une liaison, pas une affectation. (Python ne fait pas de distinction entre les deux.) Bien que l'approche d'affectation de Raku apporte des avantages fondamentaux qui valent la peine d'avoir pour le code général, elle a des implications en termes de performances. 3


Ce code avec lequel j'ai commencé ma réponse est encore lent.

Tout d'abord, le code Raku, exécuté via un compilateur Rakudo à partir de décembre 2018, est environ 5 fois plus lent que votre code Python, en utilisant un interpréteur Python à partir de juin 2019, sur le même matériel. 3

Deuxièmement, le code Raku et le code Python sont lents, par exemple par rapport à votre code C #. On peut faire mieux ...

Une alternative idiomatique mille fois plus rapide

Le code suivant mérite d'être considéré:

my \table = [ [ 0 xx Inf ] xx Inf ];
say table[ 100_000; 100_000 ]; # 0

Malgré ce code correspondant à un tableau théorique de 10 milliards d' éléments plutôt que le simple élément de 16 millions dans votre code Python et C #, le temps d'horloge pour le faire fonctionner est moins de la moitié de celui du code Python, et seulement 5 fois plus lent que le C # code. Cela suggère que Rakudo exécute le code Raku plus de mille fois plus vite que le code Python équivalent, et cent fois plus vite que le code C #.

Le code Raku semble être beaucoup plus rapide car la table est initialisée paresseusement à l'aide de xx Inf. 4 Le seul travail important est effectué sur le fonctionnement de la sayligne. Cela provoque la création de 100 000 tableaux de première dimension, puis le remplissage du 100 000e tableau de deuxième dimension avec 100 000 éléments, de sorte que le saypeut afficher le 0contenu du dernier élément de ce tableau.

Il y a plus d'une façon de le faire

Un problème sous-jacent à votre question est qu'il y a toujours plus d'une façon de le faire. 5 Si vous rencontrez de mauvaises performances pour le code où la vitesse est critique, le coder différemment, comme je l'ai fait, peut faire une différence dramatique. 6

(Une autre très bonne option est de poser une question SO ...)

L'avenir

Raku est soigneusement conçu pour être très Optimiz en mesure , par exemple en mesure d' une jours beaucoup plus vite étant donné le travail de compilateur suffisant au cours des années à venir , que, par exemple, Perl 5 ou Python 3 peut, en théorie, jamais courir, à moins qu'ils ne passent par un chaussée refonte et des années de travail de compilation correspondant.

Une analogie quelque peu correcte est ce qui s'est passé avec les performances de Java au cours des 25 dernières années. Rakudo / NQP / MoarVM sont à mi-chemin du processus de maturation que la pile Java a traversé.

Notes de bas de page

1 Je aurais pu écrire my $table := .... Mais les déclarations de la forme my \foo ...éliminent la prise en compte des sigils et permettent d'utiliser =plutôt que :=ce qui serait requis avec un identifiant sigil. (En bonus, "réduire le sigil" donne un identifiant sans sigil, familier aux codeurs dans les nombreuses langues qui n'utilisent pas de sigils, ce qui inclut bien sûr Python et C #.)

2 La mise en forme peut un jour entraîner des opérations de tableau plus rapides pour certains codes. En attendant, comme mentionné dans les commentaires sur votre question, cela fait clairement le contraire actuellement, ce qui ralentit considérablement. J'imagine que c'est en grande partie parce que chaque accès à un tableau est naïvement contrôlé dynamiquement pour le moment, lentement tout en bas, et il n'y a pas eu non plus d'efforts pour utiliser la taille fixe pour aider à accélérer les choses. De plus, lorsque j'ai essayé de trouver une solution de contournement rapide pour votre code, je n'ai pas réussi à en trouver un en utilisant le tableau de taille fixe car de nombreuses opérations sur les tableaux de taille fixe n'étaient actuellement pas implémentées. Encore une fois, il est à espérer qu'elles seront mises en œuvre un jour, mais elles n'ont probablement pas été un point de souffrance suffisant pour quiconque de travailler à leur mise en œuvre à ce jour.

3 Au moment d'écrire ces lignes , TIO utilise Python 3.7.4, à partir de juin 2019, et Rakudo v2018.12, à partir de décembre 2018. Les performances de Rakudo s'améliorent actuellement au fil du temps beaucoup plus rapidement que l'interprète officiel Python 3, donc je voudrais attendez-vous à ce que l'écart entre le dernier Rakudo et le dernier Python, lorsque Rakudo est plus lent, soit considérablement plus étroit que celui indiqué dans cette réponse. En particulier, les travaux en cours améliorent considérablement les performances des missions.

4 xx est par défaut un traitement paresseux mais certaines expressions forcent une évaluation ardue en raison de la sémantique du langage ou des limitations actuelles du compilateur. Dans le Rakudo v2018.12 de l'année, pour qu'une expression de la forme [ [ foo xx bar ] xx baz ]reste paresseuse et ne soit pas obligée d'évaluer avec impatience, à la fois bar et bazdoit être Inf. En revanche, my \table = [0 xx 100_000 for ^100_000]est paresseux sans utilisation de Inf. (Ce dernier code stocke en réalité 100 000 Seqs dans la première dimension plutôt que 100 000 Arrays - les say WHAT table[0]affichages Seqplutôt que Array- mais la plupart des codes ne pourront pas détecter la différence - say table[99_999;99_999]s'afficheront toujours 0.)

5 Certaines personnes pensent que c'est une faiblesse d'accepter qu'il existe plus d'une façon de penser et de coder des solutions à des problèmes donnés. En réalité, c'est une force à au moins trois égards. Premièrement, en général, tout problème donné non trivial peut être résolu par de nombreux algorithmes distincts avec des différences dramatiques dans le profil de performance. Cette réponse inclut une approche déjà disponible avec un Rakudo d'un an qui sera plus de mille fois plus rapide que Python dans la pratique dans certains scénarios. Deuxièmement, un langage délibérément flexible et multi-paradigme comme Raku permet à un codeur (ou une équipe de codeurs) d'exprimer une solution qu'ils considèrent élégante et maintenable, ou qui fait juste le travail, en fonction de ce qu'ilspenser est le meilleur, pas ce que la langue impose. Troisièmement, les performances de Rakudo en tant que compilateur d'optimisation sont actuellement particulièrement variables. Heureusement, il a un excellent profileur 6 , donc on peut voir où se trouve un goulot d'étranglement, et une grande flexibilité, donc on peut essayer un codage alternatif et cela peut produire un code beaucoup plus rapide.

6 Lorsque les performances sont importantes ou si vous étudiez des problèmes de performances, consultez la page doc Raku sur les performances ; la page couvre une gamme d'options, y compris l'utilisation du profileur Rakudo.

raiph
la source