Занадто швидкий, занадто мегаморфний: що впливає на продуктивність виклику методу в Java?

       Від перекладача:
суперечка прихильників написання final скрізь і всюди і їх супротивників те саме спору остроконечников і тупоконечников. Як і в деяких інших спільнотах, в нашій компанії цей уповільнений суперечка йшла роками. І тільки ця стаття Річарда Вербертона (Richard Warburton) дозволила нашим гострокінечників взяти верх.

 
 
Про що мова?
Почнемо з невеликого оповідання. Кілька тижнів тому я відправив у список розсилки Java core libs свою пропозицію прибрати модифікатор final з деяких методів. У результаті виникло декілька тем для дискусії. Одна з них, наприклад, — з'ясувати, якою мірою погіршиться продуктивність виклику методу, який був final , якщо цей final з нього прибрати.
 
У мене були деякі міркування про те, виникне регресія продуктивності чи ні, але я спочатку спробував дізнатися, публікував чи хто-небудь вже результати бенчмарків з цього питання. На жаль, я нічого не зміг знайти. Це не означає, що вони не існують або що інші люди не досліджували ситуацію, але я не зустрічав жодного коду, що пройшов експертну перевірку. Так що саме час написати кілька бенчмарків.
 
 
Методологія бенчмаркінгу
Отже, я вирішив використати чудовий фреймворк JMH для того, щоб провести бенчмаркінг. Якщо ви не впевнені, що фреймворк допоможе вам отримати точні результати бенчмаркінгу, то вам варто подивитися це виступ Олексія Шіпілева (TheShade ), автора фреймворка, або по-справжньому крутий блог Нітсана Вакарта (Nitsan Wakart) , який пояснює, як це допомагає.
 
У моєму випадку я хотів зрозуміти, що вплинуло на продуктивність виклику методу. Я вирішив спробувати різні варіації виклику методів і виміряти витрати на них. Маючи набір критеріїв і варіюючи тільки однин фактор за раз, ми можемо зрозуміти, як різні фактори або їх комбінації впливають на вартість виклику методу.
 
 
Inlining
 image
Одночасно найбільш і найменш очевидний впливає фактор — чи відбувається виклик методу взагалі! Фактичний виклик методу може бути так оптимізований компілятором, що його не залишиться зовсім. Взагалі кажучи, існує два способи зменшити вартість виклику. Один з них — безпосередньо вбудовувати сам метод, другий — використовувати inline cache. Не хвилюйтеся — це досить прості концепції, але є трохи термінології, в якій слід розібратися. Уявімо, що у нас є клас з ім'ям Foo, який визначає метод, званий bar.
 
 
class Foo {
  void bar() { ... }
}

Ми можемо викликати метод bar, написавши код, який виглядає наступним чином:
 
 
Foo foo = new Foo();
foo.bar();

Головне тут — це місце, де bar насправді викликається — foo.bar () — його називають callsite . Коли ми говоримо, що метод був заінлайнен (вбудований), це означає, що тіло методу береться і вставляється в callsite, замість виклику методу. Для програм, які складаються з безлічі невеликих методів (я думаю, так більш правильно писати програми) вбудовування може привести до значного прискорення. Це тому, що програма не витрачає більшу частину свого часу на виклики методів замість того, щоб робити роботу! Ми можемо контролювати, вбудований метод чи ні в JMH, за допомогою анотації CompilerControl. Ми повернемося до концепції inline cache трохи пізніше.
 
 
Глибина ієрархії і перевизначення методів
 image
Якщо ми вирішуємо видалити ключове слово final з методу, це означає, що ми будемо мати можливість перевизначити (override) його. Це ще один фактор, який потрібно брати до уваги. Так що я взяв методи і викликав їх на різних рівнях ієрархії класів; також були методи, перевизначені на різних рівнях ієрархії. Це дозволило мені визначити, наскільки глибоко ієрархії класів взаємодіють з перевизначенням методів.
 
 
Поліморфізм
 image
Коли я згадав ідею callsite раніше, я потай хотів обійти досить важливе питання. Бо не-final метод можна перевизначити в підкласі, наші callsite-и можуть в кінцевому підсумку викликати різні методи. Так що, можливо, я маю справу з Foo або його дочірнім класом Baz, який теж реалізує bar (). Як компілятор дізнається, який метод викликати? Всі методи в Java за замовчуванням віртуальні (переопределяеми), і для кожного виклику доводиться шукати правильний метод в так званій таблиці віртуальних методів (vtable). Це досить повільно, тому що оптимізують компілятори завжди намагаються знизити витрати на подібні пошуки. Підхід, згаданий раніше, — інлайнінг або вбудовування — відмінно діє, якщо ваш компілятор може довести, що даний callsite може викликати лише одну конкретну реалізацію методу. Це називається Мономорфность callsite.
 
На жаль, здебільшого доводити, що callsite строго мономорфен, зрештою непрактично. JIT компілятори, як правило, застосовують альтернативний підхід, профілюємо, які типи викликаються в callsite і припускаючи, що якщо callsite був Мономорфность у своїх перших N викликах, то тоді він гідний спекулятивної оптимізації, заснованої на припущенні, що він завжди буде Мономорфность. Така спекулятивна оптимізація, як правило, вірна, але не завжди; тому компілятор повинен впровадити захист Перез викликом методу, щоб переконатися в типі об'єкта, у якого викликається метод.
 
Однак мономорфні callsite-и — це не єдиний випадок, коли ми хочемо прооптімізіровать. Багато callsite-и є, що називається, біморфний (bimorphic) — тобто є два методи, які можуть бути викликані. Ви все ще можете вбудувати біморфний callsite-и, використовуючи ваш код захисту, перевіривши, яку реалізацію викликати, а потім приступити до неї. Це все ще дешевше, ніж повний виклик методу. Крім того, можна оптимізувати цей кейс за допомогою inline cache. Inline cache насправді не вбудовує тіло методу в callsite, але це має спеціалізовану таблицю переходів, яка діє, як кеш на повній таблиці віртуальних методів. JIT-компілятор Hotspot підтримує біоморфною вбудовані кеші, а будь callsite з 3мя і більше можливими реалізаціями вважає мегаморфним.
 
Таким чином, виділяються 3 види викликів для порівняння і дослідження: випадки мономорфного, біморфного і мегаморфного виклику.
 
 
Результати
Згрупуємо підсумки так, щоб можна було розгледіти ліс серед дерев; я представлю сухі цифри разом з їх невеликим аналізом. Конкретні цифри / витрати насправді не так вже нас і цікавлять. Цікаво співвідношення між різними типами викликів методів, щоб при цьому статистичні похибки били невеликі. Існує досить значна різниця — в 6.26 раз — між найшвидшим і самим повільним. Насправді ця різниця буде, ймовірно, більше — за витрат, пов'язаних з виміром часу порожнього методу.
 
Вихідний код для цих бенчмарков доступний на GitHub . Щоб уникнути плутанини, я представив у частині результатів у різних блоках. Поліморфні бенчмарки виробляються за допомогою PolymorphicBenchmark, а решта — за допомогою JavaFinalBenchmark
 
 
Прості callsite-и
 
Benchmark                                                    Mode   Samples         Mean   Mean error    Units
c.i.j.JavaFinalBenchmark.finalInvoke                         avgt        25        2.606        0.007    ns/op
c.i.j.JavaFinalBenchmark.virtualInvoke                       avgt        25        2.598        0.008    ns/op
c.i.j.JavaFinalBenchmark.alwaysOverriddenMethod              avgt        25        2.609        0.006    ns/op

Наш перший набір результатів показує вартість викликів віртуального методу, final методу і методу, який входить в глибоку ієрархію і перевизначається. Зверніть увагу, що у всіх цих випадках ми змусили компілятор не вбудовувати методи. Як бачимо, різниця між часом мінімальна і наш СКО показують, що це не має великого значення. Таким чином, ми можемо укласти, що просто додаючи final ключове слово, не зможемо істотно поліпшити продуктивність виклику. Перевизначення методу також, мабуть, не має великого значення.
 
 
Вбудовування простих callsite-ів
 
Benchmark                                                    Mode   Samples         Mean   Mean error    Units
c.i.j.JavaFinalBenchmark.inlinableFinalInvoke                avgt        25        0.782        0.003    ns/op
c.i.j.JavaFinalBenchmark.inlinableVirtualInvoke              avgt        25        0.780        0.002    ns/op
c.i.j.JavaFinalBenchmark.inlinableAlwaysOverriddenMethod     avgt        25        1.393        0.060    ns/op

Тепер візьмемо ті ж три випадки і знімемо обмеження вбудовування. Знову final і віртуальні виклики методів зрештою мають однакову тривалість. Вони в 4 рази швидше, ніж у випадку заборони вбудовування, що я записав би на рахунок, власне, вбудовування. Виклик усюди перевизначеного методу в кінцевому підсумку виявляється між ними двома. Я підозрюю, що це тому, що сам метод має кілька можливих реалізацій підкласів і, отже, компілятор повинен вставити перевірку типу. Механіка цього пояснюється вище більш детально в розділі «Поліморфізм».
 
 
Вплив ієрархії класів
 
Benchmark                                                    Mode   Samples         Mean   Mean error    Units
c.i.j.JavaFinalBenchmark.parentMethod1                       avgt        25        2.600        0.008    ns/op
c.i.j.JavaFinalBenchmark.parentMethod2                       avgt        25        2.596        0.007    ns/op
c.i.j.JavaFinalBenchmark.parentMethod3                       avgt        25        2.598        0.006    ns/op
c.i.j.JavaFinalBenchmark.parentMethod4                       avgt        25        2.601        0.006    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentMethod1              avgt        25        1.373        0.006    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentMethod2              avgt        25        1.368        0.004    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentMethod3              avgt        25        1.371        0.004    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentMethod4              avgt        25        1.371        0.005    ns/op

Ого, ось це великий блок методів! Кожен з пронумерованих викликів методів (1-4) показує, наскільки глибоко в ієрархії класів був викликаний метод. Так parentMethod4 означає, що ми викликаємо метод, оголошений в 4-м батьківському класі. Якщо ви подивитеся на цифри, то різниця між 1 і 4 дуже мала. Таким чином, ми можемо укласти, що глибина ієрархії не має ніякого значення. При вбудовуванні всі слідують того ж шаблоном: глибина ієрархії не має ніякого значення. Наша продуктивність вбудованих методів порівнянна з inlinableAlwaysOverriddenMethod, але повільніше, ніж inlinableVirtualInvoke. Я знову відніс би це до перевірки типу. JIT компілятор може профілювати методи, щоб з'ясувати, що тільки один був вбудований, але він не може довести, що так буде завжди.
 
 
Вплив ієрархії класів на final методи
 
Benchmark                                                    Mode   Samples         Mean   Mean error    Units
c.i.j.JavaFinalBenchmark.parentFinalMethod1                  avgt        25        2.598        0.007    ns/op
c.i.j.JavaFinalBenchmark.parentFinalMethod2                  avgt        25        2.596        0.007    ns/op
c.i.j.JavaFinalBenchmark.parentFinalMethod3                  avgt        25        2.640        0.135    ns/op
c.i.j.JavaFinalBenchmark.parentFinalMethod4                  avgt        25        2.601        0.009    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentFinalMethod1         avgt        25        1.373        0.004    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentFinalMethod2         avgt        25        1.375        0.016    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentFinalMethod3         avgt        25        1.369        0.005    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentFinalMethod4         avgt        25        1.371        0.003    ns/op

Тут та ж схема, що і вище — ключове слово final , схоже, не має ніякого значення. Я думав, що теоретично тут можна довести, що inlinableParentFinalMethod4 вбудовуємо і виключити перевірку типу, але, схоже, це не так.
 
 
Поліморфізм
 
Monomorphic: 2.816 +- 0.056 ns/op
Bimorphic: 3.258 +- 0.195 ns/op
Megamorphic: 4.896 +- 0.017 ns/op
Inlinable Monomorphic: 1.555 +- 0.007 ns/op
Inlinable Bimorphic: 1.555 +- 0.004 ns/op
Inlinable Megamorphic: 4.278 +- 0.013 ns/op

Нарешті ми підійшли до випадку полиморфного виклику. Вартість мономорфного виклику, грубо кажучи, така ж, як і у наших звичайних віртуальних викликів, описаних вище. У міру того, як нам треба здійснити пошуки на великих таблицях віртуальних методів, вони стають повільніше по мірі появ біоморфного і мегаморфних випадків. Як тільки ми дозволяємо вбудовування, профілювання викидає зайве, і наш мономорфний і біоморфного callsite опускається до вартості наших вбудованих викликів з перевіркою типу. Дуже схоже на випадок ієрархії класів, тільки трохи повільніше. Мегаморфний випадок все ще дуже повільний. Нагадаю, що тут ми не налаштували Hotspot на запобігання вбудовування, він просто не реалізує поліморфний inline cache для callsite-ів складніших, ніж біоморфною.
 
 
Що ми зрозуміли?
Думаю, варто відзначити, що є багато людей, які не мають умоглядну модель продуктивності, яка обчислює різні типи викликів методу, займаючи різну кількість часу і багато людей, які розуміють, що вони використовують різну кількість часу, але насправді розуміють це не зовсім вірно. Я знаю, бо сам був таким і робив невірні припущення. Так що я сподіваюся, що це дослідження було корисним для вас. Нижче ще раз коротко наведені тези, які я і відстоював в цій статті:
 
     
Існує велика різниця між найшвидшим і самим повільним типом виклику методу.
 На практиці додавання або видалення ключового слова final насправді не впливає на продуктивність, але, якщо ви потім будете реорганізувати вашу ієрархію, то процес може почати сповільнюватися.
 Більш глибокі ієрархії класів не мають ніякого реального впливу на продуктивність викликів.
 Мономорфность виклики швидше, ніж біоморфною.
 біоморфного виклики швидше, ніж мегаморфние.
 При перевірці типу, яку ми бачимо у випадку профілювання, коли не можна довести мономорфность, виклик трохи сповільнюється, в порівнянні з Мономорфность.
 
 
Я б сказав, що ціна перевірки типу є моїм особистим «великим одкровенням». Це те, що я, як бачу, рідко обговорюється і чим часто нехтують.
 
 
Застереження і подальша робота
Зрозуміло, це не єдино можливий підхід до цього питання!
 
     
Ця стаття зосереджена навколо факторів, що впливають на продуктивність викликів методу, пов'язаних з типами виклику. Один з факторів, який я не згадав — це евристика, навколишнє метод, що вбудовується в залежності від розміру або глибини стека викликів. Якщо ваш метод занадто великий, він не буде вбудовуватися взагалі, і ви все одно в кінцевому підсумку заплатите за вартість виклику методу. Ще одна причина, щоб писати невеликі, легко читаються методи.
 Я не розглядав, як виклик через інтерфейс впливає на будь-яку з цих ситуацій. Якщо ви вважаєте це цікавим, тобто дослідження продуктивності інтерфейсу в блозі Mechanical Sympathy
 Один з факторів, який ми повністю проігнорували, — це вплив методу розміщення на інших оптимізації компілятора. Коли компілятори виконують оптимізацію, при якій аналізується лише один метод (внутрішньо-процесуальна оптимізація), для ефективної оптимізувати їм дійсно потрібно якомога більше інформації. Обмеження вбудовування може значно зменшити контекст, з яким доведеться працювати іншим оптимізаціям.
 Прив'язка пояснення аж до рівня асемблера, щоб більш детально зануритися в це питання.
 
 
Можливо, це теми для майбутніх постів.
 
Подяки:
 - Олексію Шіпілеву за фідбек до бенчмарку,
 - Користувачам Martin Thompson , Martijn Verburg, Sadiq Jaffer and Chris West — за дуже корисні відгуки та коментарі до мого блогу.
  
Джерело: Хабрахабр

0 коментарів

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