Хвостовая Рекурсия В C++ С Использованием 64-Битных Переменных. Часть 1.

На этот раз я хочу поделиться с вами одной проблемой, с которой я столкнулся, когда решил сравнить итеративные и рекурсивные функции в C++.

Между рекурсией и итерацией есть несколько различий: они подробно обсуждаются в этой статье.

становиться .

В языках общего назначения, таких как Java, C или Python, рекурсия довольно дорога по сравнению с итерацией из-за необходимости каждый раз выделять новый кадр стека.

В C/C++ эти накладные расходы можно легко устранить, указав оптимизирующему компилятору использовать хвостовую рекурсию, которая преобразует определенные типы рекурсии (или, скорее, определенные типы хвостовых вызовов) в инструкции безусловного перехода.

Для реализации такого преобразования необходимо, чтобы самым последним действием функции перед возвратом значения был вызов другой функции (в данном случае самой себя).

В этом случае безусловный переход к началу второй подпрограммы безопасен.

Основным недостатком рекурсивных алгоритмов в императивных языках является то, что не всегда возможно иметь хвостовые вызовы, т.е.

выделение места для адреса функции (и связанных с ней переменных, таких как структуры) в стеке каждый раз при ее вызове.

Если глубина рекурсии слишком велика, это может привести к переполнению стека из-за ограничения на его максимальный размер, который обычно на порядки меньше объема оперативной памяти.

В качестве теста на изучение хвостовой рекурсии я написал простую функцию Фибоначчи на C++ в Visual Studio. Давайте посмотрим, как это работает:

   

 int fib_tail(int n, int res, int next)
 {
   if (n == 0)
   {
     return res;
   }
   return fib_tail(n - 1, next, res + next);
 }

Чтобы выполнить хвостовой вызов перед возвратом значения, функция фиб_хвост В качестве финального действия он вызывает себя.

Давайте теперь посмотрим на сгенерированный ассемблерный код. Для этого я скомпилировал программу в режиме выпуска, используя ключ оптимизации /O2. Вот как выглядит код:

Хвостовая рекурсия в C++ с использованием 64-битных переменных.

Часть 1.

Есть! Обратите внимание на последнюю строку: вместо инструкции ВЫЗОВ использовал СПМ .

В данном случае сработала хвостовая рекурсия, и у нашей функции не будет проблем с переполнением стека, поскольку на уровне ассемблера она превращена в итеративную функцию.

Мне этого оказалось недостаточно, и я решил поэкспериментировать с производительностью, увеличив входную переменную н .

Затем я изменил тип переменных, используемых в функции, с интервал на без подписи длинный длинный .

После повторного запуска программы у меня внезапно произошло переполнение стека! Вот как выглядит эта версия нашей функции:

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); }

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

Хвостовая рекурсия в C++ с использованием 64-битных переменных.

Часть 1.

Как я и ожидал, хвостовой рекурсии здесь не было! Теперь вместо ожидаемого СПМ использовал ВЫЗОВ .

Между тем, единственная разница между двумя версиями нашей функции заключается в том, что во втором случае я использовал 64-битную переменную вместо 32-битной.

Возникает вопрос: почему компилятор не использует хвостовую рекурсию при использовании 64-битных переменных? Я решил скомпилировать программу в 64-битном режиме и посмотреть, как она себя поведет. Сгенерированный ассемблерный код:

Хвостовая рекурсия в C++ с использованием 64-битных переменных.

Часть 1.

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

Я задал свой вопрос на сайте Переполнение стека — похоже, проблема в самом компиляторе Microsoft C++.

Автор одного из комментариев сказал, что в других компиляторах C++ такой проблемы не наблюдается, но мне нужно убедиться в этом самому.

Я разместил пример кода на GitHub – вы можете скопировать его и попробовать запустить самостоятельно.

На Реддит и Stackoverflow также сообщил мне, что описанная проблема не возникает в VS2013 Community Edition. Я пробовал работать в VS2013 Ultimate, но и там столкнулся с проблемами.

В ближайшие несколько дней я постараюсь протестировать код под GCC и сравнить результаты.

См.

пример проекта на GitHub .

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

До скорой встречи! Продолжение: habrahabr.ru/company/pvs-studio/blog/261029 Теги: #компиляторы #оптимизация кода #Ассемблер #64-бит #хвостовая рекурсия #x64 #64бит #64-бит #64-битное программирование