Что быстрее:Распределение стека или распределение кучи

https://stackoverflow.com/questions/161053

03-07-2019
|

Вопрос

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

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

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

Это кажется мне чем-то, что, вероятно, будет сильно зависеть от компилятора.В частности, для этого проекта я использую Метроверкс компилятор для КПП архитектура.Понимание этой комбинации было бы очень полезно, но в целом, как обстоят дела с GCC и MSVC++?Разве распределение кучи не так высокоэффективно, как выделение стека?Нет ли разницы?Или различия настолько незначительны, что микрооптимизация становится бессмысленной.

Решение

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

Кроме того, стек против.куча — это не только фактор производительности;это также многое говорит вам об ожидаемом времени жизни объектов.

Другие советы

Стек работает намного быстрее.В большинстве архитектур он буквально использует только одну инструкцию, например.на х86:

sub esp, 0x10

(Это перемещает указатель стека вниз на 0x10 байт и тем самым «выделяет» эти байты для использования переменной.)

Конечно, размер стека очень и очень конечен, и вы быстро это поймете, если злоупотребляете распределением стека или пытаетесь использовать рекурсию :-)

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

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

Честно говоря, написать программу для сравнения производительности тривиально:

#include <ctime>
#include <iostream>

namespace {
    class empty { }; // even empty classes take up 1 byte of space, minimum
}

int main()
{
    std::clock_t start = std::clock();
    for (int i = 0; i < 100000; ++i)
        empty e;
    std::clock_t duration = std::clock() - start;
    std::cout << "stack allocation took " << duration << " clock ticks\n";
    start = std::clock();
    for (int i = 0; i < 100000; ++i) {
        empty* e = new empty;
        delete e;
    };
    duration = std::clock() - start;
    std::cout << "heap allocation took " << duration << " clock ticks\n";
}

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

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

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

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

Если бы меня заботила наносекундная точность, я бы не использовал std::clock().Если бы я хотел опубликовать результаты в качестве докторской диссертации, я бы уделил этому больше внимания и, вероятно, сравнил бы GCC, Tendra/Ten15, LLVM, Watcom, Borland, Visual C++, Digital Mars, ICC и другие компиляторы.На самом деле выделение кучи занимает в сотни раз больше времени, чем выделение стека, и я не вижу ничего полезного в дальнейшем исследовании этого вопроса.

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

Добавьте элемент данных в empty, и получить доступ к этому элементу данных в цикле;но если я когда-либо читаю только элемент данных, оптимизатор может выполнить постоянное свертывание и удалить цикл;если я когда-либо пишу только в элемент данных, оптимизатор может пропустить все, кроме самой последней итерации цикла.Кроме того, вопрос заключался не в «распределении стека и доступе к данным по сравнению с распределением стека и доступом к данным».Распределение кучи и доступ к данным».
Объявить e volatile, но volatile часто компилируется неправильно (PDF).
Возьмите адрес e внутри цикла (и, возможно, присвоить его переменной, которая объявлена extern и определено в другом файле).Но даже в этом случае компилятор может заметить, что — по крайней мере, в стеке — e всегда будут выделяться по одному и тому же адресу памяти, а затем выполнять постоянное свертывание, как в (1) выше.Я получаю все итерации цикла, но объект никогда не выделяется.

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

На моей машине, использующей g++ 3.4.4 в Windows, я получаю «0 тактов» для выделения стека и кучи для любого распределения меньше 100 000, и даже тогда я получаю «0 тактов» для выделения стека и «15 тактов» "для распределения кучи.Когда я измеряю 10 000 000 выделений, выделение стека занимает 31 такт, а распределение кучи — 1562 такта.

Да, оптимизирующий компилятор может исключить создание пустых объектов.Если я правильно понимаю, это может даже исключить весь первый цикл.Когда я увеличил количество итераций до 10 000 000, распределение стека заняло 31 такт, а распределение кучи — 1562 такта.Я думаю, можно с уверенностью сказать, что, не сообщая g++ оптимизировать исполняемый файл, g++ не исключил конструкторы.

За годы, прошедшие с тех пор, как я написал это, предпочтение Stack Overflow отдавалось публикации производительности оптимизированных сборок.В целом я считаю это правильным.Однако я по-прежнему считаю глупым просить компилятор оптимизировать код, когда вы на самом деле не хотите, чтобы этот код оптимизировался.Мне кажется, это очень похоже на доплату за парковку, но отказ от передачи ключей.В данном конкретном случае я не хочу, чтобы оптимизатор работал.

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

#include <cstdio>
#include <chrono>

namespace {
    void on_stack()
    {
        int i;
    }

    void on_heap()
    {
        int* i = new int;
        delete i;
    }
}

int main()
{
    auto begin = std::chrono::system_clock::now();
    for (int i = 0; i < 1000000000; ++i)
        on_stack();
    auto end = std::chrono::system_clock::now();

    std::printf("on_stack took %f seconds\n", std::chrono::duration<double>(end - begin).count());

    begin = std::chrono::system_clock::now();
    for (int i = 0; i < 1000000000; ++i)
        on_heap();
    end = std::chrono::system_clock::now();

    std::printf("on_heap took %f seconds\n", std::chrono::duration<double>(end - begin).count());
    return 0;
}

отображает:

on_stack took 2.070003 seconds
on_heap took 57.980081 seconds

в моей системе при компиляции с помощью командной строки cl foo.cc /Od /MT /EHsc.

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

on_stack took 0.000000 seconds
on_heap took 51.608723 seconds

Не потому, что выделение стека на самом деле происходит мгновенно, а потому, что любой полуприличный компилятор может это заметить. on_stack не делает ничего полезного и его можно оптимизировать.GCC на моем ноутбуке с Linux также замечает, что on_heap не делает ничего полезного, а также оптимизирует его:

on_stack took 0.000003 seconds
on_heap took 0.000002 seconds

Интересную вещь я узнал о Stack vs.Распределение кучи на процессоре Xbox 360 Xenon, которое также может применяться к другим многоядерным системам, заключается в том, что распределение в куче приводит к вводу критической секции для остановки всех других ядер, чтобы распределение не конфликтовало.Таким образом, в узком цикле распределение стека было способом использовать массивы фиксированного размера, поскольку оно предотвращало зависания.

Это может быть еще одним ускорением, которое следует учитывать, если вы пишете код для многоядерности/многопроцессности, поскольку распределение вашего стека будет доступно только для ядра, на котором выполняется ваша ограниченная функция, и это не повлияет на другие ядра/ЦП.

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

Также я согласен с Торбьёрном Гюллебрингом относительно ожидаемого времени жизни объектов.Хорошая точка зрения!

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

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

В 32-битных операционных системах с несколькими потоками стек часто довольно ограничен (хотя обычно составляет не менее нескольких МБ), поскольку адресное пространство необходимо разделить, и рано или поздно один стек потоков столкнется с другим.В однопоточных системах (в любом случае однопоточный Linux glibc) ограничение гораздо меньше, поскольку стек может просто расти и расти.

В 64-битных операционных системах достаточно адресного пространства, чтобы сделать стеки потоков достаточно большими.

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

Иногда распределение стека требует добавления страниц виртуальной памяти.Добавление новой страницы обнуленной памяти не требует чтения страницы с диска, поэтому обычно это все равно будет намного быстрее, чем поиск в куче (особенно если часть кучи также была выгружена).В редкой ситуации (и вы могли бы построить такой пример) в части кучи, которая уже находится в ОЗУ, просто оказывается достаточно места, но для выделения новой страницы для стека приходится ждать, пока будет записана какая-то другая страница. на диск.В этой редкой ситуации куча работает быстрее.

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

Стек имеет ограниченную емкость, а куча — нет.Типичный стек процесса или потока составляет около 8 КБ.Вы не можете изменить размер после его выделения.

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

И самое главное, вы не можете заранее предсказать всю цепочку вызовов функций.Таким образом, выделение всего лишь 200 байт с вашей стороны может вызвать переполнение стека.Это особенно важно, если вы пишете библиотеку, а не приложение.

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

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

Это во много раз быстрее, чем выделение объекта при каждом вызове операции.

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

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

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

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

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

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

Однако существуют более серьезные проблемы, связанные с общей производительностью стека по сравнению с другими системами.Распределение на основе кучи (или, говоря немного лучше, локальное или локальное распределение).внешнее распределение).Обычно выделение кучи (внешнее) происходит медленно, поскольку оно имеет дело со многими различными типами выделения и шаблонами выделения.Уменьшение области действия используемого вами распределителя (сделание его локальным для алгоритма/кода) приведет к увеличению производительности без каких-либо серьезных изменений.Добавление лучшей структуры к вашим шаблонам распределения, например принудительное упорядочивание LIFO для пар распределения и освобождения, также может повысить производительность вашего распределителя за счет более простого и структурированного использования распределителя.Или вы можете использовать или написать распределитель, настроенный для вашего конкретного шаблона распределения;большинство программ часто выделяют несколько дискретных размеров, поэтому куча, основанная на резервном буфере нескольких фиксированных (предпочтительно известных) размеров, будет работать очень хорошо.Именно по этой причине Windows использует кучу с низкой фрагментацией.

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

Распределение стека занимает пару инструкций, тогда как самый быстрый известный мне распределитель кучи RTOS (TLSF) использует в среднем порядка 150 инструкций.Кроме того, распределение стека не требует блокировки, поскольку оно использует локальное хранилище потоков, что является еще одним огромным выигрышем в производительности.Таким образом, распределение стека может быть на 2–3 порядка быстрее в зависимости от того, насколько многопоточной является ваша среда.

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

По поводу такой оптимизации следует сделать общий вывод.

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

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

Только если вы обнаружите, что он тратит много времени на распределение ваших объектов в куче, их размещение в стеке будет заметно быстрее.

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

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

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

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

class Foo {
public:
    Foo(int a) {

    }
}
int func() {
    int a1, a2;
    std::cin >> a1;
    std::cin >> a2;

    Foo f1(a1);
    __asm push a1;
    __asm lea ecx, [this];
    __asm call Foo::Foo(int);

    Foo* f2 = new Foo(a2);
    __asm push sizeof(Foo);
    __asm call operator new;//there's a lot instruction here(depends on system)
    __asm push a2;
    __asm call Foo::Foo(int);

    delete f2;
}

В ассембе было бы так.Когда ты в func, f1 и указатель f2 был выделен в стеке (автоматизированное хранилище).И кстати, Фу f1(a1) не имеет никакого влияния инструкций на указатель стека (esp), было выделено, если func хочет получить члена f1, инструкция примерно такая: lea ecx [ebp+f1], call Foo::SomeFunc().Еще одна вещь, которую выделяет стек, может заставить кого-то подумать, что память — это что-то вроде FIFO, FIFO просто произошло, когда вы заходите в какую-то функцию, если вы находитесь в функции и выделяете что-то вроде int i = 0, никакого толчка не произошло.

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

Операционная система поддерживает части свободной памяти в виде связанного списка с полезными данными, состоящими из указателя на начальный адрес свободной части и размера свободной части.Чтобы выделить X байт памяти, просматривается список ссылок и последовательно просматривается каждая нота, проверяя, равен ли ее размер хотя бы X.Когда найдена часть размера P >= X, P разбивается на две части с размерами X и P-X.Связанный список обновляется, и возвращается указатель на первую часть.

Как видите, распределение кучи зависит от многих факторов, таких как объем запрашиваемой памяти, ее фрагментация и т. д.

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

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

Поскольку вы упомянули Metrowerks и PPC, я думаю, вы имеете в виду Wii.В этом случае память имеет большое значение, и использование метода выделения стека, где это возможно, гарантирует, что вы не будете тратить память на фрагменты.Конечно, это требует гораздо большей осторожности, чем «обычные» методы выделения кучи.Целесообразно оценить компромиссы для каждой ситуации.

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

Теперь пример, где стек нельзя использовать:

Proc P
{
  pointer x;
  Proc S
  {
    pointer y;
    y = allocate_some_data();
    x = y;
  }
}

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

Проблемы, характерные для языка 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, предоставляемом размещенной средой (например,время выполнения, предоставляемое ОС).В отличие от целей хранения автоматических объектов для вызовов функций, такие выделения являются универсальными, поэтому они не будут иметь структуру кадра, такую как стек.Традиционно они выделяют пространство из хранилища пула, называемое куча (или несколько куч).В отличие от «стека», понятие «куча» здесь не указывает на используемую структуру данных; он получен из ранних реализаций языка несколько десятилетий назад..(Кстати, стек вызовов обычно выделяется из кучи с фиксированным или заданным пользователем размером средой при запуске программы или потока.) Характер вариантов использования делает выделение и освобождение из кучи гораздо более сложным (чем выталкивание или извлечение кадры стека), и вряд ли их можно напрямую оптимизировать аппаратно.

Влияние на доступ к памяти

Обычное распределение стека всегда помещает новый кадр сверху, поэтому он имеет довольно хорошую локальность.Это удобно для кэширования.OTOH, память, выделенная случайным образом в свободном хранилище, не имеет такого свойства.Начиная с ISO C++17, существуют шаблоны ресурсов пула, предоставляемые <memory>.Прямая цель такого интерфейса — обеспечить близкое расположение результатов последовательных выделений в памяти.Это подтверждает тот факт, что эта стратегия, как правило, хороша для производительности с современными реализациями, например.быть дружелюбным к кэшированию в современных архитектурах.Речь идет о производительности доступ скорее, чем распределение, хотя.

Параллелизм

Ожидание одновременного доступа к памяти может иметь разные последствия для стека и кучи.В реализации C++ стек вызовов обычно принадлежит исключительно одному потоку выполнения.OTOH, часто бывают кучи общий среди потоков процесса.Для таких куч функции выделения и освобождения должны защищать общую внутреннюю структуру административных данных от гонки данных.В результате выделение и освобождение кучи может иметь дополнительные издержки из-за операций внутренней синхронизации.

Эффективность использования пространства

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

Ограничения распределения стека

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

Во-первых, невозможно выделить в стеке пространство с размером, указанным во время выполнения, переносимым способом с помощью ISO C++.Существуют расширения, предоставляемые такими реализациями, как alloca и VLA (массив переменной длины) G++, но есть причины избегать их использования.(IIRC, исходный код Linux недавно удалил использование VLA.) (Также обратите внимание, что в ISO C99 есть VLA, но в ISO C11 поддержка необязательна.)

Во-вторых, не существует надежного и портативного способа обнаружения исчерпания пространства стека.Это часто называют переполнением стека (хм, этимология этого сайта), но, скорее, «переполнением стека».На самом деле это часто приводит к некорректному доступу к памяти, и тогда состояние программы искажается (... или, что еще хуже, появляется дыра в безопасности).Фактически, в ISO C++ нет понятия стека и делает его неопределенным поведением, когда ресурс исчерпан.Будьте осторожны с тем, сколько места следует оставить для автоматических объектов.

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

Тем не менее, иногда желательны глубокие рекурсивные вызовы.В реализациях языков, требующих поддержки несвязанных активных вызовов (глубина вызова ограничена только общим объемом памяти), это невозможный использовать собственный стек вызовов непосредственно в качестве записи активации целевого языка, как в типичных реализациях C++.Например, СМЛ/Нью-Джерси явно выделяет кадры в куче и использует кактусы.Сложное распределение таких кадров записи активации обычно происходит не так быстро, как кадры стека вызовов.Однако при дальнейшей реализации языков с правильная хвостовая рекурсия, прямое выделение стека на объектном языке (то есть «объект» в языке хранится не в виде ссылок, а в виде примитивных значений, которые могут быть взаимно однозначно сопоставлены с неразделяемыми объектами C++) еще сложнее с большим снижением производительности в общий.При использовании C++ для реализации таких языков трудно оценить влияние на производительность.

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

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

Кетан

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

Скажите следующую функцию:

  int f(int i)
  {
      if (i > 0)
      {   
          int array[1000];
      }   
  }

Ниже приведен код генерации:

  __Z1fi:
  Leh_func_begin1:
      pushq   %rbp
  Ltmp0:
      movq    %rsp, %rbp
  Ltmp1:
      subq    $**3880**, %rsp <--- here we have the array allocated, even the if doesn't excited.
  Ltmp2:
      movl    %edi, -4(%rbp)
      movl    -8(%rbp), %eax
      addq    $3880, %rsp
      popq    %rbp
      ret 
  Leh_func_end1:

Поэтому независимо от того, сколько у вас локальных переменных (даже внутри if или switch), просто 3880 изменится на другое значение.Если у вас нет локальной переменной, эту инструкцию просто нужно выполнить.Таким образом, выделение локальной переменной не требует накладных расходов.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow