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

В цей раз я хочу поділитися з вами однією проблемою, з якою зіткнувся, коли вирішив порівняти ітераційні та рекурсивні функції C++. Між рекурсією і ітерацією є декілька відмінностей: про них докладно розказано в цій стати. У мовах загального призначення начебто Java, C або Python рекурсія досить затратна порівняно з ітерацією за необхідності кожен раз виділяти новий стековий фрейм. В C/C++ ці витрати можна легко усунути, вказавши оптимизирующему компілятору використовувати хвостову рекурсію, при якій певні типи рекурсії (а точніше, певні види хвостових викликів) перетворяться в команди безумовного переходу. Для здійснення такого перетворення необхідно, щоб самим останнім дією функції перед поверненням значення був виклик ще однієї функції (в даному випадку себе самої). При такому сценарії безумовний перехід до початку другої підпрограми безпечний. Головний недолік рекурсивних алгоритмів в імперативних мовах полягає в тому, що в них не завжди можлива реалізація хвостових викликів, тобто виділення адреси функції (і пов'язаних з нею змінних, наприклад, структур) на стеку при кожному виклику. При занадто великій глибині рекурсії це може призвести до переповнення стека через обмеження на максимальний розмір, який зазвичай на порядки менше обсягу оперативної пам'яті.

В якості тесту для вивчення хвостової рекурсії я написав в Visual Studio просту функцію Фібоначчі на C++. Давайте подивимося, як вона працює:
int fib_tail(int n, int res, int next)
{
if (n == 0)
{
return res;
}
return fib_tail(n - 1, next, res + next);
}

Щоб перед поверненням значення вийшов хвостовий виклик, функція fib_tail в якості останнього дії викликає саму себе. Тепер Давайте поглянемо на згенерований асемблерний код. Для цього я скомпілював програму в реліз-режимі з використанням ключа оптимізації /O2. Ось як виглядає цей код:

<img src=«habrastorage.org/getpro/habr/post_images/6ca/c0b/858/6cac0b858f9b1b0606eac407a2dcd28d.png» alt=«Picture » 1"/>

Є! Зверніть увагу на останній рядок: в ній замість інструкції CALL використовується JMP. В даному випадку хвостова рекурсія спрацювала, і у нашої функції не виникне жодних проблем з переповненням стека, оскільки на рівні асемблера вона перетворилася в ітераційну функцію.

Цього мені було мало, і я вирішив поекспериментувати з продуктивністю, збільшивши вхідні змінну n. Потім я змінив тип змінних, використовуваних у функції, int unsigned long long. Запустивши програму повторно, я раптово отримав переповнення стека! Ось як виглядає цей варіант нашої функції:
typedef unsigned long long ULONG64;
ULONG64 fib_tail(ULONG64 n, ULONG64 res, ULONG64 next)
{
if (n == 0)
{
return res;
}
return fib_tail(n - 1, next, res + next);
}

Давайте знову поглянемо на згенерований асемблерний код:

<img src=«habrastorage.org/getpro/habr/post_images/424/8d4/279/4248d42798102cc17c7cc2b58b1d5fde.png» alt=«Picture » 2"/>

Як я і очікував, хвостової рекурсії тут не виявилося! Тепер замість очікуваної JMP використовується CALL. Між тим, єдина відмінність між двома варіантами нашої функції полягає в тому, що в другому випадку я використав 64-бітну змінну замість 32-бітної. У зв'язку з чим виникає питання: чому компілятор не задіює хвостову рекурсію при використанні 64-бітових змінних?

Я вирішив скомпілювати програму в 64-бітному режимі і подивитися, як вона себе поведе. Згенерований асемблерний код:

<img src=«habrastorage.org/getpro/habr/post_images/1ca/59d/861/1ca59d86117c80cabaa843d42624a1a3.png» alt=«Picture » 3"/>

Тут хвостова рекурсія знову з'явилася! Завдяки 64-бітних регістрів (rax, r8, rcx, rdx) викликає і викликається функції мають загальний стек, а викликається функція повертає результат безпосередньо в точку виклику всередині викликає функції.

Я задав своє питання на сайті StackOverflow – схоже, що проблема в самому компіляторі Microsoft C++. Автор одного з коментарів повідомив, що в решті C++-компіляторах ця проблема не спостерігається, але я повинен переконатися в цьому сам.

Я виклав приклад коду на GitHub – можете скопіювати його і спробувати запустити у себе. Reddit і Stackoverflow мені також сказали, що у виданні VS2013 Community Edition описана проблема не виникає. Я спробував попрацювати в VS2013 Ultimate, але зіткнувся з нею і там. Протягом найближчих днів спробую потестувати код під GCC і порівняю результати.

См. проект Example на GitHub.

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

До швидкої зустрічі!

Продовження: habrahabr.ru/company/pvs-studio/blog/261029

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

0 коментарів

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