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

Question

Я возился с хвостово-рекурсивными функциями в C ++, и я столкнулся с небольшим затруднением с компилятором g ++.

Следующий код приводит к переполнению стека, когда numbers[] имеет размер более пары сотен целых.Изучение кода сборки, сгенерированного g ++, для следующего показывает, что twoSum_Helper выполняет рекурсивную инструкцию call для себя.

Вопрос в том, что из следующего вызывает это?

• Ошибка в следующем, что я пропускаю, которая предотвращает хвостовую рекурсию.
• Ошибка с моим использованием g ++.
• Ошибка в обнаружении хвостовых рекурсивных функций в компиляторе g ++.

Я компилирую с g++ -O3 -Wall -fno-stack-protector test.c в Windows Vista x64 через MinGW с g ++ 4.5.0.

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;
}

// 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)
        return twoSum_Helper(numbers, size, target, i + 1, i + 2);
    else
        return twoSum_Helper(numbers, size, target, i, j + 1);
}

Answer 1

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

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

Answer 2

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

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

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

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

Answer 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 и C ++. Нет рекурсии хвоста.

Answer 4

Поддержка Tail Call Optimization (TCO) ограничена в C / C ++.

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

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

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

Здесь TCO путается, возвращая структуру по значению.Это можно исправить, если результат всех рекурсивных вызовов будет записан на один и тот же адрес памяти, выделенный в другой функции twoSum (аналогично ответу https://stackoverflow.com/a/30090390/4023446 на Хвост-рекурсия не происходит )

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).

Answer 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: удален ненужный параметр согласно комментарию от asker

// 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);
}

Answer 6

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

Answer 7

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

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

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

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

Answer 8

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

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

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