C++ && multithreads: если нужна блокировка на отдельные узлы std::map, это нужны мютексы в каждом узле, или есть более оптимальный вариант?

Question

Если в многопоточной проге нужна блокировка отдельных узлов на std::map, то это нужно мютексы делать в каждом узле, или есть более оптимальные варианты?

Видел, что sizeof(std::mutex) занимает 40 байт, а sizeof(std::shared_mutex) вообще 56 байт. В моем случае это несколько избыточно. У меня деревья нужны на миллионы и более узлов.

В то же время, делать общую блокировку всего дерева то же избыточно. Обращения к дереву часты, но использование одного и того же узла очень редки.

Структура в среднем вот такого плана:

struct CounterItem {
   mutable std::shared_mutex mtx;
   mutable SomeComplexCounter counter;
};

...

std::map<Key,CounterItem> mapCounters;

...

auto& item = mapCounters.at(someKey);
item.mtx.lock();
item.counter.doSomeThing();
item.mtx.unlock();

Вопроса про общую блокировку дерева нет, с ней все понятно.

Answer 1

Подумал я, поизучал вопрос, и сделал собственный мютекс основанный на std::atomic.

Вот так вот выглядит сам класс. Тип вложенной переменной можно объявить хоть char - и тогда sizeof будет 1 байт, если таковой размер char. По крайней мере смотрел на gcc под линуксом.

template <class TT>
struct AtomicMutex {
    static_assert( TT(-1) < 0, "Need signed numeric type");

    void lockForWrite();
    void unlockForWrite();
    void lockForRead();
    void unlockForRead();

private:
    std::atomic<TT> counter = 0;
};

Вот так вот выглядит реализация:

template <class TT>
void AtomicMutex<TT>::lockForWrite() {
    TT v = 0;
    while (!counter.compare_exchange_weak(v, -1)) {
        counter.wait(v);
        v = 0;
    }
}

template <class TT>
void AtomicMutex<TT>::unlockForWrite() {
    counter = 0;
    counter.notify_all();
}

template <class TT>
void AtomicMutex<TT>::lockForRead() {
    while (true) {
        TT v = counter.load();
        if (v < 0)
            counter.wait(v);
        else if (counter.compare_exchange_weak(v, v+1))
            break;
    }
}

template <class TT>
void AtomicMutex<TT>::unlockForRead() {
    while (true) {
        TT v = counter.load();
        assert( v > 0 );
        if (counter.compare_exchange_weak(v, v-1)) {
            if (v == 1)
                counter.notify_all();
            break;
        }
    }
}

По прямому назначению - инстанцировать в итемы еще не пробовал. Но в паре своих прежних расчетных алгоритмов заменил QReadWriteLock на этот класс. Там в 15 потоков активного использования заработало без сбоев. Компилировал на gcc под линукс, на Intel процессоре.

Вот здесь можно посмотреть на гитхабе: https://github.com/victorprogrammist/atomic_mutex

Будут интересны замечания про надежность этого метода. Мютекс планируется использовать в итемах коллекций, где пересечения блокировок редки, поэтому скорость работы относительно стандартных мютексов не сильно беспокоит.

БЛОГ НА HUSL

C++ && multithreads: если нужна блокировка на отдельные узлы std::map, это нужны мютексы в каждом узле, или есть более оптимальный вариант?

Ответы (1 шт):