Почему переполнение стека остается проблемой? - PullRequest
43 голосов
/ 10 июля 2010

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

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

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

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

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

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

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

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

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

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

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

Ответы [ 11 ]

21 голосов
/ 10 июля 2010

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

20 голосов
/ 10 июля 2010

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

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

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

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

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

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

10 голосов
/ 10 июля 2010

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

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

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

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

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

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

5 голосов
/ 10 июля 2010

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

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

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

4 голосов
/ 14 июля 2010

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

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

Мотивация

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

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

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

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

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

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

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

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

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

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

3 голосов
/ 10 июля 2010

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

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

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

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

Вот пример с 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;
}

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

2 голосов
/ 14 июля 2010

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

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

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

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

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

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

1 голос
/ 10 июля 2010

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

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

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

0 голосов

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

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

0 голосов
/ 10 июля 2010

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

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

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

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

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

...