Что такое стек и куча
Перейти к содержимому

Что такое стек и куча

  • автор:

Принципы программирования: стек и куча: что это такое?

2stack-20219-1097c5.jpg

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

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

Стек — что это такое?

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

Итак, стек — это метод представления однотипных данных в порядке LIFO (Last In — First Out, то бишь, «первый вошел — последний вышел»). Некоторые ассоциируют стек с оружейным магазином для патронов, так как принцип работы схож, и первый вставленный в магазин патрон будет использоваться в последнюю очередь (у термина стек бывают и другие значения, поэтому, если речь идёт не об информационных технологиях, то смысл лучше уточнить).

Стек и простой жизненный пример

1stack-20219-ef97b7.jpg

Представьте, что на столе в коробке лежит стопка бумажных листов. Чтобы получить доступ к самому нижнему листу, вам нужно достать самый первый лист, потом второй и так далее, пока не доберётесь до последнего. По схожему принципу и устроен стек: чтобы последний элемент стека стал верхним, нужно сначала вытащить все остальные.

Стек и особенности его работы

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

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

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

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

Для чего нужен стек?

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

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

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

Стеки и операции стека

Если говорить об основных операциях, то стек имеет таковых две: 1. Push — ни что иное, как добавление элемента непосредственно в вершину стека. 2. Pop — извлечение из стека верхнего элемента.

Также, используя стек, иногда выполняют чтение верхнего элемента, не выполняя его извлечение. Для этого предназначена операция peek.

Как организуется стек?

Когда программисты организуют или реализуют стек, они применяют два варианта: 1. Используя массив и переменную, указывающую на ячейку вершины стека. 2. Используя связанные списки.

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

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

Стек и куча

Куча — хранилище памяти, расположенное в ОЗУ. Оно допускает динамическое выделение памяти и работает не так, как стек. По сути, речь идёт о простом складе для ваших переменных. Когда вы выделяете здесь участок памяти для хранения, к ней можно обращаться как в потоке, так и во всём приложении в целом (именно так и определяются переменные глобального типа). По завершении работы приложения все выделенные участки освобождаются.

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

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

Итак, теперь вы знаете и что такое стек, и что такое куча. Это довольно простые знания, больше подходящие для новичков. Если же вас интересуют более серьёзные профессиональные навыки, выбирайте нужный вам курс по программированию в OTUS!

Что такое стек и куча

В этой статье (перевод [1, 4]) делается попытка на пальцах объяснить назначение шести (возможно самых важных) концепций .NET: стек (stack), куча (heap), тип значения (value type), тип ссылки (reference type), преобразование-упаковка (boxing), преобразование-распаковка (unboxing). Будет показано, что на самом деле происходит в программе, когда Вы декларируете переменную, как работают стек и куча, когда используются ссылки на объекты, и когда объекты работают как значения, что такое упаковка и распаковка, и как эти операции влияют на скорость работы кода.

[Что происходит при декларации переменной]

Когда Вы декларируете переменную в приложении .NET (C#, C++ или Visual Basic), то она занимает некоторый кусочек оперативной памяти (RAM). С этой памятью связаны 3 понятия: имя переменной, тип данных переменной (от типа зависит размер куска памяти, который занимает переменная) и значение переменной. На рисунке ниже показан случай простого выделения памяти из стека под локальную переменную базового типа.

Dot Net declare local variable

Есть 2 типа выделения памяти для переменной — из памяти стека и из памяти кучи.

[Стек и куча]

Многие не имеют ясного представления, в чем разница между стеком и кучей. Оба этих хранилища находятся в оперативной памяти системы (Random Access Memory, RAM), но программно-аппаратный комплекс (процессор + операционная система + библиотеки .NET) работают с этими областями памяти по-разному.

Чтобы понять смысл стека и кучи, давайте посмотрим, что происходит в следующем примере кода.

public void Method1() < // Строка 1: int i=4;
// Строка 2: int y=2;
//Строка 3: class1 cls1 = new class1(); >

Строка 1 : когда выполняется код в этой строке, компилятор выделяет маленький участок памяти в стеке для хранения переменной i, куда записывается значение 4. Стек отвечает за временное хранение значений локальных переменных функции, что требуется для работы Вашего приложения.

Строка 2 : теперь выполнение переходит к следующему шагу. В точном соответствии с названием термина «стек», здесь память для переменной y выделяется сверху первого выделения памяти, в сторону уменьшения адреса. Можно представить размещение переменных в стеке как последовательность нагроможденных друг на друга коробок. Самая первая выделенная коробка находится внизу (переменная i), на неё ставится еще коробка (переменная y), и так далее.

Примечание: если быть абсолютно точным, то выделение памяти для переменных i и y в строках 1 и 2 происходит в момент вызова процедуры Method1.

Выделение памяти в стеке и соответствующее освобождение этой памяти в стеке происходит по принципу LIFO (Last In First Out), «последним пришел первым вышел». Т. е. операции выделения и освобождения происходят только в строго определенном месте памяти, которая называется «вершина стека».

Строка 3 : здесь мы создаем объект. Когда эта строка выполняется, то в стеке создается указатель на реальный объект, который сохранен в другом типе памяти, которая называется «кучей». Куча это просто хранилище для нагромождения различных объектов, к которым может произойти обращение в любой момент времени. Куча использует динамическое выделение и освобождение памяти (этим занимается специальный менеджер памяти и сборщик мусора).

Важный момент — в строке 3 задействовано два выделения памяти — одно в стеке для сохранения указателя cls1, и второе в куче, где реально сохраняются данные объекта. Оператор Class1 cls1 не выделяет память для экземпляра класса Class1, он только лишь выделяет в стеке место под переменную указателя cls1 (и неявно присваивает ей значение null). Когда выполнение достигает до ключевого слова new, тогда память выделяется из кучи, инициализируется экземпляр объекта Class1, и его адрес в куче присваивается указателю cls1.

При выходе из процедуры Metod1 происходит следующее: все переменные, размещенные в стеке (i, y, cls1), автоматически уничтожаются. Освобождение происходит в обратном порядке, по принципу LIFO, однако это происходит очень быстро, за одну инструкцию ассемблера, путем простого изменения значения вершины стека.

Еще один важный момент — здесь не освобождается память в куче. В случае программы C++ это ошибка, произойдет утечка памяти. Для программы на Java или C# ошибки тут нет, освобождение памяти кучи произойдет автоматически с помощью сборщика мусора, без вмешательства программиста — в фоновом процессе, когда у операционной системы появятся для этого ресурсы процессора.

Dot Net stack heap objects

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

Причина в том, что типы объектов бывают разной сложности, и в зависимости от сложности объекта удобны различные способы манипуляции над данными. Самые простые это типы наподобие int, они занимают область памяти из 4 байт. Такие данные при присваивании можно просто копировать, это происходит быстро, без лишних накладных расходов (одной инструкцией ассемблера). Данные объектных типов могут быть очень сложными, они могут ссылаться на другие объекты или другие примитивные типы данных. Прямое присваивание таких объектов методом копирования может занимать слишком много времени, поэтому здесь применяются ссылки. Другими словами, переменные объекта содержат ссылки на многие другие значения, каждое из которых должно быть сохранено где-то в памяти. Таким образом, объектные типы нуждаются в динамической памяти (это куча), в то время как простые типы требуют использования статической памяти (стек).

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

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

Да, объект может быть сохранен в стеке. Если Вы создаете объект внутри функции без оператора «new», то это создаст и сохранит объект в стеке, а не в куче. Предположим, что у нас есть C++ класс Member, для которого мы хотим создать объект. Также у нас есть функция somefunction( ). Вот так может выглядеть код, когда объект создается в стеке:

void somefunction() < /* Создание объекта "m" класса Member поместит его в стек,
 потому что здесь не используется ключевое слово "new",
 и объект создается внутри функции. */ Member m; > // Объект "m" уничтожается при завершении функции. 

Итак, объект «m» немедленно уничтожается, когда функция доходит до точки своего завершения, или, другими словами, когда управление исполнением операторов в коде выходит из области действия переменной m («out of scope»). Никаких специальных действий по освобождению памяти не требуется.

Если мы хотим внутри функции создать объект в куче, то код будет выглядеть следующим образом:

void somefunction() < /* Создание объекта "m" как экземпляра класса Member произведет выделение
 для него памяти в куче, потому что здесь мы использовали ключевое слово
 "new", и создали экземпляр объекта внутри функции. */ Member* m = new Member(); /* Обратите внимание, что сама переменная m здесь является указателем,
 и память для этого указателя выделяется не в куче, а в стеке.
 Таким образом, в этом примере для создания объекта задействовано
 два вида памяти - стек (для хранения указателя как локальной
 переменной функции) и куча (для хранения реальных данных экземпляра
 объекта).
 /* Данные объекта "m" должны быть явно удалены, иначе произойдет утечка
 памяти. Память, выделенную в стеке под указатель m, освобождать не нужно. */ delete m; >

В этом примере кода можно увидеть, что объект «m» был создан с помощью ключевого слова «new». Это означает, что данные для объекта «m» будут созданы в куче.

Примечание: это пример кода C++, в нем всегда важно парно вызывать операторы new и delete. Управляемый код C# свободен от такого «недостатка» — объекты, выделенные оператором new, освобождаются автоматически сборщиком мусора, когда в них отпадает надобность.

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

Любые данные, выделенные в куче оператором new (либо функциями динамического выделения памяти), нуждаются в явном освобождении кодом, написанным программистом (это касается только языка программирования C++, объекты языка C# уничтожаются автоматически сборщиком мусора).

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

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

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

Конечно, стек намного быстрее кучи. Причина в том, каким образом выделяется стек — простым назначением указателя стека (единственная команда ассемблера). В отличие от стека куча обслуживается программно, с помощью специальных вызовов API операционной системы или библиотек. Кроме того, при интенсивном использовании кучи некоторые языки, использующие автоматический сбор мусора (например, Java, C# .NET), могут вводить не прогнозируемые дополнительные задержки при выполнении кода в реальном времени.

Данные переменной в стеке автоматически освобождаются, когда переменная теряет область своего действия (go out of scope). Однако на языках наподобие C и C++ данные, сохраненные в куче, нуждаются в явном ручном удалении программистом (с помощью ключевых слов наподобие free, delete или delete[]).

Другие языки, наподобие Java и C# .NET используют специальный автоматически работающий сборщик мусора, который сам заботится об удалении ненужных объектов из кучи (программисту для этого ничего делать не нужно). Это большое удобство, за которое приходится расплачиваться замедлением работы кода в некоторых особо не благоприятных случаях.

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

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

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

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

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

[Типы-значения и типы-ссылки]

Когда мы разобрались с общей концепцией стека и кучи, настало время понять концепцию типов значений и ссылочных типов. Типы значений это такие типы переменной, которые хранят данные о себе только в одном месте. Ссылочный тип состоит как минимум из указателя на объект, когда он равен null, и также из динамического хранилища, на которое ссылается этот указатель. Таким образом, рабочий ссылочный тип использует 2 области памяти — место для хранения указателя (это стек) и место, где непосредственно содержатся данные объекта (это куча), на который ссылается указатель.

Ниже показана переменная целочисленного типа данных с именем i, значение которого присваивается другой переменной с именем j. Обе этих переменных типа значения, и они обе выделяются в стеке.

Dot Net assign value data types

Когда мы присваиваем значение типа int другому значению типа int, то это создает отдельную копию данных одной переменной в месте размещения другой переменной (данные переменных физически копируются). Другими словами, если Вы поменяете одну из этих двух переменных, то в другой переменной значение не поменяется. Данные такого вида называются «типами значений».

Примечание: к типам значений на C# также относятся структуры.

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

Другими словами, если мы поменяем данные одного из объектов (например obj), то это немедленно отразится на значениях другого объекта (obj1). Такое поведение обозначается термином «ссылочные типы» (ref).

Dot Net assign reference data types

Каким объектам относятся ссылочные типы, и к каким типы значений? .NET в зависимости от типа данных назначает место для хранения переменной либо в стеке, либо в куче. Объекты строк (String) и почти все другие более-менее сложные библиотечные объекты имеют ссылочный тип (реальные данные хранятся в куче, ссылки на них в стеке), и под любые другие примитивные типы данных используется стек (это типы значений). На рисунке ниже то же самое объясняется подробнее.

Dot Net types tree

[Boxing и unboxing]

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

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

Такие перемещения данных негативно сказываются на производительности кода программы.

При перемещении данных из типов значения в ссылочные типы (т. е. стек -> куча) такое действие обозначается термином «Boxing» (преобразование-упаковка), и соответственно обратное действие (из ссылочных типов в тип значения, куча -> стек) обозначается «UnBoxing» (преобразование-распаковка).

Dot Net boxing unboxing

Если Вы скомпилируете этот код и просмотрите результат в ILDASM, то можете увидеть в коде IL словечки box и unbox.

Dot Net boxing unboxing IL code

Чтобы понять, насколько ухудшается скорость работы, мы запустили две показанные ниже функции 10000 раз. В функции слева используется boxing, и в функции справа используется простое присваивание значения.

Boxing-функция выполнилась за 3542 мс, в то время как функция без boxing выполнилась за 2477 мс. Вывод: старайтесь избегать операций boxing и unboxing, используйте их в проекте только тогда, когда абсолютно необходимо, особенно это касается долго работающих, многочисленных повторений циклов.

Dot Net boxing performance impact

Демонстрационный код этого примера можно скачать по ссылке [2].

[Ссылки]

1. Six important .NET concepts: Stack, heap, value types, reference types, boxing, and unboxing site:codeproject.com.
2. source_code.zip — исходный код примеров из статьи.
3. Интересные моменты в C# (boxing unboxing) site:habrahabr.ru.
4. What’s the difference between a stack and a heap? site:programmerinterview.com.

Комментарии

+2 #2 Григорий 13.04.2022 20:19

Отличная статья, но по boxing/unboxing хочу добавить замечание. Когда происходит boxing, у нас КОПИРУЕТСЯ значение в новую переменную типа object со сылкой на heap, а сама изначально созданная переменная примитивного типо никак не меняется, как была 1 так и останется 1 после unboxing в новую переменную. А у Вас на картинке, i = 4, что неверно, должно быть 1.

11.8 – Стек и куча

Память, которую использует программа, обычно делится на несколько разных областей, называемых сегментами:

  • Сегмент кода (также называемый текстовым сегментом), в котором скомпилированная программа находится в памяти. Сегмент кода обычно доступен только для чтения.
  • Сегмент bss («block started by symbol», также называемый сегментом неинициализированных данных), где хранятся глобальные и статические переменные с нулевой инициализацией.
  • Сегмент данных (также называемый сегментом инициализированных данных), где хранятся инициализированные глобальные и статические переменные.
  • Куча, где размещаются динамически размещаемые переменные.
  • Стек вызовов, в котором хранятся параметры функций, локальные переменные и другая информация, относящаяся к функциям.

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

Сегмент кучи

Сегмент кучи (также известный как «free store», «свободное хранилище») отслеживает память, используемую для динамического распределения памяти. Мы уже говорили немного о куче в уроке «10.13 – Динамическое распределение памяти с помощью new и delete », поэтому это будет резюме.

В C++, когда вы используете оператор new для выделения памяти, эта память выделяется в сегменте кучи приложения.

int *ptr = new int; // ptr присваивается 4 байта в куче int *array = new int[10]; // array присвоено 40 байт в куче

Адрес этой памяти возвращается оператором new и затем может быть сохранен в указателе. Вам не нужно беспокоиться о механизме того, где расположена свободная память, и как она выделяется пользователю. Однако стоит знать, что последовательные запросы памяти могут не привести к выделению последовательных адресов памяти!

int *ptr1 = new int; int *ptr2 = new int; // ptr1 и ptr2 могут не содержать соседних адресов

Когда динамически размещаемая переменная удаляется, память «возвращается» в кучу и затем может быть переназначена по мере получения будущих запросов на выделение. Помните, что удаление указателя не удаляет переменную, а просто возвращает память по соответствующему адресу обратно операционной системе.

У кучи есть достоинства и недостатки:

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

Стек вызовов

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

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

Структура данных стек

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

Представьте себе стопку тарелок в кафетерии. Поскольку каждая тарелка тяжелая и они сложены друг на друга, вы можете сделать только одно из трех:

  1. посмотреть на поверхность верхней тарелки;
  2. снять верхнюю тарелку со стопки (открывая нижнюю, если она есть);
  3. поместить новую тарелку на верх стопки (скрывая нижнюю, если она есть).

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

  1. посмотреть верхний элемент в стеке (обычно это делается с помощью функции top() , но иногда называется peek() );
  2. снять верхний элемент из стека (выполняется с помощью функции pop() );
  3. поместить новый элемент на верх стека (выполняется с помощью функции push() ).

Стек – это структура типа «последним пришел – первым ушел» (LIFO, «last-in, first-out»). Последний элемент, помещенный в стек, будет первым извлеченным элементом. Если вы положите новую тарелку поверх стопки, первая тарелка, удаленная из стопки, будет тарелкой, которую вы только что положили последней. Последней положена, первой снята. По мере того, как элементы помещаются в стек, стек становится больше – по мере того, как элементы извлекаются, стек становится меньше.

Например, вот короткая последовательность, показывающая, как работает стек при вставке (push) и извлечении (pop) данных:

Стек: пустой Вставка 1 Стек: 1 Вставка 2 Стек: 1 2 Вставка 3 Стек: 1 2 3 Извлечение Стек: 1 2 Извлечение Стек: 1

Аналогия с тарелками – довольно хорошая аналогия того, как работает стек вызовов, но мы можем провести лучшую аналогию. Представьте себе группу почтовых ящиков, сложенных друг на друга. Каждый почтовый ящик может содержать только один элемент, и все почтовые ящики изначально пустые. Кроме того, каждый почтовый ящик прибивается к почтовому ящику под ним, поэтому количество почтовых ящиков не может быть изменено. Если мы не можем изменить количество почтовых ящиков, как мы можем добиться поведения, подобного стеку?

Во-первых, мы используем маркер (например, наклейку), чтобы отслеживать, где находится самый нижний пустой почтовый ящик. Вначале это будет самый нижний почтовый ящик (внизу стопки). Когда мы помещаем элемент в наш стек почтовых ящиков, мы помещаем его в отмеченный почтовый ящик (который является первым пустым почтовым ящиком) и перемещаем маркер на один ящик вверх. Когда мы извлекаем элемент из стека, мы перемещаем маркер на один почтовый ящик вниз так, чтобы он указывал на верхний непустой почтовый ящик, и удаляем элемент из этого почтового ящика. Всё, что ниже маркера, считается «в стеке». Всё, что находится на уровне маркера или над ним, – не в стеке.

Сегмент стека вызовов

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

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

Приведенная выше аналогия с почтовыми ящиками в значительной степени похожа на то, как работает стек вызовов. Сам стек представляет собой блок адресов памяти фиксированного размера. Почтовые ящики – это адреса памяти, а «элементы», которые мы помещаем в стек, называются кадрами (фреймами) стека. Кадр стека отслеживает все данные, связанные с одним вызовом функции. Мы поговорим о стековых кадрах чуть позже. «Маркер» – это регистр (небольшой фрагмент памяти в CPU), известный как указатель стека (иногда сокращенно «SP», «stack pointer»). Указатель стека отслеживает текущее положение вершины стека вызовов.

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

Стек вызовов в действии

Давайте подробнее рассмотрим, как работает стек вызовов. Вот последовательность шагов, которые выполняются при вызове функции:

  1. Программа обнаруживает вызов функции.
  2. Кадр стека создается и помещается в стек. Кадр стека состоит из:
    • Адрес инструкции, следующей после вызова функции (называемый адресом возврата). Таким образом, CPU запоминает, куда вернуться после выхода из вызываемой функции.
    • Все аргументы функции.
    • Память для любых локальных переменных.
    • Сохраненные копии любых регистров, измененных функцией, которые необходимо восстановить после возврата из функции.
  3. CPU переходит к начальной точке функции.
  4. Инструкции внутри функции начинают выполняться.

Когда функция завершается, происходят следующие шаги:

  1. Регистры восстанавливаются из стека вызовов
  2. Кадр стека извлекается из стека. Это освобождает память для всех локальных переменных и аргументов.
  3. Обрабатывается возвращаемое значение.
  4. CPU возобновляет выполнение по адресу возврата.

Возвращаемые значения могут обрабатываться разными способами в зависимости от архитектуры компьютера. Некоторые архитектуры включают возвращаемое значение как часть кадра стека. Другие используют регистры CPU.

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

Техническое примечание: на некоторых архитектурах стек вызовов при увеличении изменяет адрес памяти в направлении от нуля. На других он при увеличении изменяет адрес в направлении нуля. Как следствие, новые добавленные кадры стека могут иметь более высокий или более низкий адрес памяти, чем предыдущие.

Пример стека вызовов

Рассмотрим следующее простое приложение:

int foo(int x) < // b return x; >// здесь foo извлекается из стека вызовов int main() < // a foo(5); // здесь foo помещается в стек вызовов // c return 0; >

Стек вызовов в отмеченных точках выглядит следующим образом:

main()
foo() (включая параметр x) main()
main()

Переполнение стека

Стек имеет ограниченный размер и, следовательно, может содержать только ограниченный объем информации. В Windows размер стека по умолчанию составляет 1 МБ. На некоторых Unix-машинах он может достигать 8 МБ. Если программа попытается поместить в стек слишком много информации, произойдет переполнение стека. Переполнение стека происходит, когда вся память в стеке была выделена – в этом случае дальнейшие размещения начинают переполняться в другие разделы памяти.

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

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

#include int main()

Эта программа пытается разместить в стеке огромный массив (примерно 40 МБ). Поскольку стек недостаточно велик для обработки этого массива, размещение массива переполняется в части памяти, которые программе не разрешено использовать.

В Windows (Visual Studio) эта программа дает следующий результат:

HelloWorld.exe (process 15916) exited with code -1073741571.

-1073741571 – это c0000005 в шестнадцатеричном формате, что представляет собой код ОС Windows для нарушения прав доступа. Обратите внимание, что «hi» никогда не печатается, потому что программа завершается до этого момента.

Вот еще одна программа, которая вызовет переполнение стека, но по другой причине:

void foo() < foo(); >int main()

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

У стека есть достоинства и недостатки:

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

Стек и куча

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

Стек похож на чипсы Pringles, только он хранит не стопку чипсов, а стопку информации. Коробка от Pringles имеет ограниченную вместимость, так и стек имеет ограниченный размер. Стек имеет несколько правил:

  • Удалить можно данные только с верха стека. В аналогии с Pringles, вы не можете достать чипсы из середины, не сняв все чипсы, находящиеся выше;
  • Добавлять новые данные можно только с верха стека. Если вернуться к аналогии с Pringles, то мы не можем добавить новые чипсы в середину или низ, только наверх. Как следствие, данные наверху стека новее, чем данные снизу;

Стек сохраняет данные в порядке добавления и удаляет в противоположном (LIFO — Last In, First Out). Работа со стеком дает большую скорость, однако имеет одно существенное ограничение: данные, которые вы хотите сохранить в стеке, должны иметь известный размер в compile time. Иными словами, в стек можно сохранить массив, если известно, что он будет иметь фиксированную длину и в него не будут добавляться новые элементы или удаляться старые.

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

Куча — это большое пространство памяти, где нет строгой организации данных. Именно в куче хранятся данные, размер которых в compile time неизвестен. Вы можете создать вектор, который будет содержать в себе указатель на адрес в куче, где будут храниться его элементы. В момент создания вектора, просходит запрос на выделение произвольного объема памяти, операционная система ищет необходимый блок и возвращает ссылку на его начало, которая и сохраняется в стеке. Это процесс назывется выделением памяти в куче. Таким образом вы сможете изменять размер вектора, не нарушая при этом правил работы со стеком. Однако куча работает медленнее стека, так как тратит время на поиск места в памяти.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *