folly::fbvector - покращений std::vector від Facebook

Folly — це відкрита бібліотека С++, що розробляється Facebook і використовується їм у внутрішніх проектах. З метою оптимізації витрат пам'яті і процесорних ресурсів бібліотека включає власні реалізації деяких стандартних контейнерів і алгоритмів. Однією з них є folly::fbvector — заміна стандартного вектора (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, щоб порівняти продуктивність 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 (чорна лінія) — після другого.

image

Звичайно, графік вище робить кілька спрощень з приводу того, як в реальному світі працюють аллокаторы пам'яті, але факт того, що обрана 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.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.