Что и где стопка и куча?

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

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

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

Чтобы напрямую ответить на ваши вопросы:

В какой степени они контролируются ОС или языковой средой выполнения?

ОС выделяет стек для каждого потока системного уровня при создании потока. Обычно ОС вызывается средой выполнения языка для выделения кучи для приложения.

Каковы их возможности?

Стек прикреплен к потоку, поэтому, когда поток выходит из стека, он восстанавливается. Куча обычно выделяется при запуске приложения средой выполнения и освобождается при выходе из приложения (технически процесса).

От чего зависит размер каждого из них?

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

Что делает человека быстрее?

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

Наглядная демонстрация:
_{Источник изображения: vikashazrati.wordpress.com}

Стек:

• Хранится в оперативной памяти компьютера как в куче.
• Переменные, созданные в стеке, выходят из области видимости и автоматически освобождаются.
• Гораздо быстрее выделять по сравнению с переменными в куче.
• Реализован с реальной структурой данных стека.
• Хранит локальные данные, адреса возврата, используемые для передачи параметров.
• Может иметь место переполнение стека, когда используется слишком большая часть стека (в основном из-за бесконечной или слишком глубокой рекурсии, очень больших выделений).
• Данные, созданные в стеке, можно использовать без указателей.
• Вы могли бы использовать стек, если точно знаете, сколько данных вам нужно выделить до времени компиляции, и он не слишком велик.
• Обычно максимальный размер уже определяется при запуске вашей программы.

Куча:

• Хранится в оперативной памяти компьютера точно так же, как в стеке.
• В C ++ переменные в куче должны быть уничтожены вручную и никогда не выпадают из области видимости. Данные освобождаются с помощью delete, delete[] или free.
• Медленнее выделяется по сравнению с переменными в стеке.
• Используется по запросу для выделения блока данных для использования программой.
• Может иметь место фрагментация при большом количестве распределений и освобождений.
• В C ++ или C данные, созданные в куче, будут указываться указателями и выделены с помощью new или malloc соответственно.
• Могут происходить сбои выделения, если требуется выделить слишком большой буфер.
• Вы могли бы использовать кучу, если не знаете точно, сколько данных вам понадобится во время выполнения, или если вам нужно выделить много данных.
• Ответственный за утечки памяти.

Пример:

int foo()
{
  char *pBuffer; //<--nothing allocated yet (excluding the pointer itself, which is allocated here on the stack).
  bool b = true; // Allocated on the stack.
  if(b)
  {
    //Create 500 bytes on the stack
    char buffer[500];

    //Create 500 bytes on the heap
    pBuffer = new char[500];

   }//<-- buffer is deallocated here, pBuffer is not
}//<--- oops there's a memory leak, I should have called delete[] pBuffer;

Наиболее важным моментом является то, что куча и стек - это общие термины для способов выделения памяти. Их можно реализовать по-разному, и эти термины относятся к основным концепциям.

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

  

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

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

  

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

Эти изображения должны достаточно хорошо описывать два способа выделения и освобождения памяти в стеке и куче. Ням!

• В какой степени они контролируются ОС или языковой средой?

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

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

• Каков их объем?

  Стек вызовов - это настолько низкоуровневая концепция, что она не имеет отношения к «области видимости» в смысле программирования. Если вы дизассемблируете какой-то код, вы увидите относительные ссылки стиля указателя на части стека, но, что касается языка более высокого уровня, язык накладывает свои собственные правила области видимости. Однако одним из важных аспектов стека является то, что после возврата из функции все, что является локальным для этой функции, немедленно освобождается из стека. Это работает так, как вы ожидаете, учитывая то, как работают ваши языки программирования. В куче тоже сложно определить. Область видимости - это то, что предоставляется ОС, но ваш язык программирования, вероятно, добавляет свои правила о том, что такое «область видимости» в вашем приложении. Архитектура процессора и ОС используют виртуальную адресацию, которую процессор преобразует в физические адреса, и возникают ошибки страниц и т. Д. Они отслеживают, какие страницы каким приложениям принадлежат. Однако вам никогда не стоит об этом беспокоиться, потому что вы просто используете любой метод, который использует ваш язык программирования, для выделения и освобождения памяти и проверки на наличие ошибок (если выделение / освобождение не удается по какой-либо причине).

• От чего зависит размер каждого из них?

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

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

• Что делает человека быстрее?

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

(Я переместил этот ответ из другого вопроса, который был более или менее обманутым.)

Ответ на ваш вопрос зависит от реализации и может отличаться в зависимости от компилятора и архитектуры процессора. Однако вот упрощенное объяснение.

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

Куча

• Куча содержит связанный список используемых и свободных блоков. Новые выделения в куче (new или malloc) удовлетворяются путем создания подходящего блока из одного из свободных блоков. Это требует обновления списка блоков в куче. Эта метаинформация о блоках в куче также сохраняется в куче, часто в небольшой области перед каждым блоком.
• По мере роста кучи новые блоки часто распределяются с более низких адресов на более высокие. Таким образом, вы можете думать о куче как о куче блоков памяти, размер которой увеличивается по мере выделения памяти. Если куча слишком мала для выделения, размер часто можно увеличить, получив больше памяти из базовой операционной системы.
• Выделение и освобождение большого количества небольших блоков может привести к тому, что куча останется в состоянии, когда между используемыми блоками будет перемежаться много маленьких свободных блоков. Запрос на выделение большого блока может завершиться ошибкой, потому что ни один из свободных блоков не является достаточно большим, чтобы удовлетворить запрос на выделение, даже если объединенный размер свободных блоков может быть достаточно большим. Это называется фрагментацией кучи.
• Когда использованный блок, который находится рядом со свободным блоком, освобождается, новый свободный блок может быть объединен со смежным свободным блоком, чтобы создать свободный блок большего размера, эффективно уменьшая фрагментацию кучи.

Стек

• Стек часто работает в тесном тандеме со специальным регистром ЦП, называемым указателем стека. Первоначально указатель стека указывает на вершину стека (самый высокий адрес в стеке).
• У ЦП есть специальные инструкции для вставки значений в стек и выталкивания их обратно из стека. Каждое нажатие сохраняет значение в текущем местоположении указателя стека и уменьшает указатель стека. pop извлекает значение, на которое указывает указатель стека, а затем увеличивает указатель стека (вас не смущает тот факт, что добавление значения в стек уменьшает указатель стека и удаление значения увеличивает его. Помните, что стек увеличивается до самого низа). Сохраненные и извлеченные значения - это значения регистров ЦП.
• Когда функция вызывается, ЦП использует специальные инструкции, которые нажимают текущий указатель инструкции, то есть адрес кода, выполняемого в стеке. Затем ЦП переходит к функции, устанавливая указатель инструкции на адрес вызываемой функции. Позже, когда функция возвращается, старый указатель инструкции извлекается из стека, и выполнение возобновляется с кода сразу после вызова функции.
• Когда функция вводится, указатель стека уменьшается, чтобы выделить больше места в стеке для локальных (автоматических) переменных. Если функция имеет одну локальную 32-битную переменную, в стеке выделяются четыре байта. Когда функция возвращается, указатель стека перемещается назад, чтобы освободить выделенную область.
• Если функция имеет параметры, они помещаются в стек перед вызовом функции. Затем код функции может перемещаться вверх по стеку от текущего указателя стека, чтобы найти эти значения.
• Вызовы вложенных функций работают как шарм. Каждый новый вызов будет выделять параметры функции, адрес возврата и пространство для локальных переменных, и эти записи активации могут быть сложены для вложенных вызовов и будут раскручиваться правильным образом, когда функции вернутся.
• Поскольку стек представляет собой ограниченный блок памяти, вы можете вызвать переполнение стека, вызвав слишком много вложенных функций и / или выделив слишком много места для локальных переменных. Часто область памяти, используемая для стека, настраивается таким образом, что запись ниже нижнего (самого низкого адреса) стека вызывает прерывание или исключение в ЦП. Это исключительное состояние затем может быть обнаружено средой выполнения и преобразовано в какое-то исключение переполнения стека.

Можно ли разместить функцию в куче, а не в стеке?

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

Как управлять кучей, действительно зависит от среды выполнения. C использует malloc, а C ++ использует new, но во многих других языках есть сборка мусора.

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

В следующем коде C #

public void Method1()
{
    int i = 4;
    int y = 2;
    class1 cls1 = new class1();
}

Вот как управляется память

Local Variables, которые должны длиться только до тех пор, пока вызов функции находится в стеке. Куча используется для переменных, время жизни которых мы не знаем заранее, но мы ожидаем, что они продлятся какое-то время. Для большинства языков очень важно знать во время компиляции, насколько велика переменная, если мы хотим сохранить ее в стеке.

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

В Java большинство объектов попадают прямо в кучу. В таких языках, как C / C ++, структуры и классы часто могут оставаться в стеке, когда вы не имеете дело с указателями.

Более подробную информацию можно найти здесь:

Разница между выделением памяти в стеке и куче timmurphy.org

и тут:

Создание Объекты в стопке и куче

Эта статья является источником изображения выше: Шесть важных концепций .NET: стек, куча, типы значений, ссылочные типы, упаковка и распаковка - CodeProject

но имейте в виду, что он может содержать некоторые неточности.

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

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

Куча Куча - это общее имя, в которое вы помещаете данные, которые вы создаете на лету. Если вы не знаете, сколько космических кораблей собирается создать ваша программа, вы, вероятно, воспользуетесь оператором new (или malloc или эквивалентным) для создания каждого космического корабля. Это распределение будет сохраняться какое-то время, поэтому вполне вероятно, что мы будем освобождать вещи в другом порядке, чем мы их создавали.

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

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

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

Физическое расположение в памяти. Это менее актуально, чем вы думаете, из-за технологии, называемой виртуальной памятью., что заставляет вашу программу думать, что у вас есть доступ к определенному адресу, где физические данные находятся где-то еще (даже на жестком диске!). Адреса, которые вы получаете для стека, располагаются в порядке возрастания по мере того, как ваше дерево вызовов становится глубже. Адреса кучи непредсказуемы (т.е. специфичны для реализации) и, откровенно говоря, не важны.

Чтобы уточнить, этот ответ содержит неверную информацию (thomas исправил свой ответ после комментариев, круто :)). В других ответах просто не объясняется, что означает статическое распределение. Итак, я объясню три основных формы распределения и то, как они обычно связаны с кучей, стеком и сегментом данных ниже. Я также покажу несколько примеров как на C / C ++, так и на Python, чтобы помочь людям понять.

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

Однако обычно лучше рассматривать «область и время жизни, а не« стек »и« кучу ».

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

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

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

Я предоставлю простой аннотированный код на языке C, чтобы проиллюстрировать все это. Лучший способ научиться - запустить программу под отладчиком и наблюдать за ее поведением. Если вы предпочитаете читать Python, переходите к концу ответа :)

// Statically allocated in the data segment when the program/DLL is first loaded
// Deallocated when the program/DLL exits
// scope - can be accessed from anywhere in the code
int someGlobalVariable;

// Statically allocated in the data segment when the program is first loaded
// Deallocated when the program/DLL exits
// scope - can be accessed from anywhere in this particular code file
static int someStaticVariable;

// "someArgument" is allocated on the stack each time MyFunction is called
// "someArgument" is deallocated when MyFunction returns
// scope - can be accessed only within MyFunction()
void MyFunction(int someArgument) {

    // Statically allocated in the data segment when the program is first loaded
    // Deallocated when the program/DLL exits
    // scope - can be accessed only within MyFunction()
    static int someLocalStaticVariable;

    // Allocated on the stack each time MyFunction is called
    // Deallocated when MyFunction returns
    // scope - can be accessed only within MyFunction()
    int someLocalVariable;

    // A *pointer* is allocated on the stack each time MyFunction is called
    // This pointer is deallocated when MyFunction returns
    // scope - the pointer can be accessed only within MyFunction()
    int* someDynamicVariable;

    // This line causes space for an integer to be allocated in the heap
    // when this line is executed. Note this is not at the beginning of
    // the call to MyFunction(), like the automatic variables
    // scope - only code within MyFunction() can access this space
    // *through this particular variable*.
    // However, if you pass the address somewhere else, that code
    // can access it too
    someDynamicVariable = new int;


    // This line deallocates the space for the integer in the heap.
    // If we did not write it, the memory would be "leaked".
    // Note a fundamental difference between the stack and heap
    // the heap must be managed. The stack is managed for us.
    delete someDynamicVariable;

    // In other cases, instead of deallocating this heap space you
    // might store the address somewhere more permanent to use later.
    // Some languages even take care of deallocation for you... but
    // always it needs to be taken care of at runtime by some mechanism.

    // When the function returns, someArgument, someLocalVariable
    // and the pointer someDynamicVariable are deallocated.
    // The space pointed to by someDynamicVariable was already
    // deallocated prior to returning.
    return;
}

// Note that someGlobalVariable, someStaticVariable and
// someLocalStaticVariable continue to exist, and are not
// deallocated until the program exits.

Особенно ярким примером того, почему важно различать время жизни и область видимости, является то, что переменная может иметь локальную область видимости, но статическое время жизни - например, someLocalStaticVariable в приведенном выше примере кода. Такие переменные могут сбить с толку наши обычные, но неформальные привычки именования. Например, когда мы говорим «локальная», мы обычно имеем в виду «автоматически выделяемая переменная с локальной областью действия», а когда мы говорим «глобальная», мы обычно имеем в виду «статически выделенная переменная с глобальной областью действия < / em> ". К сожалению, когда дело доходит до таких вещей, как «статически размещенные переменные с областью видимости файла», многие люди просто говорят… «да ???».

int var1; // Has global scope and static allocation
static int var2; // Has file scope and static allocation

int main() {return 0;}

from datetime import datetime

class Animal:
    _FavoriteFood = 'Undefined' # _FavoriteFood is statically allocated

    def PetAnimal(self):
        curTime = datetime.time(datetime.now()) # curTime is automatically allocatedion
        print("Thank you for petting me. But it's " + str(curTime) + ", you should feed me. My favorite food is " + self._FavoriteFood)

class Cat(Animal):
    _FavoriteFood = 'tuna' # Note since we override, Cat class has its own statically allocated _FavoriteFood variable, different from Animal's

class Dog(Animal):
    _FavoriteFood = 'steak' # Likewise, the Dog class gets its own static variable. Important to note - this one static variable is shared among all instances of Dog, hence it is not dynamic!


if __name__ == "__main__":
    whiskers = Cat() # Dynamically allocated
    fido = Dog() # Dynamically allocated
    rinTinTin = Dog() # Dynamically allocated

    whiskers.PetAnimal()
    fido.PetAnimal()
    rinTinTin.PetAnimal()

    Dog._FavoriteFood = 'milkbones'
    whiskers.PetAnimal()
    fido.PetAnimal()
    rinTinTin.PetAnimal()

# Output is:
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is tuna
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is steak
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is steak
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is tuna
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is milkbones
# Thank you for petting me. But it's 13:05:02.256000, you should feed me. My favorite food is milkbones