Từ điển C# đến C++ đến kết quả unordered_map

Question

Tôi đã thực hiện một vài năm của C# bây giờ và tôi đang cố gắng tìm hiểu một số nội dung mới. Vì vậy, tôi quyết định có một cái nhìn tại c + +, để tìm hiểu về lập trình theo một cách khác.

Tôi đã thực hiện rất nhiều lượt đọc, nhưng tôi mới bắt đầu viết một số mã ngay hôm nay.

Trên máy tính Windows 764 bit của tôi, chạy VS2010, tôi đã tạo hai dự án: 1) Dự án C# cho phép tôi viết mọi thứ theo cách tôi đã quen. 2) Dự án C++ "makefile" cho phép tôi chơi xung quanh, cố gắng thực hiện cùng một điều. Từ những gì tôi hiểu, đây không phải là một dự án .NET.

Tôi đã cố gắng điền một từ điển có giá trị 10K. Đối với một số lý do, C++ là đơn đặt hàng của cường độ chậm hơn.

Đây là C# bên dưới. Lưu ý tôi đặt trong một chức năng sau khi đo lường thời gian để đảm bảo nó không phải là "tối ưu hóa" đi bởi trình biên dịch:

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 

Đây là C++, không nhiều suy nghĩ đã đi vào nó (cố gắng tìm hiểu, phải không?) int đầu vào;

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 

Bây giờ, một số lưu ý. I managed to find this related SO question. Một trong những người đã viết một câu trả lời dài đề cập đến WOW64 nghiêng kết quả. Tôi đã thiết lập dự án để phát hành và đi qua tab "thuộc tính" của dự án C++, cho phép mọi thứ có vẻ như nó sẽ làm cho nó nhanh. Thay đổi nền tảng thành x64, mặc dù tôi không chắc liệu có giải quyết vấn đề wow64 của anh ấy hay không. Tôi không có kinh nghiệm với các tùy chọn trình biên dịch, có lẽ các bạn có nhiều hơn một đầu mối?

Ồ, và kết quả: C#: 0,32ms C++: 8,26ms. Điều này hơi lạ. Tôi đã hiểu sai về điều gì .Quad có nghĩa là gì? Tôi đã sao chép mã bộ đếm thời gian C++ từ một nơi nào đó trên web, trải qua tất cả cài đặt tăng cường và bao gồm/libfile rigmarole. Hoặc có lẽ tôi đang thực sự sử dụng các công cụ khác nhau một cách vô tình? Hoặc có một số tùy chọn biên dịch quan trọng mà tôi đã không được sử dụng? Hoặc có lẽ mã C# được tối ưu hóa bởi vì trung bình là một hằng số?

Đây là dòng C++ lệnh, từ tài sản Trang-> C/C++ -> Command Line: /I "C: \ Users \ Carlos \ Desktop \ boost_1_47_0"/Zi/nologo/W3/WX-/MP/Ox/Oi/Ot/GL/D "_MBCS"/Gm-/EHsc/GS-/Gy-/kiến ​​trúc: SSE2/fp: nhanh/Zc: wchar_t/Zc: forScope/Fp "x64 \ Release \ MakeTest .pch "/ Fa" x64 \ Release \ "/ Fo" x64 \ Release \ "/Fd"x64\Release\vc100.pdb"/Gd/errorReport: hàng đợi

Mọi trợ giúp sẽ được đánh giá cao, cảm ơn.

Answer 1

Thay đổi cấp phát đơn giản sẽ giảm thời gian xuống rất nhiều.

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

0.9ms trên hệ thống của tôi (từ 10ms trước). Điều này gợi ý với tôi rằng thực sự, phần lớn thời gian của bạn không được chi tiêu trong bảng băm nào cả, nhưng trong bộ cấp phát. Lý do rằng đây là một sự so sánh không công bằng bởi vì GC của bạn sẽ không bao giờ thu thập trong một chương trình tầm thường như vậy, mang lại cho nó một lợi thế hiệu suất quá mức, và những người cấp phát bản địa làm bộ nhớ đệm đáng kể của bộ nhớ miễn phí - nhưng điều đó sẽ không bao giờ xảy ra Ví dụ, bởi vì bạn chưa bao giờ phân bổ hoặc phân bổ bất cứ điều gì và do đó không có gì để cache.

Cuối cùng, việc nâng cấp hồ bơi Boost là an toàn chỉ, trong khi bạn không bao giờ chơi với chuỗi sao cho GC chỉ có thể quay trở lại triển khai một luồng, sẽ nhanh hơn nhiều.

Tôi đã sử dụng bộ phân bổ hồ bơi không an toàn, không được phân luồng và được chuyển xuống 0,525ms cho C++ thành 0,45ms cho C# (trên máy của tôi). Kết luận: Kết quả ban đầu của bạn rất sai lệch vì các lược đồ phân bổ bộ nhớ khác nhau của hai ngôn ngữ, và một khi đã được giải quyết, thì sự khác biệt trở nên tương đối tối thiểu.

Máy chia tùy chỉnh (như được mô tả trong câu trả lời của Alexandre) đã giảm thời gian C++ xuống 0.34ms, nhanh hơn 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

Việc lưu trữ chuỗi số nguyên liên tiếp được thêm vào theo thứ tự tăng dần chắc chắn KHÔNG phải bảng băm nào được tối ưu hóa.

Sử dụng một mảng hoặc tạo ra các giá trị ngẫu nhiên khác.

Và thực hiện một số lần truy lục. Bảng băm được tối ưu hóa cao để truy xuất.

Answer 3

Visual Studio TR1 unordered_map cũng giống như stdext :: hash_map:

Một chủ đề thắc mắc tại sao nó thực hiện chậm, xem câu trả lời của tôi có liên hệ với những người khác rằng đã phát hiện ra vấn đề tương tự.Kết luận là sử dụng khác thực hiện hash_map khi trong C+++:

Alternative to stdext::hash_map for performance reasons

Btw. hãy nhớ khi nào trong C++ thì có sự khác biệt lớn giữa bản dựng gỡ lỗi được xây dựng và tối ưu hóa không được tối ưu hóa so với C#.

Answer 4

Bạn có thể thử dict.rehash(n) với các giá trị khác nhau (lớn) là n trước khi chèn các phần tử và xem điều này tác động đến hiệu suất như thế nào. Phân bổ bộ nhớ (chúng diễn ra khi thùng chứa đầy các thùng) thường đắt hơn trong C++ so với C#, và việc phục hồi cũng rất nặng. Đối với std::vector và std::deque, chức năng thành viên tương tự là reserve.

Chính sách khôi phục khác nhau và ngưỡng yếu tố tải (có xem chức năng thành viên max_load_factor) cũng sẽ tác động rất lớn đến hiệu suất của unordered_map.

Tiếp theo, vì bạn đang sử dụng VS2010, tôi khuyên bạn nên sử dụng std::unordered_map từ tiêu đề <unordered_map>. Không sử dụng boost khi bạn có thể sử dụng thư viện chuẩn.

Hàm băm thực tế được sử dụng có thể ảnh hưởng lớn đến hiệu suất. Bạn có thể thử các cách sau:

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

và sử dụng std::unordered_map<int, int, custom_hash>.

Cuối cùng, tôi đồng ý rằng đây là cách sử dụng bảng băm kém. Sử dụng các giá trị ngẫu nhiên để chèn, bạn sẽ có được bức tranh chính xác hơn về những gì đang diễn ra. Tốc độ chèn thử nghiệm của các bảng băm không phải là ngu ngốc chút nào, nhưng các bảng băm không có nghĩa là lưu trữ các số nguyên liên tiếp. Sử dụng một số vector cho việc này.