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

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

作者 |Chris Penner

译者 | 弯月，责编 | 郭芮

出品 | CSDN（ID：CSDNnews）

以下为译文：

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

点击这里可以下载本文的源代码（https://github.com/ChrisPenner/wc）。

作为参考，我使用的是Mac版的wc；其参考源代码在此（https://opensource.apple.com/source/text_cmds/text_cmds-68/wc/wc.c.auto.html）。没错，其实还有更快的wc实现。

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

下面是该任务的条件：

正确性：它应当返回被测试文件的正确的字符数、单词数和行数。

速度（真实世界的时间）：与wc的执行时间相比是快是慢？

最大常驻内存量：最多使用多少内存？内存使用量是常量还是线性的，或者是其他？

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

下面让我们开始吧。

最笨的实现

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

很不错，这段代码能正常运行，并且能获得与wc相同的结果——如果你愿意等的话。而我在测试大文件时开始不耐烦（它需要几分钟的时间），但在小文件（90MB）上的测试结果如下：

90MB的测试文件

嗯……不用我说你也知道，改进的空间非常大……

略微好一点的实现

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

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

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

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

结果这个版本遇到了更严重的问题！

程序运行花了几分钟，内存占用迅速超过了3GB！为什么会这样呢？我们使用的是严格版本的foldl'（后面的撇号 ' 表示它是严格的），但它只在“Weak Head Normal Form”（WHNF）中是严格的，也就是说，它在元组累加器中是严格的，但在实际的值中不是严格的！

这很讨厌，因为这意味着我们构造了一大堆巨大的加法操作，但只有在整个文件遍历结束后才进行求值！有时候，懒惰求值就会像这样偷偷地给我们挖坑。如果不注意，这种内存泄漏很容易就会搞垮你的Web服务器。

90MB测试文件

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

这一点小改动带来了近乎疯狂的性能提升。新的性能数据如下：

90MB测试文件

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

使用ByteStrings进一步优化

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

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

唯一的改动就是将Data.List的导入改成Data.ByteString.Lazy.Char8，然后将readFile和foldl'函数改成相应的ByteString版本：

这一点小改动将运行时间缩短到了将近一半！

90MB测试文件

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

使用幺半群

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

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

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

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

这些类型只有在统计单词数时才需要。

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

接下来需要一个半群，以及该类型的一个Monoid实例！

这里的Unknown构造函数表示Monoidal幺元，实际上我们可以不用它，而是用Maybe将Semigroupo提升为Monoid，但Maybe会给半群添加操作带来不必要的懒惰性！所以为了简单起见，我只是将其定义为类型的一部分。

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

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

这很简单，非空格字符统计为“单词”，所谓单词就是以非空格开始并结束，所谓空白，就是一个长度为零的单词，两侧被空格字符包围。

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

似乎能正常工作！

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

没问题！类似地，我们需要将单个字符变成Counts对象：

尝试一下：

看起来不错！你可以用喜欢的内容来证实这个幺半群是正确的。

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

我们将一部分复杂的内容移动到了Counts类型中，这样能大幅简化实现。一般来说这样做很好，因为测试单一数据类型比测试每个使用fold的地方要容易得多。

附带的好处是，这一改变使得速度更快了！

来庆祝一下吧！

90MB测试文件

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

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

使用内联！

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

我还给countChar和flux函数添加了INLINE。我们来看看有没有效果：

90MB测试文件

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

现在与C语言比较的结果如下：

90MB测试文件

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

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

543MB测试文件

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

使用核心

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

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

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

这里涉及了很多东西，我尽量详细地解释一下。

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

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

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

我们来尝试一下吧！

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

543MB测试文件

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

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

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

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

处理Unicode

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

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

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

输入可以是ASCII或UTF-8编码。当然还有其他流行的编码方式，但根据我有限的经验，绝大部分现代文本文件都采用两者之一。实际上，有许多网站都在致力于让UTF-8成为唯一的编码格式。

我们仅把ASCII中的空格和换行当做空格和换行处理；MONGOLIAN VOWEL SEPARATOR等字符就不考虑了。

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

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

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

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

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

实际上，我们现在的Counts幺半群不需要改动，只需要修改一下countChar函数：

这样就好了！现在我们可以处理UTF-8和ASCII了，我们甚至都不需要知道处理的是什么编码，就能永远给出正确的结果。

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

543MB文件

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

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

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

注意：这里用的streamly版本7.10是直接从Github代码库中获得的，很可能它很快就会被发不到hackage上。这段代码还使用了几个内部模块，我希望看到，像这段代码中的用例能够证明，这些模块应该暴露出来。

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

其次是流处理的代码，我们从底向上来阅读：

这一段从文件描述符中读取字节块放到Byte数组的流中。使用Byte数组可以比使用Lazy ByteString等更快！每1MB文件内容我们会使用一个单独的数组，这一点你可以根据情况调整。

这里使用mapM在数组上运行countBytes函数；countBytes本身会根据数组创建流，然后使用我们的幺半群字节计数器来运行流fold：

接下来，我们告诉streamly在数组上并行运行map，从而实现让每个线程处理一个1MB的文件块。这里将线程的数量限制在了核心数量。一旦读入所有数据，就可以立即进行处理，我们的统计代码没有任何阻塞的理由，所以增加更多的线程只会给调度器带来额外的负担而已。

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

此时我们已经统计了1MB的输入块，但我们依然需要累加所有输入块。这一点可以在另一个流fold中通过mappend实现：

就这些！来看看效果吧！

下面是非utf版本在543MB测试文件上的表现：

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

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

最后，我们在543MB测试文件上试一下UTF8版本。下面是结果：

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

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

总结

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

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

原文：https://chrispenner.ca/posts/wc

本文为 CSDN 翻译，转载请注明来源出处。

【END】