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

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

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

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

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

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

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


Если вы так и не получили ответ, пожалуйста, проверьте папку
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 для Visual Studio Code

Дата: 02 Фев 2023

Автор: Андрей Москалёв

Благодаря новому плагину PVS-Studio преимущества статического анализа теперь доступны и при работе с редактором Visual Studio Code. В этой статье мы разберём использование плагина от этапа установки …
Изменения в PVS-Studio, о которых полезно знать

Дата: 31 Янв 2023

Автор: Сергей Васильев

В этой статье расскажу о том, что появилось в PVS-Studio за последние три года, и чем это полезно пользователям анализатора. Статья модульная: можно не читать от начала до конца, а посмотреть только …
C++ — язык 2022 года. Почему так, и что с другими языками?

Дата: 20 Янв 2023

Автор: Сергей Васильев

C++ становится языком 2022 года по версии TIOBE, обгоняя Python. Rust, C#, Go и прочие — далеко позади. Странно? Сейчас разберёмся.
PVS-Studio в 2022 году

Дата: 19 Янв 2023

Автор: Полина Алексеева

На дворе январь 2023, а значит, самое время подвести итоги уже прошлого 2022 года. Мы расскажем, чем занимались, и покажем, что нового появилось в анализаторе за это время. Давайте вместе взглянем на…
PVS-Studio: 2 фишки для быстрого старта

Дата: 08 Дек 2022

Автор: Сергей Васильев

В этой заметке расскажу, как легко начать использовать PVS-Studio. Рассмотрим два сценария: когда вы пробуете анализатор впервые и когда внедряете его в проект.

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

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