TemplateHaskell 编译时的内存使用情况

Question

我在 RuzzSolver（我的 Haskell 项目之一）中使用模板 Haskell 时遇到内存消耗问题。 Sources of RuzzSolver are available on GitHub .

为了获得良好的性能，我将约 380000 个单词的字典加载到 Tree 结构中（来自容器包）。这大大加快了网格的求解速度，但加载本身需要一些时间（1 到 2 秒之间，具体取决于 CPU）。

我想在编译期间使用模板直接创建结构Haskell。

因此我改造了字典加载：

-- Dictionary.hs, line 155
getDictionary :: String -> IO Dictionary
getDictionary dictionaryFilePath = do
    content <- readFile dictionaryFilePath
    return $ foldl (+++) [] (createTree <$> lines content)

进入这个函数：

-- Dictionary.hs, line 164
getDictionaryQ :: String -> Q Exp
getDictionaryQ dictionaryFilePath = do
    content <- runIO $ readFile dictionaryFilePath
    lift $ foldl (+++) [] (createTree <$> lines content)

view Dictionary.hs

它让我可以从：

-- ruzzSolver.hs, line 68
dictionary <- getDictionary "dictionary/ruzzdictionary.txt"

至：

-- ruzzSolver.hs, line 68
let dictionary = $(getDictionaryQ "dictionary/ruzzdictionary.txt")

view ruzzSolver.hs

它（应该）可以工作，但是编译需要太多内存！在我的 8 Gb PC 上，当 GHC 达到 12 GB 的消耗量时，我不得不停止它。将词典减少到 38000 个单词可以编译，但它仍然需要 3 到 4 GB。

有没有办法让 GHC 在编译此模板Haskell代码时使用更少的内存？或者另一种将此结构嵌入可执行文件的方法？

Answer 1

也许您可以 "embed" 将 trie 放入可执行文件以节省加载和创建时间，但我预见到的一个问题是传统的 Haskell 数据结构与其他数据结构相比非常臃肿语言。

此外，大多数容器都允许插入和删除，但看起来您的数据是不变的，因此您只需要最终的数据结构。此外，您只会将它用于以下查询：

字典里有这个词吗？
而且，这个字符串是字典中某个单词的前缀吗？

您想要一个带有某种预计算索引的字典的紧凑表示，以便快速查找。

部分选项：

Option 1: Create a BerkeleyDB database.

这样的数据库允许大于和小于查询。

优点：没有数据库加载时间。

缺点：查询需要磁盘访问。虽然，一旦页面被 OS 读取，它们应该被缓存并且后续读取应该很快。

注意 - 我已经使用 Berkeley DB 在 perl 中编写了一个 boggle 求解器，因此这种方法非常可行。

与 BerkeleyDB 类似的是 CDB（常量数据库），它也有一个 Haskell 包。但是，CDB 仅支持相等查询，因此它可能不适用于您的应用程序。

Option 2. Represent the dictionary simply as the sorted file of the words. Create a custom index to make queries efficient.

一个简单的索引可以是一个 26*26*26 的元素数组，指示每个三字母前缀在文件中的偏移量。这么小的索引就可以编进程序了。将字典加载为单个（严格的）ByteString。

在字节串中使用索引和二进制搜索来解决查询。也许 ByteString 函数在这里可以很好地工作，但作为最后的手段，您始终可以在加载的字典中使用 Int 偏移量作为 "pointer"，您可以四处移动以找到下一个单词的开头。

您可以将字典 ByteString 编译成可执行文件，但加载 4 MB 的数据不会花费太长时间 - 特别是如果它已经在 OS 缓存中。

更新： 第二个想法的例子可以在 here.

中找到

TemplateHaskell 编译时的内存使用情况

TemplateHaskell memory usage when compiling

haskell

template-haskell