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

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

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

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

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

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

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

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

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

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

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

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

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

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

На моей машине, используя g ++ 3.4.4 в Windows, я получаю «0 тактов» как для размещения в стеке, так и в куче для всего, что меньше 100000 выделений, и даже тогда я получаю «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

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

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

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

Также я согласен с Torbjörn Gyllebring об ожидаемом сроке службы объектов. Хорошая точка зрения!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проблемы, специфичные для языка 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) на значение, не меньшее требуемого размера кадра. Затем кадр называется выделеннымкогда указатель стека после операций. Параметры функций также могут передаваться в кадр стека, в зависимости от соглашения о вызове, используемого для вызова. Кадр может содержать память автоматических объектов (возможно, включая параметры), указанных в исходном коде C ++. В смысле таких реализаций эти объекты «выделяются». Когда элемент управления выходит из вызова функции, кадр больше не нужен, он обычно освобождается путем восстановления указателя стека обратно в состояние перед вызовом (сохраненное ранее в соответствии с соглашением о вызовах). Это можно рассматривать как «освобождение». Эти операции фактически делают запись активации структурой данных LIFO, поэтому ее часто называют « стеком (вызова) ».

Поскольку большинство реализаций C ++ (особенно те, которые нацелены на собственный код уровня ISA и используют язык ассемблера в качестве непосредственного вывода), используют подобные стратегии, подобные этой, такая запутанная схема «выделения» популярна. Такое распределение (а также освобождение) тратит машинные циклы, и это может быть дорогостоящим, когда (неоптимизированные) вызовы происходят часто, даже если современные микроархитектуры ЦП могут иметь сложные оптимизации, реализованные аппаратно для общего шаблона кода (например, с использованием составлять движок во внедрении PUSH/ POPинструкции).

Но в любом случае, в общем, верно, что стоимость выделения кадров стека значительно меньше, чем вызов функции распределения, работающей со свободным хранилищем (если она полностью не оптимизирована) , которая сама может иметь сотни (если не миллионы). :-) операции по поддержанию указателя стека и других состояний. Функции распределения обычно основаны на API, предоставляемом размещенной средой (например, среда выполнения, предоставляемая ОС). В отличие от цели хранения автоматических объектов для вызовов функций, такие распределения являются универсальными, поэтому они не будут иметь структуру кадра, как стек. Традиционно они выделяют пространство из хранилища пула, называемого кучей (или несколькими кучами). В отличие от «стека», понятие «куча» здесь не указывает на используемую структуру данных;это получено из ранних языковых реализаций десятилетия назад, (Кстати, стек вызовов обычно выделяется с фиксированным или заданным пользователем размером из кучи средой при запуске программы или потока.) Характер вариантов использования делает распределение и освобождение из кучи гораздо более сложным (чем push или pop of кадры стека), и вряд ли можно напрямую оптимизировать аппаратно.

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

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

совпадение

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

Космическая эффективность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например, если вы выделяете что-то в стеке, а затем помещаете это в контейнер, было бы лучше разместить его в куче и сохранить указатель в контейнере (например, с помощью 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;
}

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

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

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

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

Как правило, распределение стека происходит быстрее, чем распределение кучи, как упоминалось почти в каждом ответе выше. Push или pop стека - это 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 может фактически указывать на эти новые данные.

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

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

Ketan

Я хотел бы сказать, что на самом деле код, сгенерированный 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 изменится на другое значение. Если у вас не было локальной переменной, эту инструкцию просто нужно выполнить. Так что выделите локальную переменную без накладных расходов.