Проблема с рекурсией хвоста в g++

Ответ 1

Оптимизация звонков в C или С++ крайне ограничена и в значительной степени является потерянной причиной. Причина в том, что в общем случае нет безопасного способа перехвата вызова из функции, которая передает указатель или ссылку на любую локальную переменную (в качестве аргумента для рассматриваемого вызова или фактически любого другого вызова в той же функции) - который, конечно, происходит повсюду на земле C/С++, и почти невозможно без него жить.

Вероятно, проблема связана с GSS: GCC, вероятно, компилирует возвращающую структуру, фактически передавая адрес скрытой переменной, выделенной в стеке вызывающего, в который копия копирует его, - что заставляет его попадать в вышеупомянутый сценарий.

Ответ 2

Попробуйте выполнить компиляцию с -O2 вместо -O3.

Как проверить, выполняет ли gcc оптимизацию хвостовой рекурсии? Забастовкa >

ну, в любом случае, он не работает с O2. Единственное, что работает, это вернуть объект result в ссылку, заданную как параметр.

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

Ответ 3

Я не могу заставить g++ 4.4.0 (под mingw) выполнять хвостовую рекурсию даже в этой простой функции:

static void f (int x)
  {
  if (x == 0) return ;
  printf ("%p\n", &x) ; // or cout in C++, if you prefer
  f (x - 1) ;
  }

Я пробовал варианты -O3, -O2, -fno-stack-protector, C и С++. Нет хвостовой рекурсии.

Ответ 4

Я бы посмотрел на 2 вещи.

• Обратный вызов в операторе if будет иметь цель ветвления для else в кадре стека для текущего запуска функции, которая нуждается в (что означало бы, что любая попытка TCO не сможет перезаписать исполняемый стек стека, что отрицает TCO)

• Аргумент массива numbers [] - это структура данных переменной длины, которая также может препятствовать TCO, поскольку в TCO один и тот же стек кадров используется так или иначе. Если вызов является саморегуляцией (например, ваш), он будет перезаписывать стеки определенные переменные (или локально определенные) со значениями/ссылками нового вызова. Если хвостовой вызов относится к другой функции, то он перезапишет весь кадр стека новой функцией (в случае, когда TCO может быть выполнена в = > B = > C, TCO может сделать это похожим на A = > C в памяти во время исполнения). Я бы попробовал указатель.

Прошло несколько месяцев с тех пор, как я создал что-либо на С++, поэтому я не запускал никаких тестов, но я думаю, что один из них предотвращает оптимизацию.

Ответ 5

Попробуйте изменить свой код на:

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i, int j)
{
    if (numbers[i] + numbers[j] == target)
        return gen_Result(i, j, true);
    if (i >= (size - 1))
        return gen_Result(i, j, false);

    if(j >= size)
        i++; //call by value, changing i here does not matter
    return twoSum_Helper(numbers, size, target, i, i + 1);
}

edit: удалить ненужный параметр в соответствии с комментарием от акима

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i)
{
    if (numbers[i] + numbers[i+1] == target || i >= (size - 1))
        return gen_Result(i, i+1, true);

    if(i+1 >= size)
        i++; //call by value, changing i here does not matter
    return twoSum_Helper(numbers, size, target, i);
}

Ответ 6

Поддержка оптимизации Tail Call (TCO) ограничена в C/С++.

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

Обычно TCO может быть подавлено:

• передача указателей на объекты в стеке рекурсивной функции на внешние функции (в случае, если С++ также передает такой объект по ссылке);
• с нетривиальным деструктором, даже если хвостовая рекурсия действительна (деструктор вызывается перед оператором tail return), например Почему не giff tail call оптимизация в gcc?

Здесь TCO путается, возвращая структуру по значению. Он может быть исправлен, если результат всех рекурсивных вызовов будет записан на тот же адрес памяти, выделенный в другой функции twoSum (аналогично ответу fooobar.com/questions/469005/... на Хвост-рекурсия не происходит)

struct result
{
    int i;
    int j;
    bool found;
};

struct result gen_Result(int i, int j, bool found)
{
    struct result r;
    r.i = i;
    r.j = j;
    r.found = found;
    return r;
}

struct result* twoSum_Helper(int numbers[], int size, int target,
    int i, int j, struct result* res_)
{
    if (i >= (size - 1)) {
        *res_ = gen_Result(i, j, false);
        return res_;
    }
    if (numbers[i] + numbers[j] == target) {
        *res_ = gen_Result(i, j, true);
        return res_;
    }
    if (j >= size)
        return twoSum_Helper(numbers, size, target, i + 1, i + 2, res_);
    else
        return twoSum_Helper(numbers, size, target, i, j + 1, res_);
}

// Return 2 indexes from numbers that sum up to target.
struct result twoSum(int numbers[], int size, int target)
{
    struct result r;
    return *twoSum_Helper(numbers, size, target, 0, 1, &r);
}

Значение указателя res_ является константой для всех рекурсивных вызовов twoSum_Helper. На выходе сборки (флаг -S) можно видеть, что хвостовая рекурсия twoSum_Helper оптимизирована как петля даже с двумя рекурсивными точками выхода.

Параметры компиляции: g++ -O2 -S (версия g++ 4.7.2).

Ответ 7

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

Ответ 8

Так как код twoSum_Helper вызывает себя, не должно удивляться, что сборка показывает именно это. То, что весь смысл рекурсии:-) Так что это не имеет ничего общего с g++.

Каждая рекурсия создает новый стек стека, а пространство стека ограничено по умолчанию. Вы можете увеличить размер стека (не знаете, как это сделать в Windows, в UNIX используется команда ulimit), но это только отменяет сбой.

Реальное решение - избавиться от рекурсии. См. Например этот вопрос и этот вопрос.