fel*_*ace 7 performance haskell hashtable mutable
我正在研究优化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音译(需要-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
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
使用Cuckoo作为最外面的表,使用Linear作为内部
0:04.17
分析表明,有相当多的GC,因此,使用+ RTS -A256M
0:02.11
对于输入数据,我选择了76.txt,如其中一个答案中所示,并将整个文本重复12次.它应该大约7 MB.
使用单个i5-520M内核在VirtualBox容器中在Ubuntu 12.04上运行测试.完成不止一次运行,所有结果都非常接近.
对于这个微基准测试,最后的结果非常好,但是在代码中还有其他任何改进,考虑到:
60MBsHaskell RTS报告从125MBs(Cuckoo&Linear)到409MBs(基本的,更大的堆)内存的任何地方,以执行相同的任务.不会在生产环境中这么大地调整垃圾收集器是有害的吗？是否可以重构代码,以便减少内存使用量？更新:
我想"减少垃圾"是我正在寻找的.我知道Haskell的工作方式与C++不同,但是我想知道是否可以减少命令式代码中产生的垃圾,因为C++示例消耗了一半的内存而没有任何空间泄漏.它有望在内存使用和执行时间方面有所改进(因为GC会减少).
更新2:
在表构造期间计算长度确实减少了内存占用(40MBs实际上降到了!),这导致GC花费更长时间,导致执行时间变慢(由于丢弃了从列表中懒惰读取的值) , 我相信 ？).
是的,哈希表的操作需要花费大量时间.我会尝试模仿改动,看它是否进一步改善.
这并不是一个真正的答案，但它太多了，无法发表评论，所以我将把它放在这里，直到出现更好的答案。除了一些重构/打高尔夫球之外，我没有发现您的哈希表代码有任何明显的错误（我真正查看的唯一部分）。
首先，内存使用量对我来说并不奇怪。使用 时-A256M，您要求 RTS 的最小分配区域为 256M，这样就为您的内存使用设置了下限。如果 GC 之后数据被提升或复制，内存使用量将会增加。另请注意，相对于其他语言，Haskell 数据结构往往会占用一些内存，请参阅Haskell 数据类型的内存占用示例。考虑到这两个因素，我对大分配区域的总内存使用量并不感到惊讶。
像 HashMap 或字节串 trie 这样的结构可以使用更少的内存，但使用哈希表以外的数据结构也有随之而来的缺点。
说到分配区域，这段代码有点像微基准测试，因为几乎所有分配的数据（主要是字节串数据和内部哈希表值）都是长期存在的（它们持续到程序结束）。这使您的测试程序处于这样一种情况：非常大的分配区域特别有利，而如果此数据库构建只是较大程序的一部分，则较大区域的成本可能会占主导地位。
至于生产环境的最佳 GC 设置，在实际完整程序的上下文之外很难判断。我可以说，如果性能真的很重要，那么花一些时间调整 GC 标志是值得的。如果您启用了线程运行时，情况更是如此。
除了内存问题之外，我强烈怀疑 hashtables 包在这里对你不利。根据配置文件，成本最高的 4 个函数是lookup/go、lookup、insert和delete'.go。我认为，如果它具有相当于 的功能Data.Map.alter，则可以合并您的一些操作以提高性能。如果 Python 字典没有针对像cache[key] += 1这样的情况进行优化，我会感到非常惊讶。
| 归档时间： |
|
| 查看次数： |
905 次 |
| 最近记录： |