¿Por qué este simple programa de análisis de texto es tan lento?

Question

Este es mi código para el conteo de líneas y palabras:

import System.IO 
import Data.List 
main = do 
     hSetBinaryMode stdin True 
     interact $ (\(w,l)->"line:"++(show l)++"\nwords:"++(show w)++"\n") 
        . foldl' (\(w,l) r-> w `seq` l `seq` (w+length r ,succ l)) (0,0) 
        . lines 

Esto tarda unos 10 segundos para ejecutarse en un archivo de alrededor de 100 megabytes. Lo comparé con programas similares en Lua (9s), awk (20s) y wc -l -c (0.6s).

¿Por qué este código es tan lento? ¿Cual podría ser el problema?

Answer 1

Se sabe que la E/S con String es menos que rápida en Haskell. Los bytes leídos desde el identificador en general tienen que convertirse en puntos de código Unicode, y luego se genera una lista vinculada a partir de ellos. Eso es mucho trabajo causando mucha asignación. En este caso, la conversión a puntos de código es un poco más simple, ya que establece stdin en modo binario, pero la construcción de la lista de caracteres vinculada aún lleva mucho tiempo.

Otro pequeño factor es que el recuento de líneas está usando Integer, pero eso es menor y solo juega un papel importante cuando las E/S son correctas.

Si necesita E/S rápidas, tiene que usar un tipo más adecuado para eso. Una posibilidad es usar ByteString, por ejemplo

import Data.List 
import qualified Data.ByteString.Lazy.Char8 as C 
main = do 
     txt <- C.getContents 
     putStrLn $ (\(w,l)->"line:"++(show l)++"\nwords:"++(show w)++"\n"). foldl' (\(w,l) r-> w `seq` l `seq` (w+C.length r ,succ l)) (0,0) . C.lines $ txt 

hace el trabajo en un archivo de 94 MB en 0,12 s en mi caja (wc -l -c toma 0.06s), mientras que el original usando String tomó 4.4s. Puede ser aún más optimizado,

{-# LANGUAGE BangPatterns #-} 
import Data.List 
import qualified Data.ByteString.Lazy.Char8 as C 
main = do 
     txt <- C.getContents 
     putStrLn $ (\(w,l)->"line:"++(show l)++"\nwords:"++(show w)++"\n"). loop 0 0 . C.lines $ txt 

loop :: Int -> Int -> [C.ByteString] -> (Int,Int) 
loop !w !l (ln:lns) = loop (w + fromIntegral (C.length ln)) (l+1) lns 
loop w l _ = (w,l) 

tarda sólo 0.08s, que es lo suficientemente digno para que deje de optimización de allí (un cambio similar para la versión String trae el tiempo hasta 3.6s para eso).