Могут ли системы в целом быть более эффективными, чтобы избавиться от стеков и просто использовать кучу для управления памятью?

14

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

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

Темный тамплиер
источник
1
В C и C ++ вам нужно явно освободить память, которая была выделена в куче. Это не проще.
user16764
Я использовал реализацию C #, когда профилирование показало, что объекты стека размещаются в области, подобной куче, с ужасной сборкой мусора. Мое решение? Переместите все возможное (например, переменные цикла, временные переменные и т. Д.) В постоянную память кучи. Заставили программу съесть в 10 раз больше оперативной памяти и запустить в 10 раз быстрее.
Ималлетт
@IanMallett: я не понимаю вашего объяснения проблемы и решения. У вас есть ссылка с дополнительной информацией где-нибудь? Обычно я считаю, что распределение на основе стека происходит быстрее.
Фрэнк Хайлеман
@FrankHileman основная проблема была в следующем: используемая мною реализация C # имела крайне низкую скорость сборки мусора. «Решением» было сделать все переменные постоянными, чтобы во время выполнения не происходило никаких операций с памятью. Некоторое время назад я написал статью о разработке C # / XNA в целом, в которой также обсуждаются некоторые аспекты.
Ималлетт
@IanMallett: спасибо. Как бывший разработчик C / C ++, который в настоящее время в основном использует C #, мой опыт был совершенно другим. Я считаю, что библиотеки являются самой большой проблемой. Похоже, что платформа XBox360 была недоделана для разработчиков .net. Обычно, когда у меня возникают проблемы с сборкой мусора, я переключаюсь на пул. Это помогает.
Фрэнк Хилман

Ответы:

30

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

Полное избавление от стека ради упрощения языка программирования - это неправильный способ IMO. Лучшим подходом было бы абстрагировать различия, позволить компилятору выяснить, какой тип хранилища использовать, в то время как программист собирает более высокие конструкции уровня, которые ближе к тому, что думают люди, и на самом деле, языки высокого уровня, такие как C #, Java, Python и т. д., делают именно это. Они предлагают почти идентичный синтаксис для объектов, выделенных в куче, и выделенных в стеке примитивов («ссылочные типы» и «типы значений» в .NET lingo), либо полностью прозрачные, либо с несколькими функциональными отличиями, которые вы должны понимать, чтобы использовать язык правильно (но на самом деле вам не нужно знать, как стек и куча работают внутри).

tdammers
источник
2
ВАУ ЭТО БЫЛО ХОРОШО :) Действительно лаконично и информативно для начинающего!
Темный тамплиер
1
На многих процессорах стек обрабатывается аппаратно, что является проблемой вне языка, но играет большую роль во время выполнения.
Патрик Хьюз
@ Патрик Хьюз: Да, но куча также находится в аппаратном обеспечении, не так ли?
Темный тамплиер
@ Dark Что Патрик, вероятно, хочет сказать, так это то, что архитектуры типа x86 имеют специальные регистры для управления стеком и специальные инструкции для размещения или удаления чего-либо в / из стека. Это делает это довольно быстро.
FUZxxl
3
@Donal Fellows: все верно. Но дело в том, что у стеков и куч есть свои сильные и слабые стороны, и соответственно их использование даст наиболее эффективный код.
tdammers
8

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

DeadMG
источник
Что вы имеете в виду, когда говорите, что современные машины имеют аппаратную поддержку стека? Сам стек уже в аппаратном обеспечении, не так ли?
Темный тамплиер
1
В x86 есть специальные регистры и инструкции для работы со стеком. x86 не поддерживает кучи - такие вещи создаются ОС.
Пабби
8

нет

Площадь стека в C ++ невероятно быстрая по сравнению. Я не рискну, чтобы опытные разработчики C ++ были бы открыты для отключения этой функциональности.

С C ++ у вас есть выбор и контроль. Дизайнеры не были особенно склонны вводить функции, которые добавляли значительное время выполнения или пространство.

Осуществляя этот выбор

Если вы хотите создать библиотеку или программу, которая требует, чтобы каждый объект выделялся динамически, вы можете сделать это с помощью C ++. Он будет выполняться относительно медленно, но тогда вы сможете получить эту «модульность». Для остальных из нас модульность всегда является необязательной, вводите ее по мере необходимости, потому что оба требуются для хороших / быстрых реализаций.

альтернативы

Есть другие языки, которые требуют, чтобы хранилище для каждого объекта было создано в куче; это довольно медленно, так что это ставит под угрозу дизайн (программы реального мира) таким образом, что это хуже, чем необходимость изучать оба (IMO).

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

джастин
источник
На самом деле куча имеет ту же скорость, что и стек, но не имеет специализированной аппаратной поддержки для выделения. С другой стороны, есть способы многократно ускорить кучу (в зависимости от ряда условий, которые делают их методами только для экспертов).
Donal Fellows
@DonalFellows: аппаратная поддержка стеков не имеет значения. Важно знать, что всякий раз, когда что-либо выпущено, можно выпустить все, что было выделено после него. Некоторые языки программирования не имеют куч, которые могут независимо освобождать объекты, но вместо этого имеют только метод «освободить все, что выделено после».
суперкат
6

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

На самом деле снижение производительности, вероятно, будет значительным!

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

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

Чарльз Э. Грант
источник
5

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

fredoverflow
источник
Так в основном C ++ использует только кучу?
Темный тамплиер
2
@ Dark: что? Нет. Отсутствие стека в Simula вдохновило меня сделать это лучше.
fredoverflow
Ах, я понимаю, что вы имеете в виду сейчас! Спасибо +1 :)
Темный тамплиер
3

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

kylben
источник
2

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

Поскольку выделение стека почти не занимает времени, выделение даже в очень эффективной куче будет в 100 тысяч раз (если не более 1 миллиона раз) медленнее.

Теперь представьте, сколько локальных переменных и других структур данных использует типичное приложение. Каждое маленькое «я», которое вы используете в качестве счетчика цикла, выделяется в миллион раз медленнее.

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

DXM
источник
Когда вы говорите «представьте, сколько локальных переменных и других структур данных использует типичное приложение», на какие другие структуры данных вы конкретно ссылаетесь?
Темный тамплиер
1
Являются ли значения "100k" и "1M +" как-то научными? Или это просто способ сказать "много"?
Бруно Рейс
@Bruno - ИМХО числа 100К и 1М, которые я использовал, на самом деле являются консервативной оценкой, чтобы доказать свою точку зрения. Если вы знакомы с VS и C ++, напишите программу, которая выделяет 100 байтов в стеке, и напишите программу, которая выделяет 100 байтов в куче. Затем переключитесь в режим разборки и просто посчитайте количество инструкций по сборке, которое занимает каждое выделение. Операции с кучей, как правило, представляют собой несколько вызовов функций в Windows DLL, есть сегменты и связанные списки, а затем объединяются и другие алгоритмы. Со стеком это может сводиться к одной инструкции по сборке "add esp, 100" ...
DXM
2
"100к (если не 1М +) раз медленнее"? Это немного преувеличено. Пусть это будет на два порядка медленнее, возможно, на три, но это все. По крайней мере, мой Linux способен выполнять выделение памяти размером 100 МБ (+ некоторые окружающие инструкции) менее чем за 6 секунд на ядре i5, что не может превышать нескольких сотен инструкций на выделение - на самом деле, это почти наверняка меньше. Если он на шесть порядков медленнее, чем стек, то в реализации кучи ОС что-то не так. Конечно, с Windows что-то не так, но это ...
leftaroundout
1
Модераторы, вероятно, собираются убить всю эту цепочку комментариев. Так что вот в чем дело, я признаю, что фактические цифры были извлечены из моего ...., но давайте согласимся, что фактор действительно, очень большой и не буду больше комментировать :)
ДХМ
2

Возможно, вас заинтересует «Сборка мусора - это быстро, а стек - быстрее».

http://dspace.mit.edu/bitstream/handle/1721.1/6622/AIM-1462.ps.Z

Если я правильно прочитал, эти парни модифицировали компилятор C для выделения «кадров стека» в куче, а затем использовали сборку мусора для перераспределения кадров вместо выталкивания стека.

Выделенные стеком «кадры стека» решительно превосходят выделенные в куче «кадры стека».

Брюс Эдигер
источник
1

Как стек вызовов будет работать в куче? По сути, вы должны были бы выделить стек в куче в каждой программе, так почему бы не сделать это для OS +?

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

Pubby
источник
Строго говоря, «стек вызовов» не является обязательной функцией среды выполнения языка программирования. Например, простая реализация лениво оцененного функционального языка путем сокращения графов (который я кодировал) не имеет стека вызовов. Но стек вызовов является очень широко полезным и широко используемым методом, тем более что современные процессоры предполагают, что вы используете его, и оптимизированы для его использования.
Бен
@Ben - хотя это правда (и хорошо) абстрагировать такие вещи, как распределение памяти, от языка, это не меняет преобладающую сейчас архитектуру компьютера. Следовательно, ваш код сокращения графов все равно будет использовать стек при запуске - нравится вам это или нет.
Инго
@ Инго Не совсем в каком-то значимом смысле. Конечно, ОС инициализирует часть памяти, традиционно называемую «стеком», и там будет регистр, указывающий на это. Но функции в исходном языке не представляются в виде стековых кадров в порядке вызова. Выполнение функции целиком представлено манипулированием структурами данных в куче. Даже без использования оптимизации последнего вызова невозможно «переполнить стек». Вот что я имею в виду, когда говорю, что в «стеке вызовов» нет ничего фундаментального.
Бен
Я не говорю о функциях исходного языка, но о функциях интерпретатора (или чего-либо еще), которые фактически выполняют редукцию графа. Те будут нуждаться в стеке. Это очевидно, поскольку современные аппаратные средства не делают сокращение графика. Следовательно, ваш алгоритм сокращения графа в конечном итоге сопоставлен с машинной одой, и я уверен, что среди них есть вызовы подпрограмм. QED.
Инго
1

Требуются как стек, так и куча. Они используются в разных ситуациях, например:

  1. Распределение кучи имеет ограничение, что sizeof (a [0]) == sizeof (a [1])
  2. Распределение стека имеет ограничение, что sizeof (a) является постоянной времени компиляции
  3. Распределение кучи может делать циклы, графики и т. Д. Сложные структуры данных
  4. Распределение стека может сделать деревья размером во время компиляции
  5. Куча требует отслеживания владения
  6. Распределение стека и освобождение происходит автоматически
  7. Память кучи может быть легко передана из одной области в другую через указатели
  8. Память стека является локальной для каждой функции, и объекты необходимо перемещать в верхнюю область видимости, чтобы продлить срок их службы (или хранить внутри объектов, а не внутри функций-членов)
  9. Куча плохо влияет на производительность
  10. Стек довольно быстрый
  11. Объекты кучи возвращаются из функций через указатели, которые становятся собственниками. Или shared_ptrs.
  12. Стековые объекты возвращаются из функций по ссылкам, которые не становятся владельцами.
  13. Куча требует соответствия каждого нового с правильным видом удаления или удаления []
  14. Стековые объекты используют RAII и списки инициализации конструктора
  15. Объекты кучи могут быть инициализированы в любой точке внутри функции и не могут использовать параметры конструктора
  16. Объекты стека используют параметры конструктора для инициализации
  17. Куча использует массивы и размер массива может меняться во время выполнения
  18. Стек предназначен для отдельных объектов, а размер фиксируется во время компиляции.

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

ТР1
источник
1

Современные компьютеры имеют несколько уровней кэш-памяти в дополнение к большой, но медленной системе основной памяти. Можно сделать десятки обращений к самой быстрой кэш-памяти за время, необходимое для чтения или записи одного байта из системы основной памяти. Таким образом, доступ к одному местоположению в тысячу раз намного быстрее, чем доступ к 1000 (или даже 100) независимым местоположениям по одному. Поскольку большинство приложений многократно выделяют и освобождают небольшие объемы памяти вблизи вершины стека, места на вершине стека используются и используются повторно в огромном количестве, так что подавляющее большинство (более 99% в типичном приложении) доступ к стеку может быть обработан с использованием кеш-памяти.

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

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

Supercat
источник