Что такое куча в программировании

Разбираемся с управлением памятью в современных языках программирования

Привет, Хабр! Представляю вашему вниманию перевод статьи «Demystifying memory management in modern programming languages» за авторством Deepu K Sasidharan.

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

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

Часть 1: Введение в управление памятью

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

Для чего используется оперативная память?

Когда программа выполняется в операционный системе компьютера, она нуждается в доступе к оперативной памяти (RAM) для того, чтобы:

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

Стек используется для статичного выделения памяти. Он организован по принципу «последним пришёл — первым вышел» (LIFO). Можно представить стек как стопку книг — разрешено взаимодействовать только с самой верхней книгой: прочитать её или положить на неё новую.

• благодаря упомянутому принципу, стек позволяет очень быстро выполнять операции с данными — все манипуляции производятся с «верхней книгой в стопке». Книга добавляется в самый верх, если нужно сохранить данные, либо берётся сверху, если данные требуется прочитать;
• существует ограничение в том, что данные, которые предполагается хранить в стеке, обязаны быть конечными и статичными — их размер должен быть известен ещё на этапе компиляции;
• в стековой памяти хранится стек вызовов — информация о ходе выполнения цепочек вызовов функций в виде стековых кадров. Каждый стековый кадр это набор блоков данных, в которых хранится информация, необходимая для работы функции на определённом шаге — её локальные переменные и аргументы, с которыми её вызывали. Например, каждый раз, когда функция объявляет новую переменную, она добавляет её в верхний блок стека. Затем, когда функция завершает свою работу, очищаются все блоки памяти в стеке, которые функция использовала — иными словами, очищаются все блоки ее стекового кадра;
• каждый поток многопоточного приложения имеет доступ к своему собственному стеку;
• управление стековой памятью простое и прямолинейное; оно выполняется операционной системой;
• в стеке обычно хранятся данные вроде локальных переменных и указателей;
• при работе со стеком есть вероятность получать ошибки переполнения стека (stack overflow), так как максимальный его размер строго ограничен. Например, ошибка при составлении граничного условия в рекурсивной функции совершенно точно приведёт к переполнению стека;
• в большинстве языков существует ограничение на размер значений, которые можно сохранить в стек;

Использование стека в JavaScript. Объекты хранятся в куче и доступны по ссылкам, которые хранятся в стеке. Тут можно посмотреть в видеоформате

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

• операции на куче производятся несколько медленнее, чем на стеке, так как требуют дополнительного этапа для поиска данных;
• в куче хранятся данные динамических размеров, например, список, в который можно добавлять произвольное количество элементов;
• куча общая для всех потоков приложения;
• вследствие динамической природы, куча нетривиальна в управлении и с ней возникает большинство всех проблем и ошибок, связанных с памятью. Способы решения этих проблем предоставляются языками программирования;
• типичные структуры данных, которые хранятся в куче — это глобальные переменные (они должны быть доступны для разных потоков приложения, а куча как раз общая для всех потоков), ссылочные типы, такие как строки или ассоциативные массивы, а так же другие сложные структуры данных;
• при работе с кучей можно получить ошибки выхода за пределы памяти (out of memory), если приложение пытается использовать больше памяти, чем ему доступно;
• размер значений, которые могут храниться в куче, ограничен лишь общим объёмом памяти, который был выделен операционной системой для программы.

Почему эффективное управление памятью важно?

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

Различные подходы

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

Ручное управление памятью

Язык не предоставляет механизмов для автоматического управления памятью. Выделение и освобождение памяти для создаваемых объектов остаётся полностью на совести разработчика. Пример такого языка — C. Он предоставляет ряд методов (malloc, realloc, calloc и free) для управления памятью — разработчик должен использовать их для выделения и освобождения памяти в своей программе. Этот подход требует большой аккуратности и внимательности. Так же он является в особенности сложным для новичков.

Сборщик мусора

Сборка мусора — это процесс автоматического управления памятью в куче, который заключается в поиске неиспользующихся участков памяти, которые ранее были заняты под нужды программы. Это один из наиболее популярных вариантов механизма для управления памятью в современных языках программирования. Подпрограмма сборки мусора обычно запускается в заранее определённые интервалы времени и бывает, что её запуск совпадает с ресурсозатратными процессами, в результате чего происходит задержка в работе приложения. JVM (Java/Scala/Groovy/Kotlin), JavaScript, Python, C#, Golang, OCaml и Ruby — вот примеры популярных языков, в которых используется сборщик мусора.

Сборщик мусора на основе алгоритма пометок (Mark & Sweep): Это алгоритм, работа которого происходит в две фазы: первым делом он помечает объекты в памяти, на которые имеются ссылки, а затем освобождает память от объектов, которые пометки не получили. Этот подход используется, например, в JVM, C#, Ruby, JavaScript и Golang. В JVM существует на выбор несколько разных алгоритмов сборки мусора, а JavaScript-движки, такие как V8, используют алгоритм пометок в дополнение к подсчёту ссылок. Такой сборщик мусора можно подключить в C и C++ в виде внешней библиотеки.

Получение ресурса есть инициализация (RAII)

RAII — это программная идиома в ООП, смысл которой заключается в том, что выделяемая для объекта область памяти строго привязывается к его времени существования. Память выделяется в конструкторе и освобождается в деструкторе. Данный подход был впервые реализован в C++, а так же используется в Ada и Rust.

Автоматический подсчёт ссылок (ARC)

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

Автоматический подсчёт ссылок всё так же не позволяет обрабатывать циклические ссылки и требует от разработчика использования специальных ключевых слов для дополнительной обработки таких ситуаций. ARC является одной из особенностей транслятора Clang, поэтому присутствует в языках Objective-C и Swift. Так же автоматический подсчет ссылок доступен для использования в Rust и новых стандартах C++ при помощи умных указателей.

Владение

Это сочетание RAII с концепцией владения, когда каждое значение в памяти должно иметь только одну переменную-владельца. Когда владелец уходит из области выполнения, память сразу же освобождается. Можно сказать, что это примерно как подсчёт ссылок на этапе компиляции. Данный подход используется в Rust и при этом я не смог найти ни одного другого языка, который бы использовал подобный механизм.

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

Читайте так же другие части серии:

• > Часть 1: Введение в управление памятью
• Part 4: Memory management in Go (in progress)
• Part 5: Memory management in Rust (in progress)
• Part 6: Memory management in Python (in progress)
• Part 7: Memory management in C++ (in progress)
• Part 8: Memory management in C# (in progress)

Ссылки

Вы можете подписаться на автора статьи в Twitter и на LinkedIn.

За вычитку перевода отдельное спасибо Александру Максимовскому и Катерине Шибаковой

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Стек и куча

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

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

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

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

Куча (структура данных)

Этот тип структуры данных также называют двоичной кучей.

Операции над кучей

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

Создание кучи (heapify)

Heapify — это метод для создания кучи из двоичного дерева. Он используется для создания min-кучи или max-кучи.

Шаг 1. Пусть у нас есть такой массив с 6 элементами:

Шаг 2. Создаем полное двоичное дерево из этого массива:

Шаг 3. Начнем с первого нелистового узла, его индекс равен n/2 — 1 . В нашем случае индекс равен 2:

Шаг 4. Пусть текущий элемент с индексом i будет наибольшим. Значит, i — это индекс наибольшего узла ( largest ).

Шаг 5. Индекс левого дочернего элемента ( leftChild ) равен 2i + 1 , а правого ( rightChild ) — 2i + 2 .

• Если leftChild больше, чем currentElement (т.е. элемент с индексом i ), leftChildIndex — индекс наибольшего узла ( largest ).
• Если rightChild больше, чем элемент с индексом largest , rightChildIndex — индекс наибольшего узла ( largest ).

Шаг 6. Обменяем значения largest и currentElement .

Шаг 7. Повторяем шаги 3–7 до тех пор, пока поддеревья также не станут кучами.

Алгоритм

Для создания max-кучи:

Для создания min-кучи:
То же самое, только leftChild и rightChild должны быть меньше родителя для всех узлов.

Добавление элемента

Шаг 1. Вставьте новый элемент в конец дерева.

Шаг 2. Примените метод heapify к дереву.

Алгоритм для max-кучи

Алгоритм для min-кучи

Всё то же самое, но parentNode всегда должен быть меньше newNode.

Удаление элемента

Шаг 1. Выбираем элемент, который необходимо удалить.

Шаг 2. Обменяем этот элемент с последним.

Шаг 3. Удаляем посдений элемент.

Шаг 4. Применяем метод heapify к дереву.

Алгоритм для max-кучи

Алгоритм для min-кучи

Всё то же самое, только оба дочерних узла childNodes должны быть больше, чем текущий узел currentNode .

Поиск максимального и минимального (peek)

Операция peek возвращает максимальный элемент из max-кучи и минимальный элемент из min-кучи без удаления узла.

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

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

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

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

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

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

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

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

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

Заключение

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