threads - ¿Escritura simultánea en diferentes cubos en unordered_map(C++)?

threads c++ linux

Question

C ++ novato aquí. Estoy tratando de escribir en diferentes cubos al mismo tiempo en un mapa_ordenado. Por lo que puedo decir al buscar, entiendo que esto debería ser una operación segura para subprocesos. Mi comprensión (quizás incorrecta) se basa en las respuestas here y here , así como en la parte a la que se hace referencia del estándar C ++ 11 (en particular, el punto 2 - el énfasis es mío):

23.2.2 Carreras de datos de contenedor [container.requirements.dataraces]

1 Con el fin de evitar las carreras de datos (17.6.5.9), las implementaciones deben considerar las siguientes funciones const: begin, end, rbegin, rend, front, back, data, find, lower_bound, upper_bound, equal_range, at y, excepto en contenedores asociativos o desordenados asociativos, operador [].

2 No obstante (17.6.5.9), se requieren implementaciones para evitar las carreras de datos cuando los contenidos del objeto contenido en diferentes elementos en la misma secuencia, excepto el vector<bool> , se modifican al mismo tiempo .

3 [Nota: para un vector x con un tamaño mayor que uno, x [1] = 5 y * x.begin () = 10 se pueden ejecutar simultáneamente sin una carrera de datos, pero x [0] = 5 y * x. begin () = 10 ejecutado simultáneamente puede resultar en una carrera de datos. Como excepción a la regla general, para un vector <bool> y, y [0] = true puede competir con y [1] = true. "Nota final"

En cualquier caso, parece que escribir en diferentes cubos no es seguro para subprocesos con los contenedores estándar, como lo demuestra el código a continuación. Verá que habilito un bloqueo correspondiente al cubo que se está modificando antes de escribir, pero a veces los pares no se registran correctamente. Para lo que vale, si uso un solo bloqueo, por ejemplo, solo cambio auto bkt = mm->bucket(key); a auto bkt=0; , efectivamente bloqueando todo el contenedor unordered_map - todo funciona como se esperaba.

#include <iostream>
#include <unordered_map>
#include <atomic>
#include <vector>
#include <thread>

#define NUM_LOCKS 409
#define N 100
#define NUM_THREADS 2

using namespace std;


class SpinLock
{
    public:
        void lock()
        {
            while(lck.test_and_set(memory_order_acquire)){}
        }
    void unlock()
        {
            lck.clear(memory_order_release);
        }

    private:
        atomic_flag lck = ATOMIC_FLAG_INIT;
};


vector<SpinLock> spinLocks(NUM_LOCKS);


void add_to_map(unordered_map<int,int> * mm, const int keyStart, const int keyEnd, const int tid){

    for(int key=keyStart;key<keyEnd;++key){
        auto bkt = mm->bucket(key);

        //lock bucket
        spinLocks[bkt].lock();

        //insert pair
        mm->insert({key,tid});

        //unlock bucket
        spinLocks[bkt].unlock();
    }

}


int main() {

    int Nbefore, Nafter;
    thread *t = new thread[NUM_THREADS];

    //create an unordered map, and reserve enough space to avoid a rehash
    unordered_map<int,int> my_map;
    my_map.reserve(2*NUM_THREADS*N);

    //count number of buckets to make sure that a rehash didn''t occur
    Nbefore=my_map.bucket_count();


    // Launch NUM_THREADS threads.  Thread k adds keys k*N through (k+1)*N-1 to the hash table, all with associated value = k.

    for(int threadID=0;threadID<NUM_THREADS;++threadID){
        t[threadID]=thread(add_to_map,&my_map,threadID*N,(threadID+1)*N,threadID);
    }

    // Wait for the threads to finish
    for(int threadID=0;threadID<NUM_THREADS;++threadID){
        t[threadID].join();
    }

    //count number of buckets to make sure that a rehash didn''t occur
    Nafter=my_map.bucket_count();


    cout << "Number of buckets before adding elements: " << Nbefore <<endl;
    cout << "Number of buckets after  adding elements: " << Nafter  << " <--- same as above, so rehash didn''t occur" <<endl;

    //see if any keys are missing
    for(int key=0;key<NUM_THREADS*N;++key){

        if(!my_map.count(key)){

            cout << "key " << key << " not found!" << endl;

        }
    }

    return 0;
}

El programa se cerrará cuando una clave no se haya introducido por error. Una salida de muestra es:

Number of buckets before adding elements: 401
Number of buckets after  adding elements: 401 <--- same as above, so rehash didn''t occur
key 0 not found!
key 91 not found!
key 96 not found!
key 97 not found!
key 101 not found!
key 192 not found!
key 193 not found!
key 195 not found!

Por lo tanto, mi pregunta es doble:

1. ¿Estoy haciendo algo mal en cómo estoy bloqueando los cubos?
2. Si es así, ¿hay una mejor manera de bloquear el mapa en forma de cubeta por cubeta para permitir escrituras simultáneas en diferentes cubetas?

Finalmente, mencionaré que ya probé el mapa concurrent_unordered_BB de TBB, pero en mi aplicación era mucho más lento que simplemente hacer cosas en serie. Dejando a un lado los errores, mi enfoque de bloqueo de cubeta con std :: unordered_map se desempeñó significativamente mejor.

Answer 1

Los elementos de un contenedor no son los value_type , sino los elementos value_type .

La modificación de un elemento en un contenedor std no tiene impacto de concurrencia en otros elementos. Pero modificar un cubo no tiene tal garantía.

Agregar o eliminar elementos en un grupo es una operación no const en el contenedor que no forma parte de la lista especial de operaciones no const que son seguras de usar sin sincronización.