C# do C++ słownik do niezamkniętych_map wyników

Question

Zrobiłem kilka lat C# teraz i próbuję nauczyć się nowych rzeczy. Postanowiłem więc rzucić okiem na C++, aby poznać programowanie w inny sposób.

Robiłem mnóstwo czytania, ale właśnie zacząłem dzisiaj pisać jakiś kod.

Na moim komputerze z Windows 7/64 bit, z uruchomionym VS2010, stworzyłem dwa projekty: 1) Projekt C#, który pozwala mi pisać rzeczy tak, jak jestem przyzwyczajony. 2) Projekt "makefile" w C++, który pozwala mi się bawić, próbując zaimplementować to samo. Z tego co rozumiem, to NIE jest projekt .NET.

Mam do wypełnienia słownik z wartości 10K. Z jakiegoś powodu C++ jest wolniejsze o rząd wielkości.

Oto C# poniżej. Uwaga umieścić w zależności od pomiaru czasu, aby upewnić się, że nie został „zoptymalizowany” z dala przez kompilator:

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 

Oto C++, nie wiele myśli poszła do niego (starając się dowiedzieć, prawda?) int wejście;

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 

Teraz niektóre zastrzeżenia. I managed to find this related SO question. Jeden z chłopaków napisał długą odpowiedź, w której WOW64 przekrzywił wyniki. Przygotowałem projekt do wydania i przejścia przez zakładkę "właściwości" projektu C++, dzięki czemu wszystko, co zabrzmiało tak, mogłoby przyspieszyć działanie. Zmieniono platformę na x64, ale nie jestem pewien, czy to rozwiązuje problem wow64. Nie mam takich doświadczeń z opcjami kompilatora, może masz więcej pojęcia?

Aha, i wyniki: C#: 0.32ms C++: 8.26ms. To trochę dziwne. Czy źle zinterpretowałem coś o czym .Quad znaczy? Skopiowałem kod zegara C++ z dowolnego miejsca w Internecie, przechodząc przez całą instalację doładowania i dołączając/libfile rigmarole. A może nieświadomie używam różnych instrumentów? Czy jest jakaś krytyczna opcja kompilacji, której nie używałem? A może kod C# jest zoptymalizowany, ponieważ średnia jest stała?

Oto linia C++ polecenia z posesji PAGE-> C/C++ -> Wiersz poleceń: /I "C: \ Users \ Carlos \ Pulpit \ boost_1_47_0"/Zi/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: kolejka

Każda pomoc będzie doceniona, dzięki.

Answer 1

Prosta zmiana alokatora znacznie skróci ten czas.

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

0.9ms w moim systemie (od 10 ms przed). Sugeruje to mi, że w rzeczywistości ogromna, znaczna większość twojego czasu nie jest wydawana w tabeli mieszania, ale w alokatorze. Powodem, dla którego jest to nieuczciwe porównanie, jest to, że twój GC nigdy nie zbierze się w tak trywialnym programie, dając mu nienależną przewagę wydajności, a natywne alokatory dokonują znacznego buforowania wolnej pamięci - ale to nigdy nie wejdzie w grę w tak trywialnym na przykład, ponieważ nigdy nie przydzielono ani nie anulowano niczego, więc nie ma nic do buforowania.

Wreszcie, implementacja Boost pool jest bezpieczna dla wątków, podczas gdy nigdy nie grasz z wątkami, więc GC może po prostu wrócić do implementacji jednowątkowej, która będzie znacznie szybsza.

Uciekłem ręcznie zwijany, nie zwalniający nie wątk bezpieczny przydział puli i dostałem się do 0.525ms dla C++ do 0.45ms dla C# (na moim komputerze). Wniosek: Twoje oryginalne wyniki były bardzo przekrzywione ze względu na różne schematy alokacji pamięci w obu językach, a po ich rozwiązaniu różnica stała się względnie minimalna.

Własny hasz (jak opisano w odpowiedzi Alexandre'a) skrócił mój czas C++ do 0.34ms, który jest teraz szybszy niż 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

Przechowywanie kolejnych sekwencji klawiszy numerycznych dodawanych w porządku rosnącym zdecydowanie NIE jest tym, dla którego zostały przygotowane tabele mieszania.

Użyj tablicy lub wygeneruj losowe wartości.

I wykonaj niektóre wyszukiwania. Tabele skrótu są wysoce zoptymalizowane do pobierania.

Answer 3

Visual Studio TR1 unordered_map jest taka sama jak stdext :: hash_map:

Kolejny wątek pytając dlaczego wykonuje powolny, zobacz moją odpowiedź z linkami do innych, którzy odkryli ten sam problem.Wniosek jest taki, aby użyć innej realizacji hash_map gdy w C+++:

Alternative to stdext::hash_map for performance reasons

Btw. zapamiętaj kiedy w C++ to jest duża różnica między zoptymalizowanym Release-build i niezoptymalizowanym Debug-build w porównaniu do C#.

Answer 4

Możesz spróbować dict.rehash(n) z różnymi (dużymi) wartościami n przed wstawieniem elementów i zobaczyć, jak wpływa to na wydajność. Przydziały pamięci (odbywają się, gdy pojemnik napełnia kubły) są na ogół droższe w C++ niż w C#, a ponowne łączenie jest również ciężkie. W przypadku funkcji std::vector i std::deque funkcją analogowego elementu jest reserve.

Różne zasady rehash i próg współczynnika obciążenia (spójrz na funkcję składową max_load_factor) również będą miały duży wpływ na wydajność unordered_map.

Następnie, ponieważ używasz VS2010, sugeruję użycie std::unordered_map z nagłówka <unordered_map>. Nie używaj boost, gdy możesz korzystać ze standardowej biblioteki.

Faktyczna funkcja skrótu może znacznie wpłynąć na wydajność. Możesz spróbować wykonać następujące czynności:

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

i użyć std::unordered_map<int, int, custom_hash>.

Wreszcie, zgadzam się, że jest to złe wykorzystanie tabel hashowych. Użyj losowych wartości do wstawienia, a otrzymasz dokładniejszy obraz tego, co się dzieje. Testowanie szybkości wstawiania tablic hash nie jest wcale głupie, ale tablice skrótów nie służą do przechowywania kolejnych liczb całkowitych. Użyj do tego celu vector.