在Haskell中高效解析ASCII文件

Question

我想重新用Haskell实现一些ASCII解析器，因为我认为这样可以提高速度。然而，即使是简单的“grep和计数”，也比粗糙的Python实现慢得多。

有人能解释一下为什么以及如何正确地做吗？

所以任务是，统计以字符串“foo”开头的行数。

我的非常基本的Python实现：

with open("foo.txt", 'r') as f:
    print len([line for line in f.readlines() if line.startswith('foo')])

以下是 Haskell 版本：

import System.IO 
import Data.List

countFoos :: String -> Int
countFoos str = length $ filter (isPrefixOf "foo") (lines str)

main = do
    contents <- readFile "foo.txt"
    putStr (show $ countFoos contents)

在我的MacBook Pro Retina 2015上（使用PCIe SSD），对于一个大小约为600MB，包含17001895行的文件，同时使用time命令运行，结果显示Python实现比Haskell实现快了近4倍。

> $ time ./FooCounter                                                           
1770./FooCounter  20.92s user 0.62s system 98% cpu 21.858 total

> $ time python foo_counter.py                                                   
1770
python foo_counter.py  5.19s user 1.01s system 97% cpu 6.332 total

与Unix命令行工具相比：

> $ time grep -c foo foo.txt                                                     
1770
grep -c foo foo.txt   4.87s user 0.10s system 99% cpu 4.972 total

> $ time fgrep -c foo foo.txt                                                     
1770
fgrep -c foo foo.txt  6.21s user 0.10s system 99% cpu 6.319 total

> $ time egrep -c foo foo.txt                                                     
1770
egrep -c foo foo.txt  6.21s user 0.11s system 99% cpu 6.317 total

有什么想法吗？

更新：

使用András Kovács的实现（ByteString），我将其缩短到不到半秒钟！

> $ time ./FooCounter                                                                                                               
1770
./EvtReader  0.47s user 0.48s system 97% cpu 0.964 total

- tamasgal

---

如果你还没有，请使用-O2编译。 - András Kovács

不要使用String。请改用ByteString或者（更可能的选择）Text。String类型很灵活，但几乎对任何操作都非常低效。 - MathematicalOrchid

@AndrásKovács，我忘记提到了，我已经使用-O2编译它了。 实际上，这没有任何区别:-\ 无论如何：谢谢 - tamasgal

@MathematicalOrchid 但是readFile的类型签名是readFile :: FilePath -> IO String，我该如何强制使用ByteString或Text？ - tamasgal

@septi 在 Data.Text.IO 中看一下。你会发现另一个返回 Text 的 readFile 函数。 - MathematicalOrchid

Answer 1

我对以下方案进行了基准测试：

{-# LANGUAGE OverloadedStrings #-}

import qualified Data.ByteString.Char8 as B

main =
  print . length . filter (B.isPrefixOf "foo") . B.lines =<< B.readFile "test.txt"

text.txt 是一个包含 800 万行的 170 MB 文件，其中一半的行以 "foo" 开头。我使用 GHC 7.10 编译，并加入了 -O2 -fllvm 标志。

使用严格的 ByteString 版本运行耗时0.27秒，而原始版本则需5.16秒。

然而，严格的 ByteString 版本需要加载整个文件，占用 170 MB 的内存。将导入改为 Data.ByteString.Lazy.Char8 后，运行时间为0.39秒，内存占用1 MB。

- András Kovács

---

哇，这太厉害了。用那个只用了不到半秒钟！ - tamasgal

这会把整个文件读入内存吗？因为我也需要解析大于10GB的文件... - tamasgal

是的，它加载了所有内容。请查看答案的编辑。 - András Kovács

Answer 2

您的 Haskell 版本使用类型 String 来表示文件的文本内容。 String 是 [Char] 的别名，它是一个字符的链表。这对于大字符串来说不是一个很好的表示。

请尝试使用 text 包代替。它将字符串表示为数组（在 Data.Text.* 模块中）或作为数组的链表（在 Data.Text.Lazy.* 模块中）。要移植现有代码，您可能希望使用后者，因为我猜您不想一次性将完整的 600MB 文件加载到内存中。在 Data.Text.Lazy 和 Data.Text.Lazy.IO 模块中查找您正在使用的 readFile、filter、isPrefixOf 等函数的变体。

如果您确定只需要支持 ASCII，则还可以考虑使用 bytestring 包代替 text 包。

- Toxaris