Что такое stack и heap
Урок №105. Стек и Куча
На этом уроке мы рассмотрим стек и кучу в языке C++.
Сегменты
Память, которую используют программы, состоит из нескольких частей — сегментов:
Сегмент кода (или «текстовый сегмент»), где находится скомпилированная программа. Обычно доступен только для чтения.
Сегмент bss (или «неинициализированный сегмент данных»), где хранятся глобальные и статические переменные, инициализированные нулем.
Сегмент данных (или «сегмент инициализированных данных»), где хранятся инициализированные глобальные и статические переменные.
Куча, откуда выделяются динамические переменные.
Стек вызовов, где хранятся параметры функции, локальные переменные и другая информация, связанная с функциями.
Сегмент кучи (или просто «куча») отслеживает память, используемую для динамического выделения. Мы уже немного поговорили о куче на уроке о динамическом выделении памяти в языке С++.
В языке C++ при использовании оператора new динамическая память выделяется из сегмента кучи самой программы:
Адрес выделяемой памяти передается обратно оператором new и затем он может быть сохранен в указателе. О механизме хранения и выделения свободной памяти нам сейчас беспокоиться незачем. Однако стоит знать, что последовательные запросы памяти не всегда приводят к выделению последовательных адресов памяти!
При удалении динамически выделенной переменной, память возвращается обратно в кучу и затем может быть переназначена (исходя из последующих запросов). Помните, что удаление указателя не удаляет переменную, а просто приводит к возврату памяти по этому адресу обратно в операционную систему.
Куча имеет свои преимущества и недостатки:
Выделение памяти в куче сравнительно медленное.
Выделенная память остается выделенной до тех пор, пока не будет освобождена (остерегайтесь утечек памяти) или пока программа не завершит свое выполнение.
Доступ к динамически выделенной памяти осуществляется только через указатель. Разыменование указателя происходит медленнее, чем доступ к переменной напрямую.
Поскольку куча представляет собой большой резервуар памяти, то именно она используется для выделения больших массивов, структур или классов.
Стек вызовов
Стек вызовов (или просто «стек») отслеживает все активные функции (те, которые были вызваны, но еще не завершены) от начала программы и до текущей точки выполнения, и обрабатывает выделение всех параметров функции и локальных переменных.
Стек вызовов реализуется как структура данных «Стек». Поэтому, прежде чем мы поговорим о том, как работает стек вызовов, нам нужно понять, что такое стек как структура данных.
Стек как структура данных
Структура данных в программировании — это механизм организации данных для их эффективного использования. Вы уже видели несколько типов структур данных, например, массивы или структуры. Существует множество других структур данных, которые используются в программировании. Некоторые из них реализованы в Стандартной библиотеке C++, и стек как раз является одним из таковых.
Например, рассмотрим стопку (аналогия стеку) тарелок на столе. Поскольку каждая тарелка тяжелая, а они еще и сложены друг на друге, то вы можете сделать лишь что-то одно из следующего:
Посмотреть на поверхность первой тарелки (которая находится на самом верху).
Взять верхнюю тарелку из стопки (обнажая таким образом следующую тарелку, которая находится под верхней, если она вообще существует).
Положить новую тарелку поверх стопки (спрятав под ней самую верхнюю тарелку, если она вообще была).
В компьютерном программировании стек представляет собой контейнер (как структуру данных), который содержит несколько переменных (подобно массиву). Однако, в то время как массив позволяет получить доступ и изменять элементы в любом порядке (так называемый «произвольный доступ»), стек более ограничен.
В стеке вы можете:
Посмотреть на верхний элемент стека (используя функцию top() или peek() ).
Вытянуть верхний элемент стека (используя функцию pop() ).
Добавить новый элемент поверх стека (используя функцию push() ).
Стек — это структура данных типа LIFO (англ. «Last In, First Out» = «Последним пришел, первым ушел»). Последний элемент, который находится на вершине стека, первым и уйдет из него. Если положить новую тарелку поверх других тарелок, то именно эту тарелку вы первой и возьмете. По мере того, как элементы помещаются в стек — стек растет, по мере того, как элементы удаляются из стека — стек уменьшается.
Например, рассмотрим короткую последовательность, показывающую, как работает добавление и удаление в стеке:
Stack: empty
Push 1
Stack: 1
Push 2
Stack: 1 2
Push 3
Stack: 1 2 3
Push 4
Stack: 1 2 3 4
Pop
Stack: 1 2 3
Pop
Stack: 1 2
Pop
Stack: 1
Стопка тарелок довольно-таки хорошая аналогия работы стека, но есть лучшая аналогия. Например, рассмотрим несколько почтовых ящиков, которые расположены друг на друге. Каждый почтовый ящик может содержать только один элемент, и все почтовые ящики изначально пустые. Кроме того, каждый почтовый ящик прибивается гвоздем к почтовому ящику снизу, поэтому количество почтовых ящиков не может быть изменено. Если мы не можем изменить количество почтовых ящиков, то как мы получим поведение, подобное стеку?
Во-первых, мы используем наклейку для обозначения того, где находится самый нижний пустой почтовый ящик. Вначале это будет первый почтовый ящик, который находится на полу. Когда мы добавим элемент в наш стек почтовых ящиков, то мы поместим этот элемент в почтовый ящик, на котором будет наклейка (т.е. в самый первый пустой почтовый ящик на полу), а затем переместим наклейку на один почтовый ящик выше. Когда мы вытаскиваем элемент из стека, то мы перемещаем наклейку на один почтовый ящик ниже и удаляем элемент из почтового ящика. Всё, что находится ниже наклейки — находится в стеке. Всё, что находится в ящике с наклейкой и выше — находится вне стека.
Сегмент стека вызовов
Сегмент стека вызовов содержит память, используемую для стека вызовов. При запуске программы, функция main() помещается в стек вызовов операционной системой. Затем программа начинает свое выполнение.
Когда программа встречает вызов функции, то эта функция помещается в стек вызовов. При завершении выполнения функции, она удаляется из стека вызовов. Таким образом, просматривая функции, добавленные в стек, мы можем видеть все функции, которые были вызваны до текущей точки выполнения.
Наша аналогия с почтовыми ящиками — это действительно то, как работает стек вызовов. Стек вызовов имеет фиксированное количество адресов памяти (фиксированный размер). Почтовые ящики являются адресами памяти, а «элементы», которые мы добавляем или вытягиваем из стека, называются фреймами (или «кадрами») стека. Кадр стека отслеживает все данные, связанные с одним вызовом функции. «Наклейка» — это регистр (небольшая часть памяти в ЦП), который является указателем стека. Указатель стека отслеживает вершину стека вызовов.
Единственное отличие фактического стека вызовов от нашего гипотетического стека почтовых ящиков заключается в том, что, когда мы вытягиваем элемент из стека вызовов, нам не нужно очищать память (т.е. вынимать всё содержимое из почтового ящика). Мы можем просто оставить эту память для следующего элемента, который и перезапишет её. Поскольку указатель стека будет ниже этого адреса памяти, то, как мы уже знаем, эта ячейка памяти не будет находиться в стеке.
Стек вызовов на практике
Давайте рассмотрим детально, как работает стек вызовов. Ниже приведена последовательность шагов, выполняемых при вызове функции:
Программа сталкивается с вызовом функции.
Создается фрейм стека, который помещается в стек. Он состоит из:
адреса инструкции, который находится за вызовом функции (так называемый «обратный адрес»). Так процессор запоминает, куда ему возвращаться после выполнения функции;
памяти для локальных переменных;
сохраненных копий всех регистров, модифицированных функцией, которые необходимо будет восстановить после того, как функция завершит свое выполнение.
Процессор переходит к точке начала выполнения функции.
Инструкции внутри функции начинают выполняться.
После завершения функции, выполняются следующие шаги:
Регистры восстанавливаются из стека вызовов.
Фрейм стека вытягивается из стека. Освобождается память, которая была выделена для всех локальных переменных и аргументов.
Обрабатывается возвращаемое значение.
ЦП возобновляет выполнение кода (исходя из обратного адреса).
Возвращаемые значения могут обрабатываться разными способами, в зависимости от архитектуры компьютера. Некоторые архитектуры считают возвращаемое значение частью фрейма стека, другие используют регистры процессора.
Знать все детали работы стека вызовов не так уж и важно. Однако понимание того, что функции при вызове добавляются в стек, а при завершении выполнения — удаляются из стека, дает основы, необходимые для понимания рекурсии, а также некоторых других концепций, которые полезны при отладке программ.
Основные принципы программирования: стек и куча
Мы используем всё более продвинутые языки программирования, которые позволяют нам писать меньше кода и получать отличные результаты. За это приходится платить. Поскольку мы всё реже занимаемся низкоуровневыми вещами, нормальным становится то, что многие из нас не вполне понимают, что такое стек и куча, как на самом деле происходит компиляция, в чём разница между статической и динамической типизацией, и т.д. Я не говорю, что все программисты не знают об этих понятиях — я лишь считаю, что порой стоит возвращаться к таким олдскульным вещам.
Сегодня мы поговорим лишь об одной теме: стек и куча. И стек, и куча относятся к различным местоположениям, где происходит управление памятью, но стратегия этого управления кардинально отличается.
Стек — это область оперативной памяти, которая создаётся для каждого потока. Он работает в порядке LIFO (Last In, First Out), то есть последний добавленный в стек кусок памяти будет первым в очереди на вывод из стека. Каждый раз, когда функция объявляет новую переменную, она добавляется в стек, а когда эта переменная пропадает из области видимости (например, когда функция заканчивается), она автоматически удаляется из стека. Когда стековая переменная освобождается, эта область памяти становится доступной для других стековых переменных.
Из-за такой природы стека управление памятью оказывается весьма логичным и простым для выполнения на ЦП; это приводит к высокой скорости, в особенности потому, что время цикла обновления байта стека очень мало, т.е. этот байт скорее всего привязан к кэшу процессора. Тем не менее, у такой строгой формы управления есть и недостатки. Размер стека — это фиксированная величина, и превышение лимита выделенной на стеке памяти приведёт к переполнению стека. Размер задаётся при создании потока, и у каждой переменной есть максимальный размер, зависящий от типа данных. Это позволяет ограничивать размер некоторых переменных (например, целочисленных), и вынуждает заранее объявлять размер более сложных типов данных (например, массивов), поскольку стек не позволит им изменить его. Кроме того, переменные, расположенные на стеке, всегда являются локальными.
В итоге стек позволяет управлять памятью наиболее эффективным образом — но если вам нужно использовать динамические структуры данных или глобальные переменные, то стоит обратить внимание на кучу.
Куча — это хранилище памяти, также расположенное в ОЗУ, которое допускает динамическое выделение памяти и не работает по принципу стека: это просто склад для ваших переменных. Когда вы выделяете в куче участок памяти для хранения переменной, к ней можно обратиться не только в потоке, но и во всем приложении. Именно так определяются глобальные переменные. По завершении приложения все выделенные участки памяти освобождаются. Размер кучи задаётся при запуске приложения, но, в отличие от стека, он ограничен лишь физически, и это позволяет создавать динамические переменные.
Вы взаимодействуете с кучей посредством ссылок, обычно называемых указателями — это переменные, чьи значения являются адресами других переменных. Создавая указатель, вы указываете на местоположение памяти в куче, что задаёт начальное значение переменной и говорит программе, где получить доступ к этому значению. Из-за динамической природы кучи ЦП не принимает участия в контроле над ней; в языках без сборщика мусора (C, C++) разработчику нужно вручную освобождать участки памяти, которые больше не нужны. Если этого не делать, могут возникнуть утечки и фрагментация памяти, что существенно замедлит работу кучи.
В сравнении со стеком, куча работает медленнее, поскольку переменные разбросаны по памяти, а не сидят на верхушке стека. Некорректное управление памятью в куче приводит к замедлению её работы; тем не менее, это не уменьшает её важности — если вам нужно работать с динамическими или глобальными переменными, пользуйтесь кучей.
Заключение
Вот вы и познакомились с понятиями стека и кучи. Вкратце, стек — это очень быстрое хранилище памяти, работающее по принципу LIFO и управляемое процессором. Но эти преимущества приводят к ограниченному размеру стека и специальному способу получения значений. Для того, чтобы избежать этих ограничений, можно пользоваться кучей — она позволяет создавать динамические и глобальные переменные — но управлять памятью должен либо сборщик мусора, либо сам программист, да и работает куча медленнее.
Основы управления памятью в JavaScript: как это работает и какие проблемы могут возникнуть
Большинство разработчиков редко задумываются о том, как реализовано управление памятью в JavaScript. Движок обычно делает все за программиста, так что последнему нет смысла размышлять о принципах функционирования механизма управлением памятью.
Но рано или поздно разработчикам все же приходится разбираться с проблемами, связанными с памятью — например, утечками. Ну а разобраться с ними получится лишь тогда, когда есть понимание механизма выделения памяти. Эта статья и посвящена объяснениям. В ней также есть советы о самых распространенных видах утечек памяти в JavaScript.
Жизненный цикл памяти
При создании функций, переменных и т.п. в JavaScript движок выделяет определенный объем памяти. Потом он освобождает ее — после того, как память уже не требуется.
Собственно, выделением памяти можно назвать процесс резервирования определенного объема памяти. Ну а освобождение ее — это возвращение резерва системе. Использовать ее можно повторно сколько угодно раз.
Когда выполняется объявление переменной или создается функция, то память проходит следующий цикл.
Стек памяти и куча
В целом, все вроде понятно — JavaScript выделяет память под все, что разработчик задает в коде, а потом, когда все операции выполнены, память освобождается. Но где хранятся данные?
Есть два варианта — в стеке (stack) памяти и в куче (heap). Что первое, что второе — название структур данных, которые используются движком для разных целей.
Стек (stack) — это статическое выделение памяти
Определение стека известно многим. Это структура данных, которая используется для хранения статических данных, их размер всегда известен во время компиляции. В JS сюда включили примитивные значения, например string, number, boolean, undefined и null, а также ссылки на функции и объекты.
Движок «понимает», что размер данных не меняется, поэтому выделяет фиксированный объем памяти для каждого из значений. Процесс выделения памяти до исполнения называется статическим выделением памяти (static memory allocation).
Так как браузер выделяет память заранее для каждого типа данных есть ограничение на размер данных, которые можно туда положить. Так как браузер выделяет память заранее для каждого типа данных есть ограничение на размер данных, которые можно туда положить.
Куча (heap) — динамическое выделение памяти
Что касается кучи, то она знакома многим не хуже, чем стек. Используется она для хранения объектов и функций.
Но в отличие от стека движок не может «знать», какой объем памяти необходим для того либо иного объекта, поэтому память выделяется по мере необходимости. И этот способ выделения памяти называется «динамическим» (dynamic memory allocation).
В комментариях к коду указаны нюансы выделения памяти.
// JavaScript выделяет память под этот объект в куче.
// Сами же значения являются примитивными, поэтому хранятся они в стеке.
// Массивы – тоже объекты, значит, они отправляются в кучу.
let name = ‘John’; // выделяет память для строки
const age = 24; // выделяет память для числа
name = ‘John Doe’; // выделяет память для новой строки
const firstName = name.slice(0,4); // выделяет память для новой строки
// Примитивные значения по своей природе иммутабельные: вместо того, чтобы изменить начальное значение,
// JavaScript создает еще одно.
Ссылки в JavaScript
Что касается стека, то на него указывают все переменные. Если же значение не является примитивным, в стеке содержится ссылка на объект из кучи.
В ней нет определенного порядка, а значит, ссылка на нужную область памяти хранится в стеке. В такой ситуации объект в куче похож на здание, а вот ссылка — это его адрес.
JS сохраняет объекты и функции в куче. А вот примитивные значения и ссылки — в стеке.
На этом изображении показана организация хранения разных значений. Стоит обратить внимание на то, что person и newPerson указывают здесь на один и тот же объект.
// В куче создается новый объект, а в стеке – ссылка на него.
В целом, ссылки крайне важны в JavaScript.
Сборка мусора
Теперь самое время вернуться к жизненному циклу памяти, а именно — ее освобождению.
Движок JavaScript отвечает не только за выделение памяти, но и за освобождение. При этом память системе возвращает сборщик мусора (garbage collector).
И как только движок «видит», что в переменной или функции уже нет необходимости, выполняется освобождение памяти.
Но здесь кроется ключевая проблема. Дело в том, что решить, нужна определенная область памяти или нет, нельзя. Нет настолько точных алгоритмов, которые в режиме реального времени освобождают память.
Правда, есть просто хорошо работающие алгоритмы, которые позволяют делать это. Они не идеальны, но все же гораздо лучше, чем многие другие. Ниже — рассказ о сборке мусора, которая основана на подсчете ссылок, а также об «алгоритме пометок».
Что там насчет ссылок?
Это очень простой алгоритм. Он убирает те объекты, на которые не указывает более ни одна ссылка. Вот пример, который неплохо все разъясняет.
Если вы просмотрели видео, то, вероятно, заметили, что hobbies — единственный объект в куче, на который сохранилась ссылка в стеке.
Циклы
Недостаток алгоритма в том, что он не способен учитывать циклические ссылки. Они возникают тогда, когда один или более объектов ссылаются друга на друга, оказываясь вне зоны досягаемости с точки зрения кода.
Здесь son и dad ссылаются друг на друга. Доступа к объектам уже давно нет, но алгоритм не освобождает выделенную под них память.
Именно из-за того, что алгоритм считает ссылки, присвоение объектам null ничем не помогает, поскольку у каждого объекта все еще есть ссылка.
Алгоритм пометок
Здесь на помощь приходит другой алгоритм, который называется методом mark and sweep (помечай и выметай). Этот алгоритм не считает ссылки, а определяет, можно ли получить доступ к разным объектам посредством корневого объекта. В браузере это window, а в Node.js — global.
Если объект недоступен, то алгоритм помечает его, после чего убирает. Корневые объекты при этом никогда не уничтожаются. Проблема циклических ссылок здесь не актуальна — алгоритм позволяет понять, что ни dad, ни son уже недоступны, поэтому их можно «вымести», а память — вернуть системе.
С 2012 года абсолютно все браузеры оснащаются сборщиками мусора, которые работают именно по методу mark and sweep.
Не обошлось без недостатков и здесь
Можно было бы подумать, что все отлично, и теперь можно забыть об управлении памятью, поручив все алгоритму. Но это не совсем так.
Использование большого объема памяти
Из-за того, что алгоритмы не умеют определять, когда именно память становится ненужной, приложения на JavaScript могут использовать больший объем памяти, чем нужно. И лишь сборщик может решить, освобождать или нет выделенную память.
Лучше JavaScript с управлением памятью справляются низкоуровневые языки. Но и здесь есть свои недостатки, что нужно иметь в виду. В частности, JS не даёт инструментов управления памятью, в отличие от низкоуровневые языков, в которых программист «вручную» занимается выделением и высвобождением памяти.
Память не очищается каждый новый момент времени. Освобождение выполняется с определенной периодичностью. Но разработчики не могут знать, когда именно запускаются эти процессы.
Поэтому в некоторых случаях сборка мусора может негативно отражаться на производительности, поскольку алгоритму для работы нужны определенные ресурсы. Правда, ситуация редко становится прямо совсем уж неуправляемой. Чаще всего последствия этого микроскопические.
Утечки памяти
В разработке утечка памяти — одно из самых неприятных явлений. Но если знать все самые распространенные виды утечек, то обойти проблему можно без особого труда.
Утечки памяти чаще всего случаются из-за хранения данных в глобальных переменных.
В браузере, если ошибиться и использовать var вместо const или let, движок присоединит переменную к объекту window. Аналогичным образом он выполнит операцию с функциями, определенными словом function.
// Все три переменных – user, secondUser и
// getUser – будут присоединены к объекту window.
Так поступать можно лишь в случае с функциями и переменными, которые объявлены в глобальной области видимости. Решить эту проблему можно посредством выполнения кода в строгом режиме (strict mode).
Глобальные переменные часто объявляются намеренно, это не всегда ошибка. НО в любом случае нельзя забывать об освобождении памяти после того, как в данных уже нет нужды. Для того нужно присвоить глобальной переменной null.
Коллбеки и таймеры
Приложение использует больший объем памяти, чем положено и в том случае, если забыть о таймерах и коллбеках. Главная проблема — одностраничные приложения (SPA), а также динамическое добавление коллбеков и обработчиков событий.
Эта функция выполняется каждые две секунды. Ее выполнение не должно быть бесконечным. Проблема в том, что объекты, на которые есть референс в интервале, не уничтожаются до тех пор, пока не выполняется очистка интервала. Поэтому нужно своевременно прописывать:
clearInterval(intervalId);
Проблема может возникнуть в том случае, если к кнопке привязать обработчик onClick, а саму кнопку удалить после — например, она перестала быть нужной.
Раньше большинство браузеров просто не смогли бы освободить память, выделенную для такого обработчика события. Сейчас же эта проблема уже в прошлом, но все же оставлять обработчики, которые больше вам не нужны — не стоит.
Забытые DOM-элементы в переменных
Все это похоже на предыдущий случай. Ошибка возникает в том случае, когда элементы DOM хранятся в переменной.
При удалении любого из элементов выше стоит позаботиться и об его удалении из массива. В противном случае сборщик мусора не станет его удалять автоматически.
Удаляя элемент из массива вы актуализируете его содержимое с списком элементов на странице.
Поскольку каждый дом элемент имеет ссылку на своего родителя, это ссылочно не даёт сборщику мусора высвободить занятую родителем память, что приводить к утечкам.
В сухом остатке
В статье рассказана общая механика выделения памяти, а так же автор показал какие проблемы могут возникать и как с ними бороться. Все это — важно для любого разработчика Java Script.
Комментирует Глеб Михеев, программный директор Frontend-направления образовательной платформы Skillbox:
Знание общих принципов выделения памяти важны практически с самого начала карьеры, потому что большую популярность сейчас получили веб-приложения (в прошлом их называли SPA — Single Page Applications).
Основной ключевой особенностью этих приложений является то, что они “живут во времени” — при переходе между страницами не происходит полного сброса состояния (технически страница не перезагружается, а меняется на лету), поэтому утечки памяти накапливаются, что может приводить к затормаживанию работы вкладки, браузера и компьютера пользователя.
Вторая не менее важная особенность — рендеринг данных происходит на клиенте. Поэтому при большом количестве элементов на странице или частых изменениях данных мы можем испытывать большие просадки по производительности.
Мы как разработчики должны следить за тем, как мы выделяем память при часто повторяемых операциях (рендеринг компонентов, обход циклов, объявления переменных в обработчиках событий). Потому что, если мы слишком часто будем объявлять переменные у нас будет постоянно выделяться новая память под хранение их значений, приложение будет “пухнуть” в памяти и как следствие — будет чаще срабатывать garbage collector.
Из-за этого мы будем испытывать постоянные микрофризы (js однопоточен, поэтому все процессы заблокируются на время работы garbage collector’a). Это сильно влияет на качество пользовательского опыта, и ухудшает качество приложений.