Простейшая параллельная карта с строковыми ключами в C ++ 11 - PullRequest
Новая
       33

Простейшая параллельная карта с строковыми ключами в C ++ 11

0 голосов
/ 26 ноября 2018

Как и многим разработчикам C ++, в какой-то момент мне понадобилась простая простая таблица с строковым ключом , и я хотел, чтобы она базировалась только на стандартной библиотеке C ++ 11.

By "одновременный«Я имею в виду, что несколько потоков могут работать на нем, не блокируя друг друга (большую часть времени).

Обновление: доступны два популярных решения.Не совсем «простой», но многофункциональный и производительный:

Кроме того, и, надеясь сэкономить время следующему работающему парню / галу, я делюсь самым простым решением 1022 * C ++ 11 (~ 40 LOC) Iудалось собрать вместе.

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

1 Ответ

0 голосов
/ 26 ноября 2018

После небольшого исследования вы получите один из двух вариантов:

  1. Оберните голову вокруг некоторых сверхбыстрых реализаций хеш-таблицы вокруг .Импортируйте довольно сложный / запутанный сторонний код, конвертируйте ключи в хэши, обрабатывайте коллизии, развлекайтесь довольно долго.

  2. Разделите вашу таблицу на более мелкие заблокированные таблицы.Используйте общие указатели для управления содержащимися данными.

Вариант № 2 решает мой текущий вариант использования практически без конфликтов, не закрывая двери для будущей оптимизации когда-нибудь она вам понадобится .Это фактически решает некоторые вещи, которые вам понадобятся, чтобы «перерасти» в более сложное решение.Вот как: 

template <typename Element, unsigned NumBlocks>
class ConcurrentTable
{
    using SharedElement = std::shared_ptr<Element>;

    class InnerMap {
        std::mutex mut_;
        std::unordered_map<std::string,SharedElement> map_;
    public:
        SharedElement get(std::string const& key) {
            std::unique_lock<mutex> lock(mut_);
            auto i = map_.find(key);
            return (i != map_.end()) ? i->second
                : SharedElement{}; // Empty pointer == not found
        }
        bool set(std::string const& key, SharedElement && value) {
            std::unique_lock<mutex> lock(mut_);
            auto [_,created] = map_.insert_or_assign(key, forward<SharedElement>(value));
            return created;
        }
        bool del(std::string const& key) {
            unique_lock<mutex> lock(mut_);
            return map_.erase(key);
        }
    };

    std::array<InnerMap, NumBlocks> maps_;
    std::hash<std::string> hash_;

    InnerMap& map_for(std::string const& key) {
        return maps_[hash_(key) % NumBlocks];
    }

public:
    SharedElement get(std::string const& key) {
        return map_for(key).get(key);
    }
    bool set(std::string const& key, SharedElement && value) {
        return map_for(key).set(key, std::forward<SharedElement>(value));
    }
    bool del(std::string const& key) {
        return map_for(key).del(key);
    }
};

Теперь вы можете создать параллельную таблицу строк для строк следующим образом: 

ConcurrentTable<std::string,128> my_concurrent_table;

С 128 подстолями достаточно хеш-пространства длянапример, 10 одновременных потоков для случайного доступа к таблице.Если вам нужно больше потоков или меньше конфликтов, увеличьте размер.

Кредит идет на SO SO, чьи слова положили начало моему решению: «если вы делаете многопоточный доступ, вам все равно придется разделять».(Извините, что пишу в затылке, не могу найти оригинальную цитату!)

...