windows - Problema de rendimiento con problema de Euler y recursión en tipos Int64

performance haskell

Question

Actualmente estoy aprendiendo a Haskell usando el proyecto de problemas de Euler como mi patio de recreo. Me sorprendió lo lento que resultaron mis programas Haskell comparados con programas similares escritos en otros idiomas. Me pregunto si he visto algo, o si este es el tipo de penalizaciones de rendimiento que uno debe esperar al usar Haskell.

El siguiente programa está inspirado en el problema 331, pero lo cambié antes de publicarlo, así que no arruino nada para otras personas. Calcula la longitud del arco de un círculo discreto dibujado en una cuadrícula de 2 ^ 30 x 2 ^ 30. Es una implementación recursiva de cola simple y me aseguro de que las actualizaciones de la variable de acumulación que siguen la longitud del arco sean estrictas. Sin embargo, lleva casi un minuto y medio completarlo (compilado con la bandera -O con 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)

Aquí hay una implementación correspondiente en Java. Tarda unos 4.5 segundos en completarse.

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);
}

}

EDITAR: Después de las discusiones en los comentarios hice algunas modificaciones en el código Haskell e hice algunas pruebas de rendimiento. Primero cambié n a 2 ^ 29 para evitar desbordamientos. Luego probé 6 versiones diferentes: con Int64 o Int y con bangs antes de norm2 o ambos y norm2 y acc en la declaración arcLength'' xy !norm2 !acc . Todos están compilados con

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

Aquí están los resultados:

(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)

Estoy usando GHC 7.0.2 en un Windows 7 de 64 bits (distribución binaria de la plataforma Haskell). Según los comentarios, el problema no ocurre al compilar en otras configuraciones. Esto me hace pensar que el tipo Int64 está roto en la versión de Windows.

Answer 1

El indicador de optimización normal para el código relacionado con el rendimiento es -O2 . Lo que -O , -O , hace muy poco. -O3 no hace mucho (¿alguna?) Más de -O2 - incluso solía incluir "optimizaciones" experimentales que a menudo hacían los programas notablemente más lentos.

Con -O2 obtengo un rendimiento competitivo con 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

Y Java es aproximadamente 1 segundo más rápido (20%):

tommd@Mavlo:Test$ time java ArcLength
843298604
3880
real 0m3.961s
user 0m3.936s
sys 0m0.024s

Pero una cosa interesante sobre GHC es que tiene muchos backends diferentes. Por defecto, utiliza el generador de código nativo (NCG), que hemos cronometrado anteriormente. También hay un backend LLVM que a menudo funciona mejor ... pero no aquí:

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

Pero, como FUZxxl mencionó en los comentarios, LLVM lo hace mucho mejor cuando agrega algunas anotaciones de rigor:

$ 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

También hay un viejo generador de "via-c" que usa C como lenguaje intermedio. Lo hace bien en este caso:

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

Esperemos que el NCG se mejore para que coincida con via-c en este caso antes de que eliminen este back-end.

Answer 2

Hay un par de cosas interesantes en tu pregunta.

Deberías usar -O2 principalmente. Simplemente hará un mejor trabajo (en este caso, identificando y eliminando la pereza que todavía estaba presente en la versión -O ).

En segundo lugar, su Haskell no es lo mismo que Java (realiza diferentes pruebas y ramas). Al igual que con otros, ejecutar su código en mi cuadro de Linux da como resultado un tiempo de ejecución de alrededor de 6 segundos. Parece bien

Asegúrate de que sea lo mismo que Java

Una idea: hagamos una transcripción literal de su Java, con el mismo flujo de control, operaciones y tipos.

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)

Echar un vistazo al núcleo

ghc-core un vistazo rápido al Núcleo, usando ghc-core , y mostrará un muy buen bucle de tipo sin caja:

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)

es decir, todo unboxed en registros. ¡Ese lazo se ve genial!

Y funciona bien (Linux / x86-64 / GHC 7.03):

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

Comprobando el asm

Obtenemos un montaje razonable también, como un buen bucle:

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

Usando el backend -fvia-C .

¡Así que esto se ve bien!

Mi sospecha, como se menciona en el comentario anterior, tiene que ver con la versión de libgmp que tienes en Windows de 32 bits que genera código deficiente para libgmp de 64 bits. Primero intente actualizar a GHC 7.0.3, y luego intente con algunos de los otros backends del generador de código; luego, si todavía tiene un problema con Int64 , presente un informe de error al trac de GHC.

Confirmando ampliamente que de hecho es el costo de hacer esas llamadas C en la emulación de 32 bits de 64 bits, podemos reemplazar Int64 con Integer , que se implementa con llamadas C a GMP en cada máquina, y de hecho, el tiempo de ejecución va de 3s a más de un minuto.

Lección: use hardware de 64 bits si es posible.

Answer 3

He jugado un poco con el código y esta versión parece ejecutarse más rápido que la versión de Java en mi computadora portátil (3.55 vs 4.63):

{-# 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

Answer 4

Hm, instalé una nueva plataforma Haskell con 7.0.3, y -ddump-simpl aproximadamente el siguiente núcleo para tu programa ( -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#
[...]

Entonces GHC se dio cuenta de que puede descomprimir sus enteros, lo cual es bueno. Pero esta llamada hs_getInt64 parece sospechosamente a una llamada C. Mirando la salida del ensamblador ( -ddump-asm ), vemos cosas como:

pushl %eax
movl 76(%esp),%eax
pushl %eax
call _hs_gtInt64
addl $16,%esp

Así que esto se parece mucho a que cada operación en el Int64 se convierta en una Int64 llamada C en el back-end. Lo cual es lento , obviamente.

El código fuente de GHC.IntWord64 parece verificar que: en una compilación de 32 bits (como la que se envía actualmente con la plataforma), solo tendrá emulación a través de la interfaz FFI.

Answer 5

Hmm, esto es interesante. Así que compilé ambos programas y los probé:

% 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

Entonces alrededor de 6.6 segundos para la solución de Java . El siguiente es ghc con alguna optimización:

% 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

Poco menos de 13 segundos para ghc -O

Probando con una mayor optimización:

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

Con más indicadores de optimización, la solución de Haskell tomó menos de 6 segundos

Sería interesante saber qué compilador de versión está utilizando.

Answer 6

dberg , siento que todo esto tuvo un mal comienzo con la desafortunada -O bandera. Solo para enfatizar un punto hecho por otros, para la compilación y las pruebas ordinarias, hágalo como yo y pegue esto en su .bashrc o lo que sea:

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