Питання Чому GCC не оптимізує a * a * a * a * a до (a * a * a) * (a * a * a)?


Я роблю певну чисельну оптимізацію на науковій програмі. Одне я помітив, що GCC оптимізує дзвінок pow(a,2) склавши його в a*a, але дзвінок pow(a,6) не оптимізовано і буде фактично викликати функцію бібліотеки pow, що сильно уповільнює продуктивність. (У контрасті, Компілятор Intel C ++, виконуваний файл icc, буде ліквідувати бібліотечний дзвінок для pow(a,6).)

Мені цікаво те, що коли я замінений pow(a,6) з a*a*a*a*a*a використовуючи GCC 4.5.1 та параметри "-O3 -lm -funroll-loops -msse4", він використовує 5 mulsd інструкції:

movapd  %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13

а якщо я пишу (a*a*a)*(a*a*a), це буде виробляти

movapd  %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm13, %xmm13

що зменшує кількість множинних інструкцій до 3. icc має подібну поведінку.

Чому компілятори не визнають цей оптимізаційний фокус?


1965
2018-06-21 18:49


походження


Що означає "визнання pow (a, 6)"? - Varun Madiath
Гм ... ти знаєш, що аaaaaa і (aaа) * (аa * a) не збігаються з номерами з плаваючою комою, чи не так? Вам доведеться скористатись -funsafe-математикою або -фастом-математикою чи щось для цього. - Damon
Я пропоную вам прочитати "Що повинен знати кожен комп'ютерник про арифметику плаваючою точки" Девід Голдберг: download.oracle.com/docs/cd/E19957-01/806-3568/... після чого ви будете мати більш повне розуміння смоли ями, що ви тільки що ввійшли! - Phil Armstrong
Дуже розумне питання. 20 років тому я запитав таке ж загальне питання, і, здавлюючи це єдине вузьке місце, скоротив час виконання симуляції Монте-Карло з 21 години до 7 годин. Код у внутрішній петлі був виконаний у 13 трильйонів разів, але він отримав симуляцію в вікно, що перевищує ніч. (див. відповідь нижче)
Може бути кинути (a*a)*(a*a)*(a*a) в суміш теж. Однакова кількість множення, але, мабуть, більш точна. - Rok Kralj


Відповіді:


Оскільки Плаваюча точка Математика не асоціативна. Спосіб групування операндів з множенням з плаваючою точкою впливає на числову точність відповіді.

Як наслідок, більшість компіляторів дуже консервативні щодо перерахунку обчислень з плаваючою точкою, якщо вони не можуть бути впевнені, що відповідь залишиться незмінною, або якщо ви скажете їм, що ви не дбаєте про числовій точності. Наприклад: в -fassociative-math варіант gcc, що дозволяє gcc переакшировать операції з плаваючою точкою або навіть -ffast-math варіант, який дозволяє ще більш агресивні компроміси точності проти швидкості.


2567
2018-06-22 15:32



Так. З -fast-math робить таку оптимізацію. Гарна ідея! Але оскільки наш код стосується більшої точності, ніж швидкість, то краще не пропускати його. - xis
IIRC C99 дозволяє компілятору робити такі "небезпечні" оптимізації FP, але GCC (на щось інше, ніж x87) робить розумну спробу виконати IEEE 754 - це не "межа помилки"; є тільки одна правильна відповідь. - tc.
Реалізація деталей pow ні тут, ні там; ця відповідь навіть не вказує pow. - Stephen Canon
@nedR: ICC за замовчуванням дозволяє повторно об'єднати. Якщо ви хочете отримати стандартну поведінку, вам потрібно встановити -fp-model precise з ICC. clang і gcc за замовчуванням на суворе дотримання w.r.t. об'єднання - Stephen Canon
@xis, це не так -fassociative-math буде невідповідним; це просто так a*a*a*a*a*a і (a*a*a)*(a*a*a) різні. Це не точність; це стосується відповідності стандартів і суворо повторюваних результатів, наприклад однакові результати на будь-якому компіляторі. Номери з плаваючою точкою вже не є точними. Рідко не підходить для компіляції -fassociative-math. - Paul Draper


Ламбдагейк правильно вказує, що оскільки асоціативність не виконується для чисел з плаваючою точкою, то "оптимізація" a*a*a*a*a*a до (a*a*a)*(a*a*a) може змінити значення. Ось чому це забороняється C99 (за винятком спеціально дозволеного користувачем, через прапорець компілятора або прагма). Як правило, припущення полягає в тому, що програміст написав, що вона зробила з причини, і компілятор повинен поважати це. Якщо хочеш (a*a*a)*(a*a*a), напиши це.

Однак це може бути біль писати; чому компілятор просто не робить [що ви вважаєте] правильним, коли ви використовуєте pow(a,6)? Тому що це буде неправильно що робити На платформі з гарною математичною бібліотекою pow(a,6) є значно більш точним, ніж будь-який a*a*a*a*a*a або (a*a*a)*(a*a*a). Просто для надання деяких даних я провела невеликий експеримент на моєму Mac Pro, вимірюючи найгіршу помилку при оцінці ^ 6 для всіх одноточних плаваючих чисел між [1,2]:

worst relative error using    powf(a, 6.f): 5.96e-08
worst relative error using (a*a*a)*(a*a*a): 2.94e-07
worst relative error using     a*a*a*a*a*a: 2.58e-07

Використовуючи pow замість дерева множення зменшує помилку, пов'язану з a коефіцієнт 4. Компілятори не повинні (і взагалі не роблять) "оптимізацію", що збільшує помилку, якщо користувач не має ліцензії на це (наприклад, через -ffast-math)

Зверніть увагу, що GCC забезпечує __builtin_powi(x,n) як альтернатива pow( ), який повинен генерувати вбудоване дерево множення. Використовуйте це, якщо ви хочете зіставити точність виконання, але не хочете активувати швидку математику.


614
2018-06-22 22:39



Зауважте також, що Visual C ++ надає "підвищену" версію pow (). Зателефонувавши _set_SSE2_enable(<flag>) з flag=1, він, якщо можливо, буде використовувати SSE2. Це трохи зменшує точність, але покращує швидкість (у деяких випадках). MSDN: _set_SSE2_enable () і POW () - TkTech
@TkTech: Будь-яка зменшена точність пов'язана з реалізацією Microsoft, а не з розмірами використовуваних регістрів. Можна доставити a правильно округлений  pow використовуючи лише 32-бітні регістри, якщо письменник бібліотеки настільки мотивований. Є SSE-основі pow реалізації, які є більше точніше, ніж більшість x87-рішень, і існують також реалізації, які суттєво зменшують швидкість. - Stephen Canon
@TkTech: Звичайно, я просто хотів сказати, що зниження точності пояснюється вибором авторів бібліотеки, який не є властивим для використання SSE. - Stephen Canon
Мені цікаво дізнатись, що ви тут використовували як "золотий стандарт" для розрахунку відносних помилок - я б, як правило, очікував, що це буде a*a*a*a*a*a, але це, мабуть, не справа! :) - j_random_hacker
@j_random_hacker: оскільки я порівнював результати з одноточністю, достатня подвійна точність для золотого стандарту - помилка відaaaaобчислений у подвійному значенні * значно менша, ніж помилка будь-якої з одноточних обчислень. - Stephen Canon


Інший подібний випадок: більшість компіляторів не оптимізуються a + b + c + d до (a + b) + (c + d) (це оптимізація, оскільки другий вираз може бути краще конвеєрним) і оцінити його як заданий (наприклад, як (((a + b) + c) + d)) Це теж відбувається через кутові справи:

float a = 1e35, b = 1e-5, c = -1e35, d = 1e-5;
printf("%e %e\n", a + b + c + d, (a + b) + (c + d));

Ці виходи 1.000000e-05 0.000000e+00


152
2018-06-23 11:44



Це не зовсім так. Changin, порядок множення / розділів (за винятком поділу на 0) безпечніше, ніж зміна порядку суми / віднімання. На мою скромну думку, компілятор повинен спробувати зв'язати mults./divs. тому що це зменшує загальну кількість операцій, і, крім продуктивності, це також є точністю. - GameDeveloper
@ DarioOO: це не безпечніше. Помножити і розділити ті ж самі, що і додавання і віднімання показника, і зміна порядку може легко призвести до тимчасових перевищення можливого діапазону показника. (Не зовсім те саме, тому що показник не зазнає втрати точності ... але представлення все ще досить обмежене, і перегрупування може призвести до непредставленим значенням) - Ben Voigt
Я думаю, що ви не володієте фоном обчислень. Множинні та розділення 2 чисел вводять однакову кількість помилок. При вирахуванні / додаванні 2 числа можуть вводити більшу помилку, особливо коли 2 числа є порядком величин різними, отже безпечніше перелаштувати мул / ділення, ніж sub / add, оскільки він вносить незначні зміни в остаточну помилку. - GameDeveloper
@ DarioOO: ризик відрізняється від mul / div: переналаштування або робить незначну зміну в кінцевому результаті, або показник переповнюється в певний момент (там, де його раніше не було), а результат масивно відрізняється (потенційно + inf або 0). - Peter Cordes


Фортран (розроблений для наукових обчислень) має вбудований оператор енергії, і, наскільки я знаю, компілятори Fortran зазвичай оптимізують підняття до цілих чисел аналогічно тому, що ви описуєте. C / C ++, на жаль, немає оператора живлення, функціонує лише бібліотека pow(). Це не перешкоджає розумним компіляторам обробляти pow спеціально і обчислюючи його швидше для спеціальних випадків, але здається, вони роблять це рідше ...

Кілька років тому я намагався зробити його більш зручним для обчислення цілих чисел у оптимальному варіанті і придумав наступне. Це C ++, а не C, хоча і все одно залежить від того, що компілятор є дещо розумним про те, як оптимізувати / вбудовані речі. У будь-якому разі, сподіваюся, що це може бути корисним на практиці:

template<unsigned N> struct power_impl;

template<unsigned N> struct power_impl {
    template<typename T>
    static T calc(const T &x) {
        if (N%2 == 0)
            return power_impl<N/2>::calc(x*x);
        else if (N%3 == 0)
            return power_impl<N/3>::calc(x*x*x);
        return power_impl<N-1>::calc(x)*x;
    }
};

template<> struct power_impl<0> {
    template<typename T>
    static T calc(const T &) { return 1; }
};

template<unsigned N, typename T>
inline T power(const T &x) {
    return power_impl<N>::calc(x);
}

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

Тоді просто використовуйте його як power<6>(a).

Це полегшує друк повноважень (не потрібно вимовляти 6 as з parens), і дозволяє вам мати такий вид оптимізації без -ffast-math у випадку, якщо у вас є щось точне залежне, таке як компенсоване підсумовування (приклад, коли порядок операцій є суттєвим).

Можливо, ви також можете забути, що це C ++, і просто використовуйте його в програмі C (якщо він компілює з C + + компілятором).

Сподіваюся, що це може бути корисним.

EDIT:

Це те, що я отримую від мого компілятора:

Для a*a*a*a*a*a,

    movapd  %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0

Для (a*a*a)*(a*a*a),

    movapd  %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm0, %xmm0

Для power<6>(a),

    mulsd   %xmm0, %xmm0
    movapd  %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
    mulsd   %xmm0, %xmm1

74
2018-06-23 10:07



Пошук оптимального дерева властивостей може бути складним, але оскільки він є цікавим лише для малих потужностей, очевидною відповіддю є попередній розв'язування його один раз (Кнут пропонує таблицю до 100) і використовувати цей жорсткокодований таблицю (це те, що gcc робить внутрішньо для powi) . - Marc Glisse
На сучасних процесорах швидкість обмежена затримкою. Наприклад, результат множення може бути доступним після п'яти циклів. У цій ситуації знайти найшвидший спосіб створити якусь владу може бути складніше. - gnasher729
Ви також можете спробувати знайти силове дерево, яке дає найнижчу верхню межу відносної похибки округлення або найнижчу середню похибку округлення. - gnasher729
Boost також підтримує це, наприклад boost :: math :: pow <6> (n); Я думаю, що він навіть намагається зменшити кількість множення шляхом вилучення загальних чинників. - gast128
Хороша ідея ! Я вже зробив це для факторіального попереднього обчислення. - Caduchon


Оскільки 32-бітове число з плаваючою комою - наприклад 1.024 - не 1.024. У комп'ютері 1,024 - інтервал: від (1,024-е) до (1,024 + е), де "е" являє собою помилку. Деякі люди цього не усвідомлюють, а також вважають, що * в a * означає множення безлічі довільної точності без будь-яких помилок, пов'язаних з цими числами. Причина, чому деякі люди не розуміють цього, - це, мабуть, математичні обчислення, які вони виконували в початкових школах: працюючи лише з ідеальними числами без додавання помилок, і вважаючи, що просто "ігнорувати" е "під час виконання множення. Вони не бачать "е", що мається на увазі у "float a = 1.2", "a * a * a" та аналогічні C-коди.

Якщо більшість програмістів розпізнає (і зможе виконати) ідею про те, що вираз C * a * a * a * a * a насправді не працює з ідеальними числами, компілятор GCC потім буде БЕЗКОШТОВНО для оптимізації "a * a * a * a * a * a ", щоб сказати" t = (a * a); t * t * t ", що вимагає меншої кількості множення. На жаль, компілятор GCC не знає, чи написав програміст код, що "a" - це число з помилкою або без нього. Таким чином, GCC буде робити лише те, що виглядає як вихідний код, - саме тому GCC бачить його "неозброєним оком".

... як тільки ти знаєш, який тип програміста ви є, ви можете використовувати перемикач "-fast-math", щоб повідомити GCC, що "Гей, GCC, я знаю, що я роблю!". Це дозволить GCC перетворити * a * a * a * a * a на інший фрагмент тексту - він відрізняється від * a * a * a * a * a - але все-таки обчислює число в межах інтервалу помилок a * a * a * a * a * a. Це добре, оскільки ви вже знаєте, що ви працюєте з інтервалами, а не ідеальними номерами.


49
2018-03-29 06:51



Номери з плаваючою точкою точні. Вони просто не обов'язково саме те, що ви очікували. Крім того, техніка з епсілон сама є наближенням до того, як реалізувати речі насправді, оскільки справжня очікувана помилка є відносно масштабу мантиси, тобто ви, як правило, досягає приблизно 1 LSB, але це може збільшитися з кожна операція виконується, якщо ви не будете обережні, тому порадьтесь до числового аналітика, перш ніж робити щось нетривіальне з плаваючою крапкою. Використовуйте правильну бібліотеку, якщо можливо. - Donal Fellows
@DonalFellows: Стандарт IEEE вимагає, щоб обчислення з плаваючою точкою давали результат, який найбільш точно відповідав би результату, якщо операндом джерела були точні значення, але це не означає, що вони фактично представляти точні значення У багатьох випадках корисніше вважати 0.1f як (1,677,722 + / -0,5) / 16,777,216, що повинно бути показано з кількістю десяткових цифр, що передбачається цією невизначеністю, ніж розглядати його як точну кількість (1,677,722 +/- 0,5) / 16 777 216 (який повинен відображатися до 24 десяткових цифр). - supercat
@supercat: IEEE-754 є досить ясним з точки зору даних з плаваючою комою робити представляють точні значення; відповідні розділи статей 3.2 - 3.4. Ви, звичайно, можете витлумачити їх інакше, як і ви можете інтерпретувати int x = 3 як означає, що x 3 +/- 0,5. - Stephen Canon
@supercat: Я цілком погоджуюсь, але це не означає це Distance не точно дорівнює його чисельному значенню; це означає, що чисельне значення є лише наближенням до певної фізичної кількості, що моделюється. - Stephen Canon
Для чисельного аналізу ваш мозок буде дякувати вам, якщо ви інтерпретуєте числа з плаваючою точкою не як інтервали, а як точні значення (які, здається, точно не є значеннями, які ви хотіли). Наприклад, якщо x десь 4,5 рази з помилкою менше 0,1, і ви обчислюєте (x + 1) - x, інтерпретація інтервалу залишає вас з інтервалом від 0,8 до 1,2, тоді як інтерпретація "точного значення" говорить ви отримаєте результат 1 з помилкою не більше 2 ^ (- 50) у подвійній точності. - gnasher729


GCC фактично оптимізує a * a * a * a * a до (a * a * a) * (a * a * a), коли a ціле число. Я спробував за допомогою цієї команди:

$ echo 'int f(int x) { return x*x*x*x*x*x; }' | gcc -o - -O2 -S -masm=intel -x c -

Є багато прапорів gcc, але нічого фантастичного. Вони означають: прочитайте зі stdin; використовувати рівень оптимізації O2; вивести мову асемблера замість двійкового; в переліку слід використовувати синтаксис синтезу мови Intel; вхідна мова знаходиться в мові C (зазвичай мову виводяться з розширення вхідного файлу, але при читанні з stdin не відбувається розширення файлу); і напишіть на stdout.

Ось важлива частина виходу. Я охарактеризував це з деякими коментарями, вказуючи на те, що відбувається на асемблері:

    ; x is in edi to begin with.  eax will be used as a temporary register.
    mov    eax, edi     ; temp1 = x
    imul    eax, edi    ; temp2 = x * temp1
    imul    eax, edi    ; temp3 = x * temp2
    imul    eax, eax    ; temp4 = temp3 * temp3

Я використовую систему GCC на Linux Mint 16 Petra, похідну Ubuntu. Ось версія gcc:

$ gcc --version
gcc (Ubuntu/Linaro 4.8.1-10ubuntu9) 4.8.1

Як зазначили інші плакати, цей параметр неможливий в плаваючому краю, оскільки арифметика з плаваючою точкою насправді не асоціативна.


49
2018-06-27 21:03



Це є законним для цілого множення, оскільки два переповнення комплементу - це невизначена поведінка. Якщо це буде переповнення, це станеться десь незалежно від операцій переобладнання. Отже, вирази без переповнення оцінюють однакові, вирази, що переповнення є невизначеною поведінкою, тому для компілятора нормально змінювати точку, в якій відбувається переповнення. gcc робить це з unsigned intтеж. - Peter Cordes


Жоден із плакатів ще не згадав про скорочення плаваючих виразів (стандарт ISO C, 6.5p8 та 7.12.2). Якщо FP_CONTRACT Прагма встановлено на ON, компілятор може розглядати такий вираз, як a*a*a*a*a*a як єдину операцію, начебто оцінюється точно з одним округленням. Наприклад, компілятор може замінити його внутрішньою функцією, яка є швидшою і точнішою. Це особливо цікаво, оскільки поведінка частково контролюється програмістом безпосередньо в вихідному коді, тоді як параметри компілятора, надані кінцевим користувачем, іноді можуть бути використані неправильно.

Стан за замовчуванням FP_CONTRACT Прагма визначається як реалізація, так що компілятор може робити такі оптимізації за замовчуванням. Таким чином, портативний код, який повинен суворо дотримуватися правил IEEE 754, повинен явним чином встановити його OFF.

Якщо компілятор не підтримує цю прагму, він повинен бути консервативним, уникаючи такої оптимізації, якщо розробник вирішив встановити його OFF.

GCC не підтримує цю прагму, але з параметрами за умовчанням він вважає це таким ON; таким чином, для цілей з апаратним FMA, якщо хтось хоче запобігти перетворенню a*b+c Для fma (a, b, c), потрібно вказати такий параметр, як -ffp-contract=off (щоб явно встановити прагму до OFF) або -std=c99 (щоб повідомити GCC, що він відповідає деякій стандартній версії C, тут C99, таким чином, дотримуйтесь вищезазначеного пункту). У минулому останній варіант не перешкоджав перетворенню, а це означає, що GCC не відповідає цьому питанню: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845


27
2018-06-23 12:44



Довгоживі популярні запитання іноді показують свій вік. Це питання було поставлене на запитання та відповідь у 2011 році, коли GCC можна було виправдати за те, що не дотримувався точно нещодавнього нещодавнього стандарту C99. Звичайно, тепер це 2014 рік, тому GCC ... ах. - Pascal Cuoq
Чи не слід відповідати на порівняно недавні питання із плаваючою точкою без прийнятої відповіді, однак? кашель stackoverflow.com/questions/23703408 кашель - Pascal Cuoq
Я вважаю це ... турбуючим, що gcc не реалізує прагми C99 з плаваючою точкою. - David Monniaux


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


26
2018-06-21 18:52



Плаваюча точка завжди детермінована. - Alice
@Alice Здається, досить ясно, що тут Бьорн використовує 'детерміністичний' у розумінні коду, що дає той самий результат на різних платформах та різних версіях компілятора тощо (зовнішні змінні, які можуть бути поза контролем програміста) - на відміну від відсутності фактичної числової випадковості під час виконання. Якщо ви вкажете, що це не є належним використанням цього слова, я не збираюся суперечити цьому. - greggo
@greggo За винятком навіть у тій інтерпретації, що він говорить, це все ще не так; це цілковита точка IEEE 754, щоб забезпечити однакові характеристики для більшості (якщо не всі) операцій на різних платформах. Тепер він не згадав про версії платформ або компіляторів, що було б дійсним питанням, якщо ви хочете, щоб кожна операція на кожному віддаленому сервері / клієнтові була однаковою ..., але це не є очевидним з його твердження. Краще слово може бути "достовірно подібним" чи щось. - Alice
@Аліце ви витрачаєте всім часом, у тому числі і свої, стверджуючи семантику. Його значення було ясним. - Lanaru
@ Ланару Повний пункт стандартів IS семантика; його значення було цілком незрозуміло. - Alice