如何將此範圍編碼C++代碼片段轉換爲Haskell性能？

我知道足夠哈斯克爾到下面的代碼轉換，但我不知道很多關於使它表現良好：如何將此範圍編碼C++代碼片段轉換爲Haskell性能？

typedef unsigned long precision; 
typedef unsigned char uc; 

const int kSpaceForByte = sizeof(precision) * 8 - 8; 
const int kHalfPrec = sizeof(precision) * 8/2; 

const precision kTop = ((precision)1) << kSpaceForByte; 
const precision kBot = ((precision)1) << kHalfPrec; 


//This must be called before encoding starts 
void RangeCoder::StartEncode(){ 
    _low = 0; 
    _range = (precision) -1; 
} 

/* 
    RangeCoder does not concern itself with models of the data. 
    To encode each symbol, you pass the parameters *cumFreq*, which gives 
    the cumulative frequency of the possible symbols ordered before this symbol, 
    *freq*, which gives the frequency of this symbol. And *totFreq*, which gives 
    the total frequency of all symbols. 
    This means that you can have different frequency distributions/models for 
    each encoded symbol, as long as you can restore the same distribution at 
    this point, when restoring. 
*/ 
void RangeCoder::Encode(precision cumFreq, precision freq, precision totFreq){ 
    assert(cumFreq + freq <= totFreq && freq && totFreq <= kBot); 
    _low += cumFreq * (_range /= totFreq); 
    _range *= freq; 
    while ((_low^_low + _range) < kTop or 
     _range < kBot and ((_range= -_low & kBot - 1), 1)){ 
    //the "a or b and (r=..,1)" idiom is a way to assign r only if a is false. 
    OutByte(_low >> kSpaceForByte); //output one byte. 
    _range <<= sizeof(uc) * 8; 
    _low <<= sizeof(uc) * 8; 
    } 
}

我知道，我知道「寫幾個版本，並使用標準來看看有什麼效果」。我不知道我的選擇是什麼，或者避免愚蠢的錯誤。

以下是我的想法。一種方法是使用狀態monad和/或鏡頭。另一種方法是將循環和狀態轉換爲顯式遞歸。我在某處讀到顯式遞歸往往在ghc上表現不佳。我認爲使用ByteString Builder會是輸出每個字節的好方法。假設我在64位平臺上運行，我應該使用unboxed Word64參數嗎？如果我將精度降低到32位，壓縮質量不會顯着降低。 GHC會爲此更好地優化嗎？

由於這不是1-1映射，因此使用StateP的管道會導致非常整齊的代碼，我會一次請求一個參數，然後讓while循環響應字節的字節。不幸的是，當我對它進行基準測試時，看起來管道開銷（不出所料）是相當大的。由於每個符號都可能導致很多字節輸出，所以感覺有點像帶有狀態的concatMap。也許這將是慣用的解決方案？雖然，連接字節列表對我來說聽起來不是很快。 ByteString有一個concatMap。也許這是正確的方法？編輯：不，它不是。它需要一個ByteString作爲輸入。

我打算在完成後發佈Hackage上的軟件包，所以任何建議（或實際的代碼！）都可以給社區帶來好處:)。我打算使用這種壓縮作爲編寫一個非常有效的內存壓縮映射的基礎。

來源

2013-06-20 Gurgeh

請重新設置代碼的格式以符合問題欄的寬度。 – leventov

只有評論堅持我認爲，但我會解決！ – Gurgeh

我在某處讀到顯式遞歸往往在ghc上表現不佳。

編號GHC產生的遞歸機器代碼很慢，不能被減少（或GHC「不想」減少）。如果遞歸可以被展開（我沒有在代碼片段中看到任何基本問題），它將被轉換爲與C或C++中的while循環幾乎相同的機器代碼。

假設我在64位平臺上運行，應該使用unboxed Word64參數嗎？如果我將精度降低到32位，壓縮質量不會顯着降低。 GHC會爲此更好地優化嗎？

你的意思是Word#？讓GHC處理它，使用盒裝類型。我從來沒有遇到過這樣的情況，即只有通過使用無箱類型才能實現一些利潤。使用32位類型在64位平臺上無助。

優化GHC性能的一個通用規則是在可能的情況下避免數據結構。如果您可以通過函數參數或閉包傳遞數據片段，請使用這個機會。

來源

2013-06-20 12:51:45 leventov

我還會提到嚴格註釋（砰的模式），並避免過多的thunk – jozefg

@jozefg是的，這是一種幫助GHC表現良好的技術。 http://stackoverflow.com/questions/16926717/unboxing-a-function – leventov

是不是拆箱向量比他們的盒裝等效？ – DiegoNolan

如何將此範圍編碼C++代碼片段轉換爲Haskell性能？

回答

相關問題