[Перевод] folly::fbvector — улучшенный std::vector от Facebook25.09.2014 15:03

Folly — это открытая С++ библиотека, разрабатываемая Facebook и используемая им во внутренних проектах. С целью оптимизации расходов памяти и процессорных ресурсов библиотека включает собственные реализации некоторых стандартных контейнеров и алгоритмов. Одной из них является folly: fbvector — замена стандартного вектора (std: vector). Реализация от Facebook полностью совместима с оригинальным интерфейсом std: vector, изменения всегда не-негативны, почти всегда измеримы, часто — существенно, а иногда даже грандиозно влияют на производительность и\или расход памяти. Просто включите заголовочный файл folly/FBVector.h и замените std: vector на folly: fbvector для использования его в своём коде.Пример folly: fbvector 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 чтобы сравнить производительность std::vector и folly::fbvector.Управление памятью Известно, что std::vector растёт экспотенциально (с константным коэффициентом роста). Важный нюанс в правильном выборе этой константы. Слишком маленькое число приведёт к частым реаллокациям, слишком большое — будет съедать больше памяти, чем реально необходимо. Изначальная реализация Степанова использовала константу 2 (т.е. каждый раз, когда вызов push_back требовал расширения вектора — его емкость увеличивается вдвое).Со временем некоторые компиляторы уменьшили эту константу до 1.5, но gcc упорно использует 2. На самом деле можно математически доказать, что константа 2 — строго худшее из всех возможных значений, потому что оно никогда не позволяет переиспользовать ранее выделенную вектором память.

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

Выделяется память, размером в 2 * n байт. Скорее всего, она будет выделена в адресном пространстве ЗА текущим вектором (может быть непосредственно за, может быть через какой-то промежуток). Старый вектор копируется в начало нового. В новый вектор добавляется новый элемент. Старый вектор удаляется. Когда дело дойдёт до увеличения этого нового вектора — он будет увеличен до 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> может быть значительно быстрее.

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

namespace folly { struct IsRelocatable: 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.