bytestring - 是什么让 ByteString IO 如此之快？

Question

我一直在尝试解决problem 1330来自 Haskell 的 acm.timus.ru。基本上，它归结为: 1) 从标准输入中读取一个长度为 N (N < 10^4) 和 M 对整数 (M < 10^5) 的数组 A； 2) 对于每个 (from, to) 对，将子数组 A[from..to] 的总和打印到标准输出。

由于 SO 不允许我在此问题中发布超过 2 个 URL，因此我将引用我的 Github repository 中的文件。以下。

我想出了两个解决方案，它们共享大部分代码。第一个 (1330_slow.hs) 使用 Prelude 函数 (getLine/read/words) 并且有点慢:

$ ./bench.sh slow_hs
slow_hs
    Time inside the program: 2.18
MD5 (output.slow_hs.txt) = 89bcf8fd69a7fce953595d329c8f033a

另一个解决方案 (1330.hs) 抛弃了这些函数，用它们的 Data.ByteString.Char8 等效项 (B.getLine/B.readInt/B.words) 替换它们，并且表现得很好:

$ ./bench.sh hs
hs
    Time inside the program: 0.27
MD5 (output.hs.txt) = 89bcf8fd69a7fce953595d329c8f033a

这个问题的时间限制是 500 毫秒，所以虽然 270 毫秒已经足够快(并且可以与我在其他语言中的解决方案相媲美，例如 C++ 和 Go)，但 2180 毫秒并没有减少它。那么为什么我的第一个解决方案如此缓慢呢？即使按照 Real World Haskell 的分析技巧，我仍然无法理解这一点(我所能弄清楚的是大部分时间都花在了 readIntPair 函数上，这并没有太大帮助)。

如果你想自己做一些测试，我有一个 Python 输入生成器 (gen_test.py) 和一个预生成的输入文件 (input.txt)，以防你没有安装 Python。以及两种解决方案之间的差异(slow_fast_diff.txt)。

Answer 1

正如其他人所说，这不是ByteString快，就是String非常非常慢。

一个 ByteString每个字符存储一个字节，加上一些簿记开销。一个 String每个字符存储 12 个字节(取决于您是在 32 位还是 64 位模式下运行)。它还将每个字符存储在非连续内存中，因此每个字符必须单独分配空间，由垃圾收集器单独扫描，并最终再次单独释放。这意味着糟糕的缓存局部性、大量的分配器时间和大量的垃圾收集时间。简而言之，它非常低效。

基本上，ByteString C 做什么，Java 做什么，C++ 做什么，C# 做什么，VB 做什么，以及几乎所有其他编程语言对字符串所做的事情。我所知道的其他语言都没有像 Haskell 那样低效的默认字符串类型。 (即使是 Haskell 方言的 Frege 也使用了更高效的字符串类型。)

我应该指出 ByteString.Char8仅处理 Latin-1 字符。它根本无法处理随机的 Unicode 字符。对于像这样的编程挑战来说，这可能不是问题，但对于“真实系统”来说，这很可能是一个问题。 ByteString并没有真正处理外来字符或不同的字符编码或任何东西；它只是假设您想要纯 ASCII。这曾经是一个安全的假设；今天，没有那么多。