Почему распределение памяти для процессов медленнее и может быть быстрее?

Я относительно хорошо знаю, как работает виртуальная память. Вся память процесса разделяется на страницы и каждая страница виртуальной памяти сопоставляется с страницей в реальной памяти или страницей в файле подкачки, или может быть новой страницей, что означает, что физическая страница все еще не выделена. ОС сопоставляет новые страницы с реальной памятью по требованию, а не когда приложение запрашивает память с помощью malloc, но только тогда, когда приложение действительно обращается к каждой странице из выделенной памяти. Но у меня все еще есть вопросы.

Я заметил это, когда профилировал мое приложение с помощью инструмента linux perf.

введите описание изображения здесь

Около 20% времени выполняет функции ядра: clear_page_orig, __do_page_fault и get_page_from_free_list. Это намного больше, чем я ожидал для этой задачи, и я провел некоторое исследование.

Начнем с небольшого примера:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define SIZE 1 * 1024 * 1024

int main(int argc, char *argv[]) {
  int i;
  int sum = 0;
  int *p = (int *) malloc(SIZE);
  for (i = 0; i < 10000; i ++) {
    memset(p, 0, SIZE);
    sum += p[512];
  }
  free(p);
  printf("sum %d\n", sum);
  return 0;
}

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

$ gcc -O1 ./mem.c && time ./a.out

-O1, потому что clang с -O2 полностью исключает цикл и вычисляет значение моментально.

Результаты: user: 0.520s, sys: 0.008s. Согласно perf, 99% этого времени находится в memset от libc. Таким образом, для этого случая производительность записи составляет около 20 гигабайт/с, что больше, чем теоретическая производительность 12,5 Гбит/с для моей памяти. Похоже, это связано с кэшем процессора L3.

Позвольте изменить тест и начать выделять память в цикле (я не буду повторять те же части кода):

#define SIZE 1 * 1024 * 1024
for (i = 0; i < 10000; i ++) {
  int *p = (int *) malloc(SIZE);
  memset(p, 0, SIZE);
  free(p);
}

Результат точно такой же. Я считаю, что free фактически не освобождает память для ОС, а просто помещает ее в некоторый свободный список в процессе. И malloc на следующей итерации просто получит точно такой же блок памяти. Вот почему нет заметной разницы.

Пусть начнется увеличение SIZE с 1 мегабайта. Время исполнения будет постепенно увеличиваться и будет насыщаться около 10 мегабайт (для меня нет разницы между 10 и 20 мегабайтами).

#define SIZE 10 * 1024 * 1024
for (i = 0; i < 1000; i ++) {
  int *p = (int *) malloc(SIZE);
  memset(p, 0, SIZE);
  free(p);
}

Время показывает: пользователь: 1.184s, sys: 0.004s. perf по-прежнему сообщает, что 99% времени находится в memset, но пропускная способность составляет около 8,3 Гбит/с. В этот момент я понимаю, что происходит, более или менее.

Если мы продолжим увеличивать размер блока памяти, в какой-то момент (для меня на 35 Мб) время выполнения резко возрастет: user: 0.724s, sys: 3.300s.

#define SIZE 40 * 1024 * 1024
for (i = 0; i < 250; i ++) {
  int *p = (int *) malloc(SIZE);
  memset(p, 0, SIZE);
  free(p);
}

Согласно perf, memset будет потреблять только 18% времени.

введите описание изображения здесь

Очевидно, что память выделяется из ОС и освобождается на каждом шаге. Как я уже упоминал ранее, ОС должна очистить каждую выделенную страницу перед ее использованием. Таким образом, 27,3% от clear_page_orig не выглядят экстраординарно: это просто 4s * 0,273 ≈ 1,1 с для ясного mem - то же самое мы получаем в третьем примере. memset заняло 17,9%, что приводит к ≈ 700 мс, что является нормальным из-за памяти уже в кэше L3 после clear_page_orig (первый и второй пример).

Что я не могу понять - почему последний случай в 2 раза медленнее, чем просто memset для памяти + memset для кеша L3? Могу ли я что-то сделать с ним?

Результаты воспроизводятся (с небольшими различиями) на родной Mac OS, Ubuntu под Vmware и Amazon c4.large.

Кроме того, я думаю, что есть место для оптимизации на двух уровнях:

  • на уровне ОС. Если ОС знает, что возвращает страницу в то же приложение, к которому она принадлежала ранее, она не может ее очистить.
  • на уровне CPU. Если ЦП знает, что страница была бесплатной, она может не очистить страницу в памяти. Он может просто очистить его в кеше и перенести его в память только после некоторой обработки в кеше.

Ответы

Ответ 1

Что здесь происходит, это немного сложно, так как оно связано с несколькими различными системами, но это определенно не связано с ценой переключения контекста; ваша программа делает очень мало системных вызовов (проверьте это с помощью strace).

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

  • Большинство реализаций malloc получают кучу памяти из ОС, вызывая sbrk или mmap во время инициализации. Объем полученной памяти может быть скорректирован в некоторых реализациях malloc. Как только память будет получена, она обычно нарезается на разные классы размеров и размещается в структуре данных, так что когда программа запрашивает память, например, malloc(123), реализация malloc может быстро найти часть памяти, соответствующую этим требованиям.
  • Когда вы вызываете free, память возвращается в свободный список и может быть повторно использована при последующих вызовах на malloc. Некоторые реализации malloc позволяют точно настроить, как это работает.
  • Когда вы выделяете большие куски памяти, большинство реализаций malloc просто передают вызовы на огромные объемы памяти прямо на системный вызов mmap, который выделяет "страницы" памяти во время. Для большинства систем 1 страница памяти составляет 4096 байт.
  • В большинстве случаев большинство ОС будут пытаться очистить страницы памяти перед передачей их процессам, которые запросили память через mmap или sbrk. Вот почему вы видите вызовы clear_page_orig в первичном выходе. Эта функция пытается записать 0s на страницы памяти.

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

Здесь описывается процесс поискового вызова:

  • Программа под названием mmap для размещения 500 МБ ОЗУ.
  • Ядро отображает область адресов в адресном пространстве процесса для запрошенной 500 МБ ОЗУ. Он отображает "несколько" (зависимых от ОС) страниц (4096 байт каждый, обычно) физической ОЗУ, чтобы вернуть эти виртуальные адреса.
  • Пользовательская программа начинает доступ к памяти, записывая ее.
  • В конце концов, пользовательская программа получит доступ к адресу, который действителен, но не имеет физической памяти, поддерживающей его.
  • Это приводит к сбою страницы в CPU.
  • Ядро отвечает на ошибку страницы, видя, что процесс обращается к действительному адресу, но один без физической ОЗУ, поддерживая его.
  • Затем ядро ​​обнаруживает, что ОЗУ выделяет этот регион. Это может быть медленным, если память для других процессов должна быть записана на диск, сначала ( "поменяется" ).

Наиболее вероятная причина, по которой вы видите ухудшение производительности в последнем случае, заключается в следующем:

  • В вашем ядре закончилась нулевая страница памяти, которая может быть распределена для выполнения вашего запроса на 40 МБ, поэтому она снова и снова обнуляет память, о чем свидетельствует ваш выход на выходе.
  • Вы генерируете pagefaults при обращении к памяти, которая еще не отображается. Поскольку вы получаете доступ к 40 МБ вместо 10 МБ, вы будете генерировать больше ошибок страницы, так как есть больше страниц памяти, которые необходимо сопоставить.
  • В качестве еще одного ответа, memset есть O (n), что означает, что чем больше памяти вам нужно записать, тем дольше это займет.
  • Меньше вероятность, так как в эти дни 40mb не так много RAM, но проверьте количество свободной памяти в вашей системе, чтобы убедиться, что у вас достаточно ОЗУ.

Если ваше приложение чрезвычайно чувствительно к производительности, вы можете напрямую вызвать mmap и:

  • передайте флаг MAP_POPULATE, который приведет к тому, что все ошибки страницы произойдут спереди и отобразятся все физическая память, - тогда вы не будете платить за ошибки при доступе к странице.
  • передать флаг MAP_UNINITIALIZED, который попытается избежать обнуления страниц памяти до распространения их в вашем процессе. Обратите внимание, что использование этого флага является проблемой безопасности и не должно использоваться, если вы не полностью понимаете последствия использования этого параметра. Возможно, что процессу могут быть выданы страницы памяти, которые использовались другими несвязанными процессами для хранения конфиденциальной информации. Также обратите внимание, что ваше ядро ​​должно быть скомпилировано для разрешения этой опции. Большинство ядер (например, ядро ​​AWS Linux) не поставляются с этой опцией, включенной по умолчанию. Вы почти наверняка не будете использовать этот вариант.

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

  • Избегайте использования memset на больших блоках памяти, если это действительно необходимо. Большую часть времени обнуление памяти перед повторным использованием одним и тем же процессом не требуется.
  • Предотвращение выделения и освобождения одних и тех же фрагментов памяти снова и снова; возможно, вы можете просто выделить большой блок вперед и повторно использовать его по мере необходимости позже.
  • Использование флага MAP_POPULATE выше, если стоимость ошибок страницы при доступе действительно вредна для производительности (маловероятно).

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

Ответ 2

Я не уверен, но я готов поспорить, что стоимость переключения контекста из пользовательского режима в ядро ​​и обратно снова доминирует над всем остальным. memset также занимает значительное время - помните, что это будет O (n).

Обновление

Я считаю, что бесплатно на самом деле не освобождает память для ОС, она просто помещается это в каком-то свободном списке в процессе. И malloc на следующей итерации просто получите точно такой же блок памяти. Вот почему нет заметная разница.

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

Теперь существует ряд реализаций slicker, см. эту статью в Википедии.