Почему проблемы с переполнением стека остаются проблемой?

Ответ 1

Я собираюсь обобщить аргументы в ответах до сих пор, потому что я не нахожу ответа на этот вопрос достаточно хорошо.

Исследование статического стека

Мотивация

Не всем это нужно.

• Большинство алгоритмов не используют глубокую рекурсию или множество потоков, поэтому многим людям не нужны динамические стеки.
• Динамический стек сделает переполнение стека с бесконечной рекурсией, что является легкой ошибкой сделать, сложнее диагностировать. (переполнение памяти, будучи столь же опасным, как переполнение стека для текущего процесса, также опасно для других процессов).
• Каждый рекурсивный алгоритм может быть эмулирован с аналогичным итерационным.

трудности с выполнением

Динамическая реализация стека оказывается не такой простой, как кажется.

• Только одно изменение размера стека недостаточно, если у вас нет неограниченного адресного пространства. Иногда вам также потребуется переместить стек.
• Перемещение стека потребует обновлений для всех указателей на структуры данных, выделенные в стеке. Хотя для данных в памяти просто (по крайней мере, в управляемых языках) просто, нет простого способа сделать то же самое для данных в регистрах процессора потока.
• Некоторые процессоры (в частности, микроконтроллеры) реализуют стек непосредственно на аппаратном обеспечении, отдельно от основной памяти.

Существующие реализации

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

• Некоторые библиотеки времени выполнения (которые?) не предварительно фиксируют весь блок памяти, выделенный для стека. Это может облегчить проблему, особенно для 64-битных систем, но не полностью устранить ее.
• Ира Бакстер рассказал нам о PARLANSE, язык, специально предназначенный для работы со сложными структурами данных с высокой степенью parallelism. Он использует небольшие кучи "зерен" работы вместо стека.
• fuzzy lolipop сказал нам, что "Правильно написанный Erlang не имеет stackoverflows! "
• Говорят, что язык программирования Google Go имеет динамический стек. (ссылка будет приятной)

Я хотел бы увидеть больше примеров здесь.

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

Ответ 2

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

Ответ 3

1) Чтобы изменить размер стеков, вы должны иметь возможность перемещать память, что означает, что указатели на что-либо в стеке могут стать недействительными после изменения размера стека. Да, вы можете использовать другой уровень косвенности для решения этой проблемы, но помните, что в стеке часто используется очень, очень.

2) Это значительно усложняет ситуацию. Операции push/pop на стеках обычно работают просто, выполняя некоторую арифметику указателя в регистре CPU. Вот почему распределение в стеке быстрее, чем распределение в свободном хранилище.

3) Некоторые процессоры (в частности, микроконтроллеры) реализуют стек непосредственно на аппаратном обеспечении, отдельно от основной памяти.

Кроме того, вы можете установить размер стека потока при создании нового потока с помощью beginthread(), так что если вы что лишнее пространство стека не нужно, вы можете соответственно установить размер стека.

Из моего опыта переполнение стека обычно вызвано бесконечными рекурсиями или рекурсивными функциями, которые выделяют массивы огромные в стеке. Согласно MSDN, размер стека по умолчанию, заданный компоновщиком, равен 1 МБ (заголовок исполняемых файлов может устанавливать свой собственный по умолчанию), который, как представляется, более чем достаточно для большинства случаев.

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

Ответ 4

Я не могу говорить за "основные языки". Многие "второстепенные" языки содержат записи активации с помощью кучи, причем каждый вызов использует кусок кучного пространства вместо линейного куска стека. Это позволяет рекурсии идти так глубоко, как у вас есть адресное пространство для размещения.

Некоторые люди здесь утверждают, что рекурсия настолько глубока, что использование "большого линейного стека" просто отлично. Это неправильно. Я бы согласился, что если вам нужно использовать все адресное пространство, вы делаете какую-то проблему. Однако, когда у вас очень большие структуры диаграммы или дерева, вы хотите разрешить глубокую рекурсию, и вы не хотите догадываться, сколько линейного пространства стека вам нужно в первую очередь, потому что вы ошибетесь.

Если вы решите пойти параллельно, и у вас есть много (от тысячи до миллиона "зерен" [думаю, небольшие потоки]), вы не можете иметь 10 Мб пространства стека, выделенного для каждого потока, потому что вы будете тратить гигабайты ОЗУ. Как вы могли бы получить миллион зерен? Легко: много зерен, которые блокируются друг с другом; когда зерно замораживается в ожидании блокировки, вы не можете избавиться от него, и все же вы все еще хотите запускать другие зерна, чтобы использовать доступные CPU. Это максимизирует объем доступной работы и, таким образом, позволяет эффективно использовать многие физические процессоры.

В параллельном языке программирования PARLANSE используется это очень большое количество моделей параллельных зерен и распределение кучи при вызовах функций. Мы разработали PARLANSE, чтобы обеспечить символический анализ и преобразование очень больших исходных компьютерных программ (скажем, несколько миллионов строк кода). Они производят... гигантские абстрактные синтаксические деревья, гигантские графики управления/потоков данных, гигантские таблицы символов, с десятками миллионов узлов. Много возможностей для параллельных работников.

Выделение кучи позволяет лексически охватить программы PARLANSE даже в границах parallelism, поскольку можно реализовать "стек" как стек кактуса, где вилки встречаются в "стеке" для субзерен, и, следовательно, каждое зерно может см. записи активации (родительские области) своих вызывающих абонентов. Это делает передачу больших структур данных дешевой при рекурсии; вы просто ссылаетесь на них лексически.

Можно подумать, что распределение кучи замедляет работу программы. Оно делает; PARLANSE платит около 5% штрафа в производительности, но получает возможность обрабатывать очень большие структуры параллельно, с таким количеством зерен, сколько может занимать адресное пространство.

Ответ 5

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

Может быть, вы имеете в виду, что стеки нельзя динамически перемещать? Корень этого, вероятно, состоит в том, что стеки тесно связаны с оборудованием. Процессоры имеют регистры и кучи логики, предназначенные для управления потоком стека (esp, ebp, call/return/enter/leave на x86). Если ваш язык скомпилирован (или даже джиттер), вы привязаны к аппаратным механизмом и не можете перемещать стопки.

Это аппаратное "ограничение", вероятно, здесь, чтобы остаться. Повторная установка стека потоков во время выполнения потока кажется далекой от разумного спроса со стороны аппаратной платформы (и добавленная сложность будет плохо мешать всем исполняемым кодом на таком мнимом процессоре, даже скомпилирована). Можно представить полностью виртуализованную среду, где это ограничение не выполняется, но поскольку такой код не может быть перекошен, он будет невыносимо медленным. Не случайно вы могли бы сделать что-то интерактивное с ним.

Ответ 6

Почему у нас, программистов, все еще есть проблема с StackOverflow?

Стек фиксированного размера прост в реализации и приемлем для 99% программ. "переполнение стека" - небольшая проблема, которая несколько редка. Поэтому нет никаких оснований менять вещи. Кроме того, это не проблема языка, она больше связана с дизайном платформы/процессора, поэтому вам придется иметь дело с ней.

Невозможно написать рекурсивный алгоритм, если вы не уверены, что глубина рекурсии крошечная. Сложность рекурсивного алгоритма с линейной памятью часто неприемлема.

Теперь это неверно. В рекурсивном алгоритме вы можете (почти?) Всегда заменять фактический рекурсивный вызов каким-то контейнером-списком, std::vector, стеком, массивом, очередью FIFO и т.д., Который будет действовать как стек. Вычисление будет "вызывать" аргументы из конца контейнера и вызывать новые аргументы в конец или начало контейнера. Обычно единственным ограничением по размеру такого контейнера является общий объем оперативной памяти.

Вот пример С++:

#include <deque>
#include <iostream>

size_t fac(size_t arg){
    std::deque<size_t> v;
    v.push_back(arg);
    while (v.back() > 2)
        v.push_back(v.back() - 1);
    size_t result = 1;
    for (size_t i = 0; i < v.size(); i++)
        result *= v[i];
    return result;
}

int main(int argc, char** argv){
    int arg = 12;
    std::cout << " fac of " << arg << " is " << fac(arg) << std::endl;
    return 0;
}

Менее изящный, чем рекурсия, но не проблема stackoverflow. Технически мы в этом случае "эмулируем" рекурсию. Вы можете думать, что stackoverflow - это аппаратное ограничение, с которым вам приходится иметь дело.

Ответ 7

Я думаю, мы увидим, что это ограничение удалено через несколько лет.

Просто нет фундаментальной технической причины для стеков фиксированного размера. Они существуют по историческим причинам и потому, что программисты компиляторов и виртуальных машин ленивы и не оптимизируются, если они сейчас достаточно хороши.

Но GO google-язык уже начинается с другого подхода. Он выделяет стек небольшими 4K частями. Есть также множество "бесуровневых" расширений языка программирования, таких как безплатный python и т.д., Которые делают то же самое.

Причина этого довольно проста, чем больше потоков у вас, тем больше адресного пространства теряется. Для программ, которые медленнее с 64-битными указателями, это серьезная проблема. На практике у вас не может быть больше тем хундертов. Это плохо, если вы пишете сервер, который может захотеть серверу 60000 клиентов с потоком для каждого из них (дождитесь 100-ядерных систем в ближайшем будущем).

В 64-битных системах это не так серьезно, но для этого все еще требуется больше ресурсов. Например, записи TLB для страниц чрезвычайно серьезны для хорошей производительности. Если вы можете удовлетворить 4000 обычных стеков потоков с одной единственной записью TLB (учитывая размер страницы в 16 МБ и 4 КБ активного пространства стека), вы можете увидеть разницу. Не тратьте 1020KB только на стек, который вы почти никогда не используете.

Малое зернистое многопоточность будет очень важным методом в будущем.

Ответ 8

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

С другой стороны, у меня редко возникали проблемы с удалением барьера из-за рекурсии. Однако я могу придумать пару обстоятельств, где это произошло. Однако переход в мой собственный стек, реализованный как std::vector, был простым решением проблемы.

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

Ответ 9

Почему на каждом главном языке память стека потоков должна быть статически распределена при создании потока?

Размер и распределение стека не обязательно связаны с языком, который вы используете. Это скорее вопрос процессора и архитектуры.

Сегменты стека ограничены 4 ГБ на современных процессорах Intel.

Эта следующая ссылка - хорошее чтение, которое может дать вам некоторые ответы, которые вы ищете.

http://www.intel.com/Assets/PDF/manual/253665.pdf - Глава 6.2

Ответ 10

У старых языков есть статический размер стека, поэтому большинство новых популярных языков (которые только что скопировали старые языки и сломали/исправили все, что они чувствовали) имеют одинаковую проблему.

Нет логической причины иметь размер статического стека, если вы не используете формальные методы. Зачем вводить ошибки, где код правильный? Например, Erlang этого не делает, потому что он обрабатывает ошибки, как и любой нормальный язык частичного программирования.

Ответ 11

Любой код, который вызовет переполнение стека в типичном стеке статической длины, в любом случае ошибочен.

• Вы можете сделать стек std::vector -подобным объектом, но у вас была бы чрезвычайно непредсказуемая производительность, когда он решил изменить размер - и в любом случае он, скорее всего, просто будет продолжать делать это, пока не будет исчерпана вся куча, и это более раздражает.
• Вы можете сделать это как std:: list, где он вырос на O (1). Тем не менее, арифметика указателя, используемая в статическом стеке, настолько критична во всех отношениях, что производительность программы будет бесполезной. Языки были изобретены, чтобы иметь одно возвращаемое значение и произвольное количество входных параметров, потому что это соответствует статичной арифметической парадигме стека/указателя.

Таким образом, динамически изменяемый размер будет A) кошмаром производительности и B) ни в коем случае не будет иметь никакого значения, так как ваш стек не должен был быть таким глубоким.