Comment faire pour que mon programme Haskell plus vite? Comparaison avec C

Question

Je suis en train de travailler sur une mise en œuvre de l'un des SHA3 candidats, JH. J'en suis au point où l'algorithme de passer tous les KATs (Réponse Connue Tests) fournies par le NIST, et ont également une instance de la Crypto-API. Ainsi, j'ai commencé à chercher dans ses performances. Mais je suis assez nouveau à Haskell et ne savez pas vraiment ce qu'il faut rechercher lors de l'analyse.

Pour le moment mon code est toujours plus lent que l'implémentation de référence écrit en C, par un facteur de 10 pour toutes les longueurs d'entrée (C code trouvé ici: http://www3.ntu.edu.sg/home/wuhj/research/jh/jh_bitslice_ref64.h).

Mon code Haskell se trouve ici: https://github.com/hakoja/SHA3/blob/master/Data/Digest/JHInternal.hs.

Maintenant, je ne vous attendez pas à parcourir tout mon code, mais je voudrais juste vous souhaitez quelques conseils sur un couple de fonctions. J'ai couru quelques tests de performance et c'est (une partie de) la performance de fichier généré par GHC:

Tue Oct 25 19:01 2011 Time and Allocation Profiling Report  (Final)

   main +RTS -sstderr -p -hc -RTS jh e False

total time  =        6.56 secs   (328 ticks @ 20 ms)
total alloc = 4,086,951,472 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

roundFunction                  Data.Digest.JHInternal  28.4   37.4
word128Shift                   Data.BigWord.Word128  14.9   19.7
blockMap                       Data.Digest.JHInternal  11.9   12.9
getBytes                       Data.Serialize.Get     6.7    2.4
unGet                          Data.Serialize.Get     5.5    1.3
sbox                           Data.Digest.JHInternal   4.0    7.4
getWord64be                    Data.Serialize.Get     3.7    1.6
e8                             Data.Digest.JHInternal   3.7    0.0
swap4                          Data.Digest.JHInternal   3.0    0.7
swap16                         Data.Digest.JHInternal   3.0    0.7
swap8                          Data.Digest.JHInternal   1.8    0.7
swap32                         Data.Digest.JHInternal   1.8    0.7
parseBlock                     Data.Digest.JHInternal   1.8    1.2
swap2                          Data.Digest.JHInternal   1.5    0.7
swap1                          Data.Digest.JHInternal   1.5    0.7
linearTransform                Data.Digest.JHInternal   1.5    8.6
shiftl_w64                     Data.Serialize.Get     1.2    1.1

Detailed breakdown omitted ...

Maintenant, rapidement, sur le JH algorithme:

C'est un algorithme de hachage qui se compose d'une fonction de compression F8, qui est répétée tant qu'il existe des blocs d'entrées (de 512 bits). C'est juste la façon dont le SHA-les fonctions opèrent. La touche F8 fonction consiste en la E8 fonction qui applique une fonction à 42 reprises. La ronde de la fonction elle-même se compose de trois parties: une sbox, une transformation linéaire et d'une permutation ("swap dans mon code).

Par conséquent, il est raisonnable que la plupart du temps est passé dans la fonction arrondi. Je voudrais savoir comment les parties pourraient être améliorés. Par exemple: le blockMap fonction est une fonction d'utilité, la cartographie d'une fonction sur les éléments dans un 4-tuple. Alors pourquoi est-il effectuer si mal? Toute suggestion serait la bienvenue, et pas seulement sur la seule les fonctions, c'est à dire sont là des changements structurels que vous auriez fait dans le but d'améliorer les performances?

J'ai essayé de chercher au Cœur de sortie, mais malheureusement c'est au dessus de ma tête.

J'attache des tas de profils à la fin aussi bien dans le cas qui pourraient être d'intérêt.

EDIT :

J'ai oublié de mentionner mon installation et de construction. Je l'exécute sur un x86_64 Arch Linux de la machine, GHC 7.0.3-2 (je crois), avec des options de compilation:

ghc --make-O2 -funbox-strict-champs

Malheureusement, il semble y avoir un bug sur le Linux plattform lors de la compilation via C ou LLVM, ce qui me donne l'erreur:

Erreur: .la taille de l'expression de XXXX ne pas évaluer à une constante

donc je n'ai pas été en mesure de voir l'effet de cette.

Answer 1

• Commutateur de décaissement des Vecteurs (à partir de la Matrice, utilisé pour les constantes)
• Utiliser unsafeIndex au lieu de subir la vérification de limites et de dépendance de données de sécurité indexation (c - !)
• Déballez Block1024 comme vous l'avez fait avec Block512 (ou au moins utiliser UnboxedTuples)
• Utiliser unsafeShift{R,L} de sorte que vous ne supportez pas la vérification de la valeur de décalage (à venir dans GHC 7.4)
• Déplier l' roundFunction de sorte que vous avez une assez laid et détaillé e8 fonction. C'était significat dans pureMD5 (le roulé version était plus joli, mais massivement plus lent que le déroulé de la version). Vous pourriez être en mesure d' utiliser le TH de faire et de garder le code smallish. Si vous faites cela, alors vous n'aurez pas besoin d' constants que ces valeurs vont être explicite dans le code et le résultat dans un plus de cache amical binaire.
• Déballez votre Word128 valeurs.
• Définir votre propre plus pour Word128, ne soulevez Integer. Voir LargeWord pour un exemple de comment cela peut être fait.
• rem pas mod
• Compiler avec l'optimisation (-O2) et essayer de llvm (-fllvm)

EDIT: Et cabalize votre repo git avec un point de référence afin que nous puissions vous aider plus facilement ;-). Bon travail sur l'inclusion d'une crypto-api instance.

Answer 2

Le graphique du bas montre que beaucoup de mémoire est occupée par des listes. Moins il y a de plus caché dans d'autres modules, on ne peut venir e8. Peut-être que vous allez mordre la balle et faire une boucle au lieu d'un pli, mais pour commencer, depuis Block1024 est une paire, l' foldl' n'a pas beaucoup de l'évaluation à la volée (à moins que la rigueur de l'analyseur est devenu nettement mieux). Essayez de faire plus strictes, data Block1024 = B1024 !Block512 !Block512, peut-être qu'il a également besoin {-# UNPACK #-} pragmas. En roundFunction, utilisez rem au lieu de mod (ce qui ne ont peu d'impact, mais il est un peu plus rapide) et de faire de l' let liaisons stricte. Dans l' swapN fonctions, vous pourriez obtenir de meilleures performances en donnant les constantes de la forme W x y plutôt que de 128 bits, les nombres hexadécimaux. Je ne peux pas garantir ces changements aideront, mais c'est ce qui semble le plus prometteur après un bref coup d'œil.

Answer 3

Ok, donc j'ai pensé carillon avec une mise à jour de ce que j'ai fait et les résultats obtenus jusqu'à présent. Les modifications apportées:

• Commutation de la Matrice de UnboxedArray (fait Word128 un type d'instance)
• Utilisé UnboxedArray + pli en e8, au lieu de listes et (prélude) fois
• Utilisé unsafeIndex au lieu de !
• Changement du type de Block1024 à un réel de type de données (semblable à Block512), et déballe ses arguments
• Mise à jour de GHC à la version 7.2.1 sur Arch Linux, ce qui permet de corriger le problème à la compilation via C ou LLVM
• Commutation de mod à rem à certains endroits, mais PAS dans roundFunction. Quand je le fais il y, le temps de compilation soudain prend énormément de temps, et le temps d'exécution devient 10 fois plus lent! Personne ne sait pourquoi que, peut-être? C'est seulement avec GHC-7.2.1, pas de GHC-7.0.3

J'ai compiler avec les options suivantes:

ghc-7.2.1 --make-O2 -funbox-strict-champs principaux.sh ./Tests/testframe.hs-fvia-C -cifo-O2

Et les résultats? Près de 50 % de réduction dans le temps. Sur une entrée de ~107 MO, le code d'utilisation de 3 minutes par rapport à la précédente 6-7 minutes. La version C utilise 42 secondes.

Choses que j'ai essayé, mais qui n'a pas d'aboutir à de meilleures performances:

• Déroulé la e8 fonction comme ceci:

  e8 !h = h 0 go

  où aller !x !n

        | n == 42   = x
        | otherwise = go h' (n + 1)
        where !h' = roundFunction x n
  

• Essayé de diviser le swapN fonctions pour utiliser le sous-jacent Word64 " directement:

  swap1 (L xh hl) =

       shiftL (W (xh .&. 0x5555555555555555) (xl .&. 0x5555555555555555)) 1 
       .|. 
       shiftR (W (xh .&. 0xaaaaaaaaaaaaaaaa) (xl .&. 0xaaaaaaaaaaaaaaaa)) 1 
  

• Essayé d'utiliser le LLVM backend

Toutes ces tentatives ont donné de moins bonnes performances que ce que j'ai actuellement. Je ne sais pas si c'est parce que je suis en train de faire mal (surtout le déroulement de e8), ou simplement parce qu'ils ne sont pire des options.

Je n'ai encore quelques questions nouvelles avec ces nouveaux réglages.

1. Soudain, j'ai eu cette étrange bosse dans l'utilisation de la mémoire. Jetez un oeil à la suite de tas de profils:

   Pourquoi est-ce arrivé? C'est à cause de la UnboxedArray? Et ce n'SYSTÈME?

2. Quand je compile via C je reçois le message d'avertissement suivant:

   Avertissement: L'-fvia-C option ne fait rien; elle sera supprimée dans une future GHC libération

   Est-ce vrai? Pourquoi, alors, dois-je voir une meilleure performance de l'utiliser, plutôt que de ne pas?

Answer 4

Il semble que vous avez une bonne quantité de peaufinage déjà; je suis curieux de ce que la performance est sans explicites rigueur annotations (BangPatterns) et les différents compilateur pragmas (UNPACK, INLINE)... Aussi, une question stupide: ce que l'optimisation des drapeaux utilisez-vous?

De toute façon, deux suggestions qui peuvent être tout à fait terrible:

1. Utilisation unboxed types primitifs où vous pouvez (par exemple, remplacer Data.Word.Word64 avec GHC.Word.Word64#, assurez - word128Shift est à l'aide de Int#, etc.) pour éviter d'allocation de tas. C'est, bien sûr, les non-portable.
2. Essayez Data.Sequence au lieu de []

En tout cas, plutôt que de chercher au Cœur de sortie, essayer de regarder les intermédiaires C fichiers (*.hc) à la place. Il peut être difficile de passer à travers, mais parfois, rend évident le compilateur n'était pas tout à fait aussi forte que vous l'auriez espéré.