Хвостова рекурсія в C++ з використанням 64-бітових змінних — Частина 2

У минулій примітки я розповідав про проблеми з рекурсією у функції Фібоначчі при використанні 64-бітових змінних аргументів і компіляції коду за допомогою Microsoft Visual C++. З'ясувалося, що компілятор включає хвостову рекурсію, коли використовуються 32-бітні змінні, але не робить цього при переході до 64-бітним. На всяк випадок нагадаю, що хвостова рекурсія – це оптимізація, вироблена компілятором, при якій деякі види хвостових викликів перетворюються в безумовні переходи. Дізнатися більше про хвостової рекурсії.

Я вирішив, що проблема криється в самому компіляторі Visual C++ і пояснюється, мабуть, наявністю в ньому бага.

Обчислювати ряди Фібоначчі з великих цілих чисел доводиться нечасто, але це дуже наочний приклад, щоб показати, як реалізуються хвостові виклики.

Результати мене не порадували, і, дотримуючись порад деяких читачів (в коментарях на цьому блозі і на сайтах Reddit і StackOverflow), я вирішив розібратися в проблемі і подивитися, як поводяться інші компілятори.

Візьмемо той же проект Visual Studio, який був використаний у минулій замітці і який я виклав на GitHub. Це була функція Фібоначчі:
typedef unsigned long long ULONG64;
ULONG64 fib_tail_x64(ULONG64 n, ULONG64 res, ULONG64 next)
{
if (n == 0) {
return res;
}
return fib_tail_x64(n - 1, next, res + next);
}

Як ви, мабуть, пам'ятаєте, при компіляції коду в реліз-режимі (який зазвичай потрібен для отримання хвостової рекурсії за рахунок команди оптимізації /Ox) для платформи Win32 хвостова рекурсія не спрацьовувала:

<img src=«habrastorage.org/getpro/habr/post_images/0ed/0e6/e5b/0ed0e6e5bb548af44335758564dc3515.png» alt=«Picture » 2"/>

Хвостова рекурсія не працює! Асемблерний код жахливий через включених покажчиків фрэйма

Є, щоправда, одна річ, яку я не намагався пробувати (а якщо вже бути чесним, то просто-напросто забув). Це вибір платформи рішення для складання проекту. У Visual Studio конфігурація Win32, яка відповідає компіляції рішення з використанням x86 інструкцій процесора, є конфігурацією за умовчанням. У наведеному вище фрагменті асемблерного коду можна бачити, що використовуються регістри EAX, EBX і т. д. – є регістрами 32-бітного процесора, відповідно до обраної конфігурацією.

Якщо ми перемкнемо на конфігурацію x64, зберемо і запустимо проект, то отримаємо наступний асемблерний код:

<img src=«habrastorage.org/getpro/habr/post_images/188/9f1/b93/1889f1b9384373846f6ded094652ce3f.png» alt=«Picture » 3"/>

Хвостова рекурсія з'явилася!!!

Ось так сюрприз! Хвостова рекурсія спрацювала при використанні x64-регістрів (RAX, RDX і т. д.), а асемблерний код став набагато коротше і чистіше!

Підводячи підсумок всього вищесказаного з приводу хвостових викликів, можна скласти наступну наочну таблицю:

<img src=«habrastorage.org/getpro/habr/post_images/b57/6f3/96a/b576f396a65542ab7763277c79019359.png» alt=«Picture » 9"/>

Виходить, що проблема проявляється тільки тоді, коли ми використовуємо x64-змінні, а в якості цільової платформи вибираємо x86.

Чесно кажучи, на цьому етапі я вже не був так упевнений в наявності бага в MS-компіляторі, тому, як і раніше незадоволений результатами, я вирішив повторити експеримент з іншим компілятором.

На цей раз я вирішив переключитися на іншу операційну систему і попрацювати з Clang, заснованому на LLVM, встановленому на моєму Macbook у складі XCode.

<img src=«habrastorage.org/getpro/habr/post_images/c31/c1a/88b/c31c1a88b8cdf7a4890aa466786c33c6.png» alt=«Picture » 4"/>

Термінал – версія clang

Для перегляду згенерованого асемблерного коду я використовував зручну утиліту Hopper Disassembler, доступну як для OS X, так і для Linux (але, як я розумію, вона цілком може працювати і з відладчиком gdb).

Я в точності повторив той же самий експеримент. На наступному малюнку показаний перший варіант згенерованого асемблера:

<img src=«habrastorage.org/getpro/habr/post_images/bbb/f29/0e7/bbbf290e73eb30d4ed213450d365d3b0.png» alt=«Picture » 5"/>

Хвостова рекурсія тут явно присутній: інструкція JNE (Jump Not Equal, перехід по нерівності) є лише умовним переходом, коли прапор ZF («нульовий» прапор) встановлений в 0. Червона стрілка на картинці вказує на адресу, в якому відбувається перехід, у разі якщо умова істинна. Уважний спостерігач, повинно бути, вже помітив, що даний код складати не для 32-бітних процесорів: використовувані асемблерні регістри насправді є 64-бітними (RBD, RDI і т. д.).

Однак зараз наша мета – переконатися, що хвостова рекурсія буде як і раніше працювати при виборі 32-бітної платформи в якості цільової.

Компілятор можна примусити згенерувати 32-бітний код з допомогою ключа -m32. Після перезбирання рішення в 32-бітному режимі я отримав наступне:

<img src=«habrastorage.org/getpro/habr/post_images/1ab/388/c5f/1ab388c5fa49a2d402dd88a0157a2bcb.png» alt=«Picture » 6"/>

Хвостова рекурсія включена!

Ура!!! За типом використовуваних регістрів ми можемо укласти, що виконуваний модуль зібраний саме під зазначену нами архітектуру, і в останньому рядку можна спостерігати несподіваний результат: хвостова рекурсія спрацювала в 32-бітному режимі!!!!!

ПРАВКА 1
Як я зрозумів, у багатьох користувачів не вийшло відтворити проблему (див. коментарі нижче, а також на Reddit). Я продовжив експериментувати з налаштуваннями оптимізації компілятора, підлаштовуючи деякі параметри. У реліз-режимі конфігурація оптимізації налаштувань за замовчуванням є наступною:

Picture 7

Параметри оптимізації за замовчуванням

Після кількох спроб я змінив параметр 'Whole Program Optimization' /GL (включено) на No (вимкнено). Також я змінив параметр 'Omit Frame Pointers', т. до. мені підказали, що з включеними покажчиками кадру згенерований асемблерний код під x86 виходить набагато довше і більш неприємним (крім того, ми, можливо, заощадили кілька тактів, уникнувши промахів по кешу). StackOverflow є розгорнуте пояснення, як відключити покажчики фрэйма.

Як би там не було, коли я перекомпилировал рішення під Win32 з урахуванням всіх описаних вище змін, одержав несподіваний результат:

Picture 8

Хвостова рекурсія під x86 – спрацьовує при виключенні 'Whole Program Optimization'

ПРАВКА 2
Кілька людей написали, що, незалежно від настройки параметра WPO (Whole Program Optimization), вони не відчували жодних проблем з хвостової рекурсією. Це спочатку здивувало мене, але потім я зрозумів, що не врахував одну важливу деталь – а саме, спосіб виклику функції Фібоначчі з main. Досі виклик функції в моєму коді для перевірки функції Фібоначчі x64-режимі виглядав наступним чином:
ULONG64 res = fib_tail_x64(40, 0, 1);

Поки все добре, нічого особливого в цьому коді немає – я просто передаю літерали в якості аргументів функції.

А якщо ми замість них будемо передавати змінні або покажчики на функцію? Давайте спробуємо:
ULONG64 a = 40;
ULONG64 res = fib_tail_x64(a, 0, 1);

Хоча код начебто не сильно змінився, виклик функції fib_tail_x64 з використанням змінних включає хвостову рекурсію незалежно від WPO (за умови, що ми використовуємо ключ оптимізації >= /O2). читач на Reddit вказав, що непрямий виклик функції через покажчики (незалежно від застосування літералів) дасть такий же результат:
volatile bool a = true;
ULONG64 res = 0;
ULONG64(*ptr)(ULONG64 n, ULONG64 res, ULONG64 next) = NULL;
if (a)
{
ptr = &fib_tail_x64;
}
res = ptr(40, 0, 1);

Остаточні висновки
Хоча спочатку я грішив на наявність в компіляторі Visual C++ бага, який був винуватцем відключення хвостової рекурсії, врешті-решт, з'ясувалося, що це не так. Асемблерні коди, згенеровані компіляторами VC++ і Clang для x86 платформ дуже схожі між собою. В якості перший ув'язнення я вирішив, що потрібно обов'язково вимикати параметр 'Whole Program Optimization' тоді, і тільки тоді, коли відбувається прямий виклик рекурсивну x64 функції, в якості аргументів якої передаються літерали.

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

Буду радий почути будь-які міркування від кого-небудь із команди, яка працює над компілятором Visual C++, з приводу причин даної "проблеми".

На цьому все, спасибі за увагу! Щоб залишатися зі мною на зв'язку, пишіть на пошту через Контакти-форму або підписуйтесь на сторінку у твіттері!

До швидких зустрічей!

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

0 коментарів

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