arrays - 在 Haskell 中存储和排序矩形数据的最佳方法是什么？

Question

我有一些 ASCII 文件，总共包含大约 1700 万行，每行/大多数行中都有一个固定的 36 字节标识符。所以我的数据是矩形的:我有很多固定宽度的行。使用 Haskell，我想读取其中的所有行，使用正则表达式来提取标识符(我已经很好了)，然后对它们进行排序并计算唯一标识符的数量(非常接近 grep | sort |唯一性)。 (我已经通过并行读取每个文件来实现并行化。)听起来像是一个简单的问题，但是......

我发现很难从这个问题中获得不错的性能，即使在排序阶段之前也是如此。据我所知。 String 对于 36 字节的 ASCII 来说太过分了，所以我想使用 ByteString。但是大小为 1700 万的(链接)列表似乎不是个好主意，所以我尝试了 IOVector ByteString。但这似乎很慢。我相信垃圾收集正在受到影响，因为我在向量中保留了数百万个小字节串:GC 花费的时间至少是代码的 3 倍(根据 +RTS -s)，我认为它随着程序继续运行只会变得更糟。

我在想我应该使用 Repa 或某种单一的巨型 ByteString/IOVector Char8/whatever(因为我知道每行的确切宽度是 36 ) 为每个线程将数据存储在一个巨大的矩形数组中，这应该可以缓解 GC 问题。但是，我仍然需要在之后对行进行排序，而 Repa 似乎不支持排序，我不想自己编写排序算法。所以我不知道如何拥有一个巨大的矩形数组，但仍然对其进行排序。

关于要使用的库、要设置的 Gcflags或其他任何内容的建议？该机器有 24 个内核和 24GB 内存，所以我不受硬件限制。我想留在 Haskell 中，因为我有很多工作正常的相关代码(也就是解析相同的文件并生成汇总统计信息)，我不想重写它们。

Answer 1

I believe the garbage collection is suffering as I retain millions of small ByteStrings in the vector

可疑。不应收集保留的 ByteString。也许您的代码中某处存在过多的数据复制？

• ByteString 是一个头部(8 字节)+ ForeignPtr Word8 ref(8 字节)+ Int 偏移量(4 字节) + Int 长度(4 字节)

• ForeignPtr 是一个 header (8 字节)+ Addr#(8 字节)+ PlainPtr ref(8 字节)

• PlainPtr 是一个 header (8 字节)+ MutableByteArray# ref(8 字节)

(根据https://stackoverflow.com/a/3256825/648955修改)

总而言之，ByteString 开销至少是 64 字节(纠正我，有些字段是共享的)。

编写自己的数据管理:大扁平Word8数组和adhoc offset wrapper

newtype ByteId = ByteId { offset :: Word64 }

使用 Ord 实例。

每个标识符的开销为 8 个字节。将偏移量存储在未装箱的 Vector 中。用这样的东西排序:http://hackage.haskell.org/packages/archive/vector-algorithms/0.5.4.2/doc/html/Data-Vector-Algorithms-Intro.html#v:sort