我优化多年的C语言竟然被80行Haskell打败了？

本文并没有说Haskell比C“好”&＃xff0c;也不会讨论任何一种语言的相对价值&＃xff0c;更不会讨论它们的实现——本文只是简单地探索了高性能Haskell&＃xff0c;同时尝试了一些有趣的技巧而已。

作者 | Chris Penner

译者 | 弯月&＃xff0c;责编 | 郭芮

出品 | CSDN&＃xff08;ID&＃xff1a;CSDNnews&＃xff09;

尽管题目有些标题党&＃xff0c;但我仍希望这篇文章能够对你有所启发&＃xff0c;至少是一篇有意思的文章&＃xff01;本文并没有说Haskell比C“好”&＃xff0c;也不会讨论任何一种语言的相对价值&＃xff0c;更不会讨论它们的实现。本文只是简单地探索了高性能Haskell&＃xff0c;同时尝试了一些有趣的技巧而已。

点击这里可以下载本文的源代码&＃xff08;https://github.com/ChrisPenner/wc&＃xff09;。

作为参考&＃xff0c;我使用的是Mac版的wc&＃xff1b;其参考源代码在此&＃xff08;https://opensource.apple.com/source/text_cmds/text_cmds-68/wc/wc.c.auto.html&＃xff09;。没错&＃xff0c;其实还有更快的wc实现。

我们的问题是&＃xff0c;利用我们喜欢的某种支持垃圾回收、基于运行时的高级语言——Haskell&＃xff0c;编写一个wc工具&＃xff0c;它要比手工优化过的C实现更快。听起来很简单&＃xff0c;是吧&＃xff1f;

下面是该任务的条件&＃xff1a;

这些是我们需要关心的主要问题。

下面让我们开始吧。

与往常一样&＃xff0c;我们应该从最笨的实现开始&＃xff0c;看看情况如何&＃xff0c;然后再以此为起点继续前进。那么&＃xff0c;用Haskell统计字符数、单词数和行数的最笨的方法是什么&＃xff1f;我们可以读入文件&＃xff0c;然后运行length、length . words和length . lines来获得计数。

1stupid :: FilePath -> IO (Int, Int, Int)
2stupid fp &＃61; do
3    contents <- readFile fp
4    return (length s, length (words s), length (lines s))


90MB的测试文件

嗯……不用我说你也知道&＃xff0c;改进的空间非常大……

我们来看看为什么上述代码的性能如此差。

首先&＃xff0c;我们遍历了三遍整个文件内容&＃xff01;这也意味着&＃xff0c;在遍历过程中&＃xff0c;GHC不能对列表进行垃圾回收&＃xff0c;因为在其他地方依然要用到该列表。结果就是&＃xff0c;文件中的每个字符都在链表里存储下来&＃xff0c;这也是为什么仅有90MB的文件占据了2.4GB内存的原因&＃xff01;哎呦&＃xff01;

好吧&＃xff0c;这个方法实在是不怎么样&＃xff0c;我们来看看如果只遍历一次会怎样。我们只需要累加三个数字&＃xff0c;所以也许可以同时处理它们&＃xff1f;遍历列表获得最终结果&＃xff0c;很自然地我想到了fold操作&＃xff01;

用fold来统计字符数或行数非常容易&＃xff1a;遇到一个字符给合计值加1&＃xff0c;当前字符为新行时给行计数加1&＃xff0c;那单词数怎么办&＃xff1f;我们无法简单地在遇到空格时加1&＃xff0c;因为连续的空给不应该算作一个新单词&＃xff01;我们需要跟踪前一个字符是否为空格&＃xff0c;只有当开始一个新单词时才给计数器加1。这并不难实现&＃xff0c;下面的实现使用了Data.List中的foldl&＃39;&＃xff1a;

1import Data.List2import Data.Char34simpleFold :: FilePath -> IO (Int, Int, Int)5simpleFold fp &＃61; do6    countFile <$> readFile fp78countFile :: String -> (Int, Int, Int)9countFile s &＃61;
10    let (cs, ws, ls, _) &＃61; foldl&＃39; go (0, 0, 0, False) s
11     in (cs, ws, ls)
12  where
13    go :: (Int, Int, Int, Bool) -> Char -> (Int, Int, Int, Bool)
14    go (cs, ws, ls, wasSpace) c &＃61;
15        let addLine | c &＃61;&＃61; &＃39;\n&＃39; &＃61; 1
16                    | otherwise &＃61; 0
17            addWord | wasSpace &＃61; 0
18                    | isSpace c &＃61; 1
19                    | otherwise &＃61; 0
20         in (cs &＃43; 1, ws &＃43; addWord, ls &＃43; addLine, isSpace c)


90MB测试文件

改正这一点只需告诉GHC在每次遍历时对内容进行严格求值。最容易的方法就是利用BangPatterns扩展&＃xff0c;我们可以在参数列表中用 ! 来强迫在每次函数执行时进行求值。下面是新版本的go&＃xff1a;

1{-# LANGUAGE BangPatterns #-}23...4    go :: (Int, Int, Int, Bool) -> Char -> (Int, Int, Int, Bool)5    go (!cs, !ws, !ls, !wasSpace) c &＃61;6        let addLine | c &＃61;&＃61; &＃39;\n&＃39; &＃61; 17                    | otherwise &＃61; 08            addWord | wasSpace &＃61; 09                    | isSpace c &＃61; 1
10                    | otherwise &＃61; 0
11         in (cs &＃43; 1, ws &＃43; addWord, ls &＃43; addLine, isSpace c)


好&＃xff0c;现在内存方面已经好很多了&＃xff0c;90MB文件只需要使用几个MB的内存&＃xff0c;意味着文件内容是以流的形式处理的&＃xff01;即使仍然有懒惰求值的坑&＃xff0c;但我们把懒惰限制在了正确的局部位置&＃xff0c;因此它自然地带来了流式处理&＃xff01;流式处理的原因是&＃xff0c;readFile实际上是懒惰IO&＃xff0c;有时候对于Web服务器等情况而言&＃xff0c;这种方式是非常自然的&＃xff0c;因为你永远无法确定IO何时发生&＃xff0c;而在我们的例子中&＃xff0c;它带来了非常好的内存占用量。

暂时我们可以不用考虑内存了&＃xff0c;那么回过头来考虑一下性能问题&＃xff01;我能想到的一种方案就是用ByteString取代String。使用String意味着我们在读取文件时隐含地进行了解码&＃xff0c;这需要花费时间&＃xff0c;而且对一切都使用链表也会造成额外开销。这样做并不能从批量读取或缓冲中得到任何好处。

修改方式实际上非常简单。bytestring包提供了一个模块&＃xff1a;Data.ByteString.Lazy.Char8&＃xff0c;它提供了一系列操作&＃xff0c;可以将懒惰的ByteString当作由字符组成的字符串来处理&＃xff0c;同时依然保留ByteString带来的性能优势。注意&＃xff0c;它并不会验证每个字节是否为有效的Character&＃xff0c;也不会做任何解码&＃xff0c;所以我们需要自行保证传递正确的数据给它。默认情况下wc假设输入为ASCII&＃xff0c;所以这里我们也可以安全地这样假设。如果输入是ASCII&＃xff0c;那么该模块中的函数就非常合理了。

唯一的改动就是将Data.List的导入改成Data.ByteString.Lazy.Char8&＃xff0c;然后将readFile和foldl&＃39;函数改成相应的ByteString版本&＃xff1a;

1import Data.Char2import qualified Data.ByteString.Lazy.Char8 as BS34simpleFold :: FilePath -> IO (Int, Int, Int)5simpleFold fp &＃61; do6    simpleFoldCountFile <$> BS.readFile fp78simpleFoldCountFile :: BS.ByteString -> (Int, Int, Int)9simpleFoldCountFile s &＃61;
10    let (cs, ws, ls, _) &＃61; BS.foldl&＃39; go (0, 0, 0, False) s
11     in (cs, ws, ls)
12  where
13    go :: (Int, Int, Int, Bool) -> Char -> (Int, Int, Int, Bool)
14    go (!cs, !ws, !ls, !wasSpace) c &＃61;
15        let addLine | c &＃61;&＃61; &＃39;\n&＃39; &＃61; 1
16                    | otherwise &＃61; 0
17            addWord | wasSpace &＃61; 0
18                    | isSpace c &＃61; 1
19                    | otherwise &＃61; 0
20         in (cs &＃43; 1, ws &＃43; addWord, ls &＃43; addLine, isSpace c)


显然我们有了一些进展。内存使用量略微增加&＃xff0c;但额外的开销似乎依然是常量级别。不幸的是&＃xff0c;我们比wc依然低了几个数量级。我们来看看还能做什么。

这里我想做一点小实验。现代的电脑通常有多个核心&＃xff0c;而且新的电脑似乎核心数量增长要比处理器速度增长还要快&＃xff0c;所以利用好这一点肯定会有优势。

但是&＃xff0c;像这种拆分计算的工作并不太容易。为了使用多个核心&＃xff0c;我们需要将任务分解成小块。理论上很容易&＃xff0c;只需将文件拆分成小块&＃xff0c;然后将每个小块分配给一个核心即可&＃xff01;但仔细想想就会发现问题&＃xff1a;合并字符计数非常容易&＃xff0c;只需计算每块计数的总和即可。行数也一样&＃xff0c;但单词数就有问题了&＃xff01;如果在某个单词中间拆分&＃xff0c;或者在连续的空格之间拆分会怎样&＃xff1f;为了合并单词计数&＃xff0c;我们需要跟踪每块的开头和结尾的状态&＃xff0c;合并时需要考虑这些问题。我可不想做这些记录的工作。

这时就轮到幺半群出场了&＃xff01;幺半群的结合律意味着&＃xff0c;我们可以设计一个合法的幺半群&＃xff0c;能在这种并行处理的情况下正确工作。但是&＃xff0c;真的能写一个幺半群来处理类似单词数统计这种复杂的任务吗&＃xff1f;

当然可以&＃xff01;一眼看上去似乎这种情况并不适合使用幺半群&＃xff0c;但一系列计数问题都可以归到同一个类别下&＃xff0c;很幸运的是我以前做过类似的问题。简单来说&＃xff0c;我们需要统计一个序列从头到尾的过程中&＃xff0c;某个不变量改变的次数。我以前曾经做过这类幺半群的通用形式&＃xff0c;叫做flux幺半群&＃xff08;http://hackage.haskell.org/package/flux-monoid&＃xff09;。我们需要做的就是&＃xff0c;统计字符从空格变成非空格的次数。我们可以利用Flux幺半群来表示它&＃xff0c;但由于我们需要谨慎地处理严格性和性能&＃xff0c;所以我要为这里的问题定义一个特殊的Flux幺半群。看下面&＃xff1a;

1data CharType &＃61; IsSpace | NotSpace
2    deriving Show
3
4data Flux &＃61;
5    Flux !CharType
6         {-# UNPACK #-} !Int
7         !CharType
8    | Unknown
9    deriving Show


CharType表示给定的字符是否为空格&＃xff1b;然后Flux类型表示一段文本块&＃xff0c;它的字段包括子一个字符是否为空格、整个块中包含多少单词&＃xff0c;以及最后一个字符是否为空格。我们不保存实际的文本内容&＃xff0c;对于本问题而言这些信息是不必要的。这里UNPACK了Int&＃xff0c;并将所有字段标记为严格&＃xff0c;来保证不会遇到前面的懒惰元组的问题。使用严格数据类型意味着在计算时不需要使用BangPatterns了。

接下来需要一个半群&＃xff0c;以及该类型的一个Monoid实例&＃xff01;

1instance Semigroup Flux where
2  Unknown <> x &＃61; x
3  x <> Unknown &＃61; x
4  Flux l n NotSpace <> Flux NotSpace n&＃39; r &＃61; Flux l (n &＃43; n&＃39; - 1) r
5  Flux l n _ <> Flux _ n&＃39; r &＃61; Flux l (n &＃43; n&＃39;) r
6
7instance Monoid Flux where
8  mempty &＃61; Unknown


这里定义的(<>)操作符用来检查两个文本块的连接点是否发生在某个单词的中间&＃xff0c;如果发生了&＃xff0c;就表明我们对同一个单词的前半部分和后半部分统计了两次&＃xff0c;所以在统计单词总数时要减去1&＃xff0c;来保证平衡。

最后需要根据单个字符构建Flux对象。

1flux :: Char -> Flux
2flux c | isSpace c &＃61; Flux IsSpace 0 IsSpace
3       | otherwise &＃61; Flux NotSpace 1 NotSpace


似乎不是那么明显&＃xff0c;但这些就足以用幺半群的方式实现单词统计了&＃xff01;

1>>> foldMap flux "testing one two three"
2Flux NotSpace 4 NotSpace
3
4>>> foldMap flux "testing on" <> foldMap flux "e two three"
5Flux NotSpace 4 NotSpace
6
7>>> foldMap flux "testing one " <> foldMap flux " two three"
8Flux NotSpace 4 NotSpace


现在单词数已经实现了&＃xff0c;接下来需要幺半群版本的字符数和行数。代码如下&＃xff1a;

1data Counts &＃61;2    Counts { charCount :: {-# UNPACK #-} !Int34           , wordCount ::  !Flux5           , lineCount :: {-# UNPACK #-} !Int6           }7    deriving (Show)89instance Semigroup Counts where
10  (Counts a b c) <> (Counts a&＃39; b&＃39; c&＃39;) &＃61; Counts (a &＃43; a&＃39;) (b <> b&＃39;) (c &＃43; c&＃39;)
11
12instance Monoid Counts where
13  mempty &＃61; Counts 0 mempty 0


1countChar :: Char -> Counts
2countChar c &＃61;
3    Counts { charCount &＃61; 1
4           , wordCount &＃61; flux c
5           , lineCount &＃61; if (c &＃61;&＃61; &＃39;\n&＃39;) then 1 else 0
6           }


1>>> foldMap countChar "one two\nthree"
2Counts {charCount &＃61; 13, wordCount &＃61; Flux NotSpace 3 NotSpace, lineCount &＃61; 1}

在继续之前&＃xff0c;我们在已有代码中使用这个幺半群&＃xff0c;确保能获得同样的结果&＃xff1a;

1module MonoidBSFold where23import Data.Char4import qualified Data.ByteString.Lazy.Char8 as BS56monoidBSFold :: FilePath -> IO Counts7monoidBSFold paths &＃61; monoidFoldFile <$> BS.readFile fp89monoidFoldFile :: BS.ByteString -> Counts
10monoidFoldFile &＃61; BS.foldl&＃39; (\a b -> a <> countChar b) mempty

附带的好处是&＃xff0c;这一改变使得速度更快了&＃xff01;

来庆祝一下吧&＃xff01;

90MB测试文件

这个修改在时间和内存两方面都获得了非常好的结果……我承认我不知道这是为什么&＃xff0c;但意外之喜我就不挑剔了。很可能是因为我们使用了完全严格的数据结构&＃xff0c;限制了某些地方的懒惰性&＃xff1b;但我不敢确信。如果你知道为什么&＃xff0c;那么请一定告诉我&＃xff01;

更新&＃xff1a;guibou指出&＃xff0c;这里的Flux和Counts类型使用了UNPACK指令&＃xff0c;而之前使用的是正常的ol&＃39;元组。显然GHC有时候能够UNPACK元组&＃xff0c;但这里似乎它并没有。通过UNPACK我们节省了一些指针间接操作&＃xff0c;也节省了内存&＃xff01;

下一个任务就是将一些定义改成内联&＃xff01;为什么呢&＃xff1f;因为需要性能时就要这么做&＃xff01;我们可以用INLINE指令告诉GHC&＃xff0c;函数的性能很重要&＃xff0c;这样它就会采用内联方式&＃xff1b;还可能会触发更多的优化。

1monoidBSFold :: FilePath -> IO Counts
2monoidBSFold paths &＃61; monoidBSFoldFile <$> BS.readFile fp
3{-# INLINE monoidBSFold #-}
4
5monoidBSFoldFile :: BS.ByteString -> Counts
6monoidBSFoldFile &＃61; BS.foldl&＃39; (\a b -> a <> countChar b) mempty
7{-# INLINE monoidBSFoldFile #-}
8


90MB测试文件

有意思的是&＃xff0c;似乎内联将执行时间缩短了75%&＃xff01;我不确定这是不是意外之喜&＃xff0c;或者只是幸运而已&＃xff0c;不过很不错&＃xff01;尽管内存使用量上涨了一些&＃xff0c;但还不至于达到担心的程度。

现在与C语言比较的结果如下&＃xff1a;

现在已经与wc很接近了&＃xff0c;但我们但目标是缩小秒以下级别的差距&＃xff0c;所以我想增加测试文件的尺寸&＃xff0c;多运行几次&＃xff0c;看看有没有新的发现。

我使用了543MB的纯文本文件运行了几次&＃xff0c;以便预热缓存。这一点十分重要&＃xff0c;因为运行几次之后运行时间整整下降了33%。我知道我的测试方法并不是完全“科学”&＃xff0c;但它能够很好地估计出效果。不论如何&＃xff0c;在大文件上的测试结果如下&＃xff1a;

这里可以看出&＃xff0c;我们已经非常接近了&＃xff01;考虑到我们使用的是支持垃圾回收的高级语言&＃xff0c;而且代码只有80行左右&＃xff0c;我认为我们已经做得很好了&＃xff01;

我们没办法使用多核心将这个任务完全并行化&＃xff0c;因为整个操作是IO密集的&＃xff0c;但我还是要试试看。

我们已经将问题表达成了一个幺半群&＃xff0c;也就是说分割计算应该相当容易了&＃xff01;这里的难度在于读取数据部分。如果将所有数据读进来&＃xff0c;再分隔成小块&＃xff0c;那就不得不将整个文件全部读入内存&＃xff0c;从而导致非常高的内存占用量&＃xff0c;也很可能会影响性能&＃xff01;我们也可以用流式方法来分割&＃xff0c;但就得处理完第一块之后才能处理第二块。我想你应该明白问题在哪儿了。我的做法是&＃xff0c;在每个核心上启动一个线程&＃xff0c;然后每个线程打开一个单独的文件描述符。然后将文件描述符跳转到各个互不重叠的块的位置。

完整的代码如下。我之前有没有说过我很喜欢在Haskell中编写并行代码&＃xff1f;

1import Types2import Control.Monad3import Data.Traversable4import Data.Bits5import GHC.Conc (numCapabilities)6import Control.Concurrent.Async7import Data.Foldable8import System.IO9import System.Posix.Files
10import qualified Data.ByteString.Lazy.Char8 as BL
11import Data.ByteString.Internal (c2w)
12import GHC.IO.Handle
13
14multiCoreCount :: FilePath -> IO Counts
15multiCoreCount fp &＃61; do
16    putStrLn ("Using available cores: " <> show numCapabilities)
17    size <- fromIntegral . fileSize <$> getFileStatus fp
18    let chunkSize &＃61; fromIntegral (size &＃96;div&＃96; numCapabilities)
19    fold <$!> (forConcurrently [0..numCapabilities-1] $ \n -> do
20        -- Take all remaining bytes on the last capability due to integer division anomolies
21        let limiter &＃61; if n &＃61;&＃61; numCapabilities - 1
22                         then id
23                         else BL.take (fromIntegral chunkSize)
24        let offset &＃61; fromIntegral (n * chunkSize)
25        fileHandle <- openBinaryFile fp ReadMode
26        hSeek fileHandle AbsoluteSeek offset
27        countBytes . limiter <$!> BL.hGetContents fileHandle)
28{-# INLINE handleSplitUTF #-}
29
30countBytes :: BL.ByteString -> Counts
31countBytes &＃61; BL.foldl&＃39; (\a b -> a <> countChar b) mempty
32{-# INLINE countBytes #-}
33


我们可以从GHC.Conc中导入“能力”的数量&＃xff08;即能够访问的核心数量&＃xff09;。然后&＃xff0c;在需要计数的文件上运行fileStat来获得文件的字节数。然后使用整数除法来决定每个核心要处理多少字节。整数除法会向下取整&＃xff0c;所以在处理剩余的字节数时要格外小心。然后使用Control.Concurrent.Async提供的forConcurrently在每个核心上运行一个单独的线程。

在每个线程内&＃xff0c;我们检查该线程是否在处理最后一块文件&＃xff0c;如果是&＃xff0c;则应该一直读取到EOF&＃xff0c;从而避免前面提到的取整问题&＃xff0c;否则就只处理chunkSize字节。然后&＃xff0c;将块的尺寸和线程编号相乘&＃xff0c;得到偏移量。然后以二进制方式打开文件&＃xff0c;使用hSeek将描述符移动到偏移量的位置。然后只需简单地读入所需的字节数&＃xff0c;然后使用与前面相同的逻辑进行fold。在所有线程处理完毕后&＃xff0c;只需使用fold将每个块的计数合并在一起即可。

有几个地方使用了<$!>来增加额外的严格性&＃xff0c;因为我们希望保证fold操作在各个线程中执行而不是在线程归并之后再进行。也许我有点过度使用严格性标注了&＃xff0c;但写多一点总比找出哪里漏了写要容易得多。

我们来尝试一下吧&＃xff01;

预热缓存之后&＃xff0c;在我的4核心、带有SSD的MacBook Pro 2013版上分别运行了两个版本几次&＃xff0c;然后平均结果&＃xff1a;

看起来效果很好&＃xff01;我们实际上比某些手工优化了几十年的C代码还要快。当然这些结果要有条件地来看&＃xff0c;很难说这里是不是有某些缓存的因素。可能有多层磁盘缓存生效了。也许&＃xff0c;多线程只有在从缓存中读取文件时才有效果&＃xff1f;

我做了很多测试&＃xff0c;发现并行执行在某些存储设备上会产生加速&＃xff0c;但在一些存储设备上甚至会变慢。所以你的情况可能不一样。希望有SSD的专家能够指出这里的问题。不过不管怎么说&＃xff0c;这个结果让我非常满意。

更新&＃xff1a;貌似的确有一些SSD的专家&＃xff01;Paul Tanner给我写了一封邮件来解释现代的NVME驱动器的确会从并行中受益&＃xff0c;只要并行访问的不是一个块&＃xff08;这里我们并没有这样做&＃xff09;。不幸的是&＃xff0c;我的老MacBook没有NVME驱动器&＃xff0c;但这意味着&＃xff0c;这段代码在现代设备上可能会运行得更快。感谢Paul&＃xff01;

此外&＃xff0c;该程序实际的用户时间为4.22s&＃xff08;被分配到了4个核心上&＃xff09;&＃xff0c;这意味着从处理器周期的角度来看&＃xff0c;并行版本实际上不如简单版本有效&＃xff0c;但能够利用多个核心&＃xff0c;能够降低真实的运行时间。

我们一直都在忽略一个问题&＃xff1a;我们假设每个文件都是ASCII&＃xff01;而真实世界并非如此。许多文档都是用UTF-8编码的&＃xff0c;也就是说&＃xff0c;当且仅当文件只包含有效的ASCII字符时&＃xff0c;整个文件才和ASCII文件一样。但是如果年轻人使用了表情符号&＃xff0c;那就乱了。

这个问题有两面性&＃xff1a;首先&＃xff0c;我们现在计算的是字节数而不是字符数&＃xff0c;因为在ASCII的世界中&＃xff0c;字符和字节在语义上是相同的。对于我们现在的代码而言&＃xff0c;如果它遇到UTF-8编码的“皱眉”符号&＃xff0c;那么至少会被计算成两个字符&＃xff0c;而实际上应该计算成一个字符。好吧&＃xff0c;也许我们应该尝试进行解码&＃xff0c;但这件事说起来容易做起来难&＃xff0c;因为我们分割文件的位置是任意挑选的&＃xff0c;也就是说有可能会将“皱眉”符号分割到两个块中&＃xff0c;导致非法编码&＃xff01;真是噩梦啊。

这也是为什么多线程wc也许不是个好主意&＃xff0c;但我不会轻易放弃的。我将做一些假设&＃xff1a;

有了这两个假设&＃xff0c;我们可以看看UTF-8编码定义&＃xff0c;来尝试解决问题。首先&＃xff0c;从UTF-8规格中我们知道&＃xff0c;它与ASCII完全向后兼容。这就是说&＃xff0c;每个ASCII字符在UTF-8中的编码就是字节本身。其次&＃xff0c;我们知道&＃xff0c;文件中的任何字节都不会与有效的ASCII字节冲突&＃xff0c;从UTF-8的维基百科页面&＃xff08;https://en.wikipedia.org/wiki/UTF-8&＃xff09;的这张表上就可以看出。后续字节开头是“1”&＃xff0c;而ASCII字节永远不会以1开头。

这两个事实表明&＃xff0c;我们不需要改变检测“空格”的逻辑&＃xff01;绝无可能将空格或换行“分割”&＃xff0c;因为它们都被编码为单字节&＃xff0c;我们也知道&＃xff0c;不可能将其他代码点的一部分错误地进行统计&＃xff0c;因为它们的编码与ASCII字节没有交集。但是&＃xff0c;我们需要改变字符计数的逻辑。

关于UTF-8的最后一点是&＃xff0c;每个UTF-8编码的代码点都必然包含下述集合中的一个字节&＃xff1a;0xxxxxxx&＃xff0c;110xxxxx&＃xff0c;1110xxxx&＃xff0c;11110xxx。后续字节均以10开始&＃xff0c;所以只要统计开头不是10的所有字节&＃xff0c;就能精确地将每个代码点只统计一次&＃xff0c;即使从代码点中间拆分也是如此&＃xff01;

将以上这些综合起来&＃xff0c;我们可以编写一个逐字符进行处理的幺半群&＃xff0c;它既可以统计UTF-8的代码点&＃xff0c;也可以统计ASCII字符&＃xff01;

注意&＃xff0c;理论上讲Unicode的代码点并不等价于“字符”&＃xff0c;有许多代码点&＃xff08;比如声调符号&＃xff09;会与其他字符“融合”并显示为一个字符&＃xff0c;但据我所知&＃xff0c;wc也没有单独考虑它们。

实际上&＃xff0c;我们现在的Counts幺半群不需要改动&＃xff0c;只需要修改一下countChar函数&＃xff1a;

1import Data.Bits2import Data.ByteString.Internal (c2w)3countByte :: Char -> Counts4countByte c &＃61;5  Counts {6            -- Only count bytes at the START of a codepoint, not continuation bytes7            charCount &＃61; if (bitAt 7 && not (bitAt 6)) then 0 else 18            , wordCount &＃61; flux c9            , lineCount &＃61; if (c &＃61;&＃61; &＃39;\n&＃39;) then 1 else 0
10            }
11    where
12      bitAt &＃61; testBit (c2w c)
13{-# INLINE countByte #-}


而wc&＃xff0c;至少在我的MacBook上的这个版本&＃xff0c;有一个-m选项用于在计数时处理多字节字符。进行几次实验就会发现&＃xff0c;wc处理多字节字符会严重地拖慢处理速度&＃xff08;它会解码每个字节&＃xff09;&＃xff1b;我们来看看我们的实现。&＃xff08;我已确认过&＃xff0c;每次在大型UTF-8文件上运行都会得到相同的结果&＃xff09;

如我们猜测的那样&＃xff0c;我们已经远远超过了C&＃xff01;我们的新版本比简单地统计每个字节要慢一些&＃xff08;因为现在要做一些额外的位检查&＃xff09;&＃xff0c;所以最好还是在程序上加一个utf标记&＃xff0c;以便在任何情况下都能达到最好的性能。

这篇文章发表后&＃xff0c;Harendra Kumar提供了一条新的提升性能的技巧&＃xff0c;从而获得了更好的内存占用量和性能&＃xff0c;同时还能支持从stdin读取流输入&＃xff01;哇&＃xff01;代码也十分优雅&＃xff01;

秘密就在streamly库中。这个库是个非常好的高级、高性能流处理库。我以前见过它&＃xff0c;但有了这次经历&＃xff0c;以后我一定会进一步了解它&＃xff01;闲话少说&＃xff0c;直接上代码。再次感谢Harendra Kumar提供的实现&＃xff01;

1module Streaming where23import Types4import Data.Traversable5import GHC.Conc (numCapabilities)6import System.IO (openFile, IOMode(..))7import qualified Streamly as S8import qualified Streamly.Data.String as S9import qualified Streamly.Prelude as S
10import qualified Streamly.Internal.Memory.Array as A
11import qualified Streamly.Internal.FileSystem.Handle as FH
12
13streamingBytestream :: FilePath -> IO Counts
14streamingBytestream fp &＃61; do
15    src <- openFile fp ReadMode
16    S.foldl&＃39; mappend mempty
17        $ S.aheadly
18        $ S.maxThreads numCapabilities
19        $ S.mapM countBytes
20        $ FH.toStreamArraysOf 1024000 src
21    where
22    countBytes &＃61;
23          S.foldl&＃39; (\acc c -> acc <> countByte c) mempty
24        . S.decodeChar8
25        . A.toStream
26
27{-# INLINE streamingBytestream #-}


首先&＃xff0c;我们要打开文件&＃xff0c;这里没有什么神秘的地方。

其次是流处理的代码&＃xff0c;我们从底向上来阅读&＃xff1a;

1FH.toStreamArraysOf 1024000 src


1S.mapM countBytes


1countBytes &＃61;
2      S.foldl&＃39; (\acc c -> acc <> countByte c) mempty
3    . S.decodeChar8
4    . A.toStream


1S.maxThreads numCapabilities


Streamly提供了许多流求值策略。这里使用了aheadly&＃xff0c;它可以并行处理流元素&＃xff0c;但依然能保证输出与输入的顺序相同。由于我们使用了幺半群&＃xff0c;所以只要它们能保证适当的顺序&＃xff0c;我们就可以用任何方式来实现计算&＃xff1a;

1S.aheadly

1S.foldl&＃39; mappend mempty


下面是非utf版本在543MB测试文件上的表现&＃xff1a;

可以看到它更快&＃xff0c;代价是占用了大量内存。我认为可以通过改变分块策略来减少内存用量。我们来试一下。下面是100KB分块和1MB分块的比较&＃xff1a;

如我所料&＃xff0c;我们可以用一点点性能来换取不错的内存占用量。对于这个结果我已经相当满意了&＃xff0c;不过你也可以继续试验其他的策略。

最后&＃xff0c;我们在543MB测试文件上试一下UTF8版本。下面是结果&＃xff1a;

我们依然比wc块&＃xff01;尽管在最终版本中可能需要减少一些内存占用&＃xff01;

总体而言&＃xff0c;我认为力流版本是最好的&＃xff0c;它从高层着手&＃xff0c;非常易读&＃xff0c;而且可以支持从任意文件描述符读取&＃xff0c;其中包括stdin&＃xff0c;这是wc非常常见的用例。streamly太酷了。

那么&＃xff0c;我们这个支持垃圾回收的、基于运行时的高级语言Haskell究竟怎样&＃xff1f;我要说&＃xff0c;它非常棒&＃xff01;我们的单核lazy-bytestring版本wc就达到了非常接近的性能。换成多核心之后就能超过wc&＃xff01;我们应当考虑在没有磁盘缓存预热的情况下的性能&＃xff0c;但纯粹就性能而言&＃xff0c;我们成功地构建了比C语言还快的东西&＃xff01;而流版本应该不会依赖于磁盘缓存。

作为一门语言&＃xff0c;Haskell并不完美&＃xff0c;但如果我能写出性能媲美C语言的程序&＃xff0c;同时保持使用高层逻辑&＃xff0c;使用完全支持类型的代码&＃xff0c;那我认为就非常好了。

原文&＃xff1a;https://chrispenner.ca/posts/wc

本文为 CSDN 翻译&＃xff0c;转载请注明来源出处。

【END】

这四个Python项目&＃xff0c;让你很快读懂Python&＃xff01;

https://edu.csdn.net/topic/python115?utm_source&＃61;csdn_bw

&＃xff01;

☞