Стоимость статического выделения памяти против динамического выделения памяти в C

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

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

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

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

Источник

4 ответа

Решение

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

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

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

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

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

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

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

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

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

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

Источник

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

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

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

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

Маллок раз

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

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

Источник

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

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

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

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

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

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

Источник

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

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

Очевидным недостатком является то, что ваш исполняемый файл будет иметь большую площадь. Другим недостатком является то, что ваш код не повторяется; каждый вызов 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. Правила видимости применяются при переводе из исходного кода в машинный код; они действительно не применяются во время выполнения.

Источник
Другие вопросы по тегам