編譯

Question

時TemplateHaskell內存使用情況我在RuzzSolver，我的Haskell的一個項目使用TemplateHaskell時有內存消耗問題。 Sources of RuzzSolver are available on GitHub。

爲了實現良好的性能，我加載〜380000字字典成Tree結構（從容器包裝）。這極大地加速了網格的求解，但是加載本身需要一些時間（取決於CPU，在1到2秒之間）。

我想在編譯時通過TemplateHaskell直接創建結構。

所以我改變了字典加載：

-- 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上，當耗電量達到12 GB時，我不得不停止GHC。將字典縮小到38000字可以編譯，但仍需要3至4 GB。

編譯此TemplateHaskell代碼時，有沒有辦法讓GHC使用更少的內存？或者將此結構嵌入到可執行文件中的另一種方法？

Answer 1

也許你可以將trie嵌入到可執行文件中以節省加載和創建時間，但是我預見到的一個問題是與其他語言中的數據結構相比，傳統的Haskell數據結構相當臃腫。

此外，大多數容器允許插入和刪除，但它看起來像你的數據是不變的，所以你只需要最終的數據結構。此外，你只會用它的查詢如：

• 這個詞是否存在於字典中？
• 而且，是這個字符串在字典中的一些單詞的前綴？

您想要使用某種預先計算的索引的緊湊表示形式來進行快速查找。

一些選項：

選項1：創建一個數據庫的BerkeleyDB。

這樣的數據庫允許大於和小於查詢。

優點：無數據庫加載時間。

缺點：需要查詢的磁盤訪問。儘管一旦頁面被操作系統讀取，它們應該被緩存並且後續讀取應該很快。

注 - 我使用Berkeley DB在Perl中編寫了一個boggle求解器，所以這種方法非常可行。

類似於BerkeleyDB是一個CDB（常量數據庫），也有一個Haskell包。但是，CDB僅支持平等查詢，因此它可能不適用於您的應用程序。

選項2.僅將字典表示爲單詞的排序文件。創建一個自定義索引以提高查詢的效率。

一個簡單的索引可能只是一個26 * 26 * 26的元素數組，指示每個三字母前綴文件的偏移量。這樣一個小的索引可以編譯到程序中。將字典加載爲單個（嚴格）ByteString。

在字節字符串中使用索引和二進制搜索來解決查詢。 也許ByteString函數可以在這裏很好的工作，但作爲最後的手段，你總是可以在被加載的字典中使用一個Int偏移量作爲一個「指針」，你可以四處移動來找到下一個單詞的開始。

您可能能夠將字典ByteString編譯到可執行文件中，但加載4 MB數據不應該花太長時間 - 特別是如果它已經在OS高速緩存中。

更新：這個第二個想法的例子可以找到here。