Производительность между прочим Динамические массивы в стеке - PullRequest
Новая
       34

Производительность между прочим Динамические массивы в стеке

3 голосов
/ 08 января 2010

В концепции языков программирования,

Книга Себесты гласит, что (Девятое издание, 284):

Недостатком фиксированных динамических массивов кучи является то, что для выделения массива из стека требуется больше времени.

Как мы можем проанализировать это утверждение? В чем разница между фиксированными динамическими массивами и динамическими массивами. Что означает это фиксированное слово?

Ответы [ 4 ]

6 голосов
/ 08 января 2010

Выделение памяти из стека очень просто. Вам просто нужно настроить указатель стека. На x64 это одна инструкция: 

sub rsp, size

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

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

2 голосов
/ 08 января 2010

Ответ от ergosys имеет правильную терминологию. Вопрос - еще один пример того, почему я ненавижу Себесту.

Во многих современных системах при выделении объекта из кучи используются точно такие же инструкции, как при выделении из стека: тестируйте и увеличивайте указатель кучи. (Это правда, что объединить распределения стека проще, чем объединить распределения кучи, но это также возможно.) Компиляторы, которые выполняют такое распределение, включают Glorious Glasgow Haskell Compiler и Стандартный ML Нью-Джерси . SML / NJ был развернут в этом состоянии более 20 лет, так что вы думаете, что Sebesta, возможно, уже подхватил его.

Резюме: Себеста, как обычно, чрезмерно обобщает . Могут быть причины, чтобы предпочесть распределение стеков, но история намного сложнее, чем, кажется, понимает Себеста, или чем Мерада описывает в своем ответе. Хорошее место для начала с пониманием более глубокой истории - статья 1013 * Эндрю Аппеля о распределении стеков .

1 голос
/ 08 января 2010

Терминология происходит от трех ортогональных понятий:

  • Может ли размер массива измениться после его первоначального размещения или останется неизменным, навсегда, "фиксированным"
  • Где расположен массив: стек или куча памяти.
  • Если размер выделения определяется во время выполнения «динамически» или во время компиляции.
1 голос
/ 08 января 2010

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

Я не совсем разбираю конец предложения:

Недостатком фиксированных динамических массивов кучи является то, что для выделения массива из стека требуется больше времени.

Вы точно не выделяете кучу памяти «из стека».

...