Contention
#опытным

Thread Contention (соревнование потоков) — это ситуация в многопоточном программировании, когда несколько потоков одновременно пытаются получить доступ к одному и тому же разделяемому ресурсу, но только один поток может использовать его в данный момент времени.

Это нормальная ситуация, на любом мьютексе потоки соревнуются. Но иногда это выходит за грани нормальности.

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

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

template <Key, Value>
class ThreadSafeMap {
    mutable std::mutex mtx;
    std::map<Key, Value> map;

public:
    void Insert(const Key &key, const Value &value) {
        std::lock_guard lg{mtx};
        map.insert(key, value);
    }
    Value &Get(const Key &key) const {
        std::lock_guard lg{mtx};
        return map.at(key);
    }
};

Если к такой мапе одновременно будет получать доступ куча потоков, то все кроме одного будут простаивать. А если таких потоков 10 или 20? Неприятненько.

Как можно снизить Contention?

👉🏿 Read-Write Lock. Если у вас много читателе и мало писателей, то можно разрешить нескольким читателям одновременно получать доступ к данным с помощью std::shared_mutex:

template <Key, Value>
class ThreadSafeMap {
    mutable std::shared_mutex mtx;
    std::map<Key, Value> map;

public:
    void Insert(const Key &key, const Value &value) {
        std::unique_lock ul{mtx};
        map.insert(key, value);
    }
    Value &Get(const Key &key) const {
        std::shared_lock sl{mtx};
        return map.at(key);
    }
};

👉🏿 Thread-Local Storage. Потоки пишут данные в свои локальные буферы, которые централизованно синхронизируют данные друг с другом, чтобы как можно меньше блокировать потоки.

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

template <Key, Value>
class FineGrainedMap {
    struct Node {
        std::mutex mtx;
        std::map<Key, Value> data;
    };
    std::vector<Node> buckets{16};  // Много мелких блокировок
    
public:
    Value& Get(const Key& key) const {
        auto& bucket = buckets[std::hash<Key>{}(key) % buckets.size()];
        std::lock_guard lock(bucket.mtx);
        return bucket.data.at(key);
    }
};

👉🏿 Используйте lock-free структуры данных. Ну как бы тут логично: нет мьютексов, нет и сontention. Не в каждой задаче это реально применить, но иногда все же можно.

Compete and win. Stay cool.

#concurrency