сравнение производительности доступа к данным в куче и стеке

Question

Широко известен здравый смысл, что для большинства алгоритмов распределение и освобождение данных в стеке происходит намного быстрее, чем в куче. В C ++ разница в коде равна

double foo[n*n]

против

double* foo = new int[n*n]

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

foo[i]

Код должен работать на нескольких разных архитектурах, поэтому попытка измерения не будет работать.

Answer 1

Могут быть (сильно зависящие от системы) проблемы с локальностью кэша и пропусками чтения / записи.Если вы запускаете вашу программу в стеке и данных кучи, то вполне возможно (в зависимости от вашей архитектуры кеша), что вы столкнетесь с большим количеством промахов кеша, чем если бы вы запустили ее полностью в одной непрерывной областистек.Вот статья Эндрю Аппеля (из SML / NJ) и Чжуна Шао, посвященная этой проблеме, где они исследуют именно это, потому что распределение стека / кучи является темой для реализации функциональных языков:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.3778

Они обнаружили некоторые проблемы с производительностью из-за ошибок записи, но предположили, что они будут решены с помощью достижений в кэшировании.

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

Answer 2

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

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

• Само выделение стека немного дешевле, чем выделение кучи, потому что распределение проще

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

Измерение этих эффектов, по крайней мере, сложно.

Рекомендация : производительность здесь не решающая. Портативность и масштабируемость рекомендуют использовать кучу для всех, кроме очень небольших объемов данных.

Answer 3

Стек будет в кеше ЦП чаще, поэтому в некоторых (большинстве?) Случаях он может быть быстрее.

Но, возможно, самый точный ответ: это зависит ...

Answer 4

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