하스켈 및 변경 가능한 구조의 성능

Question

나는 Optimizing Haskell code에 주어진 응답을 연구 중이었고 작은 입력을 사용하면 실제로 파이썬에 비해 더 빠른 하스켈이 실행된다는 것을 알게되었습니다.

그러나 데이터 세트의 크기가 커지면서 파이썬이 선두를 차지했습니다. 해시 맵 기반 버전을 사용하면 성능이 향상되었지만 여전히 뒤떨어져 있습니다.

더 나쁜 것은, 파이썬의 사전을 해시 테이블로 음역으로 변환 해 보았는데, 성능이 크게 떨어지는 것을 관찰했습니다. 나는 미래의 어플리케이션을 위해 변경 가능한 구조가 필요할 것이므로 실제로 진행되는 것을 이해하고 싶습니다.

#! /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"]) 

하스켈 원래 응답 (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 음역 (컴파일이 필요합니다.) (++

$ 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 

하스켈 (GHC 7.4 GCC 4.6.3을

C :

#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; 
} 

을 그리고 그 결과는 다음과 같습니다)을 수정합니다 .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 

하스켈 - 선형 또는 뻐꾸기를 사용하여 기본 변형 사용

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

- "trainHT"(파이썬 사전을 위해, 내가 생각하는 일에 가까운?) 내부

에 바깥 쪽 테이블과 선형에 대한 뻐꾸기를 사용하여 두 테이블

0:06.06 
0:05.69 

에 대한

0:04.17 

답변 중 하나에 표시하고, 중복으로 프로파일이 + RTS -A256M 입력 데이터에 대한

0:02.11 

_{으로, GC 꽤 많은 있다는 걸 보여, 그래서했다}

, 나는 76.txt를 선택 전체 텍스트 12 번. 약 7MB 정도가되어야합니다.

_{테스트는 i5-520M 코어 하나를 사용하여 VirtualBox 컨테이너에서 Ubuntu 12.04에서 실행되었습니다. 한번에 한 번 이상 실행하면 모든 결과가 거의 비슷합니다.}

마지막 결과는이 마이크로 벤치 꽤 괜찮지 만, 는 고려, 코드 개선하기 위해 무엇 있습니다 :

• 뻐꾸기 & 선형이 데이터 세트에 대한 더 적합 할 수는 있지만,
• Valgrind는 C++ & Python 버전은 약 60MBs을 사용하는 반면, 하스켈 RTS는 125MBs (Cuckoo)의 모든 부분을보고한다고 Valgrind는보고합니다.Linear)에서 409MBs (기본, 더 큰 힙)까지 동일한 작업을 수행 할 수 있습니다. 프로덕션 환경에서 가비지 컬렉터를 조정하지 않는 것이 좋지 않습니까? 메모리 사용량이 적어 지도록 코드를 리팩토링 할 수 있습니까?

업데이트 :

내가 찾고 있어요 "쓰레기를 줄이는 것이"추측 무엇. 하스켈은 C++과 같은 방식으로 작동하지 않는다는 것을 알고 있지만, C++ 예제는 공간 누수없이 메모리의 절반을 소비하므로 명령형 코드에서 생성되는 쓰레기를 줄일 수 있는지 알고 싶습니다. 메모리 사용량과 실행 시간면에서 개선 될 것으로 기대됩니다 (GC가 적어짐에 따라).

업데이트 2 : 테이블의 건설 기간 동안의 길이를 계산

은 (실제로 주위 40MBs 아래로!) 확실히 메모리 풋 프린트를 감소시켰다, 느린 실행의 결과로, GC 시간이 더 걸릴 원인이되는 (목록에서 느슨하게 읽은 값을 버리는 것으로 인해 나는 추정 했습니까?).

예, 해시 테이블의 작업에는 상당한 시간이 걸립니다. 나는 그것이 더 이상 향상되는지보기 위해 변경을 모방하려고 노력할 것이다.

Answer 1

이것은 실제로 대답이 아니지만 설명에 넣기에는 너무 많아서 더 나은 것이 나올 때까지 여기에 놓을 것입니다. 리팩토링/골프의 비트 이외에 분명히 해시 테이블 코드에 문제가있는 것을 보지 못했습니다 (내가 실제로 본 유일한 부분).

첫째, 메모리 사용량이 저에게는 그리 놀라운 것이 아닙니다. -A256M을 사용하면 RTS에 256M의 최소 할당 영역이 있어야하므로 메모리 사용량에 바닥을 둡니다. GC 후에 데이터가 승격 또는 복사되면 메모리 사용량이 증가합니다. 또한 Haskell 데이터 구조는 다른 언어에 비해 메모리가 부족한 경향이 있습니다 (예 : Memory footprint of Haskell data types). 이 두 가지 요인 모두를 고려할 때 큰 할당 영역에서 총 메모리 사용량에 놀라지 않습니다.

HashMap 또는 bytestring trie와 같은 구조는 해시 테이블 이외의 데이터 구조를 사용하는 부수적 인 단점이있는 적은 메모리를 사용할 수 있습니다.

할당 영역과 관련하여이 코드는 거의 모든 할당 된 데이터 (주로 바이트 데이터 및 내부 해시 테이블 값)가 오래 지속되는 (프로그램이 종료 될 때까지 지속되는) 마이크로 벤치 마크입니다. 이것은 테스트 프로그램을 매우 큰 할당 영역이 특히 유익한 상황에 놓는 반면,이 데이터베이스 구성이 큰 프로그램의 일부인 경우 더 큰 영역의 비용이 지배적이 될 수 있습니다.

프로덕션 환경에 대한 최적의 GC 설정에 대해서는 실제 전체 프로그램의 컨텍스트 외부에서 알기가 매우 어렵습니다. 성능이 중요하다면 GC 플래그를 조정하는 데 시간을 할애 할 가치가 있다고 말할 수 있습니다. 스레드 런타임을 사용하도록 설정 한 경우에도 마찬가지입니다.

메모리 문제 외에도 hashtables 패키지가 여기에서 작동하고 있다고 생각합니다. 프로필에 따르면 가장 값 비싼 4 가지 기능은 lookup/go, lookup, insert 및 delete'.go입니다. 나는 그것이 Data.Map.alter과 동등한 것이라면, 당신의 작업 중 일부는 성능 향상을 위해 합쳐질 수 있다고 생각한다. 어쨌든 파이썬 사전이 cache[key] += 1 같은 경우에 최적화되지 않았다면 나는 놀랄 것입니다.