Пояснення експерименту про ветвлениях, або філософські вишукування на тему бенчмарків у вакуумі і в реальності...

Сподіваюся, хто хотів, ознайомився з моїм пробним експериментом на Хабре статті. Тепер я вважаю, що буде правильним оприлюднити його результати і навіть дати більш детальне пояснення причин, за якими взагалі подібні експерименти проводяться. Пост буде наполовину філософським, оскільки зараз в комп'ютерному світі все настільки складно, що без філософського осмислення прийняти якісь осмислені рішення просто неможливо. Я постараюся взагалі висловити свою думку про сферичних вимірах у вакуумі, тому буде багато букв. У статті є опитування, що проводиться до 1-го травня 2016. Під катом цілком ІМХО.



В першу чергу, прошу звернути увагу на те, що експеримент я назвав словом «пробний» – і це не випадково. Я задумав більш детальне вивчення особливостей різних алгоритмів, а для цього потрібна допомога різних людей (хоча б непряма – щось десь запустити і сказати результат). Щоб у майбутньому складні експерименти проходили досить гладко, потрібно потренуватися, перевірити взагалі принципову можливість робити це таким чином. Спільнота зазвичай любить штовхати за помилки в методології дослідження або організації, а мені якраз потрібні були конструктивні вказівки на подібні помилки. Такі, на щастя, були.

По-друге, прошу мене вибачити за те, що я забув про необхідність хаотичного потоку даних, з-за цього комусь довелося тестувати все заново і виникла плутанина в тому, яку саме версію перевірив черговий учасник. У своїй статті про підрахунок одиничних бітів я дуже добре пам'ятав про важливість випадкового потоку вхідних даних, а ось тут чомусь забув. Буває. Але, як я сказав вище, це перша і найважливіша для мене причина проведення пробного експерименту, щоб менше помилитися в серйозних дослідженнях і завчасно врахувати можливі конструктивні поради.

Тепер поговоримо про методології самого дослідження і про те, в чому взагалі необхідність тестувати будь-які функції на швидкість. І є вона, ця необхідність. Звідси і розпочнеться філософія.

Пояснення до слова «розгалуження»
Інша з моїх помилок, які я допустив, в тому, що я не пояснив, що означає розгалуження. Зазвичай мене мало цікавлять академічні терміни, тому що найчастіше вони не мають відношення до реальності, а тому доводиться наділяти багато слова власним змістом.

В тій статті малося на увазі саме алгоритмічне (або логічне) розгалуження, яке неминуче з'являється в логіці програми обчислення логічного виразу і подальші дії в залежності від результату цього виразу. Таким чином, коли в коді програми ми бачимо умова, то за логікою (саме з людською логікою) це розгалуження. Чому так? Справа в тому, що розгалуження взагалі кажучи складно визначити по нормальному, коли логіка алгоритму перекладається спочатку на МП, потім компілятор переводить її на машинний мову, а потім самі інструкції процесора переводяться у внутрішні, скажімо, RISC-інструкції. На одному етапі розгалуження є, а ну іншому немає… а потім знову може з'явитися.

Тобто ви можете думати, що розгалуження у вашій програмі на мові Сі немає, а насправді воно є, або навпаки, ви написав код з розгалуженням (в логіці), а компілятор придумав, як це зробити без розгалужень в коді. Приклад:

u64 a, c;
u32 b;
c = a / b;

Розгалуження немає. Правда? Насправді є (принаймні після компілятора VC++ 2015). Справа в тому, що при так званому «2/1»-поділі (коли щось подвоєного розміру ділиться на щось одинарного розміру) результат може мати як одинарний, так і подвійний розмір. У першому випадку дана процедура поділу буде виконуватися з однією інструкцією div, у другому випадку – з двома. Так ось, щоб зрозуміти те, за якою гілці піти при такому розподілі, потрібно розрахувати розмір приватного і зробити вибір, цей вибір буде одним з розгалужень перед безпосереднім розподілом. Ще одним вибором може бути, наприклад, перевірка на ділення на нуль (хоча зазвичай такої перевірки немає). Коротше, процедура ділення не зводиться до звичайного div, це досить складна процедура. А програміст, дивлячись на цю запис, може думати, що тут лінійний код.

Другий приклад. Функція максимуму може виглядати так:

i32 max1 (i32 a, i32 b) {
return a ^ ((a ^ b) & -(a < b));
}

Тут, очевидно, немає розгалужень на архітектурі x86, напевно, не буде їх і на багатьох інших архітектурах, хоча тут є пряме логічне порівняння двох чисел. Тобто за логікою розгалуження тут є, а по коду немає. Однак замініть i32 на i64 і скомпілюйте програму в режимі x86. Розгалуження відразу з'являться. А от в такому коді:

i32 maxi1 (i32 a, i32 b) {
i32 d = a-b;
return b + (d&(~(d^((a^b)&(d^a))) >> SHIFT));
}

Розгалужень ні в логіці і не буде в програмі ні при якому фіксованому розмірі змінної, яку підтримує компілятор (мова йде про x86 при правильній компіляції). Тому я і називаю це єдиним методом пошуку максимуму (з відомих мені), який не містить розгалужень.

До чого це я все це розповідаю?

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

Я хотів показати, що кожному доступний простий експеримент, який покаже, коли треба і коли не треба позбуватися розгалужень в логіці. Ми беремо різні реалізації і порівнюємо між собою хоча б на сферичних тестах у вакуумі… і в цьому є сенс, про що я і философствую далі.

Методологія експерименту
Зрозуміло, що кожен, хто серйозно займався оптимізацією програм, звернув увагу на сильну штучність подібних вимірів часу. Дивіться: ми беремо функцію, створюємо для її роботи ідеальні умови і тестуємо її в цих ідеальних умовах. В моєму випадку такою умовою був найпростіший цикл. По часу роботи цього циклу з викликом функції в ньому і по часу роботи порожнього циклу ми намагаємося дізнатися про ефективність самої функції… і комусь могло здатися, що я так і роблю. Насправді все не так просто, тому що так робити не можна.

В реальних умовах ваша функція буде оточена іншим набором інструкцій, цикл, в якому вона буде запускатися, може виявитися більш довгим і заплутаним і час роботи цієї функції може виявитися абсолютно іншим. У якомусь сенсі такі бенчмарки, як у мене, нагадують показуху в якому-небудь магазині, який вирішив відвідати високий чиновник: ціни в ньому несподівано стають в 10 разів нижче, а зарплата персоналу в 10 разів вище… але рівно до тих пір, поки чиновник не піде з магазину. Так навіщо ж взагалі займатися цим, якщо результат не відображає реальність? Тому що якщо правильно розуміти словосполучення «відображає реальність», то все встане на свої місця.

А справа все в тому, що я не роблю висновків про швидкості роботи функції окремо. Я роблю висновок про те, яка з функцій буде швидше, а яка повільніше саме в цих тепличних умовах. При цьому мене цікавить великий відрив по швидкості, тому як невеликий відрив часто затирається складністю інших ділянок програми, а ось великий відрив гарантує (принаймні, в моєму досвіді роботи), що в реальних умовах різниця буде такою ж… за це НЕ важливо, буде сама функція працювати в 100 разів довше порівняно з ідеальними умовами – вигравати у більш повільної вона буде приблизно з тим же результатом, що я отримую в цих ідеальних умовах. Чесно скажу, я не знаю, чи це в звичайних побутових завдання, але в наукових розрахунках, коли потрібні мільйони машинних годин рахунку, це можна вважати аксіомою. У моїй практиці було тільки так і ніяк інакше. Тепер давайте спробуємо філософськи осмислити взагалі цінність будь-якого дослідження.

У нашому світі значна частина експериментів (навіть соціальних) не позбавлена того недоліку, що всі вони штучні, але за результатами цих експериментів люди все одно можуть досить достовірно передбачити таку ситуацію в реальності. Скажімо, візьміть те ж змагання за стайерскому бігу. Кілька людей одягаються в бігові труси, майку і «тапки» (іноді з шипами), роблять спеціальну розминку, виходять на старт і починають бігти з ідеально гладкою і м'якою доріжкою, наприклад, 5 км. Це ідеальні умови, в яких майстер спорту проходить дистанцію за 14 хвилин. Якщо почепити на майстра валянки і змусити надіти шубу, то він пробіжить ту ж дистанцію повільніше, особливо по болоті та калюжах, скажімо, за 18-20 хвилин… але це все одно швидше, ніж звичайний непідготовлена людина пробіжить навіть в ідеальних умовах. А в рівних умовах у нього взагалі нуль шансів. Можна взяти і інші звичайні умови: потрібно добігти до минає автобуса (або встигнути на «зелений» на пішохідному переході). Просте питання: у кого більше шансів встигнути на нього при досить великій дистанції – у майстра по стайерскому бігу або у звичайної людини? Зрозуміло, що у першого, причому шанси практично не змінюються в залежності від форми одягу і багатьох інших умов. Однак дане припущення (причому досить надійне) ми робимо тільки на основі того, що бачили, як майстри бігають 5 км за 14 хвилин. Ми просто робимо прогноз на основі знань, отриманих в ідеальних умовах. І з величезною ймовірністю ці передбачення будуть істинними в реальних умовах.

У світі програмування, звичайно, все набагато складніше. Наприклад, з чого я взяв, що мої умови, описані вище, ідеальні? Це я їх так назвав, а може виявитися, що в реальній програмі компілятор знайде спосіб так «розмазати» мою функцію за кодом програми, що час її роботи стане рівним нулю (вона буде обчислена паралельно з якимись складними операціями неподалік). Так, таке може бути, і при жорсткої оптимізації програм досвідчений програміст спробує так змінити алгоритм, щоб максимально збалансувати команди для одночасного виконання інструкцій, що входять до них, а процесор потім на ходу перемішати ці інструкції ще краще. Але це інша розмова, тому що подібні оптимізації не виконуються окремо для окремих простих функцій на зразок sign або abs, робиться все інакше: ми беремо вузький ділянку коду і дивимося на нього цілком, на те, чи можна з ним щось зробити (навіть, може, повністю переклеїти), щоб його логічний зміст залишився колишнім, але складність зменшилася. У нас ситуація інша: ми хочемо з'ясувати те, наскільки швидкою буде та або інша реалізація окремій невеликій функції, припускаючи, що ця окрема невелика функція буде досить сильно навантажена в деякому процесі, але не настільки, щоб якось жорстко її оптимізувати і розмазувати її по якимось іншим ділянкам програми.

Саме так часто і пишуться звичайні ефективні програми: коли алгоритмічна ефективність влаштовує програміста, він досягає додаткової практичної ефективності тим, що використовує добре оптимізовані окремі функції, але глибше не лізе, тому що це може виявитися накладно, і йому простіше збільшити вдвічі кількість ядер, ніж витратити силу-силенну часу, щоб досягти такого прискорення на колишньому їх кількості. Ось ці добре оптимізовані функції пишуться… увагу… під ідеальні умови! Та ж бібліотека MPIR для довгої арифметики, подивіться код і побачите там безліч реалізацій функцій низького рівня, заточених під різні процесори, причому MPIR буде вигравати у вашого самопального коду довгої арифметики як на тестах начебто моїх (сферичних у вакуумі), так і в реальних умовах, коли дані мають не дуже передбачуваний характер (зрозуміло, що перемогти MPIR можна і дуже легко, коли заздалегідь знаєш деякі серйозні особливості вхідних чисел, але я кажу про те, коли не знаєш). І таких прикладів в науковому світі повно. Функція factor в Maple буде рвати вашу самопальну функцію факторизації поліномів як в ідеальних умовах, коли ви вимірюєте час роботи шляхом багаторазового повторення випадкових тестів одного за іншим, так і в реальних програмах, де факторизація займає відчутну частку ваших обчислень (наприклад, при якій-небудь роботі з раціональними дробами). Звичайно, я допускаю те, що ви можете змагатися з factor з Maple, але таких людей дуже мало, а мова йде про звичайних користувача, які хочуть написати більш-менш хорошу програму, але важко у виборі тієї чи іншої реалізації сильно навантаженої функції.

Що я хочу сказати: не знаю, як у звичайному IT-світі, але в науковій сфері обчислювальної існує чітка кореляція між бенчмарками начебто моїх (сферичних) і реальною поведінкою досліджуваних функцій в складних розрахунках, коли ці функції вносять істотний вклад у складність всієї програми. Тобто якщо деяка функція f перемогла функцію g на сферичних тестах в 10 разів, то приблизно так само справа йде в реальній програмі. І в цьому я неодноразово переконувався з допомогою профилировщика.

Поясню ще один момент: у реальних задачах я не зустрічав необхідності оптимізувати функції min, max, sign і abs. Зазвичай вони зустрічаються в групі значно більш складних обчислень, тому абсолютно непомітні в таблиці з результатами профилировки. Просто я часто зустрічаю програмістів, які вважають своїм обов'язком спаплюжити код на основі своїх інтуїтивних припущень про оптимізацію, тоді як вузьке місце їх програми взагалі в іншій точці. Не треба так робити.

Тим не менш, мій експеримент з цими функціями все ж мав для мене сенс, не дивлячись на штучність і відірваність від реальності його очевидній необхідності. Це я пояснюю далі.

Цілі експерименту
Нагадаю, що основною метою було отримати від спільноти зворотний зв'язок у вигляді зауважень, рекомендацій і взагалі деякого поведінки. Аналізуючи все це, я роблю висновки і можу тепер зробити аналогічні експерименти більш цікавими і корисними. Тут я лише тренувався і висловлюю подяку всім, хто взяв посильну участь.

Друга мета – перевірити якість вимірювання часу моїм способом. Беручи до уваги той факт, що у кого-то час виходило негативним, можна з упевненістю сказати, що над вимірами доведеться ще подумати. Це добре, тому що аналогічний провал в серйозний експеримент був би для мене дуже важким випробуванням.

Третя мета – перевірити спроможність потенційних учасників на Хабре правильно сприймати ситуацію і діяти з урахуванням навіть можливих відхилень від плану. Така здатність мене цілком влаштовує, хоча мене трохи розчарувало те, що деякі учасники надавали результати тестування, коли програма компилировалась без будь-яких ключів оптимізації… я не знаю, який сенс у таких вимірах. Принаймні, в наукових розрахунках це може бути корисно тільки для налагодження. Тут частково моя вина, що я не пояснив даний момент, хоча потрібно було здогадатися, що раз всі програмісти дуже різні, потрібно максимально точно формулювати умови. Подібні пробні експерименти вчать розуміння цього, що теж корисно.

Четверта мета – подивитися на співвідношення часів роботи функцій на різних процесорах і з різними компіляторами. Ось тут мене здивував один момент. У деяких користувачів виходило, що функція minu0 працювала в рази повільніше інших семи функцій мінімуму та максимуму. Ось приклади (це саме хаотичної подачі даних):

Intel® Core(TM) i3-2100 CPU @ 3.10 GHz
GCC 4.9.3-r3
Опції: -std=++gnu 11 -O3

mini: 1.22 vs 2.59
maxi: 1.19 vs 2.71
minu: 13.64 vs 3.01
maxu: 1.21 vs 2.54

Intel Core i7-6700K CPU @ 4.00 GHz
5.2.1 GCC
Опції: -O3 -std=++gnu 11

mini: 0.49 vs 0.83
maxi: 0.48 vs 0.82
minu: 10.20 vs 0.74
maxu: 0.49 vs 0.91

Intel® Core(TM)2 Duo CPU E7300 @ 2.66 GHz
GCC 4.8.4
Опції: g++ -std=++gnu 11 -О3

sign: 12.95 vs 2.56
abs: 12.74 vs 0.91
mini: 2.31 vs 3.07
maxi: 2.19 vs 3.19
minu: 15.79 vs 3.54
maxu: 2.08 vs 3.77

Raspberry Pi 3, SoC: Broadcom BCM2837, CPU: ARM Cortex-A53 @ 1.2 GHz
gcc version 4.9.2 (Raspbian 4.9.2-10)
options: -std=++gnu 11 -O3
mini: 10.74 vs 17.93
maxi: 10.74 vs 14.33
minu: 24.63 vs 7.16
maxu: 10.74 vs 7.16

І так далі, цих прикладів багато. Причому тут скрізь тупил GCC, бо як clang робив все правильно:

Intel® Core(TM) i5-4210U CPU @ 1.70 GHz:
Clang 3.7 with Microsoft CodeGen (v140_clang_3_7):
Full optimization (-O3)

mini: 0.41 vs 2.61
maxi: 0.35 vs 9.28
minu: 0.69 vs 2.96
maxu: 0.44 vs 8.83

Там же в коментарях ще багато прикладів роботи Clang. Не буду наводити приклади, але VC++ 2015 теж зробив все правильно. Таким чином, розробникам компіляторів GCC дані приклади повинні бути корисні для налагодження блоку оптимізації. Тобто мій експеримент виявив косяк компілятора, який може проявитися потім десь в серйозній програмі.

Можна виділити і деякі інші результати, що заслуговують на увагу, наприклад, в деяких випадках страшна формула без розгалужень виявляє максимум або мінімум швидше формули з розгалуженням. Ось фрагмент:

Raspberry Pi 3, SoC: Broadcom BCM2837, CPU: ARM Cortex-A53 @ 1.2 GHz
gcc version 4.9.2 (Raspbian 4.9.2-10)
options: -std=++gnu 11 -O3

minu: 24.63 vs 7.16
maxu: 10.74 vs 7.16

У першій рядку ясно – це глюк GCC, про який я писав вище, а другий саме поразка методу з розгалуженням.

П'ята мета була побічно позначена вище – показати звичайним програмістам, що не треба фанатично дотримуватися якийсь догми. У кожному разі свій варіант може виявитися краще і потрібно проводити тестування, щоб зробити вибір, а не покладатися на сліпу впевненість, засновану на оптимізації під четвертий пень, що виникла в ті далекі часи, коли вони навчалися в університеті.

Шоста мета, менш значуща, – мені потрібно було поділитися своїми матеріалами (посилання [4-7] з попередньої статті), щоб згодом отримати зворотний зв'язок, зрозуміти, чи вірно я рухаюся, коли пишу подібні статті намітити для себе подальший план роботи і відшукати однодумців. Цю зворотний зв'язок я поки не отримав, але всьому свій час.

Сьома мета, непряма, — отримати привід написати цей пост, ділячись в нього своїми думками, і провести голосування.

Пропоную голосувати. Якщо 80% учасників голосування вважають, що має сенс продовжувати схожі експерименти на Хабре (зрозуміло, більш акуратно), я продовжу і крок за кроком розберу багато різних алгоритмів. Користь для співтовариства – навчання, адже в процесі експериментів я завжди пояснюю або показую, де прочитати пояснення тих речей, що тестуються. Інша користь – можливість перевірити все на своєму комп'ютері. Користь для мене – критика, коригування, підказки та поради. Якщо 80% не набереться, я зберу свою аудиторію для таких експериментів сам, просто це займе більше часу, але зате я не буду тут мішатися.

Голосуємо і до нових зустрічей: )

PS. Пояснення до голосування: під «більш серйозним» експериментом розуміється не більш складний алгоритм (алгоритми будуть різними — від sign(x) до Шенхаге — Штрассена), а я буду намагатися якось покращувати їх якість і потенційну цінність результату.

Потрібні подібні (але більш серйозні) експерименти на Хабре?

/>
/>


<input type=«radio» id=«vv72767»
class=«radio js-field-data»
name=«variant[]»
value=«72767» />
Так, знаходжу це досить корисним для себе (навіть не дивлячись на штучність, можливі помилки та можливу невідповідність реальності)
<input type=«radio» id=«vv72769»
class=«radio js-field-data»
name=«variant[]»
value=«72769» />
Боронь Боже від цього мракобісся

Проголосувало 55 осіб. Утрималося 27 осіб.


Тільки зареєстровані користувачі можуть брати участь в опитуванні. Увійдіть, будь ласка.


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

0 коментарів

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