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

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

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

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

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

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

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


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

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

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

24 Июн 2015

В прошлой заметке я рассказывал о проблемах с рекурсией в функции Фибоначчи при использовании 64-битных переменных в качестве ее аргументов и компиляции кода с помощью Microsoft Visual C++. Выяснилось, что компилятор включает хвостовую рекурсию, когда используются 32-битные переменные, но не делает этого при переходе к 64-битным. На всякий случай напомню, что хвостовая рекурсия – это оптимизация, производимая компилятором, при которой некоторые виды хвостовых вызовов преобразуются в безусловные переходы.

Я решил, что проблема кроется в самом компиляторе Visual C++ и объясняется, видимо, наличием в нем бага.

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

Результаты меня не порадовали, и, следуя советам некоторых читателей (в комментариях в этом блоге и на сайтах Reddit и StackOverflow), я решил разобраться в проблеме и посмотреть, как ведут себя другие компиляторы.

Возьмем тот же проект Visual Studio, который был использован в прошлой заметке и который я выложил на GitHub. Это была функция Фибоначчи:

typedef  unsigned long long ULONG64;
ULONG64 fib_tail_x64(ULONG64 n, ULONG64 res, ULONG64 next)
{
  if (n == 0) {
    return res;
  }
  return fib_tail_x64(n - 1, next, res + next);
}

Как вы, должно быть, помните, при компиляции этого кода в релиз-режиме (который обычно нужен для получения хвостовой рекурсии за счет команды оптимизации /Ox) для платформы Win32 хвостовая рекурсия не срабатывала:

0333_TailRecursion_Part2_ru/image1.png

Хвостовая рекурсия не работает! Ассемблерный код ужасен из-за включенных указателей фрэйма

Есть, правда, одна вещь, которую я не пытался пробовать (а если уж быть честным, то просто-напросто забыл). Это выбор платформы решения для сборки проекта. В Visual Studio конфигурация Win32, которая соответствует компиляции решения с использованием x86 инструкций процессора, является конфигурацией по умолчанию. В приведенном выше фрагменте ассемблерного кода можно видеть, что используемые регистры – EAX, EBX и т.д. – являются регистрами 32-битного процессора, в соответствии с выбранной конфигурацией.

Если мы переключим конфигурацию на x64, соберем и запустим проект, то получим следующий ассемблерный код:

0333_TailRecursion_Part2_ru/image2.png

Хвостовая рекурсия появилась!!!

Вот так сюрприз! Хвостовая рекурсия сработала при использовании x64-регистров (RAX, RDX и т.д.), а ассемблерный код стал намного короче и чище!

Подводя итог всему вышесказанному по поводу хвостовых вызовов, можно составить следующую наглядную таблицу:

0333_TailRecursion_Part2_ru/image3.png

Получается, что проблема проявляется только тогда, когда мы используем x64-переменные, а в качестве целевой платформы выбираем x86.

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

На этот раз я решил переключиться на другую операционную систему и поработать с Clang, основанном на LLVM и установленном на моем Macbook в составе XCode.

0333_TailRecursion_Part2_ru/image4.png

Терминал – версия clang

Для просмотра сгенерированного ассемблерного кода я использовал удобную утилиту Hopper Disassembler, доступную как для OS X, так и для Linux (но, как я понимаю, она вполне может работать и с отладчиком gdb).

Я в точности повторил тот же самый эксперимент. На следующей картинке показан первый вариант сгенерированного ассемблера:

0333_TailRecursion_Part2_ru/image5.png

Хвостовая рекурсия здесь явно присутствует: инструкция JNE (Jump Not Equal, переход по неравенству) является всего лишь условным переходом, когда флаг ZF ("нулевой" флаг) установлен в 0. Красная стрелка на картинке указывает на адрес, в котором совершается переход, в случае если условие истинно. Внимательный наблюдатель, должно быть, уже заметил, что данный код скомпилирован не для 32-битных процессоров: используемые ассемблерные регистры на самом деле являются 64-битными (RBD, RDI и т.д.).

Однако сейчас наша цель – убедиться, что хвостовая рекурсия будет по-прежнему работать при выборе 32-битной платформы в качестве целевой.

Компилятор можно принудить сгенерировать 32-битный код с помощью ключа -m32. После пересборки решения в 32-битном режиме я получил следующее:

0333_TailRecursion_Part2_ru/image6.png

Хвостовая рекурсия включена!

Ура!!! По типу используемых регистров мы можем заключить, что исполняемый модуль собран именно под указанную нами архитектуру, и в последней строке можно наблюдать неожиданный результат: хвостовая рекурсия сработала в 32-битном режиме!!!!!

ПРАВКА 1

Как я понял, у многих пользователей не получилось воспроизвести проблему (см. комментарии ниже, а также на Reddit). Я продолжил экспериментировать с настройками оптимизации компилятора, подстраивая кое-какие параметры. В релиз-режиме конфигурация настроек оптимизации по умолчанию является следующей:

0333_TailRecursion_Part2_ru/image7.png

Настройки оптимизации по умолчанию

После нескольких попыток я изменил параметр 'Whole Program Optimization' с /GL (включено) на No (выключено). Также я изменил параметр 'Omit Frame Pointers', т.к. мне подсказали, что с включенными указателями фрейма сгенерированный ассемблерный код под x86 получается намного длиннее и некрасивее (кроме того, мы, возможно, сэкономили несколько тактов, избежав промахов по кэшу). На StackOverflow есть развернутое объяснение, как отключить указатели фрэйма.

Как бы там ни было, когда я перекомпилировал решение под Win32 с учетом всех описанных выше изменений, то получил неожиданный результат:

0333_TailRecursion_Part2_ru/image8.png

Хвостовая рекурсия под x86 – срабатывает при выключении 'Whole Program Optimization'

ПРАВКА 2

Несколько человек написали, что, независимо от настройки параметра WPO (Whole Program Optimization), они не испытывали каких-либо проблем с хвостовой рекурсией. Это поначалу озадачило меня, но потом я понял, что не учел одну важную деталь – а именно, способ вызова функции Фибоначчи из main. До сих пор вызов функции в моем коде для проверки функции Фибоначчи в x64-режиме выглядел следующим образом:

ULONG64 res = fib_tail_x64(40, 0, 1);

Пока все хорошо, ничего особенного в этом коде нет – я просто передаю литералы в качестве аргументов функции.

А что если мы вместо них будем передавать переменные или указатели на функцию? Давайте попробуем:

ULONG64 a = 40;
ULONG64 res = fib_tail_x64(a, 0, 1);

Хотя код вроде бы не сильно изменился, вызов функции fib_tail_x64 с использованием переменных включает хвостовую рекурсию независимо от WPO (при условии, что мы используем ключ оптимизации >= /O2). Один читатель на Reddit указал, что непрямой вызов функции через указатели (независимо от применения литералов) даст точно такой же результат:

volatile bool a = true;
ULONG64 res = 0;
ULONG64(*ptr)(ULONG64 n, ULONG64 res, ULONG64 next) = NULL;
if (a)
{
  ptr = &fib_tail_x64;
}
res = ptr(40, 0, 1);

Окончательные выводы

Хотя изначально я грешил на наличие в компиляторе Visual C++ бага, который был виновником отключения хвостовой рекурсии, в конце концов, выяснилось, что это не так. Ассемблерные коды, сгенерированные компиляторами VC++ и Clang для x86 платформ очень похожи между собой. В качестве первого заключения я решил, что нужно обязательно выключать параметр 'Whole Program Optimization' тогда, и только тогда, когда происходит прямой вызов рекурсивной x64 функции, в качестве аргументов которой передаются литералы.

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

Буду рад услышать какие-либо соображения от кого-нибудь из команды, работающей над компилятором Visual C++, по поводу причин данной "проблемы".

До скорых встреч!

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

Популярные статьи по теме
Как PVS-Studio оказался внимательнее, чем три с половиной программиста

Дата: 22 Окт 2018

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

PVS-Studio, как и другие статические анализаторы кода, часто выдаёт ложные срабатывания. Но не стоит спешить считать странные срабатывания ложными. Это короткая история о том, как PVS-Studio вновь ок…
Характеристики анализатора PVS-Studio на примере EFL Core Libraries, 10-15% ложных срабатываний

Дата: 31 Июл 2017

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

После большой статьи про проверку операционной системы Tizen мне было задано много вопросов о проценте ложных срабатываний и о плотности ошибок (сколько ошибок PVS-Studio выявляет на 1000 строк кода)…
Эффект последней строки

Дата: 31 Май 2014

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

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

Дата: 21 Ноя 2018

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

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

Дата: 19 Май 2017

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

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

Дата: 22 Дек 2018

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

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

Дата: 27 Июн 2017

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

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

Дата: 16 Окт 2017

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

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

Дата: 14 Апр 2016

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

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

Дата: 20 Мар 2017

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

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

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

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