Почему malloc + memset работает медленнее, чем calloc?

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

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

Результат запутан.

Код 1:

#include<stdio.h>
#include<stdlib.h>
#define BLOCK_SIZE 1024*1024*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:

time ./a.out   
**real 0m2.693s**  
user 0m0.973s  
sys 0m1.721s

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

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

Ответы

Ответ 1

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

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

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

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

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

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

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

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

Здесь как выделение 256 MiB не работает:

  • Ваш процесс вызывает calloc() и запрашивает 256 MiB.

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

  • Ядро обнаруживает 256 Мбайт неиспользуемой ОЗУ и передает его вашему процессу, изменяя таблицу страниц.

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

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

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

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

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

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

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

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

  • Ваш процесс вызывает calloc() и запрашивает 256 MiB.

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

  • Ядро обнаруживает 256 Мбайт неиспользуемого адресного пространства, делает заметку о том, для чего это адресное пространство используется и возвращается.

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

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

Если вы используете 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 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() является обнуляющей память, которая уже обнулена, означает, что память обнуляется дважды, но это только объясняет разницу в производительности 2x. Разница в производительности здесь намного больше (я измерил более трех порядков в моей системе между malloc()+memset() и calloc()).

Трюк участника

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

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

Ответ 2

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

Ответ 3

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