2015-05-12 6 views
12

Мне очень интересно узнать, какой предпочтительный метод распределения памяти static vs dynamic хорош для производительности (например, время работы), когда вы знаете точное количество объектов/элементов в C на Linux. Стоимость для небольшого количества объектов (небольшой объем памяти), а также для большого количества объектов (огромный объем памяти).Стоимость распределения статической памяти и распределения динамической памяти в C

e.g., type A[N] против type *A = malloc(sizeof(type) * N)

Пожалуйста, дайте мне знать. Спасибо.

Примечание: Мы можем сравнить это и, возможно, знать ответ. Но я хотел бы знать понятия, объясняющие различия в производительности между этими двумя методами распределения.

+2

Это две совершенно разные «затраты». Статическое распределение является «бесплатным» с точки зрения времени выполнения, а память потребляет, если не используется с умом.Динамика оптимальна с точки зрения использования памяти (опять же, если использовать ее разумно), но требует затрат времени на процессор. –

+2

Статическое распределение также имеет гораздо меньший размер, чем динамическое распределение. –

+1

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

ответ

10

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

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

В локальной области статические распределения выделяются в стеке. Это предполагает просто резервирование фиксированного количества байтов в стеке и происходит в течение постоянного времени на выделение. Размер стека очень ограничен.

Динамическая память должна быть выделена из кучи, и даже в лучшем случае для большинства распределений потребуется время, которое масштабируется более чем линейно с каждым распределением, например, n log n time или что-то еще.

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

@update: Как указано в комментариях ниже: распределения стека не являются технически статическими распределениями (но они являются выделениями с синтаксической формой, используемой в вопросе OP).

Также, говоря о «распределении времени», я рассматриваю общее время для управления памятью (выделение и освобождение).

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

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

Динамические распределители быть быстро Компромисс значительную эффективность памяти (например, приятель распределители округлить до следующего включения двух размеров блока, как 33K Alloc будет использовать 64k)

+0

Большое спасибо за ответ. Пожалуйста, воздержитесь от моего вопроса, поскольку мне нужны некоторые моменты, чтобы поддержать ответы. – samarasa

+6

Сложность алгоритмов распределения памяти кучи сильно варьируется. Обычные алгоритмы, такие как first-fit/best-fit, обычно линейны, если нет какой-либо умной структуры данных индексации. Двоичный приятель может быть постоянным временем для распределения и логарифмического для освобождения - и распределенных распределенных распределений с распределенным распределением памяти на основе бесплатных списков для определенного предопределенного размера (например, степеней 2). –

+0

Я действительно не думаю, что вы должны сказать, что пространство стека статически распределено , Он выделяется по мере необходимости, а затем освобождается - то есть не статично – pm100

4

Глобальная память обычно выделяется, когда ваша программа (или shared module/dll) загружает и предварительно заполняет свои начальные значения. Обычно это имеет собственную секцию памяти.

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

Когда используется malloc (в C) или новый (C++), память выделяется в куче/бесплатном хранилище. Это любой блок памяти с номером. Когда требуется больше памяти, чем было уже выделено, malloc переходит к ядру, чтобы запросить больше памяти из системы. Обычно malloc будет использовать освобожденную память, уже полученную из системы.

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

  1. Куча должна выделять и освобождать любой объем памяти в любом порядке. Старые алгоритмы, используемые для перемещения списка освобожденных блоков до тех пор, пока не будет найден подходящий размер. Поскольку память может быть сильно фрагментирована, это может быть медленным. Если куча используется в нескольких потоках, необходимо обеспечить некоторую блокировку. Многое было сделано для улучшения этой ситуации, и современные кучи jemalloc и tcmalloc действительно улучшают ситуацию. Однако не рассчитывайте на это.
  2. Если требуемая память не может быть выделена из того, что уже управляется распределителем кучи, распределителю кучи нужно будет запросить ядро ​​для большей памяти. (В unix это делается с помощью системных вызовов mmap или sbrk). Ядру нужно найти некоторые нераспределенные страницы памяти, и они должны сопоставить эти страницы в пространство памяти процессов). Любая форма кэширования выходит из окна). Поэтому ожидайте, что это будет очень медленно (для компьютера).

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

2

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

int data[SOME_NUMBER]; 

void foo(/* some list of parameters here */) 
{ 
    static int some_more_data[SOME_OTHER_NUMBER]; 
    ... 
} 

Оба data и some_more_data существуют в течение всего срока программы, но some_more_data видна только в пределах foo функций .

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

Очевидным недостатком является то, что ваш исполняемый файл будет иметь большую площадь. Еще один недостаток заключается в том, что ваш код не re-entrant; каждый вызов foo работает над тем же блоком памяти, когда он читает или записывает some_more_data. В зависимости от того, что делает ваш код, это может быть или не быть большим делом.

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

void foo(/* some list of parameters here */) 
{ 
    int some_more_data[SOME_SMALLISH_NUMBER]; 
    ... 
} 

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

Если ваш код должен быть повторно абитуриент и вам нужно выделить большие блоки памяти, вы застряли в значительной степени с динамическим управлением памятью (malloc/calloc/realloc и free). В зависимости от того, как вы разрабатываете свой код, вы можете свести к минимуму некоторые проблемы с производительностью.


1. Правила визуализации применяются во время перевода с исходного на машинный код; они не применяются во время выполнения.

+0

Обе памяти для статической памяти стека (для основного потока) выделяются во время загрузки. По той же логике выделение большого блока памяти на ранней стадии выполнения не должно представлять проблемы. Постоянное использование malloc и free, однако, может представлять производительность бутылочной горловины. – doron

+0

@doron: но выделение памяти для определенного * объекта * в стеке не выполняется до ввода функции. Правда, это всего лишь вопрос настройки указателя стека, который в любом случае выполняется как часть служебного вызова функции. Как я уже сказал, использование переменной 'auto' не будет замедлять работу. –

5

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

Автоматические массивы со статически известными размерами могут быть склеены вместе с другими локальными переменными и распределены путем корректировки указателя стека. Это по существу одно целочисленное вычитание (стек растет вниз) или что-то близкое к 1 нс на современных процессорах.

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

Я попытался измерения malloc сек с различными размерами в однотридовой процесс, и я получил это, что означало бы, что malloc+free пары стоят около 50-100 раза больше, чем в качестве переменных стека для распределения < 16MiB. После этого, она пронзает вверх (32MiB и 64MiB и стоят примерно столько же, сколько распределений < = 16MiB сто раз сделать):

Malloc times

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

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

Смежные вопросы