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

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

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

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

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

** На сайте установлена reCAPTCHA и применяются
Политика конфиденциальности и Условия использования Google.
Ваше сообщение отправлено.

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


Если вы так и не получили ответ, пожалуйста, проверьте папку
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) вызывающая и вызываемая функции имеют общий стек, а вызываемая функция возвращает результат непосредственно в точку вызова внутри вызывающей функции.

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

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

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

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

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

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

Популярные статьи по теме
Любите статический анализ кода!

Дата: 16 Окт 2017

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

Я в шоке от возможностей статического анализа кода, хотя сам участвую в разработке инструмента PVS-Studio. На днях я был искренне удивлён тому, что анализатор оказался умнее и внимательнее меня.
PVS-Studio для Java

Дата: 17 Янв 2019

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

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

Дата: 22 Дек 2018

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

В канун празднования нового 2019 года команда PVS-Studio решила сделать приятный подарок всем контрибьюторам open-source проектов, хостящихся на GitHub, GitLab или Bitbucket. Им предоставляется возмо…
Главный вопрос программирования, рефакторинга и всего такого

Дата: 14 Апр 2016

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

Вы угадали, ответ - "42". Здесь приводится 42 рекомендации по программированию, которые помогут избежать множества ошибок, сэкономить время и нервы. Автором рекомендаций выступает Андрей Карпов - тех…
Технологии, используемые в анализаторе кода PVS-Studio для поиска ошибок и потенциальных уязвимостей

Дата: 21 Ноя 2018

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

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

Дата: 22 Окт 2018

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

PVS-Studio, как и другие статические анализаторы кода, часто выдаёт ложные срабатывания. Но не стоит спешить считать странные срабатывания ложными. Это короткая история о том, как PVS-Studio вновь ок…
Как и почему статические анализаторы борются с ложными срабатываниями

Дата: 20 Мар 2017

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

В своей предыдущей статье я писал, что мне не нравится подход, при котором статические анализаторы кода оцениваются с помощью синтетических тестов. В статье приводился пример, воспринимаемый анализат…
Статический анализ как часть процесса разработки Unreal Engine

Дата: 27 Июн 2017

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

Проект Unreal Engine развивается - добавляется новый код и изменятся уже написанный. Неизбежное следствие развития проекта - появление в коде новых ошибок, которые желательно выявлять как можно раньш…
Зло живёт в функциях сравнения

Дата: 19 Май 2017

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

Возможно, читатели помнят мою статью под названием "Эффект последней строки". В ней идёт речь о замеченной мной закономерности: ошибка чаще всего допускается в последней строке однотипных блоков текс…
Эффект последней строки

Дата: 31 Май 2014

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

Я изучил множество ошибок, возникающих в результате копирования кода. И утверждаю, что чаще всего ошибки допускают в последнем фрагменте однотипного кода. Ранее я не встречал в книгах описания этого …

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

Следующие комментарии

На сайте установлена reCAPTCHA и применяются
Политика конфиденциальности и Условия использования Google.
Этот сайт использует куки и другие технологии, чтобы предоставить вам более персонализированный опыт. Продолжая просмотр страниц нашего веб-сайта, вы принимаете условия использования этих файлов. Если вы не хотите, чтобы ваши данные обрабатывались, пожалуйста, покиньте данный сайт. Подробнее →
Принять