c＃to C++ dictionary unordered_map results

Question

我已經做了幾年的c＃現在，我正在嘗試學習一些新的東西。所以我決定看看C++，以不同的方式瞭解編程。

我一直在做大量的閱讀，但我今天剛開始寫一些代碼。

在我的Windows 7/64位機，運行VS2010，我創建了兩個項目： 1）C＃項目，讓我寫的東西，我習慣的方式。 2）一個C++「makefile」項目，讓我玩耍，試圖實現同樣的事情。據我所知，這不是一個.NET項目。

我試圖用10K值填充字典。出於某種原因，C++的速度要慢幾個數量級。

下面是c＃下面。注意我把一個功能的時間測量之後，以確保它沒有被「優化」掉由編譯器：

var freq = System.Diagnostics.Stopwatch.Frequency; 

int i; 
Dictionary<int, int> dict = new Dictionary<int, int>(); 
var clock = System.Diagnostics.Stopwatch.StartNew(); 

for (i = 0; i < 10000; i++) 
    dict[i] = i; 
clock.Stop(); 

Console.WriteLine(clock.ElapsedTicks/(decimal)freq * 1000M); 
Console.WriteLine(dict.Average(x=>x.Value)); 
Console.ReadKey(); //Don't want results to vanish off screen 

這裏是C++，沒有太多的思想已經進入了它（努力學習，對嗎？） int input;

LARGE_INTEGER frequency;  // ticks per second 
LARGE_INTEGER t1, t2;   // ticks 
double elapsedTime; 

// get ticks per second 
QueryPerformanceFrequency(&frequency); 

int i; 
boost::unordered_map<int, int> dict; 
// start timer 
QueryPerformanceCounter(&t1); 

for (i=0;i<10000;i++) 
    dict[i]=i; 

// stop timer 
QueryPerformanceCounter(&t2); 

// compute and print the elapsed time in millisec 
elapsedTime = (t2.QuadPart - t1.QuadPart) * 1000.0/frequency.QuadPart; 
cout << elapsedTime << " ms insert time\n"; 
int input; 
cin >> input; //don't want console to disappear 

現在，一些注意事項。 I managed to find this related SO question.其中一個人寫了一個長的回答，提到WOW64歪曲的結果。我已經將項目設置爲釋放，並通過了C++項目的「屬性」選項卡，使所有聽起來像它會使它變得更快。將平臺更改爲x64，但我不確定這是否解決了他的問題。我對編譯器選項沒有經驗，也許你們有更多的線索？

呵呵，結果：c＃：0.32ms C++：8.26ms。這有點奇怪。我是否誤解了什麼.Quad是什麼意思？我從網上的某個地方複製了C++計時器代碼，通過了所有的boost安裝和include/libfile rigmarole。或者我可能在不知不覺中使用了不同的樂器？或者有一些我沒有用過的關鍵編譯選項？或者，也許C＃代碼是優化的，因爲平均值是一個常量？

這裏的C++命令行，從屬性頁面級> C/C++ - >命令行： /I 「C：\用戶\卡洛斯\桌面\ boost_1_47_0」/紫/ NOLOGO/W3/WX-/MP/Ox/Oi/Ot/GL/D「_MBCS」/ Gm-/EHsc/GS-/Gy-/arch：SSE2/fp：fast/Zc：wchar_t/Zc：forScope/Fp「x64 \ Release \ MakeTest .pch「/ Fa」x64 \ Release \「/ Fo」x64 \ Release \「/Fd"x64\Release\vc100.pdb」/ Gd/errorReport：隊列

任何幫助將不勝感激，謝謝。

Answer 1

一個簡單的分配器更改將大大減少這個時間。

boost::unordered_map<int, int, boost::hash<int>, std::equal_to<int>, boost::fast_pool_allocator<std::pair<const int, int>>> dict; 

0.9ms在我的系統上（從10ms前）。這表明，實際上，絕大多數時間並不在哈希表中，而是在分配器中。之所以這是一個不公平的比較，是因爲你的GC永遠不會收集這樣一個微不足道的程序，給它帶來不適當的性能優勢，並且本地分配器會大量緩存空閒的內存 - 但這絕不會在這樣一個瑣碎的事情中發揮作用例如，因爲你從來沒有分配或解除分配任何東西，所以沒有什麼可以緩存的。

最後，Boost池實現是線程安全的，而您從不玩線程，因此GC可以回退到單線程實現，這將更快。

我使用了一個手動滾動的，非釋放的非線程安全池分配器，並將C++下降到0.525ms，C＃下降到0.45ms（在我的機器上）。結論：由於兩種語言的內存分配方案不同，您的原始結果非常不一致，一旦解決了這個問題，差異就會變得相對較小。

一個自定義散列器（如Alexandre的答案中所述）將我的C++時間降低到0.34ms，現在它比C＃更快。

static const int MaxMemorySize = 800000; 
static int FreedMemory = 0; 
static int AllocatorCalls = 0; 
static int DeallocatorCalls = 0; 
template <typename T> 
class LocalAllocator 
{ 
    public: 
     std::vector<char>* memory; 
     int* CurrentUsed; 
     typedef T value_type; 
     typedef value_type * pointer; 
     typedef const value_type * const_pointer; 
     typedef value_type & reference; 
     typedef const value_type & const_reference; 
     typedef std::size_t size_type; 
     typedef std::size_t difference_type; 

    template <typename U> struct rebind { typedef LocalAllocator<U> other; }; 

    template <typename U> 
    LocalAllocator(const LocalAllocator<U>& other) { 
     CurrentUsed = other.CurrentUsed; 
     memory = other.memory; 
    } 
    LocalAllocator(std::vector<char>* ptr, int* used) { 
     CurrentUsed = used; 
     memory = ptr; 
    } 
    template<typename U> LocalAllocator(LocalAllocator<U>&& other) { 
     CurrentUsed = other.CurrentUsed; 
     memory = other.memory; 
    } 
    pointer address(reference r) { return &r; } 
    const_pointer address(const_reference s) { return &r; } 
    size_type max_size() const { return MaxMemorySize; } 
    void construct(pointer ptr, value_type&& t) { new (ptr) T(std::move(t)); } 
    void construct(pointer ptr, const value_type & t) { new (ptr) T(t); } 
    void destroy(pointer ptr) { static_cast<T*>(ptr)->~T(); } 

    bool operator==(const LocalAllocator& other) const { return Memory == other.Memory; } 
    bool operator!=(const LocalAllocator&) const { return false; } 

    pointer allocate(size_type count) { 
     AllocatorCalls++; 
     if (*CurrentUsed + (count * sizeof(T)) > MaxMemorySize) 
      throw std::bad_alloc(); 
     if (*CurrentUsed % std::alignment_of<T>::value) { 
      *CurrentUsed += (std::alignment_of<T>::value - *CurrentUsed % std::alignment_of<T>::value); 
     } 
     auto val = &((*memory)[*CurrentUsed]); 
     *CurrentUsed += (count * sizeof(T)); 
     return reinterpret_cast<pointer>(val); 
    } 
    void deallocate(pointer ptr, size_type n) { 
     DeallocatorCalls++; 
     FreedMemory += (n * sizeof(T)); 
    } 

    pointer allocate() { 
     return allocate(sizeof(T)); 
    } 
    void deallocate(pointer ptr) { 
     return deallocate(ptr, 1); 
    } 
}; 
int main() { 
    LARGE_INTEGER frequency;  // ticks per second 
    LARGE_INTEGER t1, t2;   // ticks 
    double elapsedTime; 

    // get ticks per second 
    QueryPerformanceFrequency(&frequency); 
    std::vector<char> memory; 
    int CurrentUsed = 0; 
    memory.resize(MaxMemorySize); 

    struct custom_hash { 
     size_t operator()(int x) const { return x; } 
    }; 
    boost::unordered_map<int, int, custom_hash, std::equal_to<int>, LocalAllocator<std::pair<const int, int>>> dict(
     std::unordered_map<int, int>().bucket_count(), 
     custom_hash(), 
     std::equal_to<int>(), 
     LocalAllocator<std::pair<const int, int>>(&memory, &CurrentUsed) 
    ); 

    // start timer 
    std::string str; 
    QueryPerformanceCounter(&t1); 

    for (int i=0;i<10000;i++) 
     dict[i]=i; 

    // stop timer 
    QueryPerformanceCounter(&t2); 

    // compute and print the elapsed time in millisec 
    elapsedTime = ((t2.QuadPart - t1.QuadPart) * 1000.0)/frequency.QuadPart; 
    std::cout << elapsedTime << " ms insert time\n"; 
    int input; 
    std::cin >> input; //don't want console to disappear 
} 

Answer 2

存儲按升序添加的連續數字整數鍵序列絕對不是散列表優化的對象。

使用數組，或者生成隨機值。

並做一些檢索。散列表高度優化以便檢索。

Answer 3

的Visual Studio TR1 unordered_map相同stdext ::的hash_map：

另一個線程問，爲什麼它會執行緩慢，看我的鏈接到其他人已經發現了同樣的問題的答案。得出的結論是，當使用其他的hash_map實現用C+++：

Alternative to stdext::hash_map for performance reasons

順便說一句。請記住，在C++中，與C＃相比，優化版本構建和非優化調試構建之間存在很大差異。

Answer 4

在插入元素之前，您可以嘗試使用dict.rehash(n)以及不同（大）值n，並查看這會如何影響性能。內存分配（它們在容器填充桶時發生）在C++中通常比在C＃中更昂貴，並且重新哈希也很重。對於std::vector和std::deque，模擬成員函數是reserve。

不同的重排策略和負載因子閾值（看看max_load_factor成員函數）也會極大地影響unordered_map的性能。

接下來，由於您使用的是VS2010，因此我建議您使用<unordered_map>標題中的std::unordered_map。當您可以使用標準庫時，請勿使用boost。

使用的實際散列函數可能會極大地影響性能。您可以嘗試以下方法：

struct custom_hash { size_t operator()(int x) const { return x; } }; 

並使用std::unordered_map<int, int, custom_hash>。

最後，我同意這是散列表的糟糕用法。使用隨機值進行插入，可以更準確地瞭解發生的情況。測試散列表的插入速度根本不是愚蠢的，但散列表並不意味着存儲連續的整數。爲此，請使用vector。