¿Por qué la entrada basada en [Char] es mucho más lenta que la salida basada en [Char] en Haskell?

Question

Es un conocimiento común que uno no usa [Char] para leer grandes cantidades de datos en Haskell. Uno usa ByteString s para hacer el trabajo. La explicación habitual para esto es que Char s son grandes y las listas añaden su sobrecarga.

Sin embargo, esto no parece causar ningún problema con la salida.

Por ejemplo, el siguiente programa:

main = interact $ const $ unwords $ map show $ replicate 500000 38000000 

tarda sólo 131 ms para funcionar en mi equipo, mientras que el siguiente:

import Data.List 

sum' :: [Int] -> Int 
sum' = foldl' (+) 0 

main = interact $ show . sum' . map read . words 

toma 3.38 segundos si se alimenta la salida del primer programa como una entrada!

¿Cuál es la razón de tal disparidad entre el rendimiento de entrada y salida usando String s?

Answer 1

No creo que este problema necesariamente tenga que ver con E/S. Más bien, demuestra que la instancia Read para Int es bastante ineficiente.

Primero, considere el siguiente programa que solo procesa una lista perezosa. Se necesita 4.1s en mi máquina (compilado con -O2):

main = print $ sum' $ map read $ words 
     $ unwords $ map show $ replicate 500000 38000000 

Sustitución de la función read con gotas length el tiempo hasta 0.48s:

main = print $ sum' $ map length $ words 
     $ unwords $ map show $ replicate 500000 38000000 

Por otra parte, la sustitución de la función read con un manuscrito versión resultados en un tiempo de 0.52s:

main = print $ sum' $ map myread $ words 
     $ unwords $ map show $ replicate 500000 38000000 

myread :: String -> Int 
myread = loop 0 
    where 
    loop n [] = n 
    loop n (d:ds) = let d' = fromEnum d - fromEnum '0' :: Int 
         n' = 10 * n + d' 
        in loop n' ds 

Mi conjetura en cuanto a por qué i read s tan ineficiente es que su implementación utiliza el módulo Text.ParserCombinators.ReadP, que puede no ser la opción más rápida para el caso simple de leer un solo entero.