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

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

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

Стек фиксированного размера легко реализовать, и он приемлем для 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;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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