Haskell和可變結構的性能

Question

我正在研究Optimizing Haskell code中給出的答案，並注意到與Python相比，使用小輸入確實會導致更快的Haskell運行。

但隨着數據集的規模不斷擴大，Python佔據了領先地位。使用基於散列表的版本提高了性能，但仍然落後。

更糟糕的是，我嘗試將Python的字典轉換爲哈希表，並觀察到硬性能。我真的很想知道發生了什麼，因爲我需要爲將來的應用程序使用可變結構。

這裏的稍微修改的Python代碼：

​​3210

Haskell中，與原來的響應（train4），一個HashMap變體（trainHM2）和散列表音譯（trainHT）：

{-# LANGUAGE BangPatterns,DeriveGeneriC#-} 

import GHC.Generics (Generic) 

import Data.List (foldl') 
import Data.Hashable 

import qualified Data.Map as M 

import qualified Data.HashMap.Strict as HM 
import qualified Data.ByteString.Char8 as B 

import qualified Data.HashTable.IO as HT 

--Using this instead of tuples yielded a 5~10% speedup 
data StringTuple = STP !B.ByteString !B.ByteString deriving(Ord,Eq,Generic) 
instance Hashable StringTuple 

type Database3 = M.Map StringTuple (M.Map B.ByteString Int) 
type DatabaseHM = HM.HashMap StringTuple (HM.HashMap B.ByteString Int) 
type DatabaseHT = HT.BasicHashTable StringTuple DatabaseInnerHT 
type DatabaseInnerHT = (HT.BasicHashTable B.ByteString Int) 

train4 :: [B.ByteString] -> Database3 
train4 words = foldl' update M.empty (zip3 words (drop 1 words) (drop 2 words)) 
    where update m (x,y,z) = M.insertWith' (inc z) (STP x y) (M.singleton z 1) m 
      inc k _ = M.insertWith' (+) k 1 

trainHM2 :: [B.ByteString] -> DatabaseHM 
trainHM2 words = trainHM2G words HM.empty 
    where 
    trainHM2G (x:y:[]) !hm = hm 
    trainHM2G (x:y:z:rem) !hm = trainHM2G (y:z:rem) (HM.insertWith (inc z) (STP x y) (HM.singleton z 1) hm) 
      where inc k _ = HM.insertWith (+) k 1 


trainHT :: [B.ByteString] -> IO (DatabaseHT) 
trainHT words = do 
hm <- HT.new 

trainHT' words hm 
where 
    trainHT' (x:y:[]) !hm = return hm 
    trainHT' (x:y:z:rem) !hm = do 
    let pair = STP x y 
    inCache <- HT.lookup hm pair 
    case inCache of 
    Nothing -> do 
    htN <- HT.new :: IO (DatabaseInnerHT) 
    HT.insert htN z $! 1 
    HT.insert hm pair $! htN 
    Just ht -> do 
    cvM <- HT.lookup ht z 
    case cvM of 
     Nothing -> HT.insert ht z 1 
     Just cv -> HT.insert ht z $! (cv+1) 
    trainHT' (y:z:rem) hm 

main = do contents <- B.readFile "76.txt" 
     let bcont = B.split ' ' $ contents 
     print $ length bcont 
     let db = train4 $ bcont 
     print $ "Built a DB of " ++ show (M.size db) ++ " words" 
     --let db = trainHM2 $ bcont 
     --print $ "Built a DB of " ++ show (HM.size db) ++ " words"   
     --db <- trainHT $ (bcont) 
     --print $ "Built a DB" 

臨時C++ 11音譯（需要-fpermissive編譯，感覺自由糾正它）：

#include <iostream> 
#include <fstream> 
#include <sstream> 
#include <vector> 
#include <unordered_map> 
#include <tuple> 

/* 
Hash stuff here 
Taken from https://stackoverflow.com/a/7111460/314327 
*/ 
size_t hash_combiner(size_t left, size_t right) //replacable 
{ return left^right;} 

template<int index, class...types> 
struct hash_impl { 
    size_t operator()(size_t a, const std::tuple<types...>& t) const { 
     typedef typename std::tuple_element<index, std::tuple<types...>>::type nexttype; 
     hash_impl<index-1, types...> next; 
     size_t b = std::hash<nexttype>()(std::get<index>(t)); 
     return next(hash_combiner(a, b), t); 
    } 
}; 
template<class...types> 
struct hash_impl<0, types...> { 
    size_t operator()(size_t a, const std::tuple<types...>& t) const { 
     typedef typename std::tuple_element<0, std::tuple<types...>>::type nexttype; 
     size_t b = std::hash<nexttype>()(std::get<0>(t)); 
     return hash_combiner(a, b); 
    } 
}; 

namespace std { 
    template<class...types> 
    struct hash<std::tuple<types...>> { 
     size_t operator()(const std::tuple<types...>& t) { 
      const size_t begin = std::tuple_size<std::tuple<types...>>::value-1; 
      return hash_impl<begin, types...>()(1, t); //1 should be some largervalue 
     } 
    }; 
} 

/* 
Hash stuff end 
*/ 

using namespace std; 

/* 
Split, from https://stackoverflow.com/a/236803/314327 
*/ 
vector<string> &split(const string &s, char delim, vector<string> &elems) { 
stringstream ss(s); 
string item; 
while (getline(ss, item, delim)) { 
elems.push_back(item); 
} 
return elems; 
} 

vector<string> split(const string &s, char delim) { 
vector<string> elems; 
split(s, delim, elems); 
return elems; 
} 
/* 
Split end 
*/ 

typedef tuple<string,string> STP; 

unordered_map< STP,unordered_map< string,int > > train(vector<string> &words) 
{ 
unordered_map< STP,unordered_map< string,int > > cache; 

for(int i=0;i<words.size()-2;i++) 
{ 
    STP tup = make_tuple(words[i],words[i+1]); 
    auto it = cache.find(tup); 
    if(it!=cache.end()) 
    { 
    auto it2 = it->second.find(words[i+2]); 
    if(it2!=it->second.end()) 
    { 
    it2->second += 1; 
    } 
    else 
    it->second[words[i+2]] = 1; 
    } 
    else 
    {  
    unordered_map< string,int > cacheInner; 
    cacheInner[words[i+2]] = 1; 
    cache[tup] = cacheInner; 
    } 
} 

return cache; 
} 

int main() 
{ 
ifstream ifs("76.txt"); 
stringstream buf; 
buf << ifs.rdbuf(); 
string contents(buf.str()); 

auto words = split(contents,' '); 
cout << words.size(); 

auto wordCache = train(words); 

cout << "\nHashtable count " << wordCache.size(); 

cout << "\n"; 
return 0; 
} 

並且結果：

C++（GCC 4.6.3）

$ g++ -O3 -fpermissive -std=c++0x cpptest.cpp -o cpptest 
$ /usr/bin/time -f "%E" ./cpptest 
1255153 

Hashtable count 64442 
0:01.02 

的Python（2.7）

$ /usr/bin/time -f "%E" ./pytest.py 
Total of 1255153 splitted words 
Built a db of length 64442 
0:02.62 

的Haskell（GHC 7.4 .1） - 「train4」

$ ghc -fllvm -O2 -rtsopts -fforce-recomp -funbox-strict-fields hasktest.hs -o hasktest 
[1 of 1] Compiling Main    (hasktest.hs, hasktest.o) 
Linking hasktest ... 
$ /usr/bin/time -f "%E" ./hasktest 
1255153 
"Built a DB of 64442 words" 
0:06.35 

哈斯克爾 - 「trainHM2」

$ /usr/bin/time -f "%E" ./hasktest 
1255153 
"Built a DB of 64442 words" 
0:04.23 

哈斯克爾 - 「trainHT」 - （？這是接近到什麼Python不爲字典，我猜）使用基本型

$ /usr/bin/time -f "%E" ./hasktest 
1255153 
"Built a DB" 
0:10.42 

使用線性或杜鵑兩個表

0:06.06 
0:05.69 

使用杜鵑用於最外層表和線性在裏面

0:04.17 

剖析表明，有相當多的GC的，所以，用+ RTS -A256M

0:02.11 

_{輸入數據，我選擇了76.txt作爲答案的一個指示和複製的全文12次。它應該達到約7 MB。}

_{測試是在一個VirtualBox容器中的Ubuntu 12.04上運行的，使用一個i5-520M內核。不止一次運行，所有結果都非常接近。}

最後的結果是這個微基準精緻漂亮，但還有什麼代碼改善，考慮到：

• 杜鵑&線性可能更適合這個數據集，但「通用」Python解決方案在這方面沒有多少優化就很好，Valgrind報告稱C++ & Python版本大約需要60MBs，而Haskell RTS從125MBs（Cuckoo & Linear）至409MBs（基本的，較大的堆）的內存用於同一任務。不會在生產環境中調整垃圾收集器是否有害？是否有可能重構代碼，所以它的內存使用量更少？

更新：

我猜 「減少垃圾」 就是我要找的。我知道Haskell不能像C++那樣工作，但我想知道是否有可能減少命令代碼中產生的垃圾，因爲C++示例在沒有任何空間泄漏的情況下消耗了一半內存。它希望是內存使用和執行時間方面的改進（因爲GC會更少）。

更新2：

計算表施工期間的長度減少了內存佔用肯定（下降到大約40MBs，實際上！），這將導致GC需要更長的時間，導致較慢的執行時間（由於丟棄了從列表中懶得讀出的值，我認爲？）。

是的，哈希表的操作需要很長時間。我會嘗試模仿改動，看看它是否有進一步改善。

Answer 1

這不是一個真正的答案，但它太多了，所以我會把它放在這裏，直到有更好的東西出現。我沒有看到你的哈希表代碼（我真正看過的唯一部分）有什麼明顯的錯誤，除了一些重構/打高爾夫。

首先，內存使用情況對我來說並不是很讓人意外。使用-A256M，您要求RTS的最小分配區域爲256M，這樣可以佔用您的內存使用量。如果數據在GC之後被升級或複製，內存使用量將會增加。另外請注意，相對於其他語言，Haskell數據結構往往有點缺乏內存空間，例如參見Memory footprint of Haskell data types。考慮到這兩個因素，我並不感到有大量分配區域的內存使用總量。

像HashMap或字符串trie結構可以使用更少的內存，伴隨着使用哈希表以外的數據結構的附帶缺點。

說到分配區域，這個代碼有點微的基準，因爲幾乎所有分配的數據（主要是字節串數據和內部散列表值）都是長期存在的（它們持續到程序結束時）。這使得您的測試程序處於一個非常大的分配區域特別有利的情況，而如果這個數據庫構造只是較大程序的一部分，則較大區域的成本可能占主導地位。

對於生產環境的最佳GC設置，很難告訴外部實際完整程序的上下文。我可以說，如果表現真的很重要，值得花些時間調整GC標誌。如果您啓用了線程運行時，則更是如此。

除了內存問題，我強烈懷疑hashtables包在這裏對你有效。根據配置文件，4個最昂貴的功能是lookup/go,lookup,insert和delete'.go。我認爲如果它的價值相當於Data.Map.alter，那麼你的一些業務可以合併在一起以提高性能。畢竟，如果Python字典沒有針對像cache[key] += 1這樣的案例進行優化，我會感到非常驚訝。