哈斯克尔和可变结构的表现
我正在研究优化Haskell代码中给出的答案，并注意到与Python相比，使用小输入确实会导致Haskell运行更快。
但随着数据集的规模不断扩大，Python占据了领先地位。 使用基于散列表的版本提高了性能，但仍然落后。
更糟糕的是，我尝试将Python的字典转换为哈希表，并观察到了一个艰难的性能问题。 我真的很想知道发生了什么，因为我需要为将来的应用程序使用可变结构。
这里稍微修改一下Python代码：
#! /usr/bin/env python2.7
import random
import re
import cPickle
class Markov:
def __init__(self, filenames):
self.filenames = filenames
self.cache = self.train(self.readfiles())
picklefd = open("dump", "w")
cPickle.dump(self.cache, picklefd)
print "Built a db of length "+str(len(self.cache))
picklefd.close()
def train(self, text):
splitted = text.split(' ')
print "Total of %d splitted words" % (len(splitted))
cache = {}
for i in xrange(len(splitted)-2):
pair = (splitted[i], splitted[i+1])
followup = splitted[i+2]
if pair in cache:
if followup not in cache[pair]:
cache[pair][followup] = 1
else:
cache[pair][followup] += 1
else:
cache[pair] = {followup: 1}
return cache
def readfiles(self):
data = ""
for filename in self.filenames:
fd = open(filename)
data += fd.read()
fd.close()
return data
Markov(["76.txt"])
Haskell与原始响应（ train4 ），其哈希映射变体（ 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音译（需要-fmissmiss编译，随时纠正它）：
#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
Haskell - “trainHM2”
$ /usr/bin/time -f "%E" ./hasktest
1255153
"Built a DB of 64442 words"
0:04.23
Haskell - “trainHT” - 使用Basic变体（接近Python为字典所做的事情，我猜？）
$ /usr/bin/time -f "%E" ./hasktest
1255153
"Built a DB"
0:10.42
对这两个表使用Linear或Cuckoo
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内核。 不止一次运行，所有结果都非常接近。
最后的结果对于这个微基准是非常好的，但是在代码中还有什么可以改进的地方 ，考虑到：
60MBs而Haskell RTS则报告从同一任务的125MBs （杜鹃和线性）到409MBs （基本，更大的堆）内存。 不会在生产环境中调整垃圾收集器是否有害？ 是否有可能重构代码，所以它的内存使用量更少？ 更新：
我想“减少垃圾”是我正在寻找的。 我知道Haskell不能像C ++那样工作，但我想知道是否有可能减少命令代码中产生的垃圾，因为C ++示例在没有任何空间泄漏的情况下消耗了一半内存。 它希望是内存使用和执行时间方面的改进（因为GC会更少）。
更新2：
在构建表的过程中计算长度会降低内存占用量（实际上降低到40MBs左右），这会导致GC花费更长时间，从而导致执行时间变慢（由于丢弃了从名单，我想？）。
是的，哈希表的操作需要花费大量的时间。 我会尝试模仿改动，看看它是否有进一步改善。
这不是一个真正的答案，但是评论太多了，所以我会把它放在这里，直到有更好的东西出现。 我没有看到你的哈希表代码（我真正看过的唯一部分）有什么明显的错误，除了一些重构/打高尔夫。
首先，内存使用情况对我来说并不是很令人惊讶。 使用-A256M ，您要求RTS的最小分配面积为256M，这样可以占用内存。 如果数据在GC之后被升级或复制，内存使用量将会增加。 另外请注意，相对于其他语言，Haskell数据结构往往有点内存空洞，请参阅Haskell数据类型的内存占用情况。 考虑到这两个因素，我并不感到有大量分配区域的内存使用总量。
像HashMap或字符串trie这样的结构可以使用更少的内存，伴随使用哈希表以外的数据结构。
说到分配区域，这个代码有点微乎其微，因为几乎所有分配的数据（主要是字节串数据和内部散列表值）都是长期存在的（它们持续到程序结束时）。 这使得您的测试程序处于一个非常大的分配区域特别有利的情况，而如果这个数据库构造只是较大程序的一部分，则较大区域的成本可能占主导地位。
至于生产环境的最佳GC设置，很难告诉外部实际完整程序的环境。 我可以说，如果表现真的很重要，值得花些时间调整GC标志。 如果您启用了线程运行时，则更是如此。
除了内存问题，我强烈怀疑哈希表包在这里对你有用。 根据配置文件，4个最delete'.go函数是lookup/go ， lookup ， insert和delete'.go 。 我认为如果它具有Data.Map.alter的等价物， Data.Map.alter您的一些操作可以合并以获得性能提升。 如果Python字典没有针对cache[key] += 1等情况进行优化，我会感到非常惊讶。
上一篇: Haskell and mutable structures' performance
下一篇: Dowloading image resources from https with LoopJ AndroidAsyncHttp