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

Question

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

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

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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

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

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

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

Answer 5

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;
}

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

Answer 6

В отношении таких оптимизаций следует сделать общее замечание.

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

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

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

Answer 7

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

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

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

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

Answer 8

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

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

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

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

Answer 9

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

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

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

Answer 10

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

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

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