Perché unordered_map "trova + inserisci" più velocemente di "insert + check for success"?

Question

Uso una unordered_map come array 3D sparsi (128 x 128 x 128) per inserire valori in una griglia, a condizione che la cella della griglia sia ancora libera.

Fino ad ora ho sempre controllato con find() se la cella è libera e se lo è, allora ho aggiunto un elemento usando insert() o emplace(). Ora ho scoperto che posso usare il valore restituito di insert ed emplace per controllare se l'elemento è stato aggiunto o se c'era già un elemento con la stessa chiave all'interno della mappa. Ho pensato che questo avrebbe potuto migliorare le prestazioni in quanto avrei potuto rimuovere completamente l'utilizzo di find.

Come risulta, invece di migliorare le prestazioni inserendo senza trovare, le prestazioni sono effettivamente diminuite e non sono sicuro del perché.

Ho ridotto la mia applicazione a questo esempio in cui i punti vengono generati casualmente e quindi inseriti nella griglia.

#include <unordered_map> 
#include <random> 
#include <chrono> 
#include <iostream> 
#include <math.h> 
#include <algorithm> 
#include <string> 

using std::cout; 
using std::endl; 
using std::chrono::high_resolution_clock; 
using std::chrono::milliseconds; 
using std::chrono::duration_cast; 
using std::unordered_map; 

int num_elements = 5'000'000; 


void findThenInsert(){ 
    cout << endl << "find and emplace" << endl; 

    auto start = high_resolution_clock::now(); 

    std::mt19937 gen(123); 
    std::uniform_real_distribution<> dis(0, 128); 

    unordered_map<int, int> grid; 
    int count = 0; 
    for(int i = 0; i < num_elements; i++){ 
     float x = dis(gen); 
     float y = dis(gen); 
     float z = (cos(x*0.1) * sin(x*0.1) + 1.0) * 64.0; 

     int index = int(x) + int(y) * 128 + int(z) * 128 * 128; 
     auto it = grid.find(index); 
     if(it == grid.end()){ 
      grid.emplace(index, count); 
      count++; 
     } 
    } 

    cout << "elements: " << count << endl; 
    cout << "load factor: " << grid.load_factor() << endl; 

    auto end = high_resolution_clock::now(); 
    long long duration = duration_cast<milliseconds>(end - start).count(); 
    float seconds = duration/1000.0f; 
    cout << seconds << "s" << endl; 
} 


void insertThenCheckForSuccess(){ 
    cout << endl << "emplace and check success" << endl; 

    auto start = high_resolution_clock::now(); 

    std::mt19937 gen(123); 
    std::uniform_real_distribution<> dis(0, 128); 

    unordered_map<int, int> grid; 
    int count = 0; 
    for(int i = 0; i < num_elements; i++){ 
     float x = dis(gen); 
     float y = dis(gen); 
     float z = (cos(x*0.1) * sin(x*0.1) + 1.0) * 64.0; 

     int index = int(x) + int(y) * 128 + int(z) * 128 * 128; 
     auto it = grid.emplace(index, count); 
     if(it.second){ 
      count++; 
     } 
    } 

    cout << "elements: " << count << endl; 
    cout << "load factor: " << grid.load_factor() << endl; 

    auto end = high_resolution_clock::now(); 
    long long duration = duration_cast<milliseconds>(end - start).count(); 
    float seconds = duration/1000.0f; 
    cout << seconds << "s" << endl; 
} 

int main(){ 

    findThenInsert(); 
    insertThenCheckForSuccess(); 

} 

In entrambi i casi la dimensione della mappa è 82901 in seguito in modo da assumere il risultato è esattamente lo stesso.

 
find and emplace: 0.937s 
emplace then check: 1.268s 

Answer 1

Il problema è che la specifica di emplace per contenitori associativi a effetto richiede un'allocazione anche in caso di errore; il costo di questa allocazione e riallocazione domina il costo di un errore fallito nella strategia di ricerca e inserimento.

Questo perché emplace è specificato per colloco-costruzione value_type (cioè pair<Key const, T>) dalla sua argomentazione trasmessi; solo una volta che ha costruito la coppia può hash la chiave per verificare se è già presente. (Non si può semplicemente prendere il primo argomento, perché potrebbe essere std::piecewise_construct.) Inoltre non è possibile costruire lo pair nella memoria automatica e quindi spostarlo in un nodo, perché emplace non è specificato per richiedere una copia o anche mobile value_type , quindi deve eseguire un'allocazione del nodo potenzialmente costosa su ogni chiamata. (Si noti che i contenitori associativi ordinati hanno lo stesso problema, ma il costo O (log n) di una sonda è più significativo rispetto al costo di allocazione.)

A meno che non ci si aspetti che gli inserti abbiano successo nella maggior parte dei In alcuni casi, è meglio usare find-then-emplace su emplace-then-test. Si potrebbe anche usare insert, finché è assicurarsi che si sta chiamando il value_type di sovraccarico e non il modello che inoltra a emplace.

Questo è (probabilmente) risolto in C++ 17, che (dovrebbe) avere try_emplace, con semantica simile da emplace ma prestazioni migliorate nel caso di errore. (La differenza semantica è che il tipo mappato non è colloco-costruito nel caso di errore, il che rende possibile ad esempio negozio unique_ptr come tipo mappato.)

Answer 2

ritengo il problema è che si utilizza emplace anziché insert . Il problema è che le funzioni emplace nei contenitori associativi di solito allocano memoria per il nodo anche se la chiave è già presente. In questo modo, se si posizionano regolarmente duplicati, le allocazioni di memoria vengono sprecate. Se hai usato insert invece, farebbe solo l'allocazione di memoria se l'insert ha successo.

Scott Meyers says solo preferiscono colloco funzioni su funzioni di inserimento, se "il contenitore non rifiuterà il valore aggiunto di essere a causa di esso che è un duplicato"

Non riesco a riprodurre i risultati esattamente, ma my testing spettacoli che inserto (non colloco) allora prova è anche più veloce di trovare poi colloco:

auto it = grid.insert({index, count}); 

Questa decisione potrebbe anche dipendere da quanto costoso è quello di creare il tipo di valore. find non ha bisogno di costruire il tipo di valore, ha solo bisogno della chiave. Ma emplace e insert hanno bisogno della chiave e del tipo di valore, quindi nei casi in cui è costoso creare il valore potrebbe essere più veloce utilizzare find e creare il valore solo se necessario. In questo caso il tuo valore è solo uno int quindi mi aspetto che insert o emplace vincano sempre su find-then-emplace.