Доступ к данным в куче быстрее, чем из стека?

Доступ к данным в куче быстрее, чем из стека?

Не по своей природе ... в каждой архитектуре, над которой я когда-либо работал, можно ожидать, что вся память процесса будет работать с одним и тем же набором скоростей, в зависимости от того, какой уровень кэш-памяти ЦП / ОЗУ / файл подкачки содержит текущие данные, и любые задержки синхронизации на аппаратном уровне, которые могут быть вызваны операциями с этой памятью, чтобы сделать ее видимой для других процессов, включить изменения других процессов/ЦП (ядра) и т. д.

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

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

• выделение – время, затрачиваемое программой на выделение и освобождение памяти, включая случайное выделение sbrk (или аналогичного) виртуального адреса по мере роста использования кучи.
• доступ — различия в инструкциях ЦП, используемых программой для доступа к глобальным переменным, стеку и куче, а также дополнительная косвенность через указатель времени выполнения при использовании данных из кучи,
• макет – некоторые структуры данных (контейнеры/коллекции) более удобны для кэширования (и, следовательно, быстрее), в то время как реализация некоторых из них общего назначения требует выделения кучи и может быть менее дружественной к кэшу.

Распределение и освобождение

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

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

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

Для данных на основе кучи библиотека распределения кучи среды выполнения должна сверяться со своими внутренними структурами данных и обновлять их, чтобы отслеживать, какие части блока (блоков) также называются пулом (пулами) кучи. памяти, которой он управляет, связаны с определенными указателями, которые библиотека предоставила приложению, пока приложение не освободит или не удалит память. Если для памяти кучи недостаточно виртуального адресного пространства, может потребоваться вызвать функцию ОС, например sbrk, чтобы запросить больше памяти (Linux также может вызвать mmap для создания резервной памяти для больших запросов памяти, а затем отменить отображение этой памяти на free/delete).

Доступ

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

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

Для доступа к куче и указатель, и память кучи должны находиться в регистрах, чтобы данные были доступны (поэтому больше требований к кешу ЦП, а в масштабе - больше промахов кеша/накладных расходов на ошибки).

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

Макет

Если в последовательных строках вашего исходного кода перечислены глобальные переменные, они будут расположены в смежных ячейках памяти (хотя и с возможным дополнением для целей выравнивания). То же самое верно для переменных на основе стека, перечисленных в той же функции. Это здорово: если у вас есть X байтов данных, вы вполне можете обнаружить, что — для N-байтовых строк кэша — они хорошо упакованы в память, доступ к которой можно получить с помощью X/N или X/N + 1 строк кэша. Вполне вероятно, что другое соседнее содержимое стека - аргументы функций, адреса возврата и т. д. - потребуется вашей программе примерно в то же время, поэтому кэширование очень эффективно.

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

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

Обсуждение вашего примера программы

В вашем примере вы сравниваете глобальную переменную с функциональной локальной (стековой/автоматической) переменной... куча не задействована. Память кучи поступает из new или malloc/realloc. Для динамической памяти проблема производительности, на которую стоит обратить внимание, заключается в том, что само приложение отслеживает, сколько памяти используется по каким адресам — записи обо всем, что требует некоторого времени для обновления, поскольку указатели на память раздаются new/malloc/ realloc, и еще некоторое время для обновления, так как указатели deleted или freed.

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

Примечание

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

Цитата из ответа Джеффа Хилла:

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

По этой теме доступна запись в блоге stack-allocation-vs-heap-allocation-performance-benchmark Который показывает эталонный показатель стратегий распределения. Тест написан на C и выполняет сравнение между попытками чистого выделения памяти и выделением с инициализацией памяти. При различных объемах общих данных выполняется количество циклов и измеряется время. Каждое выделение состоит из 10 различных блоков alloc/init/free разных размеров (общий размер показан на диаграммах).

Тест выполняется на процессоре Intel(R) Core(TM) i7-6600U, 64-разрядной версии Linux, 4.15.0-50-generic, исправления Spectre и Meltdown отключены.

Без инициализации:

С инициализацией:

В результате мы видим, что есть существенная разница в чистых аллокациях без инициализации данных. Стек быстрее, чем куча, но обратите внимание, что количество циклов очень велико.

Когда выделенные данные обрабатываются, разница между производительностью стека и кучи уменьшается. При 1 млн циклов malloc/init/free (или stack alloc) с 10 попытками выделения в каждом цикле стек всего на 8% опережает кучу по общему времени.

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

Во всех случаях ключом является местонахождение. Если доступ находится «рядом» с предыдущим доступом, вы значительно повышаете шансы найти его в одном из более быстрых мест: например, в кеше. В этом отношении помещение меньших объектов в стек может быть быстрее, потому что, когда вы обращаетесь к аргументам функции, вы получаете доступ к памяти стека (по крайней мере, с 32-разрядным процессором Intel — с более совершенными процессорами, аргументы чаще всего находятся в регистрах). Но это, вероятно, не будет проблемой, когда задействован массив.

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

Что бы это ни стоило, цикл в приведенном ниже коде, который просто читает и записывает в каждый элемент большого массива, последовательно работает в 5 раз быстрее на моей машине, когда массив находится в стеке, а не в куче (GCC, Windows 10, флаг -O3), даже сразу после перезагрузки (когда фрагментация кучи сведена к минимуму):

const int size = 100100100;
int vals[size]; // STACK
// int *vals = new int[size]; // HEAP
startTimer();
for (int i = 1; i < size; ++i) {
    vals[i] = vals[i - 1];
}
stopTimer();
std::cout << vals[size - 1];
// delete[] vals; // HEAP

Конечно, сначала пришлось увеличить размер стека до 400 МБ. Обратите внимание, что печать последнего элемента в конце необходима, чтобы компилятор не оптимизировал все подряд.

Учитывая, что переменные и массивы переменных, объявленные в куче, работают медленнее, это просто факт. Подумайте об этом таким образом;

Глобально созданные переменные выделяются один раз и освобождаются после закрытия программы. Для объекта кучи ваша переменная должна выделяться на месте каждый раз, когда функция запускается, и освобождается в конце функции.

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

Когда дело доходит до доступа к массиву, все они работают одинаково, блок памяти сначала выделяется элементами sizeof(DataType) *. Позже можно получить доступ ->

1 2 3 4 5 6 
^ entry point [0]
      ^ entry point [0]+3