что такое куча и стек различия принцип работы
Основные принципы программирования: стек и куча
Авторизуйтесь
Основные принципы программирования: стек и куча
Мы используем всё более продвинутые языки программирования, которые позволяют нам писать меньше кода и получать отличные результаты. За это приходится платить. Поскольку мы всё реже занимаемся низкоуровневыми вещами, нормальным становится то, что многие из нас не вполне понимают, что такое стек и куча, как на самом деле происходит компиляция, в чём разница между статической и динамической типизацией, и т.д. Я не говорю, что все программисты не знают об этих понятиях — я лишь считаю, что порой стоит возвращаться к таким олдскульным вещам.
Сегодня мы поговорим лишь об одной теме: стек и куча. И стек, и куча относятся к различным местоположениям, где происходит управление памятью, но стратегия этого управления кардинально отличается.
Стек — это область оперативной памяти, которая создаётся для каждого потока. Он работает в порядке LIFO (Last In, First Out), то есть последний добавленный в стек кусок памяти будет первым в очереди на вывод из стека. Каждый раз, когда функция объявляет новую переменную, она добавляется в стек, а когда эта переменная пропадает из области видимости (например, когда функция заканчивается), она автоматически удаляется из стека. Когда стековая переменная освобождается, эта область памяти становится доступной для других стековых переменных.
Из-за такой природы стека управление памятью оказывается весьма логичным и простым для выполнения на ЦП; это приводит к высокой скорости, в особенности потому, что время цикла обновления байта стека очень мало, т.е. этот байт скорее всего привязан к кэшу процессора. Тем не менее, у такой строгой формы управления есть и недостатки. Размер стека — это фиксированная величина, и превышение лимита выделенной на стеке памяти приведёт к переполнению стека. Размер задаётся при создании потока, и у каждой переменной есть максимальный размер, зависящий от типа данных. Это позволяет ограничивать размер некоторых переменных (например, целочисленных), и вынуждает заранее объявлять размер более сложных типов данных (например, массивов), поскольку стек не позволит им изменить его. Кроме того, переменные, расположенные на стеке, всегда являются локальными.
В итоге стек позволяет управлять памятью наиболее эффективным образом — но если вам нужно использовать динамические структуры данных или глобальные переменные, то стоит обратить внимание на кучу.
Куча — это хранилище памяти, также расположенное в ОЗУ, которое допускает динамическое выделение памяти и не работает по принципу стека: это просто склад для ваших переменных. Когда вы выделяете в куче участок памяти для хранения переменной, к ней можно обратиться не только в потоке, но и во всем приложении. Именно так определяются глобальные переменные. По завершении приложения все выделенные участки памяти освобождаются. Размер кучи задаётся при запуске приложения, но, в отличие от стека, он ограничен лишь физически, и это позволяет создавать динамические переменные.
3–5 декабря, Онлайн, Беcплатно
Вы взаимодействуете с кучей посредством ссылок, обычно называемых указателями — это переменные, чьи значения являются адресами других переменных. Создавая указатель, вы указываете на местоположение памяти в куче, что задаёт начальное значение переменной и говорит программе, где получить доступ к этому значению. Из-за динамической природы кучи ЦП не принимает участия в контроле над ней; в языках без сборщика мусора (C, C++) разработчику нужно вручную освобождать участки памяти, которые больше не нужны. Если этого не делать, могут возникнуть утечки и фрагментация памяти, что существенно замедлит работу кучи.
В сравнении со стеком, куча работает медленнее, поскольку переменные разбросаны по памяти, а не сидят на верхушке стека. Некорректное управление памятью в куче приводит к замедлению её работы; тем не менее, это не уменьшает её важности — если вам нужно работать с динамическими или глобальными переменными, пользуйтесь кучей.
Заключение
Вот вы и познакомились с понятиями стека и кучи. Вкратце, стек — это очень быстрое хранилище памяти, работающее по принципу LIFO и управляемое процессором. Но эти преимущества приводят к ограниченному размеру стека и специальному способу получения значений. Для того, чтобы избежать этих ограничений, можно пользоваться кучей — она позволяет создавать динамические и глобальные переменные — но управлять памятью должен либо сборщик мусора, либо сам программист, да и работает куча медленнее.
Разница между стеком и кучей
Содержание:
Скорость является основным параметром, который различает стек и кучу; стек значительно быстрее, чем куча.
Сравнительная таблица
| Основа для сравнения | стек | отвал |
|---|---|---|
| основной | Память выделяется в (LIFO) режиме «последним первым делом». | Память выделяется в случайном порядке. |
| Распределение и выделение | автоматическая | Руководство по эксплуатации |
| Стоимость | Меньше | Больше |
| Реализация | Жесткий | Легко |
| Вызов | НА) | O (1) |
| вопрос | Нехватка памяти | Фрагментация памяти |
| Местонахождение ссылки | Превосходно | адекватный |
| гибкость | Фиксированный размер и не гибкий | Изменение размера возможно |
| Время доступа | Быстрее | Помедленнее |
Определение стека
Фрейм стека состоит из адресов или значений параметра функции и адреса возврата, который указывает, куда должен быть возвращен элемент управления после завершения выполнения функции.
Определение кучи
Распределение кучи не следует определенному подходу; скорее это позволяет случайное назначение и удаление памяти. Запрос присваивания процессом возвращает указатель на выделенную область памяти в куче, и процесс получает доступ к выделенной области памяти через указатель.
Выделение осуществляется через запрос на освобождение, в отличие от стека, где память освобождается автоматически. Куча создает дыры в распределении памяти при построении и освобождении структур данных. Он используется во время выполнения.
Вывод
Распределение стека происходит быстрее, но сложнее. С другой стороны, куча медленнее, но ее реализация проще, чем стек. Куча более эффективна, чем стек.
Разделение памяти
Куча для обработки данных
*примечание: в случае массивов для данных типа double существует исключение, согласно которому они хранятся в большой объектной куче задолго до достижения размера в 85 кб (double[] считается системой «большим» объектом при достижении размера в 1000 элементов). По отношению к оптимизации 32-битного кода это, конечно, не очень хорошо.
Разбиение на большие и малые кучи достаточно целесообразно для улучшения производительности, но об этом позже, когда будем говорить о сборщике мусора.
Элементы, размещенные в кучи, обладают своими адресами, которые являются чем-то вроде указателей на ячейки памяти, где хранятся значения этих элементов.
Стек
Тема связана со специальностями:
Стек используется для хранения порядка выполнения кода и часто называется стеком вызова, стеком выполнения или программным стеком.
Давайте взглянем на следующий участок кода:
Дабы вызвать Method2, фреймворк должен сохранить адрес конца выполнения метода, которым будет следующая строчка кода (строчка 4 в примере ниже). Этот адрес вместе с параметрами и локальными переменными вызываемого и вызывающего метода хранятся в стеке вызова, как показано на схеме ниже.
Также вы можете увидеть, что происходит, когда Method3 завершает свое выполнение (стек-фрейм покидает стек вызова).
Хранение значимых типов
Видео курсы по схожей тематике:
C# Базовый (ООП) 2021
How to C# Углубленный
Куча
Куча схож со стеком, но если стек представляется в виде последовательности коробок, складируемых друг на друге, в случае с кучей эти самые коробки аккуратно разложены и мы можем получить к ним доступ в любое время.
Хранение ссылочных типов
Рассмотрим следующий код:
Фигура ниже иллюстрирует, как выглядит стек и куча в плане хранения данных:
OBJREF, хранимый в стеке, на самом деле является ссылкой на объект MyClass, хранимый в куче.
Заметка: выражение MyClass myObj совершенно не занимает места в куче переменной myObj. Здесь всего лишь создается переменная OBJREF в стеке, после чего она инициализируется значением null. Как только выполняется команда new, куча получает действительное место памяти объекта, а сам ссылочный объект получает по адресу свое значение.
Значимые типы против ссылочных типов (стек против кучи)
Основное различие между ссылочными и значимыми типами данных заключается в том, что ссылочные типы данных передаются по адресу – то есть при передаче ссылочной переменной в виде параметра метода передается всего лишь общий адрес на ячейку памяти с данными объекта. В случае же со значимыми типами данных, между методами передается копия самого объекта. Вот как это выглядит схематически:
Как уже и было сказано, в случае со ссылочными типами данных, при присваивании ссылочному типу данных значения другого ссылочного типа данных, происходит присваивания адреса, тогда как ячейка памяти со значением остается прежней.
Бесплатные вебинары по схожей тематике:
От процедурного программирования к ООП via C Sharp
Первоапрельские соревнования по программированию на C#, Java, C++, Pascal
Техники тестирования для С# разработчиков. Уровень Advanced. Часть 1
Конечно, хранение одного вида информации в стеке, другого в куче, имеет свои причины, которые мы рассмотрим в грядущих статьях. 🙂
Заключение
Основные принципы программирования: стек и куча
Мы используем всё более продвинутые языки программирования, которые позволяют нам писать меньше кода и получать отличные результаты. За это приходится платить. Поскольку мы всё реже занимаемся низкоуровневыми вещами, нормальным становится то, что многие из нас не вполне понимают, что такое стек и куча, как на самом деле происходит компиляция, в чём разница между статической и динамической типизацией, и т.д. Я не говорю, что все программисты не знают об этих понятиях — я лишь считаю, что порой стоит возвращаться к таким олдскульным вещам.
Сегодня мы поговорим лишь об одной теме: стек и куча. И стек, и куча относятся к различным местоположениям, где происходит управление памятью, но стратегия этого управления кардинально отличается.
Стек — это область оперативной памяти, которая создаётся для каждого потока. Он работает в порядке LIFO (Last In, First Out), то есть последний добавленный в стек кусок памяти будет первым в очереди на вывод из стека. Каждый раз, когда функция объявляет новую переменную, она добавляется в стек, а когда эта переменная пропадает из области видимости (например, когда функция заканчивается), она автоматически удаляется из стека. Когда стековая переменная освобождается, эта область памяти становится доступной для других стековых переменных.
Из-за такой природы стека управление памятью оказывается весьма логичным и простым для выполнения на ЦП; это приводит к высокой скорости, в особенности потому, что время цикла обновления байта стека очень мало, т.е. этот байт скорее всего привязан к кэшу процессора. Тем не менее, у такой строгой формы управления есть и недостатки. Размер стека — это фиксированная величина, и превышение лимита выделенной на стеке памяти приведёт к переполнению стека. Размер задаётся при создании потока, и у каждой переменной есть максимальный размер, зависящий от типа данных. Это позволяет ограничивать размер некоторых переменных (например, целочисленных), и вынуждает заранее объявлять размер более сложных типов данных (например, массивов), поскольку стек не позволит им изменить его. Кроме того, переменные, расположенные на стеке, всегда являются локальными.
В итоге стек позволяет управлять памятью наиболее эффективным образом — но если вам нужно использовать динамические структуры данных или глобальные переменные, то стоит обратить внимание на кучу.
Куча — это хранилище памяти, также расположенное в ОЗУ, которое допускает динамическое выделение памяти и не работает по принципу стека: это просто склад для ваших переменных. Когда вы выделяете в куче участок памяти для хранения переменной, к ней можно обратиться не только в потоке, но и во всем приложении. Именно так определяются глобальные переменные. По завершении приложения все выделенные участки памяти освобождаются. Размер кучи задаётся при запуске приложения, но, в отличие от стека, он ограничен лишь физически, и это позволяет создавать динамические переменные.
Вы взаимодействуете с кучей посредством ссылок, обычно называемых указателями — это переменные, чьи значения являются адресами других переменных. Создавая указатель, вы указываете на местоположение памяти в куче, что задаёт начальное значение переменной и говорит программе, где получить доступ к этому значению. Из-за динамической природы кучи ЦП не принимает участия в контроле над ней; в языках без сборщика мусора (C, C++) разработчику нужно вручную освобождать участки памяти, которые больше не нужны. Если этого не делать, могут возникнуть утечки и фрагментация памяти, что существенно замедлит работу кучи.
В сравнении со стеком, куча работает медленнее, поскольку переменные разбросаны по памяти, а не сидят на верхушке стека. Некорректное управление памятью в куче приводит к замедлению её работы; тем не менее, это не уменьшает её важности — если вам нужно работать с динамическими или глобальными переменными, пользуйтесь кучей.
Заключение
Вот вы и познакомились с понятиями стека и кучи. Вкратце, стек — это очень быстрое хранилище памяти, работающее по принципу LIFO и управляемое процессором. Но эти преимущества приводят к ограниченному размеру стека и специальному способу получения значений. Для того, чтобы избежать этих ограничений, можно пользоваться кучей — она позволяет создавать динамические и глобальные переменные — но управлять памятью должен либо сборщик мусора, либо сам программист, да и работает куча медленнее.
Читайте также
Недавно вышел HTML5, и хотя я надеялся что де-факто стандартом станет XHTML2, видимо этому не судьба. Следование веб-стандартам впринципе дело самодисциплины…
Если вы выбираете ноутбук и столкнулись с разнообразием на рынке и не знаете, что вам нужно – эта статья поможет…
Каждый разработчик знает, что у него должен быть стандарт программирования, принятый в компании. Каждый разработчик также знает, что нужно постараться, чтобы…
Стек, очередь и куча
На рисунке вы можете видеть обобщенную модель организации памяти компьютера.
Стек — это область памяти, которую вы, как программист, не контролируете никоим образом. В неё записываются переменные и информация, которые создаются в результате вызова любых функций. Когда функция заканчивает работу, то вся информация о ее вызов и ее переменные удаляются из стека автоматически.
Но важнее даже не это, а то, что стек — это структура данных, которая работает по принципу «последним пришел — первым ушел» (last in first out, LIFO). На лекции Дэвид предложил представление стека, как стопки подносов в столовой. Поднос, который попал в стопку последним, новый клиент столовой возьмет в первую очередь.
Над стеком можно осуществлять две операции: push (занесение данных) и pop (изъятие данных).
Пример реализации стека языке С приведен ниже. В этом примере, стек — это просто массив строк, имеет определенную емкость (CAPACITY), и текущий размер (size):
Для реализации операции pop, необходимо проверить, не пустой стек, уменьшить текущий размер на единицу и вернуть элемент.
Очередь
Очередь (queue) — это структура данных, которая напоминает обычную очередь. То есть, в отличие от стека, она работает по принципу «первым пришел — первым ушел» (first in first out, FIFO).
Для очереди определены две операции: добавление элемента в конец очереди (enqueue) и изъятие элемента с начала очереди (dequeue).
В примере объявлена очередь, которая, по сути, представляет собой массив строк:
Чтобы реализовать операцию enqueue, необходимо убедиться, что очередь, не переполнена, добавить элемент в конец очереди и увеличить текущий размер на единицу.
Чтобы реализовать операцию dequeue, надо убедиться, что очередь не пуста, увеличить head на единицу, уменьшить текущий размер и вернуть первый элемент очереди.
Куча и переполнение буфера
Куча (heap) — область памяти, которую контролируют непосредственно программисты. Над которой вы, как программисты, получаете непосредственный контроль. Память здесь выделяется в результате вызова функции malloc.
Более глубокие знания о стеке и куче вам пока не понадобятся. Вы их получите позже, если захотите изучать программирование и компьютерные науки глубже.
Буфер — это массив определенной длины, расположенный в памяти. Переполнение буфера (buffer overflow) возникает, если мы пытаемся записать в него больше данных, чем предусмотрено размером этого массива. С помощью переполнения буфера злоумышленник может записать опасный код в память компьютера.