windows - Performance problem med Euler problem og rekursion på Int64 typer

Indlæg af Hanne Mølgaard Plasc

Problem



Jeg lærer nu Haskell ved hjælp af projektet Euler-problemer som min legeplads.
Jeg var forbløffet over, hvor langsomt mine Haskell-programmer viste sig at blive sammenlignet med lignende
programmer skrevet på andre sprog. Jeg undrer mig over, om jeg har forstået noget, eller hvis det er den slags præstationsstraffer man må forvente, når man bruger Haskell.


Følgende program inspireret af Problem 331, men jeg har ændret det før udstationering, så jeg spilder ikke noget for andre mennesker. Det beregner bue længden af ​​en diskret cirkel tegnet på et 2 ^ 30 x 2 ^ 30 gitter. Det er en simpel hale rekursiv implementering, og jeg sørger for, at opdateringerne af akkumuleringsvariablen, der holder styr på buenlængden, er strenge. Men det tager næsten et og et halvt minut at fuldføre (kompileret med -O flag med ghc).


import Data.Int

arcLength :: Int64->Int64
arcLength n = arcLength' 0 (n-1) 0 0 where
    arcLength' x y norm2 acc
        | x > y = acc
        | norm2 < 0 = arcLength' (x + 1) y (norm2 + 2*x +1) acc
        | norm2 > 2*(n-1) = arcLength' (x - 1) (y-1) (norm2 - 2*(x + y) + 2) acc
        | otherwise = arcLength' (x + 1) y (norm2 + 2*x + 1) $! (acc + 1)

main = print $ arcLength (2^30)


Her er en tilsvarende implementering i Java. Det tager cirka 4,5 sekunder at fuldføre.


public class ArcLength {
public static void main(String args[]) {
    long n = 1 << 30;
    long x = 0;
    long y = n-1;
    long acc = 0;
    long norm2 = 0;
    long time = System.currentTimeMillis();

    while(x <= y) {
        if (norm2 < 0) {
            norm2 += 2*x + 1;
            x++;
        } else if (norm2 > 2*(n-1)) {
            norm2 += 2 - 2*(x+y);
            x--;
            y--;
        } else {
            norm2 += 2*x + 1;
            x++;
            acc++;
        }
    }

    time = System.currentTimeMillis() - time;
    System.err.println(acc);
    System.err.println(time);
}


}


EDIT: Efter diskussionerne i kommentarerne lavede jeg nogle ændringer i Haskell-koden og gjorde nogle præstationsprøver. Først ændrede jeg n til 2 ^ 29 for at undgå overløb. Så forsøgte jeg 6 forskellige versioner: Med Int64 eller Int og med bangs før enten norm2 eller begge og norm2 og acc i erklæringen arcLength' x y !norm2 !acc. Alle er kompileret med


ghc -O3 -prof -rtsopts -fforce-recomp -XBangPatterns arctest.hs


Her er resultaterne:


(Int !norm2 !acc)
total time  =        3.00 secs   (150 ticks @ 20 ms)
total alloc =       2,892 bytes  (excludes profiling overheads)

(Int norm2 !acc)
total time  =        3.56 secs   (178 ticks @ 20 ms)
total alloc =       2,892 bytes  (excludes profiling overheads)

(Int norm2 acc)
total time  =        3.56 secs   (178 ticks @ 20 ms)
total alloc =       2,892 bytes  (excludes profiling overheads)

(Int64 norm2 acc)
arctest.exe: out of memory

(Int64 norm2 !acc)
total time  =       48.46 secs   (2423 ticks @ 20 ms)
total alloc = 26,246,173,228 bytes  (excludes profiling overheads)

(Int64 !norm2 !acc)
total time  =       31.46 secs   (1573 ticks @ 20 ms)
total alloc =       3,032 bytes  (excludes profiling overheads)


Jeg bruger GHC 7.0.2 under en 64-bit Windows 7 (Haskell-platformens binære distribution). Ifølge kommentarerne forekommer problemet ikke, når der kompileres under andre konfigurationer. Det får mig til at tro, at Int64-typen er brudt i Windows-udgivelsen.

Bedste reference


Hm, jeg installerede en frisk Haskell platform med 7.0.3, og få omtrent følgende kerne til dit program (-ddump-simpl):


Main.$warcLength' =
   (ww\_s1my :: GHC.Prim.Int64#) (ww1\_s1mC :: GHC.Prim.Int64#)
    (ww2\_s1mG :: GHC.Prim.Int64#) (ww3\_s1mK :: GHC.Prim.Int64#) ->
    case {\_\_pkg\_ccall ghc-prim hs\_gtInt64 [...]
           ww\_s1my ww1\_s1mC GHC.Prim.realWorld#
[...]


Så GHC har indset, at det kan udpakke dine heltal, hvilket er godt. Men denne hs\_getInt64 opkald ser mistænkeligt ud som et C-opkald. Se på assembler output (-ddump-asm), vi ser ting som:


pushl \%eax
movl 76(\%esp),\%eax
pushl \%eax
call \_hs\_gtInt64
addl $16,\%esp


Så det ser meget ud som om hver operation på Int64 bliver omdannet til et fuldt blæst C-opkald i backend. Hvilket er langsomt , selvfølgelig.


Kildekoden til GHC.IntWord64 ser ud til at bekræfte, at: I en 32-bit-bygning (som den, der for øjeblikket er leveret med platformen), vil du kun få emulering via FFI-grænsefladen. [43]

Andre referencer 1


Hmm, det er interessant. Så jeg har kun lavet begge dine programmer og prøvet dem:


\% java -version                                                                                          
java version "1.6.0\_18"
OpenJDK Runtime Environment (IcedTea6 1.8.7) (6b18-1.8.7-2~squeeze1)
OpenJDK 64-Bit Server VM (build 14.0-b16, mixed mode)
\% javac ArcLength.java                                                                                   
\% java ArcLength                                                                                         
843298604
6630


ca. 6,6 sekunder for Java-løsningen . Næste er ghc med en vis optimering:


\% ghc --version                                                                                          
The Glorious Glasgow Haskell Compilation System, version 6.12.1
\% ghc --make -O arc.hs
\% time ./arc                                                                                             
843298604
./arc  12.68s user 0.04s system 99\% cpu 12.718 total


Lige under 13 sekunder for ghc -O


Forsøger med yderligere optimering:


\% ghc --make -O3
\% time ./arc                                                                                             [13:16]
843298604
./arc  5.75s user 0.00s system 99\% cpu 5.754 total


Med yderligere optimeringsflagger tog iskelløsningen under 6 sekunder


Det ville være interessant at vide, hvilken version kompilator du bruger.

Andre referencer 2


Der er et par interessante ting i dit spørgsmål.


Du skal bruge -O2 primært. Det vil bare gøre et bedre arbejde (i dette tilfælde identificere og fjerne dovenskab, der stadig var til stede i versionen -O.


For det andet er din Haskell ikke helt den samme som Java (det gør forskellige tests og grene). Som med andre, kører din kode på min Linux-boks i omkring 6s runtime. Det virker fint.


Sørg for, at det er det samme som Java


En ide: Lad os lave en bogstavelig transkription af java med samme kontrolflow, operationer og typer.


import Data.Bits
import Data.Int

loop :: Int -> Int
loop n = go 0 (n-1) 0 0
    where
        go :: Int -> Int -> Int -> Int -> Int
        go x y acc norm2
            | x <= y        = case () of { \_
                | norm2 < 0         -> go (x+1) y     acc     (norm2 + 2*x + 1)
                | norm2 > 2 * (n-1) -> go (x-1) (y-1) acc     (norm2 + 2 - 2 * (x+y))
                | otherwise         -> go (x+1) y     (acc+1) (norm2 + 2*x + 1)
            }
            | otherwise     = acc

main = print $ loop (1 `shiftL` 30)


Kig i kerne


Vi tager et hurtigt kig på kernen ved hjælp af ghc-core, og det viser en meget flot loop af uboksetype: [44]


main\_$s$wgo
  :: Int#
     -> Int#
     -> Int#
     -> Int#
     -> Int#

main\_$s$wgo =
   (sc\_sQa :: Int#)
    (sc1\_sQb :: Int#)
    (sc2\_sQc :: Int#)
    (sc3\_sQd :: Int#) ->
    case <=# sc3\_sQd sc2\_sQc of \_ {
      False -> sc1\_sQb;
      True ->
        case <# sc\_sQa 0 of \_ {
          False ->
            case ># sc\_sQa 2147483646 of \_ {
              False ->
                main\_$s$wgo
                  (+# (+# sc\_sQa (*# 2 sc3\_sQd)) 1)
                  (+# sc1\_sQb 1)
                  sc2\_sQc
                      (+# sc3\_sQd 1);
              True ->
                main\_$s$wgo
                  (-#
                     (+# sc\_sQa 2)
                     (*# 2 (+# sc3\_sQd sc2\_sQc)))
                  sc1\_sQb
                  (-# sc2\_sQc 1)
                  (-# sc3\_sQd 1)
            };
          True ->
            main\_$s$wgo
              (+# (+# sc\_sQa (*# 2 sc3\_sQd)) 1)
              sc1\_sQb
              sc2\_sQc
              (+# sc3\_sQd 1)


det vil sige alt ubokset i registre. Denne sløjfe ser godt ud!


Og fungerer fint (Linux/x86-64/GHC 7.03):


./A  5.95s user 0.01s system 99\% cpu 5.980 total


Kontrollerer asm


Vi får også rimelig samling som en god løkke:


Main\_mainzuzdszdwgo\_info:
        cmpq    \%rdi, \%r8
        jg      .L8
.L3:
        testq   \%r14, \%r14
        movq    \%r14, \%rdx
        js      .L4
        cmpq    $2147483646, \%r14
        jle     .L9
.L5:
        leaq    (\%rdi,\%r8), \%r10
        addq    $2, \%rdx
        leaq    -1(\%rdi), \%rdi
        addq    \%r10, \%r10
        movq    \%rdx, \%r14
        leaq    -1(\%r8), \%r8
        subq    \%r10, \%r14
        jmp     Main\_mainzuzdszdwgo\_info
.L9:
        leaq    1(\%r14,\%r8,2), \%r14
        addq    $1, \%rsi
        leaq    1(\%r8), \%r8
        jmp     Main\_mainzuzdszdwgo\_info
.L8:
        movq    \%rsi, \%rbx
        jmp     *0(\%rbp)
.L4:
        leaq    1(\%r14,\%r8,2), \%r14
        leaq    1(\%r8), \%r8
        jmp     Main\_mainzuzdszdwgo\_info


Brug af -fvia-C backend.


Så det ser fint ud!





Min mistænkning, som nævnt i kommentaren ovenfor, har noget at gøre med den version af libgmp du har på 32 bit Windows, der genererer dårlig kode til 64 bit ints. Forsøg først at opgradere til GHC 7.0.3, og prøv derefter nogle af de andre kodegeneratorbaggrunde, så hvis du stadig har et problem med Int64, skal du sende en fejlrapport til GHC trac.


I vid udstrækning bekræfter, at det faktisk er omkostningerne ved at foretage disse C-opkald i 32 bit-emuleringen af ​​64 bit ints, kan vi erstatte Int64 med Integer, som implementeres med C-opkald til GMP på hver maskine, og faktisk går runtime fra 3'erne til godt over et minut.


Lektion: Brug hardware 64 bits, hvis det overhovedet er muligt.

Andre referencer 3


Det normale optimeringsflag for den pågældende kode er -O2. Hvad du brugte, -O, gør meget lidt. -O3 gør ikke meget (nogen?) Mere end -O2 - det plejede endda at omfatte eksperimentelle 'optimeringer', der ofte gjorde programmer særligt langsommere.


Med -O2 får jeg ydeevne konkurrencedygtig med Java:


tommd@Mavlo:Test$ uname -r -m
2.6.37 x86\_64
tommd@Mavlo:Test$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.0.3

tommd@Mavlo:Test$ ghc -O2 so.hs
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
tommd@Mavlo:Test$ time ./so
843298604

real    0m4.948s
user    0m4.896s
sys     0m0.000s


Og Java er ca. 1 sekund hurtigere (20\%):


tommd@Mavlo:Test$ time java ArcLength
843298604
3880

real    0m3.961s
user    0m3.936s
sys     0m0.024s


Men en interessant ting om GHC er, at den har mange forskellige backends. Som standard bruger den native code generator (NCG), som vi timed over. Der er også en LLVM backend, der ofte gør det bedre ... men ikke her:


tommd@Mavlo:Test$ ghc -O2 so.hs -fllvm -fforce-recomp
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
tommd@Mavlo:Test$ time ./so
843298604

real    0m5.973s
user    0m5.968s
sys     0m0.000s


Men som FUZxxl nævnt i kommentarerne gør LLVM meget bedre, når du tilføjer et par strengeanbefalinger:


$ ghc -O2 -fllvm -fforce-recomp so.hs
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
tommd@Mavlo:Test$ time ./so
843298604

real    0m4.099s
user    0m4.088s
sys     0m0.000s


Der er også en gammel 'via-c' generator, der bruger C som et mellemsprog. Det gør det godt i dette tilfælde:


tommd@Mavlo:Test$ ghc -O2 so.hs -fvia-c -fforce-recomp
[1 of 1] Compiling Main             ( so.hs, so.o )

on the commandline:
    Warning: The -fvia-c flag will be removed in a future GHC release
Linking so ...
ttommd@Mavlo:Test$ ti
tommd@Mavlo:Test$ time ./so
843298604

real    0m3.982s
user    0m3.972s
sys     0m0.000s


Forhåbentlig bliver NCG forbedret for at matche via-c for denne sag, før de fjerner denne backend.

Andre referencer 4


dberg, jeg føler, at alt dette kom til en dårlig start med det uheldige -O flag. Bare for at understrege et punkt, der er lavet af andre, for løbskompilering og testning, kan du lide mig og indsætte dette i din .bashrc eller hvad som helst:


alias ggg="ghc --make -O2"
alias gggg="echo 'Glorious Glasgow for Great Good!' && ghc --make -O2 --fforce-recomp"

Andre referencer 5


Jeg har spillet med koden lidt, og denne version ser ud til at køre hurtigere end Java-versionen på min bærbare computer (3.55s vs 4.63s):


{-# LANGUAGE BangPatterns #-}

arcLength :: Int->Int
arcLength n = arcLength' 0 (n-1) 0 0 where
    arcLength' :: Int -> Int -> Int -> Int -> Int
    arcLength' !x !y !norm2 !acc
        | x > y = acc
        | norm2 > 2*(n-1) = arcLength' (x - 1) (y - 1) (norm2 - 2*(x + y) + 2) acc
        | norm2 < 0 = arcLength' (succ x) y (norm2 + x*2 + 1) acc
        | otherwise = arcLength' (succ x) y (norm2 + 2*x + 1) (acc + 1)      

main = print $ arcLength (2^30)


:


$ ghc -O2 tmp1.hs -fforce-recomp
[1 of 1] Compiling Main             ( tmp1.hs, tmp1.o )
Linking tmp1 ...

$ time ./tmp1
843298604

real    0m3.553s
user    0m3.539s
sys 0m0.006s