Question Maximiser les performances de la boucle Haskell avec GHC


Afin de comparer les performances avec les listes étant lent dans ce bug GHC J'essaie d'obtenir la boucle suivante aussi vite que possible:

{-# LANGUAGE BangPatterns #-}

module Main (main) where

import Control.Monad
import Data.Word


main :: IO ()
main = do
  loop (maxBound :: Word32) $ \i -> do
    when (i `rem` 100000000 == 0) $
      print (fromIntegral i / fromIntegral (maxBound :: Word32))


loop :: Word32 -> (Word32 -> IO ()) -> IO ()
loop n f = go 0
  where
    go !i | i == n = return ()
    go !i          = f i >> go (i + 1)

compilé avec ghc -O loop.hs.

Cependant, cela prend 50 secondes sur mon ordinateur - 10 fois plus lent que le programme C équivalent:

#include "limits.h"
#include "stdint.h"
#include "stdio.h"

int main(int argc, char const *argv[])
{
  for (uint32_t i = 0; i < UINT_MAX; ++i)
  {
    if (i % 100000000 == 0) printf("%f\n", (float) i / (float) UINT_MAX );
  }
  return 0;
}

compilé avec gcc -O2 -std=c99 -o testc test.c.


Utiliser le GHC 7.8 ou le -O2 n'a pas amélioré la performance.

Cependant, compiler avec le -fllvm flag (sur l'une ou l'autre version de ghc) a apporté un 10x amélioration de la vitesse, amenant la performance au même niveau que C.

Des questions:

  1. Pourquoi le codegen natif de GHC est-il beaucoup plus lent pour mon loop?
  2. Y a-t-il un moyen d'améliorer ma boucle pour qu'elle soit rapide aussi sans -fllvm, ou est-ce déjà la boucle IO la plus rapide Word32 on peut réaliser?

14
2018-04-26 18:35


origine


Réponses:


Inspectons l'assemblage. J'ai légèrement modifié la fonction principale pour que la sortie devienne un peu plus claire (mais la performance reste identique). J'ai utilisé GHC 7.8.2 avec -O2.

main :: IO ()
main = do
  loop (maxBound :: Word32) $ \i -> do
    when (i `rem` 100000000 == 0) $
      putStrLn "foo"

Il y a beaucoup de fouillis, alors j'essaie seulement d'inclure les parties intéressantes:

Native Codegen

Main_zdwa_info:
.Lc3JD: /* check if there's enough space for stack growth */
    leaq -16(%rbp),%rax
    cmpq %r15,%rax
    jb .Lc3JO /* this jumps to some GC code that grows the stack, then
                 reenters the main closure */
.Lc3JP:
    movl $4294967295,%eax /* issue: loading the bound on every iteration */
    cmpq %rax,%r14
    jne .Lc3JB
.Lc3JC:
   /* Return from main. Code omitted */
.Lc3JB: /* test the index for modulus */
    movl $100000000,%eax /* issue: unnecessary moves */
    movq %rax,%rbx      
    movq %r14,%rax
    xorq %rdx,%rdx
    divq %rbx /* issue: doing the division (llvm and gcc avoid this) */
    testq %rdx,%rdx
    jne .Lc3JU
.Lc3JV: 
   /* do the printing. Code omitted. */
.Lc3JN:
   /* increment index and (I guess) restore registers messed up by the printing */
    movq 8(%rbp),%rax
    incq %rax  
    movl %eax,%r14d
    addq $16,%rbp
    jmp Main_zdwa_info
.Lc3JU:
    leaq 1(%r14),%rax   /*issue: why not just increment r14? */
    movl %eax,%r14d     
    jmp Main_zdwa_info

LLVM

 Main_zdwa_info:
/* code omitted: the same stack-checking stuff as in native */
.LBB1_1:
    movl    $4294967295, %esi /* load the bound */
    movabsq $-6067343680855748867, %rdi /*load a magic number for the modulus */
    jmp .LBB1_2
.LBB1_4:              
    incl    %ecx
.LBB1_2:  
    cmpq    %rsi, %rcx
    je  .LBB1_6 /* check bound */

    /* do the modulus with two multiplications, a shift and a magic number */
    /* note : gcc does the same reduction */ 
    movq    %rcx, %rax
    mulq    %rdi
    shrq    $26, %rdx
    imulq   $100000000, %rdx, %rax  
    cmpq    %rax, %rcx
    jne .LBB1_4 
    /* Code omitted: print, then return to loop beginning */
.LBB1_6:                       
    /* Code omitted: return from main */

Observations

  • IO overhead est inexistant dans les deux assemblages. Le zéro octet RealWorld Le jeton d'état est visiblement absent.

  • Le code natif n'entraîne pas beaucoup de réduction de la force, contrairement à LLVM, qui convertit facilement le module en nombres de multiplication, de décalage et de nombres magiques.

  • Le code natif natif refait la vérification de l'espace de pile à chaque itération, contrairement à LLVM. Cela ne semble toutefois pas être un surcoût important.

  • Le code natif natif est tout simplement mauvais en ce qui concerne l'attribution de boucles et de registres. Il mélange autour des registres et charge la borne à chaque itération. LLVM émet un code comparable au code écrit à la main en ordre.

En ce qui concerne votre question:

Y a-t-il un moyen d'améliorer ma boucle pour qu'elle soit rapide aussi sans -fllvm, ou est-ce que c'est déjà la boucle IO la plus rapide sur Word32?

Le mieux que je puisse faire ici est la réduction de la force manuelle, je pense, bien que je trouve personnellement cette option inacceptable. Cependant, après cela, votre code sera encore nettement plus lent. J'ai également exécuté la boucle triviale suivante, et c'est deux fois plus rapide avec LLVM qu'avec natif:

import Data.Word
main = go 0 where
    go :: Word32 -> IO ()
    go i | i == maxBound = return ()
    go i = go (i + 1)

Le coupable est encore une fois inutile le brassage des registres et le chargement lié. Il n'y a pas vraiment de moyen de remédier à ce genre de problèmes de bas niveau, mis à part le passage à LLVM.


11
2018-04-27 10:32



Une optimisation facile serait d'utiliser Float division au lieu du défaut Double. Il suffit d'écrire une fonction pratique pour remplacer fromIntegral

w2f :: Word32 -> Float
w2f = fromIntegral

Cependant, il est beaucoup plus rapide pour calculer la boucle comme ceci:

main :: IO () 
main = forM_ [0, 100000000 .. mb] $ \i ->
    print (fromIntegral i / fromIntegral mb :: Float))
    where mb = maxBound :: Word32

0
2018-04-27 04:30