Предложение в стандарт C++: ConcurrentHashMap

Сергей Мурылев, старший разработчик, Яндекс

Один из самых широко используемых сегодня языков программирования C++ был создан в далекие 80-е. С тех пор язык непрерывно совершенствуется. Каждое предложение по его улучшению проходит утверждение на собраниях Международного комитета по стандартизации. В этом процессе может принять участие любой разработчик из любой страны. Два года назад была создана российская рабочая группа (РГ21), на счету у которой уже множество изменений, внесенных в стандарт C++. В материале представлен разбор предложения, которое находится на обсуждении комитета прямо сейчас.

В чём идея?

В большинстве случаев, когда требуется сделать какое-то решение в многопоточной среде, стоит задуматься над тем, нет ли на просторах бескрайнего интернета решения, позволяющего без создания своего велосипеда контейнера достичь желаемого результата. Но при этом, как ни странно, современных программистов хоть хлебом не корми, а дай сделать какую-то свою уникальную штуку. В случае с многопоточностью это зачастую приводит к печальным последствиям и бессонным ночам за компьютером в поисках трудновоспроизводимых многопоточных багов, которые воспроизводятся исключительно при определенной фазе луны и большом терпении. Во многих языках программирования, таких как Java и C#, есть ассоциативный потокобезопасный контейнер, который позволяет решать достаточно широкий класс задач, когда надо что-то закешировать, выполнять дедупликацию поступивших на вход сообщений или просто не хочется связываться с какими-то key-value базами данных. Какое-то время назад мы посовещались с товарищами из комитета по стандартизации С++ и пришли к выводу, что это хорошая идея для внесения в стандарт.

Если посмотреть на то, что сделано в Java, там все сделано относительно просто: есть небольшое количество шардов, которые кофигурятся в конструкторе. Каждый из них представляет из себя отдельную хеш-таблицу с открытой адресацией при выполнении операций доступа к элементам по хешу от ключа вычисляется номер шарда, шард блокируется и выполняется доступ к элементам. Для того, чтобы это не было совсем медленно, разделяются блокировки на чтение и блокировки на запись.

Ограничения

Несмотря на кажущуюся простоту есть пара нюансов, которые налагают дополнительные ограничения на реализацию в С++:

1. Java использует внутренний механизм ссылок, который позволяет нам организовать разделяемый доступ к контенту таблицы. В С++ это можно явно сделать, если хранить внутри shared_ptr, который содержит атомарный счётчик и требует лишних усилий, если внутри хранится маленький контент. Поэтому мы решили вместо этого отдавать наружу копию контента.
2. В интерфейсе std::unordered_map есть итераторы, которые в многопоточной среде сделать достаточно проблематично. Понятно, что блокировать все не вариант, поэтому, например, в той же Java они есть, но они спроектированы для работы из одного потока и по факту могут стать неприятной неожиданностью для тех, кто невнимательно читал документацию. Вместо этого мы сделали отдельный интерфейс unordered_map_view. Он во многом похож на интерфейс unordered_map, но когда мы отдаем эту штуку пользователю, мы либо блокируем всё, либо налагаем ответственность за то, что этим объектом будет пользоваться только один поток.
3. В С++ бывают объекты, которые нельзя копировать. Так как мы решили отдавать наружу копии хранимых объектов, в этом случае этот интерфейс окажется неработоспособен. Для того, чтобы как-то осуществлять доступ к таким объектам, мы сделали ряд методов, которые позволяют вызывать пользовательскую функцию над элементом хеш-таблицы по ключу.

Давайте подробнее рассмотрим сам интерфейс, который мы предлагаем внести в стандарт:

Операции доступа по ключу

			template<typename K>
optional<mapped_type> find(const K&& key) const;
template<typename K, typename... Args>
mapped_type find(K&& key, Args&&... default_value) const;
template<typename K, typename F>
void visit(K&& key, F&& f) const;
		

Метод find можно использовать для поиска элементов по ключу в контейнере. В случае отсутствия элемента, первая версия метода вернет пустой optional, а вторая вернет значение по умолчанию, сконструированное из списка аргументов, который начинается после ключа. Метод visit нужен для того, чтобы обращаться к некопируемым элементам. Функтор F должен принимать в качестве аргумента константную ссылку на тип ассоциированного с ключем значения (const mapped_type&).

Операции добавления элементов

			template<typename K, typename... Args>
bool emplace(K&& key, Args&&... val);
template<typename K, typename F, typename... Args>
void emplace_or_visit(K&& key, F&& f, Args&&... args);
template<typename K, typename... Args>
bool insert_or_assign(K&& key, Args&&... val);
		

Мы решили убрать оператор [] из интерфейса потому, что он является непрозрачным и завязан на копирование. Вместо него мы сделали методы emplace и emplace_or_visit, первый метод возвращает true, если он смог создать элемент ключу и false, если по этому ключу в контейнере уже что то было. Метод emplace_or_visit пытается создать элемент по ключу и если у него это не получается, то он пытается вызывать функтор F, который должен принимать в качестве аргумента ссылку на тип ассоциированного с ключем значения (mapped_type&). Метод insert_or_assign пытается вставить в контейнер элемент, и если по ключу до него ничего не было, то он возвращает true, иначе он переписывает значение и возвращает false.

Операции обновления элементов

			template<typename K, typename F>
void visit(K&& key, F&& f);
template<typename K, typename... Args>
size_type update(K&& key, Args&&... val);
		

Метод visit работает аналогично константной версии, только разница в том, что функтор F принимает значение по неконстантной ссылке и соответственно, может его изменять. Метод update пытается переписать значение по ключу, возвращает 0, если он ничего не нашёл и ничего не сделал, или 1, если он смог найти и поменять элемент по ключу.

Операции удаления элементов

			template<typename K>
size_type erase(K&& key);
template<typename K, typename F>
size_type erase_and_visit(K&& key, F&& f);
		

Метод erase выглядит аналогично методу из unordered_map и делает то же самое – удаляет элемент по ключу. Отличается только сигнатура за счёт использования универсальных ссылок. Это позволяет не делать много перегруженных методов. Функция erase_and_visit отличается тем, что перед тем, как удалить, вызывает функтор.

Пример использования

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

			int main() {
	using namespace std;
	using id_t = unsigned long long;
	using use_count_t = size_t;

	concurrent_unordered_map<id_t, use_count_t> stats;

	constexpr unsigned threads_count = 10;
	thread threads[threads_count];
	for (auto& t: threads) {
    			t = thread([&stats]() {
                // В данном случае мы эмулируем 
                // поведение пользователей с помощью 
                // случайной последовательности с 
                // равномерным распределением
        		std::default_random_engine e1;
        		std::uniform_int_distribution uniform_dist(1, 5);
        		for (auto i = 0; i < 10; ++i) {
            		auto id = uniform_dist(e1);
            		stats.emplace_or_visit(
                    		id,
                    		[](auto& v){ ++v; },
                    		1
            		);

            		process_stuff(id);
        		}
    		});
	}

	for (auto& t: threads) {
    	t.join();
	}

	process_stats(std::move(stats.make_unordered_map_view()));
}
		

Текст пропозала c последними моими изменениями можно посмотреть у меня на гитхабе, там же неподалёку от него можно посмотреть референсную имплементацию.