Порівняння Lock-free алгоритмів — CAS і FAA на прикладі JDK 7 і 8

Багато ядер не буває
Атомарні операції (atomics), наприклад, Compare-and-Swap (CAS) або Fetch-and-Add (FAA) широко поширені в паралельному програмуванні.

Мульти — або багатоядерні архітектури встановлені однаково як в продуктах настільних і серверних комп'ютерів, так і у великих центрах обробки даних і суперкомп'ютерах. Приклади конструкцій включають Intel Xeon Phi з 61 ядрами на чіпі, який встановлений в Tianhe-2, або AMD Bulldozer з 32 ядрами на сайті, розгорнутих в Cray XE6. Крім того, кількість ядер на кристалі неухильно зростає і процесорів з сотнями ядер, за прогнозами, будуть виготовлені в осяжному майбутньому. Спільною рисою всіх цих архітектур є зростаюча складність підсистем пам'яті, що характеризується кількома рівнями кеш-пам'яті з різними політиками включення, різними протоколами когерентності кеш-пам'яті, а також різними мережевими топологіями на чіпі, що з'єднують ядра і кеш-пам'ять.
Практично всі такі архітектури забезпечують атомарні операції, які мають численні застосування в паралельному коді. Багато з них (наприклад, Test-and-Set) можуть бути використані для реалізації блокувань та інших механізмів синхронізації. Інші, наприклад, Fetch-and-Add Compare-and-Swap дозволяють будувати різні lock-free і wait-free алгоритми і структури даних, які мають більш міцні гарантії прогресу, ніж блокування на основі коду. Незважаючи на їх важливість і повсюдне вживання, виконання атомарних операцій повністю не проаналізовано досі. Наприклад, на загальну думку, Compare-and-Swap йде повільніше, ніж Fetch-and-Add. Тим не менш, це всього лише показує, що семантика Compare-and-Swap вводить поняття «wasted work», в результаті – більш низька продуктивність деякого коду.

Compare-and-Swap
Згадаймо, що з себе представляє CAS (в процесорах Intel він здійснюється групою команд cmpxchg) – Операція CAS включає 3 об'єкта-операнда: адреса комірки пам'яті (V), очікуване старе значення (A) і нове значення (B). Процесор атомарно оновлює адреса клітинки (V), якщо значення в комірці пам'яті збігається зі старим очікуваним значенням(A), інакше зміни не зафіксується. У будь-якому випадку, буде виведена величина, яка передувала часу запиту. Деякі варіанти методу CAS просто повідомляють, успішно пройшла операція, замість того, щоб відобразити саме поточне значення. Фактично, CAS тільки повідомляє: «Напевно, за адресою V дорівнює A; якщо так воно і є, помістіть туди ж B, в іншому разі не робіть цього, але обов'язково скажіть мені, яка величина — поточна.»
Самим природним методом використання CAS для синхронізації буде читання значення A зі значенням адреси V, виконати багатокрокове обчислення для отримання нового значення B, і потім скористатися методом CAS для заміни значення параметра V з колишнього, A, на нове, B. CAS виконає завдання, якщо V за цей час не змінювався. Що, власне кажучи, спостерігається в JDK 7:
public final int incrementAndGet() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return next;
}
}
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

Де сам метод — unsafe.compareAndSwapInt є native, виконується на процесорі атомарно і на асемблері виглядає наступним чином, якщо включити роздруківку асемблерного коду:
lock cmpxchg [esi+0xC], ecx

Інструкція виконується наступним чином: читається значення з області пам'яті, зазначений першим операндом і блокування шини після читання не знімається. Потім відбувається порівняння значення за адресою пам'яті з регістром eax, де зберігається очікуване старе значення, і якщо вони були рівні, то процесор записує значення другого операнда (регістр ecx) в область пам'яті, зазначену першим операндом. По завершенні запису блокування шини знімається. Особливості x86 в цьому запис відбувається в будь-якому випадку, за тим винятком, що якщо значення були не рівні, то в область пам'яті заноситься значення, яке було отримане на етапі читання з цієї ж області пам'яті.
Таким чином ми отримуємо роботу в циклі з перевіркою змінної, причому яка може закінчитися невдачею і всю роботу в циклі до перевірки необхідно починати заново.

Fetch-and-Add
Fetch-and-Add працює простіше і не містить ніяких циклів (в архітектурі Intel здійснюється групою команд xadd). Також він включає 2 об'єкта-операнда: адреса комірки пам'яті (V) і значення (S), на яке слід збільшити старе значення, збережене за адресою пам'яті (V). Так, FAA можна описати в такому вигляді: отримати значення, що знаходиться за вказаною адресою (V) і зберегти його тимчасово. Потім у вказану адресу (V) занести збережений раніше значення, збільшену на значення, яке з себе являє 2 об'єкт-операнд (S). Причому всі зазначені вище операції виконуються атомарно і реалізовані на апаратному рівні.
В JDK 8 код виглядає так:
public final int incrementAndGet() {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
public final int getAndAddInt(Object var1, long var2, int var4) {
int var5;
do {
var5 = this.getIntVolatile(var1, var2);
} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

return var5;
}

«Нго, — скажете Ви, — чим дана реалізація відрізняється від 7 версії»?
Тут приблизно такий же цикл і все виконується схожим чином. Однак, той код, який ви бачите і написаний на Java не виконується в кінцевому підсумку на процесорі. Той код, який пов'язаний з циклом і установкою нового значення замінюється в кінцевому підсумку на одну операцію асемблера:
lock xadd [esi+0xC], eax

Де, відповідно, в регістрі eax зберігається значення, на яке потрібно буде збільшити старе значення, збережене за адресою [esi+0xC]. Повторюся, все виконується атомарно. Але такий фокус спрацює, якщо процесор підтримує цю функцію і у Вас 8 версія JDK, інакше виконається звичайний CAS.

Що б я ще хотів би додати...
  1. CAS є «оптимістичним» алгоритмом і допускає невиконання операції, в той час як FAA немає. У FAA немає явної лазівки у вигляді уразливості через віддаленого втручання, отже, немає необхідності в циклі для повторних спроб.
  2. Якщо ви використовуєте стандартний CAS підхід, припускаючи, що ваша система використовує найбільш популярну реалізацію когерентності через snoop-base або «підслуховування», то це може викликати read-to-share транзакцію, щоб отримати основну рядок кеша або стан E. Compare-And-Swap має ефективну пам'ять семантик по відношенню до протоколів когерентності кешів, що може викликати іншу транзакцію шини, щоб оновити лінію до M стану. Таким чином, в найгіршому випадку стандартний CAS підхід може піддати шину двох транзакцій, але реалізація Fetch-And-Add буде прагнути провести передачу лінії безпосередньо до M стану. У процесі ви б могли спекулювати значеннями і отримувати короткий шлях без попередніх завантажень, як це намагається отримати «голий» CAS. До того ж, це можливо при складних реалізаціях процесора для виконання узгоджених операцій та цільового дослідження лінії M стані. Нарешті, у деяких випадках можна успішно вставити інструкцію передвибірки для запису (PREFETCHW) перед виконанням операцій, щоб уникнути транзакції оновлення. Але цей підхід має бути застосований з особливою увагою, оскільки в деяких випадках це може принести більше шкоди, ніж користі. Враховуючи все це, FAA, де це можливо, має перевагу.
  3. Припустимо, ви намагаєтеся збільшити змінну (наприклад, инкрементировать) з допомогою CAS циклу. Коли CAS починає збиватися досить часто, можна виявити, що гілка для виходу з циклу (зазвичай виникає при відсутності або легкому навантаженні) починає прогнозувати помилкові шляхи, які прогнозують нам, що ми залишимося в петлі. Тому, коли CAS в кінцевому рахунку досягне мети, ви словите branch mispredict (помилкове припущення гілки) при спробі вийти з циклу. Це може бути болісно на процесорах з глибоким конвеєром і призвести до цілого вороху out-of-order (позачергові виконання) спекуляцій машини. Як правило, ви не хочете, щоб цей шматок коду приводив до втрат швидкості. У зв'язку з вище сказаним, коли CAS починає часто терпіти невдачу, гілка починає прогнозувати, що управління залишається у циклі і у свою чергу, цикл працює швидше за рахунок вдалого передбачення. Як правило, ми хочемо деякого back-off в циклі. І при легкому навантаженні з нечастими невдачами branch mispredict служить в якості потенційного неявного back-off. Але при більш високій навантаженні ми втрачаємо перевага back-off, що випливають з branch mispredict. У FAA немає циклів і ніяких проблем.
Тести
Ну і наостанок я написав простенький тест, який ілюструє роботу атомарного инкрементирования в JDK 7 і 8:

Як ми бачимо, продуктивність коду у FAA буде краще і його ефективність збільшується зі збільшенням числа потоків від 1.6 рази до приблизно 3.4 рази.

Версії Java для тестів: Oracle JDK7u80 і JDK8u111 — 64-Bit Server VM. CPU — Intel Core i5-5250U покоління Broadwell, OS — macOS Sierra 10.12.2, RAM — 8-Gb.
Ну і якщо цікаво, посилання на код тесту — исходники тесту
Чекаю зауважень, поліпшень і інше.
Джерело: Хабрахабр

0 коментарів

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