Одновременная запись в разные ведра в unordered_map (С++)?

С++ новичок здесь. Я пытаюсь писать в разные ведра одновременно в unordered_map. Насколько я могу судить по поиску, я понимаю, что это должна быть операция с потоком. Мое (возможно неправильное) понимание основано на ответах здесь и здесь, а также на упомянутой части стандарт С++ 11 (особенно пункт 2 - акцент мой):

23.2.2 Гонки данных контейнера [container.requirements.dataraces]

1 В целях предотвращения расследований данных (17.6.5.9) реализации должны учитывать следующие функции: begin, end, rbegin, rend, front, back, data, find, lower_bound, upper_bound, equal_range, at и, за исключением ассоциативных или неупорядоченных ассоциативных контейнеров, оператор [].

2 Несмотря на (17.6.5.9), для предотвращения расы данных требуется реализация, когда содержимое содержащегося объекта в разных элементах в одной и той же последовательности, за исключением vector<bool>, изменяется одновременно.

3 [Примечание: для вектора x с размером больше единицы x [1] = 5 и * x.begin() = 10 могут выполняться одновременно без гонки данных, но x [0] = 5 и * x.begin() = 10, выполняемый одновременно, может привести к гонке данных. В качестве исключения к общему правилу для вектора <bool> y, y [0] = true может участвовать в гонке с y [1] = true. -end note]

В любом случае кажется, что запись в разные ведра не является потокобезопасной со стандартными контейнерами, о чем свидетельствует приведенный ниже код. Вы увидите, что я разрешаю блокировку, соответствующую изменяемому ведро, прежде чем писать, но иногда пары не записываются правильно. Для чего это стоит, если я использую один замок - например, просто измените auto bkt = mm->bucket(key); на auto bkt=0;, эффективно заблокировав весь контейнер unordered_map - все будет работать так, как ожидалось.

#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;
}

Программа выйдет, когда ключ был ошибочно не введен. Пример вывода:

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!

Итак, мой вопрос в два раза:

Я делаю что-то неправильно в том, как я блокирую ведра?
Если это так, есть ли лучший способ заблокировать карту по принципу "ведро за ведром", чтобы включить одновременную запись в разные ведра?

Наконец, я упомянул, что я уже пробовал TBB concurrent_unordered_map, но он был намного медленнее в моем приложении, чем просто делать что-то в серийном. Отброшенные ошибки в стороне, мой подход к блокировке с помощью buck с использованием std:: unordered_map выполнялся значительно лучше.

Ответ 1