7

问题

我想要一个程序，它将编写一个序列，例如，

1
...
10000000

到一个文件。可以编写并获得不错性能的最简单的代码是什么？我的直觉是存在一些缺乏缓冲的问题。我的 C 代码以 100 MB/s 的速度运行，而通过参考，Linux 命令行实用程序dd以9 GB/s 3 GB/s 的速度运行（抱歉，不精确，请参阅评论——我对全局顺序更感兴趣- 量级）。

有人会认为现在这将是一个已解决的问题......即任何现代编译器都会立即编写出执行相当好的此类程序......

C代码

#include <stdio.h>

int main(int argc, char **argv) {
    int len = 10000000;
    for (int a = 1; a <= len; a++) {
        printf ("%d\n", a);
    }
    return 0;
}

我正在用clang -O3. 调用 8 次的性能骨架putchar('\n')可以获得相当的性能。

哈斯克尔代码

一个简单的 Haskell 实现以 13 MiB/秒的速度运行，使用ghc -O2 -optc-O3 -optc-ffast-math -fllvm -fforce-recomp -funbox-strict-fields. （我没有用 重新编译我的库-fllvm，也许我需要这样做。）代码：

import Control.Monad
main = forM [1..10000000 :: Int] $ \j -> putStrLn (show j)

我最好的 Haskell 测试运行速度更慢，为 17 MiB/秒。问题是我找不到将Vector's转换为ByteString's 的好方法（也许有使用 iteratees 的解决方案？）。

import qualified Data.Vector.Unboxed as V
import Data.Vector.Unboxed (Vector, Unbox, (!))

writeVector :: (Unbox a, Show a) => Vector a -> IO ()
writeVector v = V.mapM_ (System.IO.putStrLn . show) v

main = writeVector (V.generate 10000000 id)

看起来写ByteString's 很快，正如这段代码所证明的，写了等量的字符，

import Data.ByteString.Char8 as B
main = B.putStrLn (B.replicate 76000000 '\n')

这将获得 1.3 GB/s，虽然没有 1.3 GB/s 快dd，但显然要好得多。

4

3 回答 3

7

首先进行一些完全不科学的基准测试：

所有程序都已使用默认优化级别（gcc 为 -O3，GHC 为 -O2）编译并运行

time ./prog > outfile

作为基准，C 程序需要 1.07 秒来生成约 76MB（78888897 字节）的文件，吞吐量约为 70MB/s。

  1. “幼稚”的 Haskell 程序 ( forM [1 .. 10000000] $ \j -> putStrLn (show j)) 耗时 8.64 秒，约为 8.8MB/s。
  2. 相同forM_而不是forM5.64s，大约 13.5MB/s。
  3. ByteStringdflemstr 回答的版本耗时 9.13 秒，大约 8.3MB/秒。
  4. dflemstr的Text答案版本耗时 5.64 秒，约为 13.5MB/秒。
  5. 问题中的Vector版本耗时 5.54 秒，约为 13.7MB/秒。
  6. main = mapM_ (C.putStrLn . C.pack . show) $ [1 :: Int .. 10000000]，其中C，Data.ByteString.Char8耗时 4.25s，约 17.9MB/s。
  7. putStr . unlines . map show $ [1 :: Int .. 10000000]耗时 3.06s，约 24.8MB/s。

  8. 手动循环，

    main = putStr $ go 1
  where
    go :: Int -> String
    go i
        | i > 10000000 = ""
        | otherwise = shows i . showChar '\n' $ go (i+1)

    耗时 2.32s，约 32.75MB/s。

  9. main = putStrLn $ replicate 78888896 'a'耗时 1.15s，约 66MB/s。
  10. main = C.putStrLn $ C.replicate 78888896 'a'其中C，Data.ByteString.Char8耗时 0.143s，约 530MB/s，与lazy ByteStrings 的数据大致相同。

我们可以从中学到什么？

首先，不要使用forMormapM除非你真的想收集结果。就性能而言，这很糟糕。

然后，ByteString输出可能非常快（10.），但如果ByteStringto 输出的构建速度很慢（3.），您最终会得到比原始String输出更慢的代码。

3. 有什么可怕的？好吧，所有涉及String的s都很短。所以你会得到一个列表

Chunk "1234567" Empty

在任何两个这样的对象之间，Chunk "\n" Empty放入 a，然后将结果列表连接起来，这意味着在构建Emptya 时，所有这些 s 都会被丢弃。... (Chunk "1234567" (Chunk "\n" (Chunk "1234568" (...))))这是很多浪费的构造-解构-重建。可以通过ing 到 strict s 并使用（以及换行符）来实现与 theText和固定“天真”版本相当的速度。通过消除代价高昂的单例可以获得更好的性能，略好于 6.。如果将换行符粘贴到s 上，使用而不是，则连接必须处理一半稍长的 s，这是有回报的。StringpackByteStringfromChunksData.List.intersperseString\k -> shows k "\n"showByteString

我对文本或向量的内部结构不够熟悉，无法提供关于观察到的性能原因的半受过教育的猜测，所以我将它们排除在外。可以说，与固定的幼稚String版本相比，性能提升最多是微不足道的。

现在，6. 表明ByteString输出比String输出快，足以在这种情况下，packing 的额外工作得到补偿。但是，不要被它愚弄，相信总是如此。如果String要打包的 s 很长，则打包可能比String输出花费更多的时间。

但是一千万次调用putStrLn，无论String是版本还是ByteString版本，都需要很多时间。stdout Handle只抓取一次并String在非 IO 代码中构造输出会更快。unlines已经做得很好，但我们仍然为列表的构建而苦恼map show [1 .. 10^7]。不幸的是，编译器没有设法消除它（但它消除了[1 .. 10^7]，这已经很不错了）。所以我们自己做吧，通向8。这并不算太糟糕，但仍然是C程序的两倍多。

可以通过低级直接填充ByteStrings 而不通过Stringvia来制作更快的 Haskell 程序show，但我不知道 C 速度是否可以达到。无论如何，那个低级代码不是很漂亮，所以我会为你省去我所拥有的，但有时如果速度很重要，就必须亲自动手。

于 2012-04-10T03:08:15.337 回答
3

使用惰性字节字符串为您提供了一些缓冲，因为字符串将立即写入，并且只会在需要时生成更多数字。此代码显示了基本思想（可能会进行一些优化）：

import qualified Data.ByteString.Lazy.Char8 as ByteString

main =
  ByteString.putStrLn .
  ByteString.intercalate (ByteString.singleton '\n') .
  map (ByteString.pack . show) $
  ([1..10000000] :: [Int])

我仍然使用Strings 来表示这里的数字，这会导致可怕的减速。如果我们切换到text库而不是bytestring库，我们可以访问整数的“本机”显示函数，并且可以这样做：

import Data.Monoid
import Data.List
import Data.Text.Lazy.IO as Text
import Data.Text.Lazy.Builder as Text
import Data.Text.Lazy.Builder.Int as Text

main :: IO ()
main =
  Text.putStrLn .
  Text.toLazyText .
  mconcat .
  intersperse (Text.singleton '\n') .
  map Text.decimal $
  ([1..10000000] :: [Int])

我不知道您如何测量这些程序的“速度”（使用该pv工具？），但我想这些程序之一将是您可以获得的最快的简单程序。

于 2012-04-09T22:01:15.183 回答
3

如果您要获得最佳性能，那么从整体角度来看会有所帮助；即，您想编写一个函数，该函数映射[Int]到将内存块写入文件的一系列系统调用。

惰性字节串是一系列内存块的良好表示。将惰性字节串映射到一系列写入内存块的系统调用是L.hPut正在做的事情（假设是import qualified Data.ByteString.Lazy as L）。因此，我们只需要一种方法来有效地构造相应的惰性字节串。这就是惰性字节串构建器所擅长的。使用新的字节串构建器（这里是API 文档），下面的代码可以完成这项工作。

import qualified Data.ByteString.Lazy          as L
import           Data.ByteString.Lazy.Builder       (toLazyByteString, charUtf8)
import           Data.ByteString.Lazy.Builder.ASCII (intDec)
import           Data.Foldable                      (foldMap)
import           Data.Monoid                        (mappend)
import           System.IO                          (openFile, IOMode(..))

main :: IO ()
main = do
    h <- openFile "/dev/null" WriteMode
    L.hPut h $ toLazyByteString $
        foldMap ((charUtf8 '\n' `mappend`) . intDec) [1..10000000]

请注意，我输出到/dev/null以避免磁盘驱动程序的干扰。将数据移动到操作系统的工作保持不变。在我的机器上，上面的代码运行时间为 0.45 秒，比原来的 5.4 秒快 12 倍。这意味着 168 MB/s 的吞吐量。我们可以使用有界编码额外提高 30% 的速度（220 MB/s）]。

import qualified Data.ByteString.Lazy.Builder.BasicEncoding as E

L.hPut h $ toLazyByteString $
    E.encodeListWithB 
        ((\x -> (x, '\n')) E.>$< E.intDec `E.pairB` E.charUtf8) 
        [1..10000000]

它们的语法看起来有点古怪，因为 aBoundedEncoding a指定将 Haskell 类型的值转换为a有界长度的字节序列，以便可以在 compile-time 计算边界。这允许诸如E.encodeListWithB执行一些额外的优化以实现缓冲区的实际填充的功能。有关更多信息，请参阅Data.ByteString.Lazy.Builder.BasicEncoding上述 API 文档链接中的文档（唷，愚蠢的新用户超链接限制）。

这是我所有基准测试的来源。

结论是，只要我们了解实现的成本模型并使用正确的数据结构，我们就可以从声明式解决方案中获得非常好的性能。每当构造一个打包的值序列（例如，表示为字节串的字节序列）时，要使用的正确数据结构是字节串Builder。

于 2012-04-25T07:52:57.470 回答