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

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

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

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

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

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

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

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

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

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

sub esp, 0x10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кетан

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Я хотел бы сказать, что на самом деле код генерируется 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    80, %rsp
      popq    %rbp
      ret 
  Leh_func_end1:

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

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, никакого нажатия не произошло.