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

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

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

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

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

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

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

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

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

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

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

Выделение стека Usually просто состоит из вычитания из регистра указателя вершины стека. Это - тонны быстрее, чем поиск "кучи".

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

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

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

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

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

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

Также я соглашаюсь с TorbjГ¶rn Gyllebring об ожидаемом времени жизни объектов. Положительная сторона!

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

sub esp, 0x10

(Который спускает указатель вершины стека 0x10 байтами и таким образом "выделяет" те байты для использования переменной.)

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

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

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

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

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

#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++, Цифровой Марс, ICC и другие компиляторы. Как это, выделение "кучи" занимает сотни времен дольше, чем выделение стека, и я не вижу ничего полезного об исследовании вопроса дальше.

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

1. Добавляют элемент данных к empty, и доступ что элемент данных в цикле; но если я только когда-либо читал из элемента данных, оптимизатор может сделать сворачивание констант и удалить цикл; если я только когда-либо пишу в элемент данных, оптимизатор может пропустить все кроме самого последнего повторения цикла. Кроме того, вопросом не было "выделение стека и доступ к данным по сравнению с выделением "кучи" и доступ к данным".

2. Объявляют e volatile, , но volatile часто компилируется неправильно (PDF).

3. Берут адрес [1 110] внутренняя часть цикл (и, возможно, присвойте его переменной, которая объявляется extern и определяется в другом файле). Но даже в этом случае, компилятор может заметить, что - на стеке, по крайней мере - e будет всегда выделяться в том же адресе памяти, и затем делать сворачивание констант как в (1) выше. Я получаю все повторения цикла, но объект на самом деле никогда не выделяется.

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

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

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

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

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

#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

Существует общая точка, которая будет сделана о такой оптимизации.

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

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

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

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

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

Ketan

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

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

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

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

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

, Как Вы видите, выделение "кучи" зависит от факторов мая как то, сколько памяти Вы запрашиваете, насколько фрагментированный память и так далее.

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

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

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

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

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

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

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

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