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

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

На данный момент этот блок не поддерживается, но мы не забыли о нём! Наша команда уже занята его разработкой, он будет доступен в ближайшее время.

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

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

Стек

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

Из-за такой природы стека управление памятью оказывается весьма логичным и простым для выполнения на ЦП; это приводит к высокой скорости, в особенности потому, что время цикла обновления байта стека очень мало, т.е. этот байт скорее всего привязан к кэшу процессора. Тем не менее, у такой строгой формы управления есть и недостатки. Размер стека — это фиксированная величина, и превышение лимита выделенной на стеке памяти приведёт к переполнению стека. Размер задаётся при создании потока, и у каждой переменной есть максимальный размер, зависящий от типа данных. Это позволяет ограничивать размер некоторых переменных (например, целочисленных), и вынуждает заранее объявлять размер более сложных типов данных (например, массивов), поскольку стек не позволит им изменить его. Кроме того, переменные, расположенные на стеке, всегда являются локальными.

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

Куча

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

Вы взаимодействуете с кучей посредством ссылок, обычно называемых указателями — это переменные, чьи значения являются адресами других переменных. Создавая указатель, вы указываете на местоположение памяти в куче, что задаёт начальное значение переменной и говорит программе, где получить доступ к этому значению. Из-за динамической природы кучи ЦП не принимает участия в контроле над ней; в языках без сборщика мусора (C, C++) разработчику нужно вручную освобождать участки памяти, которые больше не нужны. Если этого не делать, могут возникнуть утечки и фрагментация памяти, что существенно замедлит работу кучи.

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

Заключение

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

Стек (Stack) & Куча (Heap)

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

Стек (Stack)

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

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

import Foundation func someFunction()

Переменная «a» и константа «b» будут храниться в стеке, пока функция someFunction() выполняется. При завершении функции, они будут автоматически удалены из стека.

Куча (Heap)

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

Куча в Swift управляется с помощью ARC (Automatic Reference Counting), что означает, что память освобождается автоматически, когда объект больше не используется. Когда объект создается в куче, Swift выделяет память для этого объекта и возвращает указатель на эту память. Этот указатель можно использовать для доступа к объекту и его свойствам.

Вот пример создания объекта класса в куче:

import Foundation class MyClass < var property: Int = 0 >let myObject = MyClass() myObject.property = 10

В этом примере мы создали объект класса «MyClass» в куче с помощью оператора «new». Затем мы установили значение свойства «property» объекта «myObject».

Отличия стека и кучи

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

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

Кроме того, в стеке память выделяется автоматически, когда вы объявляете переменную или вызываете функцию, в то время как в куче память выделяется явно, когда вы создаете объект. В Swift у вас есть возможность управлять, когда память выделяется и освобождается в куче, используя специальные функции, такие как «alloc» и «dealloc».

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

Еще немного об отличиях и типах, которые хранятся в той или иной области памяти

В Swift значения переменных могут быть либо типа значений (value type), либо ссылочного типа (reference type).

Типы значений (value) в Swift включают примитивные типы данных, такие как Integer, Boolean и Double, а также структуры, перечисления и кортежи. Типы значений хранятся непосредственно в стеке, в памяти, выделенной для функции или блока кода, в котором они определены. Когда переменная типа значения копируется в другую переменную или передается в функцию, копируется само значение, а не ссылка на объект.

Ссылочные типы (reference) в Swift включают классы, замыкания и функции. Объекты ссылочных типов хранятся в куче, и переменные, которые указывают на эти объекты, хранят ссылки на них. Когда переменная ссылочного типа копируется в другую переменную или передается в функцию, копируется только ссылка на объект, а не сам объект.

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

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

Наконец, важно помнить, что в Swift большинство стандартных типов данных, таких как String, Array и Dictionary, являются value типами, хранящимися в стеке.

Еще больше информации в нашем телегам канале.

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() вызывает себя бесконечно, в конечном итоге в стеке закончится память и произойдет переполнение.

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

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

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

В программировании есть два разных понятия, которые обозначаются одним и тем же словом «куча». Одно про выделение памяти, второе — про организацию данных. Разберём оба и закроем этот вопрос.

Это про данные

Эта статья из цикла про типы данных. Уже было:

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

Куча и работа с памятью

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

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

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

Аналогия со стройплощадкой

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

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

В программе: мы выделили память для переменной, использовали переменную, она больше не нужна. Можно сказать «Эта память свободна» и использовать её снова.

На стройке: мы храним определённый вид труб на палете №53. Мы говорим крановщику: «Поднимайте на этаж то, что лежит на палете 53». Если мы ошибёмся с номером, то крановщик поднимет на этаж не те трубы.

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

�� Прямой доступ к памяти есть не во всех языках программирования. Многие компиляторы и интерпретаторы ставят между программистом и памятью своеобразного администратора — диспетчера памяти. Он сам решает, какие переменные нужны, а какие нет; когда чистить память; сколько памяти на что выделить.

С одной стороны, это удобно: программист просто говорит «храни данные». А где они будут храниться и как их получить — это вопрос другой системы.

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

Куча и организация данных

Второй вид кучи в программировании — это организация данных.

Куча — это такой вид дерева, у которого есть одно важное свойство:

если узел A — это родитель узла B, то ключ узла A больше ключа узла B (или равен ему).

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

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

Для чего нужны кучи данных

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

• для пирамидальной сортировки большого количества данных, когда объём требуемой памяти не зависит от размера массива, который мы сортируем;
• для нахождения самого быстрого пути из точки A в точку B, когда мы знаем промежуточные расстояния между ними и точками по пути;
• для поиска нужного элемента по каким-то критериям за минимальное время;
• для вычисления оптимальной последовательности действий, если мы знаем параметры и условия для каждого действия.

Зачем это знать

Если вы просто пишете веб-приложения на JS — в принципе, это знать не нужно. Вы не можете из JS напрямую управлять памятью, а для простых задач вам вряд ли придётся часто обходить деревья и делать сложные сортировки.

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