Під капотом STL: візуалізація алгоритмів стандартної бібліотеки C++
Вітаю, спільното! Мене звати Макс, я працюю розробником у компанії Apriorit вже понад пʼять років. Сьогодні я хочу розглянути доволі класичну тему роботи з С++, а саме: алгоритми стандартної бібліотеки. Зважаючи на довгу історію цієї мови програмування, непомірну кількість рядків коду та сучасні продукти, розробка яких почалася задовго до народження автора статті, може скластися враження, що у світі С++ давно нічого не відбувається, відповіді на всі питання вже знайдені, а підводні камені давно не привертають нічиєї уваги, але, запевняю, це все ще не так.
Насамперед слід зазначити, що, оскільки з кожним роком С++ Standard Template Library (STL) вбирає в себе все більше і більше функціоналу, задля змістовного огляду алгоритмів надалі ми введемо декілька обмежень:
— розглянемо лише деякі алгоритми С++ до версії С++17 включно, і, що очевидно, виключно в рамках стандартної бібліотеки;
— алгоритми будемо розбирати у парі з найрозповсюдженішим неперервним мутабельним контейнером, тобто std::vector з його стандартним алокатором;
— оскільки ми тут за ключовими концепціями та загальним розумінням, то деякі деталі внутрішньої будови алгоритмів будуть розглядатись досить абстрактно.
Почнемо з найважливішого питання: нащо нам потрібна стандартна бібліотека та чому її використання є дуже важливою частиною роботи, незалежно від мови програмування?
Подобається нам це чи ні, та незважаючи на початок
Повертаючись до C++ STL. З моєї практики, оскільки бібліотека створена саме для розв’язання проблем, найбільш важливо не тільки розуміти, які саме проблеми ми можемо вирішити стандартними підходами, а й мати бачення того, що від нас потребує стандартна бібліотека, щоб не створити нових. Власне, з розумінням того, як зазвичай влаштовані ті чи інші алгоритми, а також які вони використовують підходи для вирішення задач, нам допоможуть візуалізації, до котрих ми звернемось вже незабаром. Але перед тим нам треба згадати загальні положення та вимоги, до яких апелює STL.
Back to basics
Ітератори
Як ми всі пам’ятаємо, літера T в STL означає Template, і на мій погляд найбільш важливим шаблоном, який пронизує всю бібліотеку, є ітератор.
Що таке взагалі ітератор? Незалежно від мови програмування чи платформи, з котрою ми працюємо, ми завжди працюємо з даними, структурами даних, що визначають розміщення цих даних в пам’яті та алгоритмами, які проводять операції над структурами даних. Оскільки ми маємо безліч різних структур даних та ще більшу кількість алгоритмів, частина з котрих має власні вимоги до моделей пам’яті та роботи з ними, задля розмежування використовується патерн-ітератор. Виходячи з загального поняття, ітератор — це патерн, що надає нам простий інтерфейс для доступу до даних, незважаючи на особливості їх розміщення в пам’яті.
Загалом стандартна бібліотека С++17 налічує п’ять основних різновидів ітераторів, функціонал котрих звужується знизу догори, як на рисунку:
Легко помітити закономірність: що простіше влаштована модель пам’яті тієї чи іншої структури даних, то більше можливостей у її ітератора, а вже через це структура придатна до роботи з більшою кількістю алгоритмів. Виходячи з цього, найцікавішим для нас ітератором є random_access_iterator, оскільки з ним сумісна абсолютна більшість алгоритмів стандартної бібліотеки. А також він характерний для найрозповсюдженіших структур даних STL, а саме: array, vector та *string.
В рамках С++ ітератори працюють наступним чином:
Як ви вже згадали, в кожного ітератора є свій begin() та end(), де перший вказує на початок даних, а другий — на елемент, наступний після кінця проміжку даних. Залежно від типу ітератора, він також може мати rbegin() та rend() функціонал, що дозволяє безпечно ітеруватися з кінця колекції.
Зазвичай робота з ітераторами має під собою передачу алгоритму інформації про розміщення першого елементу послідовності незалежно від її типу та елементу за останнім елементом нашої послідовності. У нашому випадку послідовність обмежена arr.end(), який посилається на елемент за останнім, тобто на невалідний елемент для доступу. Крім того, оскільки це random_access_iterator, то ми майже не маємо обмежень в операціях, що дозволяє нам як використовувати оператор квадратних дужок до ітератора, так і просто інкрементувати його у будь-якому з напрямів:
{
std::array<int, 10> arr { 12, 5, 3, 4, 3, 6, 7, 4, 8, 10 };
std::sort(arr.begin(), arr.end());
for (auto it = arr.begin(); it != arr.end(); ++it)
std::cout << *it << ' '; // 3 3 4 4 5 6 7 8 10 12
auto it = arr.begin();
std::cout << '\n' << it[5]; // 6
}
Категорії алгоритмів
Як ми вже згадали, ітератори мають власні особливості та відповідні категорії. А як щодо алгоритмів?
Аналогічним чином алгоритми можуть бути розбиті на дві велетенські умовні групи: немодифікуючі та модифікуючі, де перші — здебільшого забезпечують обхід колекцій, водночас другі — проводять ті чи інші модифікації.
Загалом, якщо розглядати тільки частину <algorithm>, виключивши більш специфічні <numeric> та <memory>, ми отримаємо наступне дерево, що розбиває більше сотні алгоритмів за десятьма умовними категоріями, з яких ми надалі розглянемо половину:
Неявні вимоги алгоритмів
Крім очевидних явних вимог алгоритмів щодо ітераторів, які перевіряються ще на етапі компіляції — ми можемо зустріти два види неявних вимог, невиконання яких призведе до UB:
1. Вимоги strict weak ordering
Більшість алгоритмів С++, що використовують предикати (представляються лямбдою, вільною функцією, функціональним об’єктом або обгорткою std::function) — мають неявні вимоги щодо впорядкування, порушення яких призводить до UB.
Предикати Comp вимагають узгодження Strict Weak Ordering, що полягає у наступних правилах:
— асиметрія: якщо comp(a, b) істинний, то comp(b, a) має бути хибним;
— транзитивність: якщо comp(a, b) і comp(b, c) істинні, то comp(a, c) також істинний;
— транзитивність еквівалентності: eq(a, b) := !comp(a, b) && !comp(b, a), в рамках цього eq повинен бути еквівалентністю;
— детермінованість: під час роботи алгоритму чи декількох алгоритмів, як правило, стан їх компаратора не повинен змінюватися чи залежати від зовнішнього стану.
На практиці ці помилки виглядають приблизно наступним чином:
// порушення асиметрії: comp(5, 5) && comp(5, 5) == true
bool comp(int a, int b) { return a <= b; }
// порушення асиметрії при порівнянні кількох полів:
// {"Alice", 20000315} < {"Bob", 19951020}: "Alice" < "Bob" == true
// {"Bob", 19951020} < {"Alice", 20000315}: "Bob" < "Alice" == false, 19951020 < 20000315 == true
// a < b ∧ b < a - протиріччя
struct User
{
std::string name;
std::uint64_t birth_date;
};
bool operator<(const User& u1, const User& u2)
{
if (u1.name < u2.name) return true;
// загубили перевірку u2.name < u1.name
return u1.birth_date < u2.birth_date;
}
// порушення транзитивності: 1 < 2, 2 < 3, але !(1 < 3)
bool comp2(int a, int b) { return (a + 1) == b; }
// порушення транзитивності еквівалентності: "abc123" ≡ "abc456", "abc456" ≡ "abc789", але "abc123" ≢ "abc789"
bool comp3(std::string_view left, std::string_view right) { return left.substr(0, 3) < right.substr(0, 3); }
// залежність від глобального стану
int pivot;
bool comp4(int a, int b) { return (a % pivot) < (b % pivot); }
// неузгоджені компаратори між sort та lower_bound
std::sort(vct.begin(), vct.end(), ByLenOnly{});
std::lower_bound(vct, "abc", std::ranges::less{});
2. Специфічні до алгоритмів вимоги
Крім озвучених неявних вимог щодо strict weak ordering компаратора, алгоритми можуть також вимагати дотримання власних вимог, наприклад:
— binary_search/lower_bound/upper_bound/equal_range, set_* та inplace_merge — вимагають, щоб вхідний діапазон був відсортований, причому з використанням одного і того ж компаратора;
— remove, unique, partition — вимагають додаткового виклику специфічних операцій, наприклад erase, оскільки виконують лише підготовку даних;
— copy* та transform — вимагають наявність достатнього місця для вихідного ітератора.
Алгоритми стандартної бібліотеки
std::partition
Почнемо з чогось простого, з чим ми працюємо щодня, рідко замислюючись про те, яка магія ховається під капотом. Доволі часто нам треба взяти готову послідовність та розбити її на дві групи, використовуючи якийсь предикат, щоб потім прибрати все зайве.
Наприклад, в нас є якась послідовність чисел: [15] [2] [46] [8] [23] [5], яку треба розбити на діапазони парних та непарних. Очевидним кандидатом для «відтиснення» елементів є std::partition, з його допомогою ми матимемо наступне:
{
std::vector<int> vct { 15, 2, 46, 8, 23, 5 };
// mid вказує на початок непарних
auto mid = std::partition(vct.begin(), vct.end(),
[](int x) { return x % 2 == 0; });
// ...
}
Виглядає досить просто, але що насправді відбувається всередині?
Як вже можна було звернути увагу, в нас використовується два ітератори: один ітерується з початку послідовності, у той час, як інший — з кінця, що є дуже розповсюдженим підходом поміж стандартних алгоритмів.
Логіка алгоритму доволі проста:
— жовтогарячий ітератор йде з початку послідовності та знаходить невідповідний предикату елемент;
— зелений ітератор, рухаючись з кінця, навпаки знаходить відповідний до предиката елемент, як на першому етапі;
— відбувається swap значень ітераторів;
— цикл продовжується, допоки ітератори не зустрінуться, як на четвертому етапі;
В рамках роботи з цим алгоритмом треба пам’ятати одну дуже важливу річ:
— std::partition не зберігає відносний порядок елементів, задля цього слід використовувати std::stable_partition.
std::remove
Окей, ми загадали, як можна розбивати послідовність на дві частини за предикатом, а що робити, якщо нам треба просто прибрати якийсь зайвий елемент з послідовності?
Наприклад, ми маємо послідовність [1] [3] [2] [3] [4] [3] і нам треба позбутись трійок. Фактично ми можемо також скористатись std::partition, але ідіоматичніше буде використання std::remove:
{
std::vector<int> vct { 1, 3, 2, 3, 4, 3 };
// лишаємо все крім трійок
auto new_end = std::remove(vct.begin(), vct.end(), 3);
// видаляємо "хвіст" зі сміттям
vct.erase(new_end, vct.end());
}
Розглянемо, що ховається від нас під капотом:
Алгоритм дуже схожий з std::partition, робота також спирається на використання двох ітераторів, але:
— обидва ітератори рухаються зліва направо;
— жовтогарячий ітератор працює з елементами, що не задовольняють предикату, його простіше сприймати як записуючий.
Цей ітератор «відкриває» елемент для запису на першому етапі;
— зелений ітератор краще вважати читаючим ітератором. На другому етапі він знаходить елемент, що не відповідає предикату, тобто двійку;
— на третьому етапі відбувається swap значень записуючого та читаючого ітераторів, після чого вже третій елемент відкривається на запис, адже він являє собою сміття;
— на четвертому етапі зелений — читаючий ітератор знову знаходить елемент, що не відповідає предикату;
— на п’ятому етапі відбувається swap, після чого записуючий ітератор зміщує свою позицію та відкриває новий елемент на запис;
— ітерації продовжуються, допоки зелений-читаючий ітератор не почне вказувати на end() послідовності, як на етапі 6.
— на останньому, сьомому етапі відбувається виклик vector::erase, і «сміттєва» частина вектора відмічається під перезапис.
Для цього алгоритму слід відзначити багато деталей, оскільки алгоритм:
— зберігає порядок елементів, що не задовольняють предикат;
— буквально залишає за собою сміття у правій частині для подальшого видалення;
— потребує від нас окремого виклику erase, задля «маркування» даних під перезапис;
— працює трохи швидше аніж std::partition для великих об’ємів даних, адже ми ітеруємось з однієї сторони, що зменшує кількість cache-miss’ів процесора.
std::rotate
Перейдемо до чогось складнішого, а саме трансформуючих алгоритмів. Що робити, якщо нам треба «прокрутити» деяку послідовність елементів, щоб кінець послідовності був розміщений на початку, як це зазвичай відбувається для черг?
Для прикладу візьмемо послідовність елементів [1] [2] [3] [4] [5] [6] [7] [8] [9] та зробимо так, щоб елементи [7] [8] [9] розмістилися на початку. У цьому нам допоможе std::rotate. Загалом ця операція буде виглядати наступним чином:
{
std::vector<int> vct { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
// зміщаємо елементи [7] [8] [9] на початок
std::rotate(vct.begin(), vct.begin() + 6, vct.end());
}
Найцікавіше, як завжди, всередині:
В рамках цього алгоритму ми розглядаємо більш специфічний випадок з BidirectionalIterator, адже саме він характерний для техніки трьох обертів, у той час як RandomAccess у багатьох стандартних бібліотеках може опускати цю техніку на користь більш оптимізованих підходів з алокацією.
Як ми могли звикнути, тут також використовується два ітератори задля наступної логіки:
— послідовність розбивається на два проміжки;
— перший проміжок обертається так, щоб змінити свою послідовність в протилежний напрямок, як на першому етапі. Під обертанням мається на увазі використання std::reverse в парі з std::iter_swap, задля обходу послідовності з обох кінців і зміни її значень місцями;
— для другого проміжку робиться те ж саме — алгоритм звертає його порядок, як на другому етапі;
— на фінальному третьому етапі відбувається третє обертання й порядок елементів змінюється для всієї послідовності, тим самим переміщаючи останню трійку елементів на початок.
Хоча цей алгоритм і не має дуже специфічних особливостей, але є одне логічне обмеження, порушення якого призведе до UB: другий параметр (у нашому випадку vct.begin() + 6) слід задавати з обережністю, адже він повинен знаходитись виключно між vct.begin() та vct.end().
std::transform
Ще одним цікавим прикладом трансформуючих алгоритмів є нормування послідовності.
Припустимо, що у нас є послідовність [1] [2] [3] [4] [5] [6] [7] [8] [9], для якої нам треба вирівняти елементи так, щоб мінімальним був трійка, а максимальним — сімка. Для цього ми можемо скористатись алгоритмом std::transform у парі із std::clamp, де перший дозволяє обійти послідовність, використавши трансформуючий предикат, а другий як частина трансформуючого предиката буде нормувати елементи. У коді такий підхід виглядатиме наступним чином:
{
std::vector<int> vct { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
std::transform(vct.begin(), vct.end(), vct.begin(),
[](int val) { return std::clamp(val, 3, 7); });
}
У випадку цієї пари алгоритмів все виглядає дуже просто:
— ми маємо один ітератор, який викликає компаратор для кожного елемента при прямій проходці;
— компаратор (std::clamp) перевіряє значення елемента та змінює його відповідно до границь значень, тобто або підганяє до трійки, або зрізає до сімки;
— процес відбувається, доки ітератор не дійде до межі послідовності.
Як завжди, треба пам’ятати декілька важливих деталей:
— третій параметр std::transform — це вихідний ітератор, тобто послідовність може бути не лише перезаписана на місці, а й винесена в окрему структуру даних, розмір якої повинен бути відповідним для розміщення даних, адже std::transform не перевіряє межі послідовності;
— std::clamp не перевіряє діапазон, тобто виклик std::clamp(val, 7, 3) призведе до UB, адже ми маємо min > max.
std::lower_bound
Розглядаючи алгоритми, ніяк не можна пройти повз пошуку, особливо в рамках відсортованих послідовностей. Наявність відсортованості автоматично повинна нагадувати нам про можливість використання бінарного пошуку, але std::binary_search стандартної бібліотеки надає змогу лише перевірити наявність елемента, не розкриваючи його позиції. То що робити?
У цьому випадку на допомогу приходить std::lower_bound та std::upper_bound(), які, використовуючи бінарний пошук, надають доступ до першого елемента, що не менший за шукане значення та першого елемента, що більший за шукане значення відповідно. У коді бінарний пошук елемента зліва виглядатиме наступним чином:
{
std::vector<int> vct { 1, 2, 3, 4, 6, 6, 7, 8 };
int value = 5;
auto it = std::lower_bound(vct.begin(), vct.end(), value);
if (it != vct.end() && *it == value)
{
// …
}
}
Під капотом все як завжди цікавіше:
Ми маємо два ітератори, що рухаються з різних боків послідовності:
— ці ітератори не використовують прямий перебір, натомість вони розділяють послідовність навпіл на кожному з етапів, відкидаючи зайву половину для пошуку, як на першому етапі;
— після отримання скороченого проміжку, в котрому потенційно лежить наш елемент, проміжок також поділяється навпіл, що можна побачити на другому етапі;
— це відбувається, доки ми не знайдемо один елемент, який буде або відповідати шуканому елементу, або бути елементом зі значенням більше;
— оскільки на третьому етапі четвірка — менша за шуканий елемент, то шукана п’ятірка потенційно буде знаходитись у правій частині діапазону, тобто: [elem; end()), і якщо elem не відповідає шуканому елементу, як в нашому випадку, то його в діапазоні немає.
В рамках роботи з std::lower_bound та std::upper_bound слід пам’ятати про декілька важливих вимог:
— діапазон, у котрому ми шукаємо елемент, повинен бути відсортованим тим самим компаратором, яким відбувається пошук;
— оскільки ми можемо отримати ітератор зі значенням end(), ще до його використання необхідно провести відповідну перевірку.
std::equal_range
Ми вже розглянули, як std::lower_bound та std::upper_bound можуть допомагати з пошуком меж входження елемента. Але що робити, коли потрібно отримати одразу обидві межі — і ліву, і праву? В рамках рішення такої задачі стандартна бібліотека надає std::equal_range:
{
std::vector<int> vct { 1, 2, 4, 4, 4, 6, 7, 8 };
int value = 4;
auto [low, high] = std::equal_range(vct.begin(), vct.end(), value);
if (low != high)
{
// …
}
}
Під капотом від нас приховали використання і std::lower_bound, і std::upper_bound:
Фактично алгоритм std::equal_range це бінарний пошук для одного й того ж елементу з обох частин:
— на першому етапі ми розділяємо послідовність навпіл та шукаємо будь-який елемент, еквівалентний шуканому, реалізуючи звичайний бінарний пошук;
— на другому етапі обмеження відбувається вже з лівої сторони, допоки ми не знайдемо позицію еквівалентну чи більшу шуканій;
— на третьому етапі ітератори вже вказують на одну й ту саму позицію-початок шуканої послідовності;
— починаючи з четвертого етапу реалізується логіка upper_bound, тепер ми розглядаємо праву частину, отриману при першому розбитті;
— надалі відбувається такий же бінарний пошук із подвійним скороченням послідовності, допоки ми не знайдемо елемент, який буде «закривати» шукану послідовність, як на етапі п’ять;
— в результаті на шостому етапі ми отримаємо шукану підпослідовність [first; second).
Використання std::equal_range накладає аналогічні до std::lower_bound та std::upper_bound вимоги:
— діапазон, у котрому ми шукаємо елемент, повинен бути відсортований тим самим компаратором, за якого відбувається пошук;
— оскільки обидва ітератори у поверненій парі можуть вказувати на end() або на одну й ту саму позицію, коли елемент не знайдено, перед використанням діапазону варто перевіряти, що low != high.
std::sample
Коли необхідно реалізувати будь-яку випадкову вибірку елементів, ніяк не можна обійтись без використання алгоритму std::sample, що дозволяє обрати k випадкових елементів з послідовності. На перший погляд усе просто: у випадку std::vector ми заздалегідь знаємо розмір послідовності, тож можна просто згенерувати випадковий набір індексів. А що, якщо ми заздалегідь не знаємо розміру послідовності, але все одно потребуємо рівноімовірної вибірки?
Для наочності у такому випадку можна скористатись std::istringstream та його input-ітератором::
{
std::istringstream stream{"1 2 3 4 5 6 7 8"};
std::vector<int> result(3);
int static_seed = 42;
std::mt19937 gen(static_seed);
std::sample(std::istream_iterator<int>(stream),
std::istream_iterator<int>(),
result.begin(),
result.size(),
gen);
}У випадку input-ітератора std::sample використовує Reservoir Sampling, що виглядатиме наступним чином:
Reservoir Sampling використовує простий принцип: для кожного
— на першому етапі відбувається повне первинне заповнення резервуара першими елементами послідовності;
— на другому етапі ми випадково обираємо одну з трьох позицій і розміщуємо в неї четвірку, витісняючи двійку;
— на третьому етапі випадковий індекс виходить за межі резервуара, тому п’ятірка не потрапляє у вибірку;
— на четвертому етапі випадковий індекс знову влучає в резервуар, і шестірка витісняє одиницю;
— на п’ятому етапі сімка не потрапляє у вибірку, оскільки випадковий індекс виходить за межі резервуара;
— на шостому етапі вісімка витісняє трійку, займаючи останню позицію.
Цей алгоритм має деякі яскраві особливості:
— std::sample може зберігати відносний порядок елементів вибірки лише для forward-сумісних ітераторів, у випадку з input ітератором порядок буде випадковим;
— оскільки ми маємо справу з імовірностями, варто пам’ятати про використання динамічного seed для реальних задач.
Паралельні алгоритми у С++17
Дотепер ми розглядали алгоритми в їхньому традиційному вигляді, що цілком підходить для розв’язання більшості повсякденних задач. Утім коли обсяг даних зростає до мільйонів елементів, послідовне виконання стає вузьким місцем і виникає потреба в паралельних обчисленнях. Чи є спосіб їх застосувати, не змінюючи логіки й не заглиблюючись у тонкощі багатопоточності? C++17 пропонує саме таке рішення.
C++17 значно розширив функціонал стандартної бібліотеки, і що дуже важливо для нас — це поширилось на стандартні алгоритми, додаючи політики виконання для паралельних та векторизованих перевантажень звичних нам алгоритмів. Ці перевантаження існують задля зручного:
— «прозорого» використання багатоядерності;
— стандартизованої можливості векторизації там, де це безпечно та підтримується залізом;
— розширення функціоналу стандартних алгоритмів.
Фактично в C++17 більшість алгоритмів просто отримали додаткові перевантаження з параметром політик, а також додався сам заголовок <execution> з трьома політиками:
— std::execution::seq — послідовне виконання задля зворотної сумісності існуючих алгоритмів;
— std::execution::par — потенційне виконання ітерації паралельно в різних потоках;
— std::execution::par_unseq — потенційне поєднання і багатопоточності, і векторизації SIMD.
Дуже важливо почати з того, що стандарт не гарантує, що параметр політики примусить алгоритм використовувати паралельність. Коли ми передаємо параметр паралельної політики — це лише щось на кшталт дозволу для компілятора та рантайму на використання паралельності для того чи іншого алгоритму.
При подальшому розгляді паралельних алгоритмів ми будемо вважати, що задана нами політика гарантовано працює у 100% випадків.
Загальні вимоги паралельних політик
Як ми вже звикли, стандартна бібліотека завжди ставить певні вимоги, що також характерно і для нових політик виконання:
std::execution::par і std::execution::par_unseq як паралельні політики загалом висувають наступні вимоги:
— відсутність залежностей між ітераціями — предикат чи операція не повинні покладатися на порядок або змінювати спільний стан без синхронізації;
— відсутність винятків — оскільки в рамках компонентів алгоритмів використовуються потоки, а потоки мають власний стек, ми повинні пам’ятати, що будь-який необроблений виняток в рамках потоку буде призводити до виклику std::terminate, а оскільки паралельні реалізації алгоритмів стандартної бібліотеки не передбачають будь-якого перехоплення, винятки заборонені;
— гнучкі ітератори — більша частина алгоритмів з паралельними перевантаженнями потребує ітераторів, не слабших за Random Access.
Крім загальних вимог кожна з політик вводить і свої специфічні положення, а саме:
std::execution::par:
— реалізація може ділити діапазон на блоки з подальшою обробкою в потоках;
— політика не надає гарантій порядку побічних ефектів щодо контейнера або зовнішнього стану;
— предикати, крім звичайного strict weak ordering, повинні або не створювати «гонок» як таких, або мати власну синхронізацію.
std::execution::par_unseq:
— функціонує аналогічно до std::execution::par, але додатково дозволяє векторизацію SIMD;
— потребує найсуворіших вимог до «чистоти» операцій: повну відсутність залежностей між сусідніми елементами та неузгоджених доступів.
Загальна логіка роботи паралельності та векторизації С++
Хоча паралельні політики значно ускладнюють внутрішню логіку, ми все одно можемо виділити основні етапи, які допоможуть зрозуміти, що зазвичай відбувається, коли ми вирішуємо використати перевантаження std::execution::par або par_unseq. Почнемо з простого прикладу, де ми маємо вектор, наповнюємо його псевдовипадковими числами, після чого намагаємося відсортувати його з використанням std::execution::par:
#include <algorithm>
#include <execution>
#include <vector>
#include <random>
#include <iostream>
int main()
{
std::vector<int> data(1'000'000);
std::mt19937 rng(42); // static seed
std::uniform_int_distribution<int> dist(0, 1'000'000);
std::generate(data.begin(), data.end(), [&]() { return dist(rng); });
std::sort(std::execution::par, data.begin(), data.end());
return 0;
}
Коли ми компілюємо цей код, компілятор проводить первинну диспетчеризацію, перевіряє підтримку паралельності та створює для нас бінар. Під час виконання нашого бінаря на етапі виклику сортування відбувається магія:
Насамперед я хотів би зосередити вашу увагу на жовтогарячих блоках. Ці блоки є нестабільними етапами, які безпосередньо залежать від цільової платформи та компілятора, які можна поділити на дві умовні групи:
- Windows MSVC Parallel STL — використовує Concurrency Runtime та Parallel Patterns Library (PPL);
- *nix-системи — своєю чергою використовують GCC та LLVM, за якими компоненти діляться ще на дві групи:
— GCC (libstdc++), що зазвичай спирається на бекенд Thread Building Blocks (oneTBB) або OpenMP;
— LLVM (libc++), що зазвичай спирається або на Parallel STL (PSTL), або на OpenMP/SIMD-бекенди.
Такий перелік може виглядати страшно, але фактично це лише різновиди «чорних скриньок», до яких звертається стандартна бібліотека задля делегування тієї чи іншої роботи, якщо ми та компілятор захочемо використати паралельні обчислення.
Передусім нас цікавить загальна послідовність того, що відбувається під капотом у більшості випадків:
1. Первинна диспетчеризація виклику функції — з того, що нас цікавить, тут рантайм вирішує, чи є можливість та потреба у використанні паралельності.
2. Вибір загального алгоритму сортування — на цьому етапі «чорна скринька» обирає стратегію, за якою буде відбуватися процес сортування, конкретну реалізацію алгоритму сортування, на які проміжки буде розбита вхідна послідовність, за яким алгоритмом проміжні послідовності будуть об’єднані у вихідну послідовність тощо.
3. Розбиття послідовності — тут відбувається звичайне розбиття вхідної послідовності на блоки, які надалі у вигляді задач будуть обчислюватися в окремих потоках.
4. Передача підготовлених блоків задач у пул — слід зазначити, що на цьому етапі більшість «чорних скриньок» може як використовувати створений системний пул потоків, так і створювати власний після першого виклику застосунка. І хоча другий варіант здається доволі оптимальним, як правило, на практиці декілька викликів підряд із паралельною політикою все ще матимуть значний оверхед на кожен з викликів, оскільки рантайм прийматиме рішення незалежно для кожного з викликів.
5. Сортування задач — тут кожна задача обчислюється незалежно, в рамках окремого потоку.
6. Об’єднання результатів — на цьому етапі зазвичай використовується один з паралельних алгоритмів об’єднання, в нашому випадку відсортованих послідовностей.
Щоб усе стало наочнішим, звернемося до такого прикладу, де відбувається паралельне сортування послідовності з шістнадцяти елементів:
На першому етапі відбувається просте розбиття вхідної послідовності на чотири незалежні блоки.
На другому етапі, оскільки блоки незалежні, ми можемо використати для них звичайне сортування в окремих чотирьох потоках.
Після того як ми отримали відсортовані проміжки послідовностей, вони будуть об’єднані у вихідний відсортований результат за допомогою одного з алгоритмів об’єднання.
Підсумовуючи, паралельні алгоритми стандартної бібліотеки зазвичай спираються на три прості етапи:
— розбиття вхідної послідовності на блоки;
— незалежне виконання операції над блоками;
— збір результатів обробки блоків у один результат.
PAR_UNSEQ та SIMD
Тепер, коли ми розглянули деталі роботи std::execution::par, саме час поговорити про std::execution::par_unseq і його зв’язок з SIMD.
Дуже цікавим у минулому прикладі є те, що зазвичай при консервативному підході та підтримці заліза std::execution::par та std::execution::par_unseq будуть відрізнятися лише швидкістю операцій, наприклад: порівняння, копіювання та зміни позицій елементів на другому та третьому етапах. У цьому, як уже можна було здогадатися, за всю магію відповідає SIMD.
SIMD (Single Instruction/Multiple Data) — це парадигма паралельних обчислень, за якої одна машинна інструкція виконується одночасно над декількома елементами даних. Простими словами, процесор замість звичайної операції, наприклад, серії порівнянь двох чисел при сортуванні, може об’єднати дані у вектори й використати не чергу порівнянь, а лише одну операцію порівняння для обох векторів одночасно.
Яскравим прикладом використання SIMD може бути алгоритм merge для двох відсортованих послідовностей, який зазвичай відбувається на третьому етапі заданого раніше підходу паралельного сортування.
У рамках merge в нас є задача об’єднання двох відсортованих послідовностей.
1) Передусім, оскільки SIMD це завжди про вектори, вхідні послідовності поділяються навпіл, щоб отримати дві підпослідовності: початок та кінець.
2) Після цього на зеленому етапі ми незалежно знаходимо мінімальні та максимальні значення між кожною парою підпослідовностей. Тобто знаходимо мінімуми між початками та кінцями послідовностей, і аналогічно знаходимо максимуми між початками та кінцями послідовностей. І все ще слід пам’ятати, що кожна операція min чи max відбувається лише за одну інструкцію.
3) Потім ми рекурсивно об’єднуємо першу отриману пару low та high і другу.
4) Як результат залишається лише об’єднати вже об’єднані між собою частини у вихідну відсортовану послідовність.
Тепер, коли найскладніший етап позаду, нам залишається тільки вкотре закріпити декілька важливих моментів:
— хоча std::execution::par та std::execution::par_unseq зазвичай відрізняються лише використанням векторизації, не слід забувати, що друга політика має найсуворіші правила щодо залежностей між елементами та неузгоджених доступів;
— як правило, не слід використовувати декілька паралельних алгоритмів один за одним, оскільки компілятори все ще не вміють оптимізувати їх належним чином, що навпаки може тільки значно зменшити продуктивність;
— слід пам’ятати, що хоча стандартна бібліотека є найзручнішим рішенням для кросплатформної розробки — паралельні алгоритми можуть видавати непередбачувані результати не тільки на різному залізі та платформах, а й просто з різними компіляторами.
Висновки
Підсумовуючи: глибоке розуміння алгоритмів STL надає реальні переваги у щоденній роботі. Коли ми точно розуміємо, яких вимог потребує той чи інший алгоритм, ми можемо писати ефективний та ідіоматичний код.
Усе, що ми розглянули в цій статті — вимоги до діапазонів, предикатів та паралельних обчислень — це не просто теорія. Врахування цих нюансів робить код надійним, позбавляє нас від прихованих дефектів та непередбачених помилок.
У практичній розробці, особливо в production-середовищі, саме ці деталі визначають стабільність, переносимість і довготривалу життєздатність рішень. Тому увага до внутрішньої логіки стандартної бібліотеки та її обмежень є звичною частиною нашого інженерного підходу команд, що працюють із системним C++.
На завершення варто пам’ятати: STL — не чорна скринька, а колекція прозорих і надійних інструментів, ефективність яких напряму залежить від послідовного дотримання їхніх правил.
Сподобалась стаття? Підписуйтесь на автора, щоб отримувати сповіщення про нові публікації на пошту.
Mikhail Boiko
Alexander Dyachenko
Mikhail Boiko
Valentin Nechayev
5 коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарів