FSharp exécute mon algorithme plus lentement que Python!

Question

Il y a des années, j'ai résolu un problème par le biais de la programmation dynamique:

http://users.softlab.ece.ntua.gr/~ttsiod/fillupDVD.html

La solution a été codé en Python.

Dans le cadre de l'élargissement de mes horizons, j'ai récemment commencé à apprendre OCaml/F#. Quoi de mieux pour tester les eaux, que d'en faire un port direct de l'impératif code que j'ai écrit en Python à F# - et à partir de là, se déplaçant dans les étapes vers une fonctionnelle de la solution de programmation.

Les résultats de cette première, port direct... sont déconcertantes:

Sous Python:

  bash$ time python fitToSize.py
  ....
  real    0m1.482s
  user    0m1.413s
  sys     0m0.067s

En Vertu De FSharp:

  bash$ time mono ./fitToSize.exe
  ....
  real    0m2.235s
  user    0m2.427s
  sys     0m0.063s

(dans le cas où vous avez remarqué le "mono" ci-dessus: j'ai testé sous Windows ainsi, avec Visual Studio même vitesse).

Je suis perplexe..., pour dire le moins. Python exécute le code plus rapide que F# ? Un binaire compilé, à l'aide de l' .NET runtime, s'exécute plus lentement que Python est interprété code?!?!

Je sais que sur les coûts de démarrage de la Vm (mono dans ce cas) et comment les Ece d'améliorer les choses pour les langues comme le Python, mais quand même... je m'attendais à une accélération, pas un ralentissement de la!

Ai-je fait quelque chose de mal, peut-être?

J'ai téléchargé le code ici:

http://users.softlab.ntua.gr/~ttsiod/fsharp.slower.than.python.tar.gz

Notez que le code F# est plus ou moins directement, ligne par ligne, la traduction du code Python.

P. S. Il y a bien sûr d'autres gains, par exemple, le type statique de la sécurité offerte par F# - mais si la vitesse résultante d'un impératif de l'algorithme est de pire en vertu de F# ... je suis déçu, pour dire le moins.

EDIT: accès Direct, comme demandé dans les commentaires:

le code Python: https://gist.github.com/950697

le FSharp code: https://gist.github.com/950699

Answer 1

Le Dr Jon Harrop, que j'ai contacté par e-mail, a expliqué ce qui se passe:

Le problème est tout simplement que le programme a été optimisé pour Python. C'est souvent lorsque le programmeur est le plus familier avec un langage que les autres, bien sûr. Vous avez juste à savoir un ensemble différent de règles qui dictent la façon dont F# les programmes devraient être optimisé... Plusieurs choses m'ont sauté aux yeux comme l'utilisation d'un "for i in 1..n ne" boucle plutôt que d'un "for i=1 to n do" de la boucle (qui est plus rapide en général, mais pas important ici), à plusieurs reprises de faire la Liste.mapi sur une liste d'imiter un index de tableau (qui a alloué intermédiaire des listes inutilement) et votre utilisation du F# TryGetValue pour le Dictionnaire qui alloue inutilement (l' .NET TryGetValue qui accepte une ref est plus rapide en général, mais pas tellement ici)

... mais le véritable assassin problème s'est avéré être votre utilisation d'une table de hachage pour mettre en œuvre une densité de la matrice 2D. À l'aide d'une table de hachage est idéal en Python parce que sa table de hachage de la mise en œuvre a été extrêmement bien optimisé (comme en témoigne le fait que votre code Python est en cours d'exécution aussi rapide que F# compilé en code natif!) mais les tableaux sont une bien meilleure manière de représenter des matrices denses, en particulier lorsque vous souhaitez une valeur par défaut de zéro.

Le plus drôle, c'est que lorsque j'ai codé cet algorithme, je NE utilisez un tableau -- j'ai changé la mise en œuvre d'un dictionnaire pour des raisons de clarté (en évitant la limite de tableau contrôles effectués le code plus simple et beaucoup plus facile de raisonner sur).

Jon a transformé mon code au dos :-)) dans son tableau de la version, et il fonctionne à 100 fois la vitesse.

Morale de l'histoire:

• F# Dictionnaire des besoins de travail... lors de l'utilisation de n-uplets clés, compilé F# est plus lent que interprétée Python tables de hachage!
• Évident, mais pas de mal de le répéter: Nettoyeur de code signifie parfois... beaucoup plus lent code.

Merci à vous, Jon -- beaucoup apprécié.

EDIT: le fait que le remplacement de Dictionnaire avec le Tableau fait F# enfin courir à la vitesse d'un langage compilé est prévu pour fonctionner, n'est-ce pas nier le besoin d'une correction dans le Dictionnaire de la vitesse (j'espère que F# personnes à partir de MS sont la lecture de ce). D'autres algorithmes dépendent de dictionnaires/tables de hachage, et ne peut pas être facilement changé à l'aide de tableaux; de faire des programmes de souffrir "interprète-vitesses" chaque fois que l'on utilise un Dictionnaire, est sans doute un bug. Si, comme certains l'ont dit dans les commentaires, le problème n'est pas F# mais avec .NET Dictionnaire, alors je dirais que c'est... un bug dans .NET!

EDIT2: La solution la plus claire, qui ne nécessite pas l'algorithme de passer à des tableaux (certains algorithmes ne pourront tout simplement pas être prête pour cela), c'est pour changer cela:

let optimalResults = new Dictionary<_,_>()

dans ce:

let optimalResults = new Dictionary<_,_>(HashIdentity.Structural)

Cette modification rend le code F# exécuté 2,7 x fois plus vite, donc finalement battre en Python (1,6 x plus rapide). La chose étrange est que les tuples par défaut utiliser la comparaison structurelle, donc, en principe, la comparaison faite par le Dictionnaire sur les touches sont les mêmes (avec ou sans Structurels). Dr Harrop théorise que la différence de vitesse peut être attribuée à virtuel dépêche: "autant que je sache, .NET fait peu pour optimiser virtuel envoi de distance et le coût du virtuel, l'expédition est extrêmement élevé sur du matériel moderne, parce que c'est un "calculé goto" qui saute le compteur de programme, à une imprévisible emplacement et, par conséquent, nuit à la direction de la prévision logique et sera presque certainement entraîner l'ensemble de la CPU pipeline d'être vidé et rechargé".

En clair, et comme suggéré par Don Syme (regardez en bas 3 réponses), "être explicite quant à l'utilisation des structurel de hachage lors de l'utilisation de référence de type de clés en conjonction avec le .NET collections". (Dr Harrop dans les commentaires ci-dessous également dit que nous devrions toujours utiliser des comparaisons Structurelles lors de l'utilisation .NET collections).

Chère équipe F# dans la SEP, si il y a un moyen pour résoudre ce problème, s'il vous plaît.

Answer 2

Comme l'a souligné Jon Harrop, la construction des dictionnaires à l'aide de Dictionary(HashIdentity.Structural) donne une amélioration majeure des performances (facteur 3 sur mon ordinateur). Il s’agit presque certainement du changement le moins invasif que vous devez effectuer pour obtenir de meilleures performances que Python. Votre code reste idiomatique (au lieu de remplacer des tuples par des structs, etc.) et parallèle à l’implémentation de Python.

Answer 3

Edit: je me suis trompé, ce n'est pas une question de valeur type ou de type de référence. Le problème était lié à la fonction de hachage, comme expliqué dans d'autres commentaires. Je garde ma réponse ici, car il y a un très intéressant débat. Mon code partiellement résolu le problème de performances, mais ce n'est pas la nettoyer et de la solution recommandée.

--

Sur mon ordinateur, j'ai fait votre échantillon exécuter deux fois plus vite en remplaçant le n-uplet avec une struct. Cela signifie, l'équivalent du code F# devraient courir plus vite que votre code Python. Je ne suis pas d'accord avec les commentaires disant que .NET tables de hachage sont lents, je crois qu'il n'y a pas de différence significative avec Python ou en d'autres langues implémentations. Aussi, je ne suis pas d'accord avec le "Vous ne pouvez pas 1-de-1 de traduire le code de croire qu'il sera plus rapide": F# code sera généralement plus rapide que Python pour la plupart des tâches (le typage statique est très utile pour le compilateur). Dans votre exemple, la plupart du temps est consacré à faire à la table de hachage des recherches, il est donc juste d'imaginer que les deux langues doit être presque aussi rapide.

Je pense que le problème de performances est liée à gabage collection (mais je n'ai pas vérifié avec un profiler). La raison pour laquelle à l'aide de tuples peuvent être moins rapide que les structures ont été discutés dans une question ( Pourquoi le nouveau Tuple de type en .Net 4.0 un type de référence (la classe) et non une valeur de type (struct)) et une page MSDN (Bâtiment n-uplets):

Si ils sont des types référence, ce signifie qu'il y a peut être beaucoup de déchets généré si vous êtes à la modification de certains éléments dans un tuple dans une boucle serrée. [...] F# tuples ont été les types de référence, mais il y avait un sentiment de l'équipe qui ils ont pu réaliser une performance amélioration si deux, et peut-être trois, élément de tuples ont été les types de valeur au lieu de cela. Certaines équipes qui les ont créés interne tuples avait utilisée au lieu de la valeur de types de référence, en raison de leur les scénarios ont été très sensibles à création d'un grand nombre d'objets gérés.

Bien sûr, comme Jon a dit dans un autre commentaire, l'optimisation évidente dans votre exemple, pour remplacer les tables de hashage avec des tableaux. Les tableaux sont évidemment beaucoup plus rapide (integer index, pas de hachage, pas de collision de la manipulation, pas de réaffectation, plus compact), mais c'est très spécifique à votre problème, et ça n'explique pas la différence de performances avec Python (pour autant que je sais, le code Python est à l'aide de tables de hachage, pas des tableaux).

Pour reproduire mes 50% de l'accélération, voici le code complet: http://pastebin.com/nbYrEi5d

En bref, j'ai remplacé le tuple avec ce type:

type Tup = {x: int; y: int}

Aussi, il semble comme un détail, mais vous devez déplacer l' List.mapi (fun i x -> (i,x)) fileSizes hors de la boucle englobante. Je crois Python enumerate ne fait pas l'attribuer à une liste (de sorte qu'il est équitable d'allouer à la liste qu'une seule fois en F#, ou utiliser Seq module, ou d'utiliser une mutable compteur).