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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24 апреля в 10:00, Онлайн, Беcплатно

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

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

Заключение

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

Куча Windows и семейство функций GlobalAlloc

Куча (heap) — это пул памяти какого-либо процесса. Когда программе требуется блок памяти, онавызывает функцию, выделяющую память из кучи, а чтобы освободить ранее выделенную память, — функцию, парную первой. Выравнивание по границам, кратным 4 Кб, в этом случае не производится; диспетчер кучи использует пространство на выделенных ранее страницах или обращается к VirtualAlloc, чтобы получить дополнительные страницы. Одна из двух куч, с которыми программа работает, — куча Windows. Для выделения из нее памяти служит функция HeapAlloc, а для освобождения — функция HeapFree. HeapAlloc особенно удобна для выделения «крупных» блоков памяти.

Может быть, приложение и не будет явно вызывать НеарАlloc, но за него это сделает функция GlobalAlloc, унаследованная от Winl6. В идеальном мире 32-разрядных программ функция GlobalAlloc не понадобилась бы, но мы имеем дело с реальным миром. Все еще остается колоссальный объем кода, перенесенного из Winl6, в том числе OLE, в котором вместо 32-разрядных адресов применяются параметры типа «описатель памяти» (HGLOBAL).

Работа функции GlobalAlloc зависит от передаваемых ей атрибутов. Если ей указывается GMEM_FIXED, она просто вызывает НеарАlloс и возвращает адрес, приводя тип данных к 32-битному значению HGLOBAL. Если же ей передается GMEM_MOVEABLE, возвращаемое значение HGLOBAL является указателем на элемент «таблицы описателей» в данном процессе. В этом элементе содержится указатель на память, выделенную функцией HeapAlloc.

Зачем нужна «перемещаемая» (moveable) память, если она вводит еще один слой «непрямого управления»? Здесь мы встречаемся с наследием Winl6, в котором операционная система когда-то действительно перемещала блоки памяти. В Win32 перемещаемые блоки памяти существуют лишь для поддержки GlobalReAlloc, которая выделяет новый блок памяти, копирует в него содержимое старого блока, освобождает последний и помещает адрес нового блока в существующий элемент таблицы описателей.

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

Буфер обмена Windows использует фиксированную память, тем самым можно передавать адреса, возвращенные HeapAlloc, и приводить возвращаемые значения HGLOBAL к void-указателям. Можно также передавать фиксированный адрес OLE-функции, которая принимает параметр типа HGLOBAL, однако значения HGLOBAL, возвращаемые OLE-функциями, являются перемещаемыми, поэтому приложение должны вызывать GlobalLock.

Куча библиотеки С периода выполнения, _heapmin и С++-операторы new и delete

Однако, куча Windows (и функция HeapAlloc) – это не та куча, с которой приложение будете работать чаще всего. Существует еще одна куча — ею управляет библиотека С периода выполнения (С RunTime library, CRT). Доступ к CRT-куче реализуется функциями malloc и free, напрямую вызываемыми операторами C++ new и delete. Эта куча оптимизирована для выделения блоков малого размера.

Конечно, функция malloc вызывает VirtualAlloc, но делает это очень хитро. При первом вызове она резервирует регион размером 1 Мб (в будущих версиях Visual C++ эти значения могут измениться) и передает блок памяти, размер которого кратен 64 Кб (если malloc вызван чтобы выделить память размером 64 Кб или менее, выделяется один 64-килобайтный блок. При последующих вызовах память выделяется по возможности из этого блока; в ином случае диспетчер кучи вызывает VirtualAlloc, чтобы передать дополнительную память. После того, как весь регион размером 1 Мб израсходован, malloc резервирует еще один регион размер 2 Мб, потом другой, но уже размером 4 Мб и т.д., передавая память по мере необходимости.

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

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