folly::fbvector — улучшенный std::vector от Facebook

Folly ^[1] — это открытая С++ библиотека, разрабатываемая Facebook и используемая им во внутренних проектах. С целью оптимизации расходов памяти и процессорных ресурсов библиотека включает собственные реализации некоторых стандартных контейнеров и алгоритмов. Одной из них является folly::fbvector ^[2] — замена стандартного вектора (std::vector). Реализация от Facebook полностью совместима с оригинальным интерфейсом std::vector, изменения всегда не-негативны, почти всегда измеримы, часто — существенно, а иногда даже грандиозно влияют на производительность иили расход памяти. Просто включите заголовочный файл folly/FBVector.h и замените std::vector на folly::fbvector для использования его в своём коде.

Пример

folly::fbvector<int> numbers({0, 1, 2, 3});
numbers.reserve(10);
for (int i = 4; i < 10; i++) {
  numbers.push_back(i * 2);
}
assert(numbers[6] == 12);

Мотивация

std::vector — устоявшаяся абстракция, которую многие используют для динамически-аллоцируемых массивов в С++. Также это самый известный и самый часто используемый контейнер. Тем большим сюрпризом оказывается то, что его стандартная реализация оставляет достаточно много возможностей по улучшению эффективности использования вектора. Этот документ объясняет, как реализация folly::fbvector улучшает некоторые аспекты std::vector. Вы можете воспользоваться тестами из folly/test/FBVectorTest.cpp ^[3] чтобы сравнить производительность std::vector и folly::fbvector.

Управление памятью

Известно, что std::vector растёт экспотенциально (с константным коэффициентом роста). Важный нюанс в правильном выборе этой константы. Слишком маленькое число приведёт к частым реаллокациям, слишком большое — будет съедать больше памяти, чем реально необходимо. Изначальная реализация Степанова использовала константу 2 (т.е. каждый раз, когда вызов push_back требовал расширения вектора — его емкость увеличивается вдвое).

Со временем некоторые компиляторы уменьшили эту константу до 1.5, но gcc упорно использует 2. На самом деле можно математически доказать, что константа 2 — строго худшее из всех возможных значений, потому что оно никогда не позволяет переиспользовать ранее выделенную вектором память.

Чтобы понять почему это так — представьте себе вектор размером в n байт, уже полностью заполненный, в который пытаются добавить ещё один элемент. Это приводит, согласно реализации std::vector, к следующим шагам:

1. Выделяется память, размером в 2 * n байт. Скорее всего, она будет выделена в адресном пространстве ЗА текущим вектором (может быть непосредственно за, может быть через какой-то промежуток).
2. Старый вектор копируется в начало нового.
3. В новый вектор добавляется новый элемент.
4. Старый вектор удаляется.

Когда дело дойдёт до увеличения этого нового вектора — он будет увеличен до 4 * n, далее — до 8 * n и т.д. При каждом новом выделении памяти её будет требоваться больше, чем для всех предыдущих векторов, вместе взятых, поскольку на каждом шаге k нам понадобиться (2 ^ k) * n байт памяти, а это всегда больше суммы (2 ^ (k — 1)) * n + (2 ^ (k — 2)) * n… + ((2 ^ 0 )) * n

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

График показывает что при константе увеличения ёмкости равной 1.5 (синяя линия) память может быть переиспользована уже послге 4-го шага увеличения вектора, при 1.45 (красная линия) — после третьего, и при 1.3 (чёрная линия) — после второго.

Конечно, график выше делает несколько упрощений по поводу того, как в реальном мире работают аллокаторы памяти, но факт того, что выбранная gcc константа 2 является теоретически худшим случаем, от этого не меняется. fbvector использует константу 1.5. И это не бьёт по производительности на малых размерах векторов, из-за того, как fbvector взаимодействует с jemalloc.

Взаимодействие с jemalloc

Практически все современные аллокаторы памяти выделяют память определёнными квантами, выбранными так, чтобы минимизировать накладные расходы на управление памятью и в то же время дать хорошую производительность на малых размерах выделяемых блоков. К примеру, аллокатор может выбирать блоки примерно так: 32, 64, 128,… 4096, затем пропорционально размеру страницы до 1 МБ, затем инкременты по 512 КБ и так далее.

Как обсуждалось выше, std::vector также требует выделения памяти квантами. Размер следующего кванта определяется исходя из текущей ёмкости вектора и константы роста. Таким образом в почти каждый момент времени у нас имеется некоторое количество неиспользуемой в текущий момент времени памяти в конце вектора, и сразу за ним — некоторое количество неиспользуемой памяти в конце блока памяти, выделенного аллокатором. Сам по себе напрашивается вывод о том, что союз аллокатора вектора и общего аллокатора памяти может дать оптимизацию расхода ОЗУ — ведь вектор может попросить у аллокатора блок «идеального» размера, исключив неиспользуемую память в блоке, выделенном аллокатором. Ну и вообще общую стратегию выделения памяти вектором и аллокатором можно заточить лучше, если знать точную реализацию того и другого. Именно это и делает fbvector — он автоматически определяет использование jemalloc и подстраивается под его алгоритмы выделения памяти.

Некоторые аллокаторы памяти не поддерживают in-place реаллокацию (хотя большинство современных всё-же поддерживают). Это результат не слишком удачного дизайна сишной функции realloc(), которая сама решает, переиспользовать ли ей ранее выделенную память, или выделить новую, скопировать туда данные и освободить старую. Этот недостаток контроля выделения памяти сказывается и на операторе new в С++ и на поведении std:allocator. Это серьёзный удар по производительности, поскольку in-place реаллокация, будучи очень дешевой, приводит к значительно менее аггрессивной стратегии роста потребляемой памяти.

Реаллокация объектов

Одним из важных вопросов размещения объектов С++ в памяти является то, что по-умолчанию они считаются неперемещаемыми. Перемещаемым считается объект типа, который может быть скопирован в другое место памяти путём побитового копирования и при этом в новом месте объект полностью сохранит свою валидность и целостность. К примеру, int32 является перемещаемым, потому что 4 байта полностью описывают состояние 32-битного знакового числа, если скопировать эти 4 байта в другое место памяти — этот блок памяти может полностью однозначно быть интерпретирован как то же самое число.

Предположение С++ о том, что объекты являются неперемещаемыми вредит всем и делает это лишь ради нескольких спорных моментов архитектуры. Перемещение объекта предполагает выделение памяти под новый объект, вызов его конструктора копирования, уничтожение старого объекта. Это не очень приятно и вообще против здравого смысла. Представьте себе теоретический разговор капитана Пикара и Скептического Инопланетянина:

Скептический Инопланетянин: Итак, этот ваш телепорт — как он работает?
Пикар: Он берёт человека, дематериализует его в одном месте и материализует в другом
Скептический Инопланетянин: Хм… это безопасно?
Пикар: Да, правда в первых моделях были мелкие недочёты. Сначала человек просто клонировался, создавался в новом месте. После этого оператор телепорта должен был вручную застрелить оригинал. Спроси О'Браяна, он работал интерном как-раз на этой должности. Не очень элегантная была реализация.

(прим. переводчика: видимо, это писалось до внедрения конструкторов перемещения в последних стандартах С++).

На самом деле только часть объектов нействительно неперещаемы:

• Те, в которых есть указатели на внешние объекты
• Те, на которые указывают указатели из других объектов

Объекты первого типа всегда могут быть переделаны с минимальными затратами. Объекты второго типа не должны создаваться оператором new и удаляться оператором delete — они должны быть управляемы умными указателями и никаких проблем не будет.

Перемещаемые объекты весьма интересны для std::vector, поскольку знание о том, как перемещать объекты внутри вектора существенно влияет на эффективность реаллокации вектора этих объектов. Вместо вышеописанного Пикардовского цикла перемещения, объекты можно перемещать простым memcpy или memmove. К примеру, работа с типами вроде vector<vector> или vector<hash_map<int, string>> может быть значительно быстрее.

Для того, чтобы поддерживать безопасное перемещение объектов, fbvector использует типаж (trait) folly::IsRelocatable, определённый в «folly/Traits.h». По-умолчанию, folly::IsRelocatable::value консервативно возвращает false. Если вы точно знаете, что ваш тип Widget является перемещаемым, вы можете сразу после объявления этого типа дописать:

namespace folly {
  struct IsRelocatable<Widget> : boost::true_type {};
}

Если вы не сделаете этого, fbvector не скомпилируется с BOOST_STATIC_ASSERT.

Дополнительные ограничения

Некоторые улучшения также возможны для «простых» типов (точнее для тех, которые имеют тривиальную операцию присваивания) или для тех типов, которые имеют конструктор, не выбрасывающий исключений (nothrow default constructor). К счастью, эти типажи уже присутствуют в стандарте С++ (ну или в Boost). Суммируя, для работы с fbvector тип Widget должен удовлетворять условию:

BOOST_STATIC_ASSERT( IsRelocatable::value && (boost::has_trivial_assign::value || boost::has_nothrow_constructor::value));

Эти типажи на самом деле очень близки — достаточно сложно сконструировать класс, который будет удовлетворять одной части условия и нарушить другую (разве что специально очень постараться). fbvector использует эти простые условия для минимизации операций копирования для основных операций с вектором (push_back, insert, resize).

Для упрощения проверки типа на совместимость с fbvector в Traits.h есть макрос FOLLY_ASSUME_FBVECTOR_COMPATIBLE.

Разное

Реализация fbvector сконцентрирована на эффективности использования памяти. В будущем может быть улучшена реализация копирования из-за того, что memcpy не является intrinsic-функцией в gcc и не идеально работает для больших блоков данных. Также возможно улучшение в области взаимодействия с jemalloc.

Удачного вам использования fbvector.

Автор: tangro

Источник ^[4]