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

Question

Этот вопрос загадывает меня годами, и, учитывая название этого сайта, это то место, которое нужно задать.

Почему мы, программисты, до сих пор Stackru проблема?

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

Я буду говорить в контексте C#/Java, потому что я использую их чаще всего, но это, вероятно, более широкая проблема.

Фиксированный размер стека приводит к огромным проблемам:

• Невозможно написать рекурсивный алгоритм, если вы не уверены, что глубина рекурсии мала. Линейная сложность памяти рекурсивного алгоритма часто недопустима.
• Не существует дешевого способа начать новые темы. Вы должны выделить огромный блок памяти для стека, чтобы учесть все возможные варианты использования потока.
• Даже если вы не используете очень глубокую рекурсию, у вас всегда есть риск нехватки места в стеке по той причине, что размер стека является произвольным фиксированным числом. Учитывая, что Stackru обычно неустраним, на мой взгляд, это большая проблема.

Now, if the stack was resized dynamically, all of the problems above would be much alleviated, because stack overflow would only be possible when there is a memory overflow.

But this is not the case yet. Зачем? Are there some fundamental limitations of modern CPUs which would make it impossible/inefficient? If you think about the performance hit that reallocations would impose, it should be acceptable because people use structures like ArrayList all the time without suffering much.

Итак, вопрос в том, что я что-то упускаю, и Stackru не является проблемой, или я что-то упускаю, и есть много языков с динамическим стеком, или есть какая-то серьезная причина, по которой это невозможно / трудно реализовать?

Изменить: Некоторые люди говорили, что производительность будет большой проблемой, но учтите это:

• Мы оставляем скомпилированный код без изменений. Доступ к стеку остается прежним, поэтому производительность в "обычном случае" остается прежней.
• Мы обрабатываем исключение ЦП, которое происходит, когда код пытается получить доступ к нераспределенной памяти и запускает нашу процедуру "перераспределения". Перераспределения не будут частыми, потому что <поместите ваш обычный аргумент ArrayList здесь>. Должен работать на большинстве процессоров защищенного режима без потери производительности. Нет?

Answer 1

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

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

мотивация

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

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

Трудности реализации

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

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

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

Answer 4

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

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

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

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

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

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

Answer 5

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

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

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

Answer 6

Почему у нас, программистов, остается проблема Stackru?

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

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

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

Вот грубый пример C++:

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

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

Answer 7

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

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

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

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

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

Мелкозернистая многопоточность будет очень и очень важной техникой в ​​будущем.

Answer 8

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

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

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

Answer 9

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

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

Answer 10

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

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

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

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

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

Answer 11

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

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

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