7

我正在研究优化 Haskell 代码中给出的答案，并注意到与 Python 相比，使用小输入确实会导致 Haskell 运行速度更快。

但随着数据集规模的扩大，Python 占据了领先地位。使用基于 hashmap 的版本提高了性能，但仍然落后。

更糟糕的是，我尝试将 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

蟒蛇 (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。

测试在 VirtualBox 容器中的 Ubuntu 12.04 上运行，使用单个 i5-520M 内核。做了不止一次的运行，所有的结果都非常接近。

最后一个结果对于这个微基准测试来说非常好，但是考虑到以下几点，代码中还有什么需要改进的地方：

  • Cuckoo & Linear 可能更适合此数据集，但“通用”Python 解决方案在这方面无需太多优化即可使用，
  • Valgrind 报告说，C++ 和 Python 版本大约需要60MBs，而 Haskell RTS 报告从125MBs(Cuckoo&Linear) 到409MBs(Basic, large heap) 的任何地方的相同任务的内存。在生产环境中对垃圾收集器进行如此多的调整不会有害吗？是否可以重构代码以减少内存使用？

更新 ：

我想“减少垃圾”是我正在寻找的。我知道 Haskell 的工作方式与 C++ 不同，但我想知道是否可以减少命令式代码中产生的垃圾，因为 C++ 示例消耗了一半的内存而没有任何空间泄漏。它有望在内存使用和执行时间方面有所改进（因为 GC 会更少）。

更新 2：

在表构建期间计算长度确实减少了内存占用（40MBs实际上降低到大约 ！），这导致 GC 花费更长的时间，导致执行时间更慢（由于丢弃了从列表中延迟读取的值， 我相信 ？）。

是的，哈希表的操作需要大量时间。我会尝试模仿更改，看看它是否会进一步改进。

4

1 回答 1

4

这不是一个真正的答案，但是评论太多了，所以我会把它放在这里，直到出现更好的东西。除了一些重构/打高尔夫球之外，我没有看到您的哈希表代码（我真正看过的唯一部分）有任何明显错误。

首先，内存使用对我来说并不奇怪。使用-A256M时，您要求 RTS 的最小分配区域为 256M，这样就可以限制您的内存使用量。如果数据在 GC 后被提升或复制，内存使用量将会增加。另请注意，相对于其他语言，Haskell 数据结构往往有点占用内存，例如，参见Haskell 数据类型的内存占用。考虑到这两个因素，我对大分配区域的总内存使用情况并不感到惊讶。

HashMap 或 bytestring trie 之类的结构可以使用更少的内存，但使用哈希表以外的数据结构也有随之而来的缺点。

说到分配区域，这段代码有点像微基准，因为几乎所有分配的数据（主要是字节串数据和内部哈希表值）都是长期存在的（它们会持续到程序结束）。这会将您的测试程序置于一个非常大的分配区域特别有益的情况下，而如果此数据库构建只是较大程序的一部分，则较大区域的成本可能会占主导地位。

至于生产环境的最佳 GC 设置，在实际完整程序的上下文之外很难判断。我可以说，如果性能真的很重要，那么花一些时间调整 GC 标志是值得的。如果您启用了线程运行时，则更是如此。

除了内存问题，我强烈怀疑 hashtables 包在这里对你不利。根据配置文件，成本最高的 4 个函数是lookup/go、lookup、insert和delete'.go。我认为如果它具有等效的Data.Map.alter，则可以合并您的某些操作以提高性能。如果 Python 字典没有针对这种情况进行优化，我会感到非常惊讶cache[key] += 1。

于 2013-10-09T06:39:04.690 回答