metrica
Мы используем куки, чтобы пользоваться сайтом было удобно.
Хорошо
to the top
close form

Заполните форму в два простых шага ниже:

Ваши контактные данные:

Шаг 1
Поздравляем! У вас есть промокод!

Тип желаемой лицензии:

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

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

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

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

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

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


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

Вебинар: Трудности при интеграции SAST, как с ними справляться - 04.04

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

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

24 Июн 2015

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

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

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

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

Возьмем тот же проект 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 получается намного длиннее и некрасивее (кроме того, мы, возможно, сэкономили несколько тактов, избежав промахов по кэшу). На Stack Overflow есть развернутое объяснение, как отключить указатели фрэйма.

Как бы там ни было, когда я перекомпилировал решение под 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. Перепечатка и перевод сделаны с разрешения автора.

Популярные статьи по теме


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

Следующие комментарии next comments
close comment form