Новый стандарт C++, C++23, впервые с C++11 расширил всем привычную линейку контейнеров: помимо знакомых array, vector, (unordered_)set, (unordered_)map и прочим в нее теперь входят непонятные flat_set, flat_map, flat_multiset и flat_multimap. Ответим на вопросы, что это за контейнеры, когда они могут быть полезны, сравним дизайн стандартизированных «плоских» контейнеров с дизайном плоских контейнеров из Boost и ETL и, конечно, произведём замеры и сравним производительность flat_ и не flat_ контейнеров.

Важно сказать, что на самом деле все эти «плоские» контейнеры даже не контейнеры в строгом смысле, а лишь адаптеры контейнеров: подобно stack и queue они не реализуют какую-то собственную уникальную структуру хранения данных, а лишь вводят свой дополнительный порядок поверх структуры, предоставляемой другим контейнером.

И прежде чем начать рассмотрение каждого из «плоских» контейнеров по отдельности, не менее важно понять одну общую для них всех вещь: они называются »плоскими», потому что они действительно плоские — под капотом у них лежат не красно-черные (или AVL) деревья, как у std::(multi)set и std::(multi)map и не хэш-таблицы, как у std::unordered_(multi)set и std::unordered_(multi)map, а последовательные контейнеры.

Например, как бы вы реализовали set, если вы бы не знали о вышеупомянутых деревьях? Легко: берем std::vector и реализуем insert так, чтобы он поддерживал этот вектор в отсортированном состоянии. То есть, примерно так:

template <typename ...>
std::pair<iterator, bool> flat_set<...>::insert(const K& value) {
  // Ищем в контейнере value или же подходящее место для его вставки
  auto it = std::lower_bound(
    vec.begin(), vec.end(), value
  ); // Бинарный поиск, O(log N)
  // Если не нашли совсем или нашли не то, то вставляем
  if (it == vec.end() || value < *it) {
    vec.insert(
      it, std::move(value)
    ); // O(N) и потенциальная реаллокация :(
    return std::pair<iterator, bool>{std::move(it), true};
  }
  // Иначе возвращаем найденное
  return std::pair<iterator, bool>{std::move(it), false};
}

А find() в таком случае реализуется как обычный бинарный поиск (со сложностью O(log\ N)). Так вот, так же (но более обобщенно) устроен и flat_set, и flat_multiset (в его случае вместо lower_bound используется upper_bound и новый элемент вставляется безусловно), и flat_map и flat_multimap (но в их случае мы оперируем двумя контейнерами: одним для хранения ключей, другим для хранения значений).

Аналогично, даже не меняя реализации, вместо std::vector мы могли бы использовать std::deque. В общем, любой последовательный контейнер. Именно поэтому плоские контейнеры и являются адаптерами: разные контейнеры под капотом могут иметь разные плюсы и минусы, поэтому нет причин жестко завязываться на какой-то единственный из них. И именно поэтому их определение выглядит вот так:

template<
    class Key,
    class Compare = std::less<Key>,
    class KeyContainer = std::vector<Key> // Контейнер для ключей
> class flat_set; // Точно такое же для flat_multiset

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class KeyContainer = std::vector<Key>, // Контейнер для ключей
    class MappedContainer = std::vector<T> // Контейнер для значений
> class flat_map; // Точно такое же для flat_multimap

Если же сравнивать асимптотическую сложность операций в плоских и не плоских контейнерах, то получим следующее:

std::unordered_(multi)set/map

std::(multi)set/map

std::flat_(multi)set/map

insert(value)

В среднем O(1)

O(log\ N)

O(N)

erase(value)

В среднем O(1)

O(log\ N)

O(N)

find(value)

В среднем O(1)

O(log\ N)

O(log\ N)

Примечание к таблице

В таблице выше, для полноты картины, было приведено сравнение всех имеющихся в стандартной библиотеке ассоциативных контейнеров.

Однако дальше в тексте, главным образом, будут сравниваться лишь упорядоченные контейнеры: std::(multi)set/map и новые плоские контейнеры (которые также являются упорядоченными) std::flat_(multi)set/map.

О неупорядоченных контейнерах — контейнерах, основанных на хэш-таблицах, говориться не будет, так как неупорядоченные и упорядоченные контейнеры — разного поля ягоды. Если вам не нужен порядок, то вам, за очень редкими исключениями (которые будут отмечены в заключении), и не нужны плоские контейнеры — хэш-таблицы во всём будут быстрей.

Асимптотически, казалось бы, мы не очень выигрываем. Тем не менее, по сравнению с (multi)set и (multi)map «плоская» реализация имеет и некоторые плюсы: более быструю итерацию, меньшее потребление памяти и лучшую кэш-локальность.

Но взамен нас неминуемо ждут менее стабильные итераторы, способные инвалидироваться на любой вставке и удалении; невозможность хранения не-копируемых и не-перемещаемых типов; более слабые гарантии безопасности исключений (никто не защитит нас от исключений в конструкторах копирования/перемещения при сдвиге элементов в ходе вставки/удаления) и более медленные вставки и удаления (мало того, что нам нужно поддерживать отсортированность, так ведь при каждой вставке в наш вектор нам нужно двигать элементы)

Более спорный вопрос: получим ли мы более быстрый поиск? (его сложность —O(log\ N)как в плоских, так и не в плоских контейнерах) Один из классиков С++, Matt Austern, в своей статье (2000 год) заявляет, что получим:

Both std::lower_bound and set::find take time proportional to log N, but the constants of proportionality are very different. Using g++ (...) it takes X seconds to perform a million lookups in a sorted vector<double> of a million elements, and almost twice as long (...) using a set. Moreover, the set uses almost three times as much memory (48 million bytes) as the vector (16.8 million).

Но более новые бенчмарки (2014 год; впрочем, на меньших объемах данных) показывают обратное (boost::container::flat_map, исключая один нюанс, о котором будет сказано чуть позже, идеологически устроен так же, как стандартизированный std::flat_map):

Однако, оставим этот вопрос на потом. А сейчас, с сформированным пониманием, зачем нам в принципе могут понадобиться эти контейнеры, рассмотрим интерфейс всех этих новый адаптеров.

Интерфейс

К счастью, интерфейс flat_set, flat_multiset, flat_map и flat_multimap задумывался так, чтобы на них можно было просто взять и заменить их не «плоские» аналоги (то есть, другие упорядоченные ассоциативные контейнеры — std::set, std::map и иже с ними), так что интерфейсы плоских и не плоских контейнеров практически совпадают.

Например, простенький демонстрационный пример с страницы std::set на cppreference без проблем скомпилируется (и вывод, конечно, будет тем же самым), если все вхождения std::set заменить на std::flat_set (godbolt).

Тот самый пример (в оригинале)
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <set>
#include <string_view>
 
template<typename T>
std::ostream& operator<<(std::ostream& out, const std::set<T>& set)
{
    if (set.empty())
        return out << "{}";
    out << "{ " << *set.begin();
    std::for_each(std::next(set.begin()), set.end(), [&out](const T& element)
    {
        out << ", " << element;
    });
    return out << " }";
}
 
int main()
{
    std::set<int> set{1, 5, 3};
    std::cout << set << '\n';
 
    set.insert(2);
    std::cout << set << '\n';
 
    set.erase(1);
    std::cout << set << "\n\n";
 
    std::set<int> keys{3, 4};
    for (int key : keys)
    {
        if (set.contains(key))
            std::cout << set << " does contain " << key << '\n';
        else
            std::cout << set << " doesn't contain " << key << '\n';
    }
    std::cout << '\n';
 
    std::string_view word = "element";
    std::set<char> characters(word.begin(), word.end());
    std::cout << "There are " << characters.size() << " unique characters in " << std::quoted(word) << ":\n" << characters << '\n';
}

И точно так же в любом коде все вхождения std::map можно заменить на std::flat_map и всё заработает. Так же возьмем пример с страницы на cppreference (godbolt).

Пример (почти в оригинале)
#include <iostream>
#include <map>
#include <string>
#include <string_view>
 
void print_map(std::string_view comment, const std::map<std::string, int>& m)
{
    std::cout << comment;
    // Iterate using C++17 facilities
    for (const auto& [key, value] : m)
        std::cout << '[' << key << "] = " << value << "; ";
    std::cout << '\n';
}
 
int main()
{
    // Create a map of three (string, int) pairs
    std::map<std::string, int> m{{"CPU", 10}, {"GPU", 15}, {"RAM", 20}};
 
    print_map("1) Initial map: ", m);
 
    m["CPU"] = 25; // update an existing value
    m["SSD"] = 30; // insert a new value
    print_map("2) Updated map: ", m);
 
    // Using operator[] with non-existent key always performs an insert
    std::cout << "3) m[UPS] = " << m["UPS"] << '\n';
    print_map("4) Updated map: ", m);
 
    m.erase("GPU");
    print_map("5) After erase: ", m);
 
    std::erase_if(m, [](const auto& pair){ return std::get<1>(pair) > 25; });
    print_map("6) After erase: ", m);
    std::cout << "7) m.size() = " << m.size() << '\n';
 
    m.clear();
    std::cout << std::boolalpha << "8) Map is empty: " << m.empty() << '\n';
}

Почему я написал «почти»: на самом деле это не оригинальный код с cppreference. Я внес в него правку: поменял строку №33. Изначально в ней был фрагмент pair.second > 25, а не std::get<1>(pair) > 25. Мне пришлось это сделать из-за того, что компилятор (как gcc, так и clang) стал ругаться, что pair (аргумент лямбда-функции) это std::tuple, а не std::pair. Фича это или баг — непонятно. Стандарт определяет тип const_reference у std::flat_map как pair<const key_type&, mapped_type&>, а не tuple [flat.multimap.defn]

P.S. Впоследствии выяснилось, что, по всей видимости, это особенности libstdc++. При использовании libc++ ошибок не возникает. См. godbolt и обсуждение в @procxx (Telegram)

В чём же flat_set все-таки отличается от set:

  • У flat_set есть конструкторы, которые принимают контейнер-хранилище, который может быть как отсортирован, так и нет (в этом случае flat_set отсортирует его и даже удалит дубликаты за вас). Пример доступен под спойлером и на godbolt.

Пример
#include <vector>
#include <flat_set>

int main() {
  std::vector<int> elements = {0, 1, 2, 3, 4, 5};

  {
    // Код ниже работает, т.к.
    // std::vector — контейнер по умолчанию для flat_set
    // Если мы попробуем передать, например, std::deque,
    // то нас ждёт облом
    std::flat_set<int> flat_set(elements);
  }

  {
    // А вот этот не работает
    // std::set<int> set(elements);
  }

  {
    // Но лучше сделать так, чтобы конструктор не занимался
    // лишней сортировкой
    std::flat_set<int> flat_set(
      std::sorted_unique_t{},
      elements
    );
  }
}
  • Метод flat_set::extract вместо того, чтобы извлекать узлы (которых у flat_set нет), извлекает контейнер-хранилище. Пример доступен под спойлером и на godbolt.

Пример
#include <flat_map>
#include <print>

int main() {
    std::vector<std::string> keys = {
        "one", "two", "three"
    };
    std::vector<int> values = {
        1, 2, 3
    };
    std::flat_map flat_map(
        std::move(keys), std::move(values)
    );

    std::println("{}", flat_map);

    /*
        Определение containers:
        struct containers
        {
            key_container_type keys;
            mapped_container_type values;
        };
    */
    auto containers = std::move(flat_map).extract();

    // Заметьте, keys и values отсортированы, так как ранее они
    // отсортировались в конструкторе
    // Так что мы можем воспользоваться replace
    // (он ожидает отсортированные данные)
    flat_map.replace(
        std::move(containers.keys),
        std::move(containers.values)
    );

    std::println("{}", flat_map);
}
  • Аналогично, вместо перегрузок insert, принимающих узлы, у flat_set введён метод replace, заменяющий контейнер-хранилище на переданный в аргументе (важный нюанс: передаваемый как аргумент контейнер должен быть отсортирован и в нем не должно быть пар с повторяющимися ключами, иначе будет UB). Пример доступен под спойлером и на godbolt.

Пример
#include <cassert>
#include <flat_set>

/*
    void replace( container_type&& cont );
*/

int main() {
    std::vector<int> keys{1, 2, 3};
 
    std::flat_set<int> flat_set;
    assert(flat_set.empty());
 
    flat_set.replace(std::move(keys));
    assert(flat_set.size() == 3);
    assert(keys.empty());
 }
  • Как мы уже видели в примере с конструктором, у нас появились новые теги: std::sorted_unique_t для flat_set (или flat_map) и std::sorted_equivalent_t для flat_multiset (или flat_multimap) для тех случаев, когда мы точно знаем, что передаваемые нами данные отсортированы. Пример доступен под спойлером и на godbolt.

Пример
#include <flat_set>

int main() {
    std::flat_set<int> flat_set;

    // Тут всё хорошо, insert отсортирует
    // данные за нас
    flat_set.insert({
        15, 27, 18, 7, 41
    });

    // Тут тоже всё хорошо, так как данные
    // отсортированы
    flat_set.insert(
        std::sorted_unique_t{},
        {1, 2, 3, 4, 5}
    );

    // А тут мы нарушили контракт. У нас UB
    flat_set.insert(
        std::sorted_unique_t{},
        {68, 6, 4, 3, 20}
    );
}

Аналогично отличаются интерфейсы flat_map и map, только конструкторы, методы extract и replace оперируют не одним контейнером, а двумя: одним для ключей, другим для значений. Кроме того, у flat_map определены методы keys и values, возвращающие ссылки на соответствующие контейнеры. Пример доступен под спойлером и на godbolt.

Пример
#include <flat_map>
#include <print>

int main() {
    std::vector<std::string> keys = {
        "one", "two", "three"
    };
    std::vector<int> values = {
        1, 2, 3
    };
    std::flat_map flat_map(
        std::move(keys), std::move(values)
    );

    std::println("{}", flat_map);

    /*
        Тип containers:
        struct containers
        {
            key_container_type keys;
            mapped_container_type values;
        };
    */
    auto containers = std::move(flat_map).extract();

    // Заметьте, keys и values отсортированы, так как ранее они
    // отсортировались в конструкторе
    // Так что мы можем воспользоваться replace
    // (он ожидает отсортированные данные)
    flat_map.replace(
        std::move(containers.keys),
        std::move(containers.values)
    );

    std::println("{}", flat_map);
}

Вывод программы:

{"one": 1, "three": 3, "two": 2}
{"one": 1, "three": 3, "two": 2}

Отличие от аналогов

Несмотря на то, что плоские контейнеры были приняты только в C++23 и реализованы в основных компиляторах (gcc 15, clang 21) лишь недавно, они известны в сообществе C++ давно: о них писал и Matt Austern, и Andrei Alexandrescu. А последний даже реализовал flat_map в своей библиотеке Loki под названием AssocVector.

Кроме того, flat_set и flat_map вошли даже в Boost 1.48 больше 12 лет назад под названиями boost::container::flat_set, boost::container::flat_map вместе со своими mutli версиями (из менее популярных проектов плоские контейнеры также реализованы в ETL и Chromium).

Почти единственное, чем отличаются AssocVector и boost::container::flat_map от своих стандартизированных версий — способом хранения данных. Если std::flat_map хранит ключи и значения в отдельных контейнерах, то AssocVector и boost::container::flat_map хранят их в одном контейнере в виде пар (а-ля std::vector<std::pair<K, V>>).

Почему std::flat_map так отличается от своих предков? Неожиданно, но flat_map был сделан именно так, потому что такое расположение элементов в памяти, внезапно, ускоряет вставку маленьких пар ключ-значение на 40-60% по сравнению с классическим дизайном.

Под спойлером приведены результаты бенчмарков, проведенных Zach Laine, автором std::flat_map, и приведенных в оригинальном пропозале P0429R1 «A standard flat_map» (split_map_t в легенде — современный std::flat_map в реализации Zach Laine).

Результаты бенчмарков от Zach Laine
Оригинальные изображения: insert, iterate, lookup
Оригинальные изображения: insert, iterate, lookup

В остальном стандартизированные контейнеры отличаются от их предков из Boost и Loki лишь большей обобщенностью: AssocVector не позволяет изменять тип хранилища, в котором будут лежать данные — там всегда используется std::vector; контейнеры из Boost не позволяли этого вплоть до Boost 1.66, но даже сейчас, когда на дворе уже Boost 1.88, в реализации этой фичи до сих пор чинят баги.

Однако, в одной из ранних реализаций плоских контейнеров, ETL, всё же есть одна занятная особенность, заслуживающая упоминания: в целях улучшения производительности операций вставки, в ней плоские контейнеры реализованы не как отсортированные массивы (плоские контейнеры в ETL имеют ограниченный размер, задаваемый как шаблонный параметр) значений, а как массивы указателей на значения. При этом значения, конечно, вынуждены храниться в отдельном контейнере. С одной стороны мы получаем чуть более быструю вставку за счет того, что указатели относительно дешево копировать, а с другой чуть более долгий доступ к элементам за счет того, что до них нам теперь придется ходить через указатель.

Авторы ETL не приводят никаких сравнений производительности своей реализации с какими-либо другими реализациями, поэтому сделаем их самостоятельно.

Попробуем последовательно повставлять N пар с ключом — псевдо(случайно) сгенерированным int64_t, а значением — захардкоженным int64_t{1} и замерим, сколько времени это займет. На всех графиках ниже по оси X — количество пар в контейнере (шт.), по оси Y — время работы программы (в секундах или миллисекундах — см. подписи на графиках) или объем занимаемой контейнером оперативной памяти (в Мбит или Кбит — см. подписи на графиках).

Бенчмарк последовательной вставки N элементов в контейнер. Ключ — случайный int64_t, значение — int64_t{1}.
Бенчмарк последовательной вставки N элементов в контейнер. Ключ — случайный int64_t, значение — int64_t{1}.

Потом сделаем то же самое, но теперь ключом будет 50-символьный std::string.

Бенчмарк последовательной вставки N элементов в контейнер. Ключ — случайный 50-символьный string, значение — int64_t{1}.
Бенчмарк последовательной вставки N элементов в контейнер. Ключ — случайный 50-символьный string, значение — int64_t{1}.

Что-же, рост производительности по сравнению с std::flat_map виден невооруженным глазом. При этом потребление оперативной памяти всё так же остается низким и вырастает не так уж и значительно, максимум на 10–20%.

Графики потребления памяти тут

Для int64_t:

Для std::string (50 символов):

:

Графики для удаления выглядят точь-в-точь как графики для вставки, и поэтому приведены не будут. Поэтому сразу перейдем к замерам скорости поиска и итерации.

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

Бенчмарк последовательного поиска N элементов в контейнере в случайном порядке. Ключ — случайный int64_t, значение — int64_t{1}.
Бенчмарк последовательного поиска N элементов в контейнере в случайном порядке. Ключ — случайный int64_t, значение — int64_t{1}.
Бенчмарк последовательного поиска N элементов в контейнере в случайном порядке. Ключ — случайный std::string, значение — int64_t{1}.
Бенчмарк последовательного поиска N элементов в контейнере в случайном порядке. Ключ — случайный std::string, значение — int64_t{1}.

Видим, что поиск отдельных элементов действительно стал намного медленнее. Но если мы замерим скорость итерации, то этот график нас порадует (в этом случае замеры производились только для int64_t).

Бенчмарк итерации по N элементам в контейнере. Ключ — случайный int64_t, значение — int64_t{1}.
Бенчмарк итерации по N элементам в контейнере. Ключ — случайный int64_t, значение — int64_t{1}.

По-прежнему быстро!

Нужно ли нам ускорение вставки при том, что по своей природе плоские контейнеры созданы для того, чтобы в них один раз при создании всё вставить и больше не вставлять — вопрос открытый, но, тем не менее, спасибо ETL за интересную реализацию.

Замеры

Наконец, поставим точку в вопросе, быстрее ли в плоских контейнерах поиск, чем не в плоских. Но не будем мелочиться, и сравним плоские контейнеры не только с их не плоскими аналогами, но и с контейнерами, основанными на хэш-таблицах: std::unordered_set, std::unordered_map.

Замеры будем проводить по заветам статьи «Benchmark of major hash maps implementations» за авторством Tessil (Thibaut Goetghebuer-Planchon) — измерим скорость вставки, удаления и поиска для трёх видов ключей-значений: int64_tint64_t, string (15 случайных символов) — int64_t, string (50 случайных символов) — int64_t. При этом сделаем это при разном количестве пар: 200'000 пар, 400'000 пар, и так далее до 3'000'000 пар с шагом 200'000 (кроме этого я сделал замеры для 10–100 пар с шагом 10 и для 20'000–100'000 пар с шагом 20'000, но потом решил, что подробно обсуждать эти результаты бессмысленно — по большей части они совпадают с результатами для 200'000–3'000'000 пар, поэтому речи о них далее вестись не будет, хоть их результаты вы так же можете посмотреть под спойлером ниже). Кроме того, отдельно измерим скорость итерации для ключей-значений int64_tint64_t.Каждое измерение будем повторять пять раз, а в качестве итогового значения выбирать наилучший результат. Исходники всех бенчмарков доступны на github, замеры производились на Linux 6.8.0, Intel® Xeon® Gold 6354 3 ГГц, 8 Гб ОЗУ, компилятор: clang 21.0.0, опции компиляции: -stdlib=libc++ -O3 -march=native -std=c++23.

Если вам интересно посмотреть результаты целиком, добро пожаловать под спойлер (осторожно, очень много букв и графиков). А далее мы лишь подведем итоги.

Результаты бенчмарков
Диапазон 10–100 (шаг 10)

На всех графиках ниже по оси X — количество пар в контейнере (шт.), по оси Y — время работы программы (в секундах или микросекундах — см. подписи на графиках) или объем занимаемой контейнером оперативной памяти (в Мбит или Кбит — см. подписи на графиках).

int64_t — int64_t

Вставки в случайной порядке

Перед каждым замером мы создаем std::vector с значениями [0, N) и перемешиваем этот вектор с помощью функции std::shuffle. Затем для каждого значения k в векторе мы вставляем пару ключ-значение (k, 1) в контейнер.

Вставки пар с случайным ключом

Перед каждым замером мы создаем std::vector размером N, где каждое значение случайным образом генерируется единым генератором (псевдо)случайных чисел из всех возможных положительных значений, которые может содержать int64_t. Затем для каждого значения k в векторе мы вставляем пару ключ-значение (k, 1) в контейнер.

График использования оперативной памяти приведен ниже.

Удаление пар с случайным ключом

Перед каждым замером мы вставляем N элементов таким же образом, как в предыдущем тесте «Вставки пар с случайным ключом». Затем мы удаляем каждый ключ один за другим в случайном порядке, отличном от того, в котором они были вставлены.

Поиск пар

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки в случайной порядке». Затем мы считываем каждую пару ключ-значение в случайном порядке, отличном от того, в котором они были вставлены.

Поиск пар с случайным ключом

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы считываем каждую пару ключ-значение в случайном порядке, отличном от того, в котором они были вставлены.

Поиск несуществующих пар

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор N случайных элементов, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Поиск после удаления половины

Перед каждым замером мы вставляем nb\_entries элементов таким же образом, как в тесте «Вставки пар с случайным ключом», а затем случайным образом удаляем половину этих значений. Затем мы пытаемся найти все исходные значения в другом порядке, что приводит к 50% совпадений и 50% промахов.

Итерирование

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы итерируемся по контейнеру, при этом считывая все пары ключ-значение.

string (15 символов) — int64_t

Вставки пар с случайным ключом

Мы N раз генерируем строку-ключ и вставляем ее в контейнер с значением std::int64_t{1}.

График использования оперативной памяти приведен ниже.

Удаление пар с случайным ключом

Перед каждым замером мы вставляем N элементов в контейнер, как в предыдущем тесте «Вставки пар с случайным ключом». Затем мы удаляем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск пар с случайным ключом

Перед каждым замером мы вставляем N элементов в контейнер, как в тесте «Вставки пар с случайным ключом». Затем мы ищем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск несуществующих пар

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор nb\_entries случайных строк, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Поиск после удаления половины

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки пар с случайным ключом», а затем случайным образом удаляем половину этих значений. Затем мы пытаемся найти все исходные значения в другом порядке, что приводит к 50% совпадений и 50% промахов.

string (50 символов) — int64_t

Вставки пар с случайным ключом

Мы N раз генерируем строку-ключ и вставляем ее в контейнер с значением std::int64_t{1}.

График использования оперативной памяти приведен ниже.

Удаление пар с случайным ключом

Перед каждым замером мы вставляем Nэлементов в контейнер, как в предыдущем тесте «Вставки пар с случайным ключом». Затем мы удаляем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск пар с случайным ключом

Перед каждым замером мы вставляем Nэлементов в контейнер, как в тесте «Вставки пар с случайным ключом». Затем мы ищем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск несуществующих пар

Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор случайных строк, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Поиск после удаления половины

Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом», а затем случайным образом удаляем половину этих значений. Затем мы пытаемся найти все исходные значения в другом порядке, что приводит к 50% совпадений и 50% промахов.

Диапазон 10'000–100'000 (шаг 20'000)
int64_t — int64_t

Вставки в случайной порядке

Перед каждым замером мы создаем std::vector с значениями [0, N) и перемешиваем этот вектор с помощью функции std::shuffle. Затем для каждого значения k в векторе мы вставляем пару ключ-значение (k, 1) в контейнер.

Вставки пар с случайным ключом

Перед каждым замером мы создаем std::vector размером N, где каждое значение случайным образом генерируется единым генератором (псевдо)случайных чисел из всех возможных положительных значений, которые может содержать int64_t. Затем для каждого значения k в векторе мы вставляем пару ключ-значение (k, 1) в контейнер.

График использования оперативной памяти приведен ниже.

Удаление пар с случайным ключом

Перед каждым замером мы вставляем N элементов таким же образом, как в предыдущем тесте «Вставки пар с случайным ключом». Затем мы удаляем каждый ключ один за другим в случайном порядке, отличном от того, в котором они были вставлены.

Поиск пар

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки в случайной порядке». Затем мы считываем каждую пару ключ-значение в случайном порядке, отличном от того, в котором они были вставлены.

Поиск пар с случайным ключом

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы считываем каждую пару ключ-значение в случайном порядке, отличном от того, в котором они были вставлены.

Поиск несуществующих пар

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор N случайных элементов, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Поиск после удаления половины

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки пар с случайным ключом», а затем случайным образом удаляем половину этих значений. Затем мы пытаемся найти все исходные значения в другом порядке, что приводит к 50% совпадений и 50% промахов.

Итерирование

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы итерируемся по контейнеру, при этом считывая все пары ключ-значение.

string (15 символов) — int64_t

Вставки пар с случайным ключом

Мы N раз генерируем строку-ключ и вставляем ее в контейнер с значением std::int64_t{1}.

График использования оперативной памяти приведен ниже.

Удаление пар с случайным ключом

Перед каждым замером мы вставляем N элементов в контейнер, как в предыдущем тесте «Вставки пар с случайным ключом». Затем мы удаляем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск пар с случайным ключом

Перед каждым замером мы вставляем N элементов в контейнер, как в тесте «Вставки пар с случайным ключом». Затем мы ищем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

График использования оперативной памяти приведен ниже.

Поиск несуществующих пар

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор N случайных строк, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Поиск после удаления половины

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки пар с случайным ключом», а затем случайным образом удаляем половину этих значений. Затем мы пытаемся найти все исходные значения в другом порядке, что приводит к 50% совпадений и 50% промахов.

string (50 символов) — int64_t

Вставки пар с случайным ключом

МыN раз генерируем строку-ключ и вставляем ее в контейнер с значением std::int64_t{1}.

График использования оперативной памяти приведен ниже.

Удаление пар с случайным ключом

Перед каждым замером мы вставляем Nэлементов в контейнер, как в предыдущем тесте «Вставки пар с случайным ключом». Затем мы удаляем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск пар с случайным ключом

Перед каждым замером мы вставляем Nэлементов в контейнер, как в тесте «Вставки пар с случайным ключом». Затем мы ищем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск несуществующих пар

Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор случайных строк, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Поиск после удаления половины

Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом», а затем случайным образом удаляем половину этих значений. Затем мы пытаемся найти все исходные значения в другом порядке, что приводит к 50% совпадений и 50% промахов.

Диапазон 200'000–3'000'000 (шаг 200'000)

Вставлять сотни тысяч и миллионы элементов в плоские контейнеры слишком медленно, поэтому тут я произвел только бенчмарки поиска и итерации.

int64_t — int64_t

Поиск пар

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки в случайной порядке». Затем мы считываем каждую пару ключ-значение в случайном порядке, отличном от того, в котором они были вставлены.

Поиск пар с случайным ключом

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы считываем каждую пару ключ-значение в случайном порядке, отличном от того, в котором они были вставлены.

Поиск несуществующих пар

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор N случайных элементов, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Итерирование

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы итерируемся по контейнеру, при этом считывая все пары ключ-значение.

string (15 символов) — int64_t

Поиск пар с случайным ключом

Перед каждым замером мы вставляем N элементов в контейнер, как в тесте «Вставки пар с случайным ключом». Затем мы ищем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск несуществующих пар

Перед каждым замером мы вставляем N элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор N случайных строк, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

string (50 символов) — int64_t

Поиск пар с случайным ключом

Перед каждым замером мы вставляем N элементов в контейнер, как в тесте «Вставки пар с случайным ключом». Затем мы ищем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск несуществующих пар

Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор случайных строк, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Итак, производить много одиночных вставок в плоские контейнеры, как и ожидалось, очень медленно (я даже не смог дождаться прохождения замеров для N \in [200\ 000, 3\ 000\ 000], поэтому провел замеры вставки и удаления для N \in [20\ 000, 100\ 000]): хоть найти место для вставки занимает O(log \  N), но сложность вставки в вектор — по-прежнему O(N).

Бенчмарк последовательной вставки N элементов в контейнер. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.
Бенчмарк последовательной вставки N элементов в контейнер. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.

Удаление также ничем не отличается от вставки: плоские контейнеры драматически проигрывают классическим.

Посмотрите сами, если не верите

Осторожно, графики std::flat_map и boost::containers::flat_map сливаются в одну линию!

Бенчмарк последовательного удаления N элементов в рандомном порядке. Ключи и значения — как в предыдущем бенчмарке. Ось X — количество элементов. Ось Y — время работы программы.
Бенчмарк последовательного удаления N элементов в рандомном порядке. Ключи и значения — как в предыдущем бенчмарке. Ось X — количество элементов. Ось Y — время работы программы.

Единственный интересный момент тут — подтверждение наблюдений Zach Laine, что flat map с двумя контейнерами под капотом (std::flat_map) обгоняет flat map с одним контейнером под капотом (boost::containers::flat_map) по скорости вставки элементов. Но ни о каких 40–60% ускорения тут речи, конечно, не идет. Максимальный наблюдаемый прирост производительности — 12%.

Интересно, но при удалении такой прирост не наблюдается, хотя, казалось бы, операции максимально похожи.

Если смотреть же на скорость поиска, то тут, при малых размерах ключей, например, 8-байтном std::int64_t, и больших объемах, плоские контейнеры существенно превосходят классические упорядоченные контейнеры.

Бенчмарк поиска пар в случайном порядке. Ключи и значения — как в бенчмарке вставки. Ось X — количество элементов. Ось Y — время работы программы.
Бенчмарк поиска пар в случайном порядке. Ключи и значения — как в бенчмарке вставки. Ось X — количество элементов. Ось Y — время работы программы.

Как и при 15-символьным ключе std::string.

Бенчмарк поиска пар в случайном порядке. Ключ — случайный 15-символьный std::string, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.
Бенчмарк поиска пар в случайном порядке. Ключ — случайный 15-символьный std::string, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.

Однако при 50-символьном ключе std::string производительность плоских контейнеров значительно ухудшается и уже не многим становится лучше производительности классических упорядоченных контейнеров.

Бенчмарк поиска пар в случайном порядке. Ключ — случайный 50-символьный std::string, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.
Бенчмарк поиска пар в случайном порядке. Ключ — случайный 50-символьный std::string, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.

На условно маленьких (20'000–100'000 пар) же объемах невысокий прирост производительности наблюдается при абсолютно всех сценариях: даже с маленьким, 8-битным, ключом, std::flat_map лишь незначительно превосходит boost::map.

Бенчмарк поиска пар в случайном порядке. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.
Бенчмарк поиска пар в случайном порядке. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.

А на совсем маленьких объемах (10–100 пар) всё еще хуже: плоские контейнеры как с ключом int64_t, так и с ключом std::string становятся аутсайдерами и если кого-то и обгоняют, то очень неуверенно.

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

Бенчмарк итерации по парам. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.
Бенчмарк итерации по парам. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.

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

Граф потребления ОЗУ. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — объем занимаемой контейнером оперативной памяти.
Граф потребления ОЗУ. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — объем занимаемой контейнером оперативной памяти.

Но классические контейнеры тоже не так плохи и при больших ключах (50-символьный std::string) разница в потреблении памяти становится уже не такой большой.

Граф потребления ОЗУ. Ключ — случайный 50-символьный std::string, значение — int64_t{1}. Ось X — количество элементов. Ось Y — объем занимаемой контейнером оперативной памяти.
Граф потребления ОЗУ. Ключ — случайный 50-символьный std::string, значение — int64_t{1}. Ось X — количество элементов. Ось Y — объем занимаемой контейнером оперативной памяти.

Итог

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

  • Вставка и удаление элементов из плоских контейнеров это ужасно дорого, и лучше делать это как можно реже.

  • Поиск в плоских контейнерах действительно сильно быстрее, чем в классических упорядоченных ассоциативных, но только при больших объемах данных (> 1'000'000 пар) и маленьких размерах ключей. Если пар меньше (20'000–100'000) или ключи большие, то он быстрее, но не сильно. Если же пар совсем мало (10–100), то они оказываются даже медленнее.

  • График времени итерации по плоским контейнерам невероятно красив — он практически плоский. По скорости итерации плоские контейнеры обгоняют все остальные контейнеры на порядки.

  • Плоские контейнеры занимают меньше памяти, чем классические. Для маленьких ключей — на сотни процентов меньше, для больших — на десятки.

И дать совет: если вам нужен упорядоченный ассоциативный контейнер и вы можете инициализировать его при создании — используйте один из плоских контейнеров, ассимптотически они ничем не хуже простых, но по константе выигрывают. Иначе используйте std::(multi)map и std::(multi)set. Если же вам даже не важен порядок — значит, вам не нужны ни плоские контейнеры, ни std::(multi)map и std::(multi)set, используйте хэш-таблицу по вашему вкусу, разве что если ваш случай не критичен к скорости итерации — тут плоские контейнеры не знают равных.

Комментарии (7)


  1. dyadyaSerezha
    06.06.2025 14:50

    Спасибо за интересную статью, но не могу не придраться:

    или объем занимаемой контейнером оперативной памяти (в Мбит или Кбит — см. подписи на графиках).

    Не в Мбит/Кбит, а в обыденных мега/кило, то есть, в миллионах и тысячах, но байт.


  1. Jijiki
    06.06.2025 14:50

    классно спасибо) интересно как они поведут себя там где им место в вокселях(пишу так потомучто 6 граней подразумеваю от центроида по логике отрисовки тоже вокселем), там вся последовательность плоская, я на векторе делал), со всеми оптимизациями(воксельными)) там вообще класс выходит

    получается в bvh их тоже можно использовать вроде, надо же только пробежаться ) надо тестить )


  1. Tuxman
    06.06.2025 14:50

    Спасибо за статью. Было бы ещё здорово сравнить с std::pmr контейнерами c
    monotonic_buffer_resource.


    1. dalerank
      06.06.2025 14:50

      Так pmr это всё те же контейнеры, у них только аллокаторы другие используются. При желании вы и flat_map можете сделать pmr, там перф подрастает по другой причине


      1. AnatoliiShablov
        06.06.2025 14:50

        Да. Благодаря чему обычные map set становятся cache friendly. И казалось бы время поиска/вставки/... тоже должны уменьшиться. Но надо бенчить


        1. dalerank
          06.06.2025 14:50

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


  1. SergeyVSorokin
    06.06.2025 14:50

    Мы заменяли обычный map на flatmap (из Abseil) после того, как я наблюдал деструктор map, который работал 10 минут и при этом ещё блочил все остальные потоки приложения, если они пытались что-то сделать с памятью.

    Замена на flat map привела к ускорению и экономии памяти что-то там в сотни раз по всему алгоритму, пауза на освобождение памяти тоже исчезала. Скорость вставки в чистом виде не замерялась, так как там ещё некоторая логика есть для вычисления что вставлять, включая чтение из базы, поэтому так просто не выделить вклад именно хеша. Но мне кажется на искусственных тестах вставка тоже быстрее была.

    Так что рекомендую, при больших объемах данных.