Почему malloc + memset медленнее, чем calloc?

Question

Известно, что calloc отличается от malloc тем, что инициализирует выделенную память. При calloc память обнуляется. При malloc память не очищается.

Так что в повседневной работе я считаю calloc malloc + memset. Кстати, ради интереса я написал следующий код для теста.

Результат сбивает с толку.

Код 1:

#include<stdio.h>
#include<stdlib.h>
#define BLOCK_SIZE 1024time ./a.out   
**real 0m2.693s**  
user 0m0.973s  
sys 0m1.721s  

256 int main() { int i=0; char *buf[10]; while(i<10) { buf[i] = (char*)calloc(1,BLOCK_SIZE); i++; } }

Вывод кода 1:

time ./a.out  
**real 0m0.287s**  
user 0m0.095s  
sys 0m0.192s  

Код 2:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define BLOCK_SIZE 1024*1024*256
int main()
{
        int i=0;
        char *buf[10];
        while(i<10)
        {
                buf[i] = (char*)malloc(BLOCK_SIZE);
                memset(buf[i],'\0',BLOCK_SIZE);
                i++;
        }
}

Вывод кода 2:

*1024*

Замена memset на bzero(buf[i],BLOCK_SIZE) в коде 2 дает тот же результат.

Мой вопрос: Почему malloc + memset намного медленнее, чем calloc? Как может calloc сделать это?

Answer 1

Короткая версия: всегда используйте calloc() вместо malloc()+memset(). В большинстве случаев они будут одинаковыми. В некоторых случаях calloc() будет выполнять меньше работы, поскольку может полностью пропустить memset(). В других случаях calloc() может даже обмануть и не выделять никакой памяти! Однако malloc()+memset() всегда будет выполнять всю работу.

Понимание этого требует краткого обзора системы памяти.

Быстрый тур по памяти

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

Распределители памяти, такие как malloc() и calloc(), в основном используются для того, чтобы занимать небольшие выделения (от 1 байта до 100 КБ) и группировать их в большие пулы памяти. Например, если вы выделите 16 байтов, malloc() сначала попытается получить 16 байтов из одного из своих пулов, а затем запросит больше памяти у ядра, когда пул начнет работать без нагрузки. Однако, поскольку программа, о которой вы спрашиваете, выделяет сразу большой объем памяти, malloc() и calloc() будут просто запрашивать эту память непосредственно из ядра. Порог для этого поведения зависит от вашей системы, но я видел 1 МБ, использованный в качестве порога.

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

Таблица страниц отображает адреса памяти в фактическую физическую память. Адреса вашего процесса, от 0x00000000 до 0xFFFFFFFF в 32-разрядной системе, не являются реальной памятью, а вместо этого являются адресами в виртуальной памяти. Процессор делит эти адреса на страницы по 4 КиБ, и каждая страница может быть назначена другой кусок физической оперативной памяти путем изменения таблицы страниц. Только ядру разрешено изменять таблицу страниц.

Как это не работает

Вот как работает выделение 256 Мбайт не работает:

1. Ваш процесс вызывает calloc() и запрашивает 256 МБ.

2. Стандартная библиотека вызывает mmap() и запрашивает 256 МБ.

3. Ядро находит 256 МБ неиспользуемой оперативной памяти и передает ее вашему процессу путем изменения таблицы страниц.

4. Стандартная библиотека обнуляет ОЗУ с помощью memset() и возвращает с calloc().

5. Ваш процесс в конечном итоге завершается, и ядро ​​освобождает ОЗУ, чтобы его мог использовать другой процесс.

Как это на самом деле работает

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

• Когда ваш процесс получает новую память от ядра, эта память, вероятно, использовалась ранее другим процессом. Это угроза безопасности. Что если в этой памяти есть пароли, ключи шифрования или секретные рецепты сальсы? Чтобы предотвратить утечку конфиденциальных данных, ядро ​​всегда очищает память, прежде чем передать ее процессу. Мы могли бы также очистить память, обнуляя ее, и если новая память обнуляется, мы могли бы также сделать это гарантией, поэтому mmap() гарантирует, что новая память, которую она возвращает, всегда обнуляется.

• Существует множество программ, которые выделяют память, но не используют ее сразу. Иногда память выделяется, но никогда не используется. Ядро это знает и ленится. Когда вы выделяете новую память, ядро ​​вообще не касается таблицы страниц и не отдает ОЗУ вашему процессу. Вместо этого он находит некоторое адресное пространство в вашем процессе, записывает, что должно быть там, и дает обещание, что он поместит туда оперативную память, если ваша программа когда-либо действительно ее использует. Когда ваша программа пытается прочитать или записать данные с этих адресов, процессор вызывает сбой страницы , и ядро ​​начинает выделять ОЗУ этим адресам и возобновляет работу вашей программы. Если вы никогда не используете память, сбой страницы никогда не происходит, и ваша программа фактически никогда не получает ОЗУ.

• Некоторые процессы выделяют память и затем читают из нее, не изменяя ее. Это означает, что многие страницы в памяти разных процессов могут быть заполнены нетронутыми нулями, возвращаемыми из mmap(). Поскольку все эти страницы одинаковы, ядро ​​заставляет все эти виртуальные адреса указывать на одну общую 4-килобайтную страницу памяти, заполненную нулями. Если вы попытаетесь записать в эту память, процессор вызовет еще одну страницу сбоя, и ядро ​​войдет, чтобы дать вам новую страницу с нулями, которая не используется другими программами.

Окончательный процесс выглядит примерно так:

1. Ваш процесс вызывает calloc() и запрашивает 256 МБ.

2. Стандартная библиотека вызывает mmap() и запрашивает 256 МБ.

3. Ядро находит 256 МБ неиспользуемого адресного пространства, записывает, для чего теперь используется это адресное пространство, и возвращает.

4. Стандартная библиотека знает, что результат mmap() всегда заполняется нулями (или будет , когда он действительно получит немного ОЗУ), поэтому он не касается памяти, поэтому нет ошибки страницы, и ОЗУ никогда не отдается вашему процессу.

5. Ваш процесс в конечном итоге завершается, и ядру не нужно восстанавливать ОЗУ, поскольку оно никогда не выделялось.

Если вы используете memset() для обнуления страницы, memset() вызовет сбой страницы, приведет к выделению ОЗУ, а затем обнулит ее, даже если она уже заполнена нулями. Это огромный объем дополнительной работы и объясняет, почему calloc() быстрее, чем malloc() и memset(). Если в конечном итоге использовать память в любом случае, calloc() все еще быстрее, чем malloc() и memset(), но разница не так уж и смешна.

---

Это не всегда работает

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

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

рассеивание неправильных ответов

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

Функция calloc() не использует какую-либо специальную версию memset() с выравниванием по памяти, и это в любом случае не сделает ее намного быстрее. Большинство реализаций memset() для современных процессоров выглядят примерно так:

function memset(dest, c, len)
    // one byte at a time, until the dest is aligned...
    while (len > 0 && ((unsigned int)dest & 15))
        *dest++ = c
        len -= 1
    // now write big chunks at a time (processor-specific)...
    // block size might not be 16, it's just pseudocode
    while (len >= 16)
        // some optimized vector code goes here
        // glibc uses SSE2 when available
        dest += 16
        len -= 16
    // the end is not aligned, so one byte at a time
    while (len > 0)
        *dest++ = c
        len -= 1

Как видите, memset() очень быстрый, и вы не получите ничего лучше для больших блоков памяти.

Тот факт, что memset() обнуляет память, которая уже обнулена, означает, что память обнуляется дважды, но это объясняет только двукратную разницу в производительности. Разница в производительности здесь намного больше (я измерял более трех порядков в моей системе между malloc()+memset() и calloc()).

Вечеринка

Вместо 10-кратного цикла напишите программу, которая выделяет память до тех пор, пока malloc() или calloc() не возвратит NULL.

Что произойдет, если вы добавите memset()?

Answer 2

Поскольку во многих системах в свободное время обработки ОС пытается самостоятельно установить свободную память на ноль и пометить ее как безопасную для calloc(), поэтому при вызове calloc() она может уже иметь свободную обнуленную память дать вам.

Answer 3

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