[Перевод] Хвостовая рекурсия в C++ с использованием 64-битных переменных — Часть 2
В прошлой заметке я рассказывал о проблемах с рекурсией в функции Фибоначчи при использовании 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 хвостовая рекурсия не срабатывала:
Хвостовая рекурсия не работает! Ассемблерный код ужасен из-за включенных указателей фрэйма
Есть, правда, одна вещь, которую я не пытался пробовать (а если уж быть честным, то просто-напросто забыл). Это выбор платформы решения для сборки проекта. В Visual Studio конфигурация Win32, которая соответствует компиляции решения с использованием x86 инструкций процессора, является конфигурацией по умолчанию. В приведенном выше фрагменте ассемблерного кода можно видеть, что используемые регистры — EAX, EBX и т.д. — являются регистрами 32-битного процессора, в соответствии с выбранной конфигурацией.
Если мы переключим конфигурацию на x64, соберем и запустим проект, то получим следующий ассемблерный код:
Хвостовая рекурсия появилась!!!
Вот так сюрприз! Хвостовая рекурсия сработала при использовании x64-регистров (RAX, RDX и т.д.), а ассемблерный код стал намного короче и чище!
Подводя итог всему вышесказанному по поводу хвостовых вызовов, можно составить следующую наглядную таблицу:
Получается, что проблема проявляется только тогда, когда мы используем x64-переменные, а в качестве целевой платформы выбираем x86.
Честно говоря, на этом этапе я уже не был так уверен в наличии бага в MS-компиляторе, поэтому, по-прежнему недовольный результатами, я решил повторить эксперимент с другим компилятором.
На этот раз я решил переключиться на другую операционную систему и поработать с Clang, основанном на LLVM и установленном на моем Macbook в составе XCode.
Терминал — версия clang
Для просмотра сгенерированного ассемблерного кода я использовал удобную утилиту Hopper Disassembler, доступную как для OS X, так и для Linux (но, как я понимаю, она вполне может работать и с отладчиком gdb).
Я в точности повторил тот же самый эксперимент. На следующей картинке показан первый вариант сгенерированного ассемблера:
Хвостовая рекурсия здесь явно присутствует: инструкция JNE (Jump Not Equal, переход по неравенству) является всего лишь условным переходом, когда флаг ZF («нулевой» флаг) установлен в 0. Красная стрелка на картинке указывает на адрес, в котором совершается переход, в случае если условие истинно. Внимательный наблюдатель, должно быть, уже заметил, что данный код скомпилирован не для 32-битных процессоров: используемые ассемблерные регистры на самом деле являются 64-битными (RBD, RDI и т.д.).
Однако сейчас наша цель — убедиться, что хвостовая рекурсия будет по-прежнему работать при выборе 32-битной платформы в качестве целевой.
Компилятор можно принудить сгенерировать 32-битный код с помощью ключа -m32. После пересборки решения в 32-битном режиме я получил следующее:
Хвостовая рекурсия включена!
Ура!!! По типу используемых регистров мы можем заключить, что исполняемый модуль собран именно под указанную нами архитектуру, и в последней строке можно наблюдать неожиданный результат: хвостовая рекурсия сработала в 32-битном режиме!!!
ПРАВКА 1
Как я понял, у многих пользователей не получилось воспроизвести проблему (см. комментарии ниже, а также на Reddit). Я продолжил экспериментировать с настройками оптимизации компилятора, подстраивая кое-какие параметры. В релиз-режиме конфигурация настроек оптимизации по умолчанию является следующей:
Настройки оптимизации по умолчанию
После нескольких попыток я изменил параметр 'Whole Program Optimization' с /GL (включено) на No (выключено). Также я изменил параметр 'Omit Frame Pointers', т.к. мне подсказали, что с включенными указателями фрейма сгенерированный ассемблерный код под x86 получается намного длиннее и некрасивее (кроме того, мы, возможно, сэкономили несколько тактов, избежав промахов по кэшу). На StackOverflow есть развернутое объяснение, как отключить указатели фрэйма.
Как бы там ни было, когда я перекомпилировал решение под Win32 с учетом всех описанных выше изменений, то получил неожиданный результат:
Хвостовая рекурсия под 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++, по поводу причин данной »проблемы».
На этом все, спасибо за внимание! Чтобы оставаться со мной на связи, пишите на почту через Contact-форму или подписывайтесь на страничку в твиттере!
До скорых встреч!
