17

Как физически выглядят куча и стек в оперативной памяти?

12
  • так а доступ в куче проходит медленнее чем в стэке. Или это присходит на программном а не аппаратном уровне?
    – voipp
    4 дек 2013 в 18:32
  • 3
    Может автор изучает вопрос виртуальной памяти - да, куча и стек могут оказаться на жестком диске, если их туда засвоппит операционная система. Другой вопрос, что стек в данном случае это некий сегмент (область памяти) программы, а куча будет в сегмента данных (с атрибутами RW), в противовес сегменту кода (который RO). А вообще странно говорить про такие вещи - нужно отделять мух от котлет и теплое не мешать с мягким.
    – gecube
    4 дек 2013 в 20:36
  • 5
    "Физически" это транзисторы и конденсаторы
    – DreamChild
    5 дек 2013 в 6:49
  • 1
    @voipp, а почему Вы решили, что стек быстрый, а куча медленная? Насколько мне известно, время доступа к памяти в них одинаковое.
    – avp
    5 дек 2013 в 10:18
  • 3
    @voipp: Мне не кажется, что информация, которую вы прочитали, соответствует действительности. Как правильно сказал @DreamChild, и стек, и хип — не более чем аппаратура. То, что стек меньше хипа по размеру в типичном случае, не значит ничего: вы можете обращаться к данным локально в хипе и нелокально в стеке. (Вы имели в виду кэширование на уровне процессора, но оно работает не так, как вы думаете.) Регистров в языках высокого уровня нет и не будет никогда по многим причинам (например, потому, что оптимизирующий компилятор умеет оптимизировать лучше человека.)
    – VladD
    5 дек 2013 в 11:48

3 ответа 3

28
  1. И стек и куча оба находятся физически в RAM (не рассматриваем архитектурные вывихи с использованием спец. процессоров/компов)
  2. Их размеры и расположение определяются осью
  3. При этом куча может быть фрагментирована (иногда довольно сильно). Обычно у осей бывают специальные процедуры для дефрагментации кучи.
  4. Стек обычно никогда не фрагментирован (наверное можно придумать реализации стека с фрагментацией, но это оксюморон).
  5. Стек как бы быстрее потому, что у него единственный параметр с которым работает - это указатель положения стека (обычно регистр) - поэтому все операции со стеком работают в разы быстрее чем с кучей. Операция извлечения/записи из стека это 1 телодвижение процессора POP/PUSH
  6. С кучей сложнее именно из-за его фрагментации и простая операция извлечения значения из него может вылиться в десятки (если не сотни) телодвижений процессора.
  7. Минусы стека в малости его размера (он всегда по сравнению с кучей на порядок меньше) - ну и в том, что доступ к нему только последовательный.
6
  • 5
    @Barmaley: 6) Это имеет смысл для выделения памяти в куче, но если у вас есть указатель на объект в куче, и указатель на объект в стеке, скорость доступа строго одинакова. 7) Опять-таки, доступ ведётся не последовательным чтением, а разыменованием указателя.
    – VladD
    6 дек 2013 в 20:15
  • 4
    Действительно, скорость доступа к данным в стеке и куче одинакова. Т.е. пункты 5) и 6) это ошибка. Я не поленился и проверил время заполнения (несколько попыток) массива из 2 млн. int (больше в стек у меня не влезает) в куче и стеке. void fill (int a[], int n) { srand(0); for (int i = 0; i < n; i++) a[rand() % n] = rand(); } Такой метод избран, чтобы минимизировать влияние кэша и предвыборки данных в него. Результаты (clock_gettime(CLOCK_THREAD_CPUTIME_ID, &ts);) ./a.out 100 stack: avg: 43.332 (msec) heap: avg: 42.283 (msec)
    – avp
    6 дек 2013 в 22:14
  • @avp надо не так пробовать, надо добиться того, чтобы куча фрагментировалась - с этой целью надо сделать тучу рандомных аллокаций разного размера и также хаотично их удалять, только после этого проверьте скорость доступа к большому (!) массиву в куче. А иначе если куча не фрагментирована скорость конечно будет одинаковой.
    – Barmaley
    8 дек 2013 в 18:47
  • @Barmaley ♦, в любом случае весь массив в куче будет находиться в последовательных ячейках (естественно, в виртуальном адресном пространстве). Или Вы рассматриваете теоретчески возможню в cc-NUMA ситуацию, когда ОС выделяет процессу память (mmap-ом?) из физической памяти другого узла? -- К сожалению, во первых, сейчас у меня нет доступа к подобной системе, ну, а во вторых, я не очень представляю, как смоделировать в cc-NUMA такую устойчиво повторяемую ситуацию.
    – avp
    9 дек 2013 в 6:48
  • 2
    @Barmaley ♦, а физическая память всегда может быть фрагментирована, что в куче, что в стеке, что в коде. Но тут Вы заблуждаетесь, на скорость доступа (в обычных, а не NUMA архитектурах) это не влияет.
    – avp
    9 дек 2013 в 7:52
25

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

Как вам уже ответили "физически" - это транзисторы и конденсаторы. Так что сам вопрос скорее всего был поставлен не совсем корректно. Наверное, вы имели в виду что-то вроде - "Где находится куча и стек, как они устроены".

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

Вот пример организации сегментной памяти.

изображение взято из статьи http://jpauli.github.io/2015/04/16/segmentation-fault.html

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

Для более глубинного понимания, вам нужно ознакомиться с понятием "виртуальная память", а также со способами её организации "Сегментная адресация памяти","Страничная память"

Это кратко и немного по поводу представления виртуальной памяти в физическую.

По поводу устройства памяти внутри процесса:

внутри процесса

Снова вкратце, процесс думает, что ему выделяется цельное пространство, в котором уже размещаются области - "код","стек", "куча".
Стек заполняется и растет при вызове новых методов в свободную область в сторону УМЕНЬШЕНИЯ адресов. Куча растет наоборот в сторону УВЕЛИЧЕНИЯ адресов. За тем, чтобы памяти хватило снова-таки следит ОС.

Что хранится в блоке CODE, а также о много другом вы можете узнать из рекоммендованных мной материалов в этой ответе.

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

  1. Азы устройства памяти

  2. Известная статья "Что каждый программист должен знать о памяти"

  3. Организация виртуальной памяти. Таблицы страниц и прочее.

  4. Преобразование логического адреса в линейный.

  5. Устройство MMU

  6. Элемент списка

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

6

Лучше сказать так. Типичными операциями при работе с памятью являются её выделение/освобождение и чтение/запись. Операции выделения и освобождения памяти работают в куче медленнее.

Доступ к данным (чтение/запись) происходит практически с одинаковой скоростью. Практически - потому что в стеке типичным является доступ к значениям напрямую, а в куче - через указатель. Напрямую на самом деле тоже означает что-нибудь в духе ptr [esp+10h], т.е. чтобы получить данные, процессору нужно прибавить некоторое число к значению регистра esp и обратиться к памяти по этому адресу. Если (типичная ситуация) указатель на фрагмент памяти в куче лежит на стеке, то возникает два уровня косвенности - сначала надо получить значение указателя через "ptr [esp+10h]", а потом прочитать значение по этому адресу.

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

3
  • "Доступ к данным (чтение/запись) происходит практически с одинаковой скоростью" А если данные фрагментированы, то разве чтение их не замедлится?
    – voipp
    7 дек 2013 в 11:14
  • 2
    @voipp: Что означает «данные фрагментированы»? Если вы говорите о фрагментировании массива, то такого не бывает, массив всегда идёт подряд. Если у вы говорите об обращении к разным объектам, они могут быть разнесены в памяти и при их расположении в стеке, и в куче.
    – VladD
    7 дек 2013 в 11:57
  • 2
    Да, поддерживаю @VladD. Структура тоже не может быть фрагментирована. Если у вас на стеке структура с std::string, то содержимое строки, обычно, - уже в куче :) . Скорее надо задумываться о структурах данных, которые стоит использовать, а не об их расположении. Список, допустим, иногда может быть лучше массива, но он предрасположен к фрагментации (и больше памяти расходует)... 8 дек 2013 в 9:01

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.