Что вы знаете об ограничениях размера стека вызовов в C++?

Question

Что вы знаете об ограничениях размера стека вызовов в C++?

Тип вопроса: C++ Core Вероятность: 25% Категория: C/C++ Разработчик

Ответ

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

Ключевые аспекты:

Типичный размер: По умолчанию в Linux — 8 МБ (можно проверить и изменить командой ulimit -s). В Windows для основного потока — 1 МБ, для создаваемых потоков — по умолчанию тоже 1 МБ, но его можно задать в std::thread.
Причины переполнения (Stack Overflow):
- Глубокая или бесконечная рекурсия.
- Создание больших объектов на стеке (например, std::array<int, 1000000> или char buffer[1024 * 1024]).
- Много вложенных вызовов функций с большим количеством локальных переменных.

Пример проблемного кода:

void recursiveFunction(int depth) {
    int localArray[1000]; // Выделяет 4 КБ на стеке при каждом вызове
    // ... какая-то работа
    if (depth > 0) {
        recursiveFunction(depth - 1); // При depth > 2000 почти гарантированно переполнит стек
    }
}

Стратегии предотвращения и решения:

Избегать глубокой рекурсии. Переписывать рекурсивные алгоритмы на итеративные, если глубина может быть большой.
Выделять большие данные в куче. Использовать std::vector, std::make_unique или new.
Явно увеличивать размер стека потока. Например, в POSIX с помощью pthread_attr_setstacksize, а в C++11 — передавая нужный размер в конструктор std::thread.
Использовать -fstack-usage (GCC/Clang) для анализа использования стека функциями.

Практический пример замены рекурсии на итерацию:

// Рекурсивный обход (опасен при большой глубине)
void traverseTreeRecursive(TreeNode* node) {
    if (!node) return;
    process(node);
    traverseTreeRecursive(node->left);
    traverseTreeRecursive(node->right);
}

// Итеративный обход с использованием стека в куче (std::stack)
void traverseTreeIterative(TreeNode* root) {
    std::stack<TreeNode*> nodeStack;
    nodeStack.push(root);
    while (!nodeStack.empty()) {
        TreeNode* current = nodeStack.top();
        nodeStack.pop();
        if (current) {
            process(current);
            nodeStack.push(current->right); // Сначала кладем правый
            nodeStack.push(current->left);  // Затем левый
        }
    }
}

Ответ 18+ 🔞

А, стек вызовов! Ну это ж классика, ёпта. Представь себе, что у каждого потока в программе есть своя личная полочка в памяти, такая узенькая и короткая. На неё складываются все локальные переменные, аргументы функций и адреса, куда возвращаться после вызова. И размер этой полки — овердохуища маленький, его специально ограничивают.

Что важно запомнить, чтобы не обосраться:

Сколько места есть: В линуксе по умолчанию — 8 мегабайт. Проверить можно командой ulimit -s. В винде у основного потока — 1 МБ, у остальных тоже обычно 1 МБ, но в std::thread можно свой размер впендюрить.
Почему всё летит в пизду (Stack Overflow):
- Рекурсия, которая ушла в бесконечность или просто слишком глубокая. Классика жанра.
- Создание здоровенных объектов прямо на стеке. Ну вот взял и объявил char buff[10 * 1024 * 1024] — а через секунду программа накрылась медным тазом.
- Функции, которые вызывают функции, которые вызывают ещё функции... И в каждой по куче локальных переменных. В итоге — хитрая жопа.

Вот смотри, как можно всё запороть:

void recursiveFunction(int depth) {
    int localArray[1000]; // Каждый вызов — 4 килобайта на стек! Ёб твою мать!
    // ... что-то делаем
    if (depth > 0) {
        recursiveFunction(depth - 1); // Вызови это с depth > 2000 — и будет тебе хиросима, чувак.
    }
}

Как не словить волнение ебать и всё починить:

Забей на глубокую рекурсию. Переписывай алгоритмы так, чтобы они работали в цикле. Рекурсия — это красиво, но стек не резиновый.
Большие данные — только в кучу! Не выёбывайся, используй std::vector, std::make_unique или, на худой конец, new. Стек для мелочёвки.
Можно увеличить размер стека потока вручную. В POSIX есть pthread_attr_setstacksize, в плюсах — передай размер в конструктор std::thread. Но это костыль, а не решение.
Включи анализ использования стека. Флаг -fstack-usage у GCC/Clang покажет, какая функция сколько жрёт. Очень полезная штука, чтобы не гадать на кофейной гуще.

Смотри, как можно переписать рекурсивный пиздец на что-то адекватное:

// Рекурсивный обход дерева (красиво, но опасно)
void traverseTreeRecursive(TreeNode* node) {
    if (!node) return;
    process(node);
    traverseTreeRecursive(node->left);
    traverseTreeRecursive(node->right);
}

// Итеративный обход. Используем стек, но он в куче, а не тот системный!
void traverseTreeIterative(TreeNode* root) {
    std::stack<TreeNode*> nodeStack;
    nodeStack.push(root);
    while (!nodeStack.empty()) {
        TreeNode* current = nodeStack.top();
        nodeStack.pop();
        if (current) {
            process(current);
            nodeStack.push(current->right); // Сначала правую ветку
            nodeStack.push(current->left);  // Потом левую
        }
    }
}

Вот и вся магия. Главное — понимать, что стек это не помойка, куда можно скидывать что попало. Доверия к нему — ноль, если не следишь за размерами.