¿Por qué este programa Haskell es mucho más lento que uno equivalente de Python?

performance io

Question

Como parte de un desafío de programación, necesito leer, desde stdin, una secuencia de enteros separados por espacios ( en una sola línea ) e imprimir la suma de esos enteros a stdout. La secuencia en cuestión puede contener hasta 10,000,000 de enteros.

Tengo dos soluciones para esto: una escrita en Haskell ( foo.hs ), y otra, equivalente, escrita en Python 2 ( foo.py ). Lamentablemente, el programa (compilado) Haskell es consistentemente más lento que el programa Python, y no puedo explicar la discrepancia en el rendimiento entre los dos programas; vea la sección de referencia a continuación. En todo caso, hubiera esperado que Haskell tuviera la ventaja ...

¿Qué estoy haciendo mal? ¿Cómo puedo explicar esta discrepancia? ¿Hay alguna manera fácil de acelerar mi código Haskell?

(Para información, estoy usando un Macbook Pro de mediados de 2010 con 8 Gb de RAM, GHC 7.8.4 y Python 2.7.9).

foo.hs

main = print . sum =<< getIntList
getIntList :: IO [Int]
getIntList = fmap (map read . words) getLine

(compilado con ghc -O2 foo.hs )

foo.py

ns = map(int, raw_input().split())
print sum(ns)

Punto de referencia

A continuación, test.txt consta de una única línea de 10 millones de enteros separados por espacios.

# Haskell
$ time ./foo < test.txt
1679257
real 0m36.704s
user 0m35.932s
sys 0m0.632s
# Python
$ time python foo.py < test.txt
1679257
real 0m7.916s
user 0m7.756s
sys 0m0.151s

Answer 1

Me atrevería a adivinar que una gran parte de tu problema son las words . Cuando map read . words map read . words , lo que en realidad estás haciendo es esto:

1. Escanee la entrada buscando un espacio, construyendo una lista de espacios no a medida que avanza. Hay muchos tipos diferentes de espacios, y la comprobación de cualquier carácter que no sea un tipo común de espacio implica adicionalmente una llamada externa a una función C (lenta). Estoy planeando arreglar esto alguna vez, pero todavía no he llegado a eso, e incluso así estarás construyendo y tirando listas sin ninguna buena razón, y buscando espacios cuando realmente solo quieres verificar dígitos
2. Lea la lista de caracteres acumulados para tratar de hacer un número de ellos. Producir el número. La lista acumulada ahora se convierte en basura.
3. Regresa al paso 1.

Esta es una manera bastante ridícula de proceder. Creo que incluso puedes hacerlo mejor usando algo horrible como las reads , pero tendría más sentido usar algo como ReadP . También puedes probar tipos más geniales de cosas como el análisis basado en secuencias; No sé si eso ayudará mucho o no.

Answer 2

read es lento Para el análisis masivo, use bytestring o text primitives, o attoparsec .

Hice algunas evaluaciones comparativas. Su versión original se ejecutó en 23,9 segundos en mi computadora. La versión siguiente funciona en 0.35 segundos:

import qualified Data.ByteString.Char8 as B
import Control.Applicative
import Data.Maybe
import Data.List
import Data.Char
main = print . sum =<< getIntList
getIntList :: IO [Int]
getIntList =
map (fst . fromJust . B.readInt) . B.words <$> B.readFile "test.txt"

Al especializar el analizador en su archivo test.txt , pude obtener el tiempo de ejecución en 0.26 segundos:

getIntList :: IO [Int]
getIntList =
unfoldr (B.readInt . B.dropWhile (=='' '')) <$> B.readFile "test.txt"

Answer 3

Leer es lento

La lectura rápida, a partir de esta respuesta , le reducirá a 5,5 segundos.

import Numeric
fastRead :: String -> Int
fastRead s = case readDec s of [(n, "")] -> n

Las cadenas son listas vinculadas

En Haskell, el tipo de String es una lista enlazada. Usar una representación empaquetada ( bytestring si realmente solo quieres ascii pero Text también es muy rápido y admite unicode). Como se muestra en esta respuesta , el rendimiento debería ser el cuello y el cuello.