Почему вход на основе [Char] намного медленнее, чем на выходе [Char] в Haskell?

Question

Общеизвестно, что никто не использует [Char] для чтения больших объемов данных в Haskell. Один использует ByteString s, чтобы сделать работу. Обычным объяснением этого является то, что Char s большие и списки добавляют свои накладные расходы.

Однако, похоже, это не вызывает проблем с выводом.

Например, следующая программа:

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

требуется всего 131 мс для запуска на моем компьютере, в то время как следующее:

import Data.List

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

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

занимает 3,38 секунды, если в качестве входа используется выход первой программы!

В чем причина такого несоответствия между входной и выходной характеристиками при использовании String с?

Answer 1

Я не думаю, что эта проблема обязательно связана с вводом / выводом.Скорее, это демонстрирует, что экземпляр Read для Int довольно неэффективен.

Сначала рассмотрим следующую программу, которая просто обрабатывает отложенный список.На моем компьютере требуется 4,1 с (скомпилировано с -O2):

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

Замена функции read на length уменьшает время до 0,48 с:

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

Кроме того, замена функции read на рукописную версию приводит к времени 0,52 с:

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

Я думаю, почему read настолько неэффективен, что его реализация использует Text.ParserCombinators.ReadPмодуль, который может оказаться не самым быстрым выбором для простого случая чтения одного целого числа.