Для получения триального ключа
заполните форму ниже
Team license
Enterprise license
** Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Запросите информацию о ценах
Новая лицензия
Продление лицензии
--Выберите валюту--
USD
EUR
RUB
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Бесплатная лицензия PVS-Studio для специалистов Microsoft MVP
** Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

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

Мне интересно попробовать плагин на:
** Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Ваше сообщение отправлено.

Мы ответим вам на


Если вы так и не получили ответ, пожалуйста, проверьте папку
Spam/Junk и нажмите на письме кнопку "Не спам".
Так Вы не пропустите ответы от нашей команды.

>
>
Хвостовая рекурсия в C++ с использовани…

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

23 Июн 2015

В этот раз я хочу поделиться с вами одной проблемой, с которой столкнулся, когда решил сравнить итерационные и рекурсивные функции в 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. Вот как выглядит этот код:

0332_TailRecursion_Part1_ru/image1.png

Есть! Обратите внимание на последнюю строку: в ней вместо инструкции 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);
}

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

0332_TailRecursion_Part1_ru/image2.png

Как я и ожидал, хвостовой рекурсии тут не оказалось! Теперь вместо ожидаемой JMP используется CALL. Между тем, единственное различие между двумя вариантами нашей функции заключается в том, что во втором случае я использовал 64-битную переменную вместо 32-битной. В связи с чем возникает вопрос: почему компилятор не задействует хвостовую рекурсию при использовании 64-битных переменных?

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

0332_TailRecursion_Part1_ru/image3.png

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

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

Я выложил пример кода на GitHub - можете скопировать его и попробовать запустить у себя. На Reddit и Stack Overflow мне также сказали, что в издании VS2013 Community Edition описанная проблема не возникает. Я попробовал поработать в VS2013 Ultimate, но столкнулся с ней и там. В течение ближайших дней попробую потестировать код под GCC и сравню результаты.

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

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

До скорой встречи!

Эта статья была опубликована в Coding Adventures Blog. Перепечатка и перевод сделаны с разрешения автора.

Популярные статьи по теме
Единороги компании PVS-Studio

Дата: 30 Авг 2022

Автор: Андрей Карпов

Скорее всего вы перешли на эту статью, заинтересовавшись одним из наших рисунков единорогов. Приятно видеть ваш интерес. Сейчас мы расскажем, почему рисуем этих единорогов, что они означают и чем воо…
Обрабатывать ли в PVS-Studio вывод других инструментов?

Дата: 26 Май 2022

Автор: Андрей Карпов

Анализатор PVS-Studio умеет "схлопывать" повторяющиеся предупреждения. Предоставляет возможность задать baseline, что позволяет легко внедрять статический анализ в legacy-проекты. Стоит ли предостави…
15000 ошибок в открытых проектах

Дата: 24 Май 2022

Автор: Андрей Карпов

Количество багов в нашей коллекции перевалило за отметку 15000. Именно такое количество ошибок обнаружила команда PVS-Studio в различных открытых проектах. Особенно интересно, что это всего лишь побо…
Комментарии в коде как вид искусства

Дата: 04 Май 2022

Автор: Сергей Хренов

Приветствую всех программистов, а также сочувствующих. Кто из нас хотя бы раз в жизни не оставлял комментарии в коде? Был ли это ваш код, а может, чужой? Что за комментарии вы написали: полезные или …
Visual Studio 2022 стильно и свежо. История о её поддержке в PVS-Studio

Дата: 15 Фев 2022

Автор: Николай Миронов

Кажется, анонс Visual Studio 2022 был только недавно, и вот она уже вышла. Это означало ровно одно – поддержать данную IDE нужно в ближайшем релизе PVS-Studio. О том, с какими сложностями пришлось ст…

Комментарии (0)

Следующие комментарии
Unicorn with delicious cookie
Мы используем куки, чтобы пользоваться сайтом было удобно. Хотите узнать подробнее?
Принять