Относящиеся к языку C ++
Прежде всего, нет так называемого выделения "стека" или "кучи", предписанного C ++ . Если вы говорите об автоматических объектах в области видимости блока, они даже не «выделяются». (Кстати, длительность автоматического хранения в C определенно НЕ совпадает с «распределенной»; последняя является «динамической» на языке C ++.) И динамически выделенная память находится в свободном хранилище , не обязательно в «куча», хотя последний часто является (по умолчанию) реализацией .
Хотя согласно абстрактным семантическим правилам автоматические объекты по-прежнему занимают память, соответствующая реализация C ++ может игнорировать этот факт, когда она может доказать, что это не имеет значения (когда она не меняет наблюдаемого поведения программы). Это разрешение предоставляется правилом «как будто» в ISO C ++, которое также является общим условием, допускающим обычную оптимизацию (и в ISO C также существует почти такое же правило). Помимо правила «как будто», ISO C ++ также имеет правила копирования, позволяющие пропускать определенные создания объектов. При этом задействованные вызовы конструктора и деструктора опускаются. В результате автоматические объекты (если таковые имеются) в этих конструкторах и деструкторах также исключаются по сравнению с наивной абстрактной семантикой, подразумеваемой исходным кодом.
С другой стороны, бесплатное распределение магазина - это определенно «распределение» по замыслу. В соответствии с правилами ISO C ++ такое распределение может быть достигнуто путем вызова функции выделения . Однако, начиная с ISO C ++ 14, существует новое (не как если бы) правило, позволяющее объединять вызовы функций глобального распределения (т. Е. ::operator new) в определенных случаях. Поэтому части операций динамического размещения также могут быть недоступны, как в случае автоматических объектов.
Функции распределения выделяют ресурсы памяти. Объекты могут быть дополнительно распределены на основе распределения с использованием распределителей. Для автоматических объектов они представляются непосредственно - хотя к базовой памяти можно получить доступ и использовать ее для предоставления памяти другим объектам (путем размещения new), но это не имеет большого смысла в качестве свободного хранилища, потому что нет никакого способа переместить ресурсы в другое место.
Все остальные проблемы выходят за рамки C ++. Тем не менее, они могут быть значительными.
О реализациях C ++
C ++ не предоставляет записи активации активации или некоторые виды первоклассных продолжений (например, знаменитым call/cc), нет никакого способа напрямую манипулировать кадрами записи активации - там, где реализация должна размещать автоматические объекты , Если нет (непереносимых) взаимодействий с базовой реализацией («нативный» непереносимый код, такой как код встроенной сборки), пропуск базового распределения кадров может быть довольно тривиальным. Например, когда вызываемая функция является встроенной, кадры могут быть эффективно объединены с другими, поэтому нет способа показать, что такое «распределение».
Однако, как только соблюдается взаимодействие, все становится сложным. Типичная реализация C ++ предоставляет возможность взаимодействия на ISA (архитектура с набором инструкций) с некоторыми соглашениями о вызовах в качестве двоичной границы, совместно используемой с собственным (машинным) уровнем кода ISA. Это было бы явно дорогостоящим, в частности, при поддержании указателя стека , который часто напрямую хранится в регистре уровня ISA (возможно, с конкретными машинными инструкциями для доступа). Указатель стека указывает границу верхнего кадра (в данный момент активного) вызова функции. Когда вводится вызов функции, необходим новый кадр, и указатель стека добавляется или вычитается (в зависимости от соглашения ISA) на значение, не меньшее требуемого размера кадра. Кадр затем называется , выделенным , когда указатель стека после операций. Параметры функций могут также передаваться в кадр стека, в зависимости от соглашения о вызове, используемого для вызова. Кадр может содержать память автоматических объектов (возможно, включая параметры), указанных в исходном коде C ++. В смысле таких реализаций эти объекты «выделяются». Когда элемент управления выходит из вызова функции, кадр больше не нужен, он обычно освобождается путем восстановления указателя стека обратно в состояние перед вызовом (сохраненное ранее в соответствии с соглашением о вызовах). Это можно рассматривать как «освобождение». Эти операции делают запись активации эффективной структурой данных LIFO, поэтому ее часто называют " стеком (вызова) ". Указатель стека эффективно указывает верхнюю позицию стека.
Поскольку большинство реализаций C ++ (особенно те, которые нацелены на собственный код уровня ISA и используют язык ассемблера в качестве непосредственного вывода), используют подобные стратегии, подобные этой, такая запутанная схема «выделения» популярна. Такое распределение (а также освобождение) тратит машинные циклы, и это может быть дорого, когда (неоптимизированные) вызовы происходят часто, даже если современные микроархитектуры ЦП могут иметь сложные оптимизации, реализованные аппаратными средствами для общего шаблона кода (например, с использованием стековый движок в реализации PUSH / POP инструкций).
Но в любом случае, в общем случае это правда, что стоимость выделения кадров стека значительно меньше, чем вызов функции распределения, работающей со свободным хранилищем (если только она полностью не оптимизирована) , которая сама по себе может содержать сотни (если не миллионы :-) операций для поддержки указателя стека и других состояний. Функции распределения обычно основаны на API, предоставляемом размещенной средой (например, среда выполнения, предоставляемая ОС). В отличие от цели хранения автоматических объектов для вызовов функций, такие распределения являются универсальными, поэтому они не будут иметь структуру кадра, как стек. Традиционно они выделяют пространство из хранилища пула, которое называется heap (или несколько куч). В отличие от «стека», понятие «куча» здесь не указывает на используемую структуру данных; он получен из ранних языковых реализаций десятилетия назад . (Кстати, стек вызовов обычно выделяется с фиксированным или заданным пользователем размером из кучи средой при запуске программы или потока.) Характер сценариев использования делает распределение и освобождение из кучи гораздо более сложным (чем push или pop of стековые кадры), и вряд ли можно напрямую оптимизировать аппаратно.
Влияние на доступ к памяти
Обычное выделение стека всегда помещает новый фрейм сверху, поэтому он имеет довольно хорошую локализацию. Это удобно для кеширования. OTOH, память, случайно распределенная в бесплатном магазине, не имеет такого свойства. Начиная с ISO C ++ 17, существуют шаблоны ресурсов пула, предоставляемые <memory>. Непосредственная цель такого интерфейса - сделать так, чтобы результаты последовательных распределений были близки друг другу в памяти. Это признает тот факт, что эта стратегия в целом хороша для производительности с современными реализациями, например быть дружественным к кешу в современных архитектурах. Это касается производительности доступа , а не выделения , хотя.
параллелизм
Ожидание одновременного доступа к памяти может иметь различные эффекты между стеком и кучами. Стек вызовов обычно принадлежит только одному потоку выполнения в реализации C ++. OTOH, кучи часто совместно используются между потоками в процессе. Для таких куч функции распределения и освобождения должны защищать общую внутреннюю административную структуру данных от гонки данных. В результате выделения кучи и освобождения могут иметь дополнительные издержки из-за операций внутренней синхронизации.
Эффективность использования пространства
Из-за особенностей сценариев использования и внутренних структур данных, кучи могут страдать от фрагментации внутренней памяти , а стек - нет. Это не оказывает прямого влияния на производительность выделения памяти, но в системе с виртуальной памятью низкая эффективность использования пространства может ухудшить общую производительность доступа к памяти. Это особенно ужасно, когда жесткий диск используется для подкачки физической памяти. Это может вызвать довольно длительную задержку - иногда миллиарды циклов.
Ограничения распределения стека
Хотя выделение стека часто превосходит производительность по сравнению с выделением кучи в реальности, это, конечно, не означает, что распределение стека всегда может заменить распределение кучи.
Во-первых, нет способа выделить пространство в стеке с размером, указанным во время выполнения, переносимым способом с ISO C ++. Существуют расширения, предоставляемые реализациями, такими как alloca и VLA (массив переменной длины) G ++, но есть причины избегать их использования. (IIRC, источник Linux недавно исключает использование VLA.) (Также обратите внимание, что ISO C99 имеет VLA, но ISO C11 делает поддержку необязательной.)
Во-вторых, нет надежного и портативного способа обнаружения исчерпания пространства стека. Это часто называют переполнением стека (хм, этимология этого сайта), но, скорее всего, «переполнением стека». В действительности это часто приводит к недопустимому доступу к памяти, а затем состояние программы портится (... или, что еще хуже, дыра в безопасности). На самом деле ISO C ++ не имеет понятия стека и делает его неопределенным поведением, когда ресурс исчерпан . Будьте осторожны с тем, сколько места нужно оставить для автоматических объектов.
Если пространство стека исчерпано, в стеке выделено слишком много объектов, что может быть вызвано слишком большим количеством активных вызовов функций или неправильным использованием автоматических объектов. Такие случаи могут указывать на наличие ошибок, например, рекурсивный вызов функции без правильных условий выхода.
Тем не менее, иногда требуются глубокие рекурсивные вызовы. В реализациях языков, требующих поддержки несвязанных активных вызовов (глубина вызовов ограничена только общим объемом памяти), невозможно использовать собственный стек вызовов непосредственно в качестве записи активации целевого языка, как в типичных реализациях C ++. Например, SML / NJ явно выделяет кадры в куче и использует стеки кактусов . Сложное распределение таких кадров записи активации обычно не так быстро, как кадры стека вызовов. Однако при дальнейшей реализации языков с правильной хвостовой рекурсией прямое выделение стека на языке объектов (то есть «объект» в языке сохраняется не как ссылки, а как примитивные значения, которые могут быть однозначными один, сопоставленный с неразделенными объектами C ++), еще более сложный, с большей потерей производительности в целом. При использовании C ++ для реализации таких языков сложно оценить влияние на производительность.