Может ли кто-нибудь объяснить поведение производительности следующей памяти, выделяющей программу C?

Ответ 1

Короткий ответ

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

Подробнее

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

• Вставьте вызов calloc перед первым вызовом ALLOC. Вы увидите, что после этого Time for Time A и Time B будут одинаковыми.

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

• Используйте time для времени выполнения версии calloc и версии USE_MMAP. Когда я это сделал, я увидел, что время выполнения для USE_MMAP было последовательно немного меньше.

• Я работал с strace -tt -T, который показывает время, когда был сделан системный вызов и сколько времени потребовалось. Вот часть вывода:

Выход Strace:

21:29:06.127536 mmap(NULL, 2000015360, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fff806fd000 <0.000014>
21:29:07.778442 mmap(NULL, 2000015360, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fff093a0000 <0.000021>
21:29:07.778563 times({tms_utime=63, tms_stime=102, tms_cutime=0, tms_cstime=0}) = 4324241005 <0.000011>

Вы можете видеть, что первый вызов mmap занял 0.000014 секунды, но это около 1.5 секунд, прошедших до следующего системного вызова. Затем второй вызов mmap занял 0.000021 секунды, после чего последовал вызов times через несколько сотен микросекунд позже.

Я также выполнил часть выполнения приложения с помощью gdb и увидел, что первый вызов calloc привел к многочисленным вызовам на memset, в то время как второй вызов calloc не вызывал никаких вызовов на memset. Вы можете увидеть исходный код calloc здесь (ищите __libc_calloc), если вы заинтересованы. Что касается того, почему calloc выполняет memset при первом вызове, но не в последующих, я не знаю. Но я уверен, что это объясняет поведение, о котором вы просили.

Что касается того, почему массив, который был обнулен memset, имеет улучшенную производительность, я предполагаю, что это связано с тем, что значения загружаются в TLB, а не в кеш, поскольку это очень большой массив. Независимо от конкретной причины разницы в производительности, о которой вы спрашивали, это то, что два вызова calloc ведут себя по-разному, когда они выполняются.

Ответ 2

Вы также должны проверить с помощью malloc вместо calloc. Единственное, что делает calloc, это заполнить выделенную память нулями.

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

Ответ 3

Думаю, я мог бы написать больше или меньше, тем более, что меньше.

Причина может отличаться от системы к системе. Однако; для кливера:

Общее время, используемое для каждой операции, - это наоборот; если вы время calloc + итерация.

то есть:.

Calloc arr1 : 0.494992654
Calloc arr2 : 0.000021250
Itr arr1    : 0.430646035
Itr arr2    : 0.790992411
Sum arr1    : 0.925638689
Sum arr2    : 0.791013661

Calloc arr1 : 0.503130736
Calloc arr2 : 0.000025906
Itr arr1    : 0.427719162
Itr arr2    : 0.809686047
Sum arr1    : 0.930849898
Sum arr2    : 0.809711953

Первый calloc впоследствии malloc имеет более длительное время выполнения, затем второй. Вызов, т.е. malloc(0) до любого calloc и т.д., Выравнивает время используется для malloc подобных вызовов в одном процессе (пояснение ниже). Можно однако см. небольшое снижение времени для этих вызовов, если вы делаете несколько строк.

Итерационное время, однако, будет сглажено.

Итак, короче говоря; Общее используемое системное время самое высокое, на которое когда-либо получалось alloc'ed в первую очередь. Это, однако, накладные расходы, которые не могут быть экранированы в ограничении процесса.

Продолжается много технического обслуживания. Быстрое касание некоторых случаев:

Сокращение на странице

В память запроса процесса обслуживается диапазон виртуальных адресов. Этот диапазон переводит таблицу страниц в физическую память. Если страница переведена байтом на байт мы быстро получим огромные таблицы страниц. Это, как один, является причиной, почему диапазоны памяти подаются в кусках - или на страницах. Размер страницы - это система зависимый. Архитектура также может обеспечивать различные размеры страниц.

Если мы посмотрим на выполнение вышеуказанного кода и добавим некоторые чтения из /proc/PID/stat мы видим это в действии (примечание RSS):

PID Stat {
  PID          : 4830         Process ID
  MINFLT       : 214          Minor faults, (no page memory read)
  UTIME        : 0            Time user mode
  STIME        : 0            Time kernel mode
  VSIZE        : 2039808      Virtual memory size, bytes
  RSS          : 73           Resident Set Size, Number of pages in real memory
} : Init

PID Stat {
  PID          : 4830         Process ID
  MINFLT       : 51504        Minor faults, (no page memory read)
  UTIME        : 4            Time user mode
  STIME        : 33           Time kernel mode
  VSIZE        : 212135936    Virtual memory size, bytes
  RSS          : 51420        Resident Set Size, Number of pages in real memory
} : Post calloc arr1

PID Stat {
  PID          : 4830         Process ID
  MINFLT       : 51515        Minor faults, (no page memory read)
  UTIME        : 4            Time user mode
  STIME        : 33           Time kernel mode
  VSIZE        : 422092800    Virtual memory size, bytes
  RSS          : 51428        Resident Set Size, Number of pages in real memory
} : Post calloc arr2

PID Stat {
  PID          : 4830         Process ID
  MINFLT       : 51516        Minor faults, (no page memory read)
  UTIME        : 36           Time user mode
  STIME        : 33           Time kernel mode
  VSIZE        : 422092800    Virtual memory size, bytes
  RSS          : 51431        Resident Set Size, Number of pages in real memory
} : Post iteration arr1

PID Stat {
  PID          : 4830         Process ID
  MINFLT       : 102775       Minor faults, (no page memory read)
  UTIME        : 68           Time user mode
  STIME        : 58           Time kernel mode
  VSIZE        : 422092800    Virtual memory size, bytes
  RSS          : 102646       Resident Set Size, Number of pages in real memory
} : Post iteration arr2

PID Stat {
  PID          : 4830         Process ID
  MINFLT       : 102776       Minor faults, (no page memory read)
  UTIME        : 68           Time user mode
  STIME        : 69           Time kernel mode
  VSIZE        : 2179072      Virtual memory size, bytes
  RSS          : 171          Resident Set Size, Number of pages in real memory
} : Post free()

Как мы видим, страницы, фактически выделенные в памяти, переносятся на arr2 в ожидании запрос страницы; который длится до начала итерации. Если мы добавим a malloc(0) до calloc of arr1 мы можем зарегистрировать, что ни один массив не выделяется в физическом память перед итерацией.

Поскольку страница не может быть использована, более эффективно выполнять сопоставление по запросу. Поэтому, когда процесс, т.е. Делает a calloc достаточным количеством страниц зарезервированы, но не обязательно фактически выделены в реальной памяти.

Когда адрес ссылается на страницу таблицы страниц. Если адрес на странице, которая не выделена, система обслуживает ошибку страницы и страницу впоследствии распределяется. Общая сумма выделенных страниц называется Resident Установите размер (RSS).

Мы можем провести эксперимент с нашим массивом, итерируя (касаясь), т.е. 1/4 от него. Здесь я также добавил malloc(0) перед любым calloc.

Pre iteration 1/4:
RSS          : 171              Resident Set Size, Number of pages in real meory

for (i = 0; i < SIZE / 4; ++i)
    arr1[i] = 0;

Post iteration 1/4:
RSS          : 12967            Resident Set Size, Number of pages in real meory

Post iteration 1/1:
RSS          : 51134            Resident Set Size, Number of pages in real meory

Чтобы ускорить работу, большинство систем дополнительно кэшируют N самых последних page table в буфере просмотра перевода (TLB).

brk, mmap

Когда процесс (c|m|…)alloc, верхние границы кучи расширяются на brk() или sbrk(). Эти системные вызовы являются дорогостоящими и компенсируют этот malloc собирает несколько меньших вызовов в один более крупный brk().

Это также влияет на free(), поскольку отрицательный brk() также является ресурсом дорогостоящим они собираются и выполняются как большая операция.

Для огромного запроса; например, в вашем коде, malloc() использует mmap(). Порог для этого, который настраивается mallopt(), является образованным Значение

Мы можем повеселиться, модифицируя SIZE в вашем коде. Если мы используем malloc.h и используйте

struct mallinfo minf = mallinfo();

(no, not milf), мы можем это показать (Примечание Arena и Hblkhd,...):

Initial:

mallinfo {
  Arena   :         0 (Bytes of memory allocated with sbrk by malloc)
  Ordblks :         1 (Number of chunks not in use)
  Hblks   :         0 (Number of chunks allocated with mmap)
  Hblkhd  :         0 (Bytes allocated with mmap)
  Uordblks:         0 (Memory occupied by chunks handed out by malloc)
  Fordblks:         0 (Memory occupied by free chunks)
  Keepcost:         0 (Size of the top-most releasable chunk)
} : Initial

MAX = ((128 * 1024) / sizeof(int)) 

mallinfo {
  Arena   :         0 (Bytes of memory allocated with sbrk by malloc)
  Ordblks :         1 (Number of chunks not in use)
  Hblks   :         1 (Number of chunks allocated with mmap)
  Hblkhd  :    135168 (Bytes allocated with mmap)
  Uordblks:         0 (Memory occupied by chunks handed out by malloc)
  Fordblks:         0 (Memory occupied by free chunks)
  Keepcost:         0 (Size of the top-most releasable chunk)
} : After malloc arr1

mallinfo {
  Arena   :         0 (Bytes of memory allocated with sbrk by malloc)
  Ordblks :         1 (Number of chunks not in use)
  Hblks   :         2 (Number of chunks allocated with mmap)
  Hblkhd  :    270336 (Bytes allocated with mmap)
  Uordblks:         0 (Memory occupied by chunks handed out by malloc)
  Fordblks:         0 (Memory occupied by free chunks)
  Keepcost:         0 (Size of the top-most releasable chunk)
} : After malloc arr2

Затем вычитаем sizeof(int) из MAX и получаем:

mallinfo {
  Arena   :    266240 (Bytes of memory allocated with sbrk by malloc)
  Ordblks :         1 (Number of chunks not in use)
  Hblks   :         0 (Number of chunks allocated with mmap)
  Hblkhd  :         0 (Bytes allocated with mmap)
  Uordblks:    131064 (Memory occupied by chunks handed out by malloc)
  Fordblks:    135176 (Memory occupied by free chunks)
  Keepcost:    135176 (Size of the top-most releasable chunk)
} : After malloc arr1

mallinfo {
  Arena   :    266240 (Bytes of memory allocated with sbrk by malloc)
  Ordblks :         1 (Number of chunks not in use)
  Hblks   :         0 (Number of chunks allocated with mmap)
  Hblkhd  :         0 (Bytes allocated with mmap)
  Uordblks:    262128 (Memory occupied by chunks handed out by malloc)
  Fordblks:      4112 (Memory occupied by free chunks)
  Keepcost:      4112 (Size of the top-most releasable chunk)
} : After malloc arr2

Мы регистрируем, что система работает как рекламируемая. Если размер распределения ниже порогового значения sbrk, а память обрабатывается внутри malloc, else mmap.

Структура этого также помогает предотвратить фрагментацию памяти и т.д.

Точка, что семейство malloc оптимизировано для общего использования. Однако mmap пределы могут быть изменены для удовлетворения особых потребностей.

Обратите внимание на это (и вниз через 100 строк), когда/если изменяется порог mmap.  .

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

Touch pages … (Here with page size of 4 kB)

for (i = 0; i < SIZE; i += 4096 / sizeof(int)) {
    arr1[i] = 0;
    arr2[i] = 0;
}

Itr arr1    : 0.312462317
CPU arr1    : 0.32

Itr arr2    : 0.312869158
CPU arr2    : 0.31

Также смотрите:

• Краткое описание параметров времени компиляции
• Важная статистика
• ... на самом деле весь файл является прочитанным.

Примечания:

Итак, CPU знает физический адрес? Нах.

В мире памяти многое должно быть адресовано;). Основное оборудование для это блок управления памятью (MMU). Либо как интегрированная часть процессор или внешний чип.

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

Адрес, который мы, как смертные, видим, является логическим адресом, который использует процессор. MMU переводит это на физический адрес.

Адрес CPU состоит из двух частей: адрес страницы и смещение. [PAGE_ADDRESS.OFFSET]

И процесс получения физического адреса может иметь что-то вроде:

.-----.                          .--------------.
| CPU > --- Request page 2 ----> | MMU          |
+-----+                          | Pg 2 == Pg 4 |
      |                          +------v-------+
      +--Request offset 1 -+            |
                           |    (Logical page 2 EQ Physical page 4)
[ ... ]     __             |            |
[ OFFSET 0 ]  |            |            |
[ OFFSET 1 ]  |            |            |
[ OFFSET 2 ]  |            |            |     
[ OFFSET 3 ]  +--- Page 3  |            |
[ OFFSET 4 ]  |            |            |
[ OFFSET 5 ]  |            |            |
[ OFFSET 6 ]__| ___________|____________+
[ OFFSET 0 ]  |            |
[ OFFSET 1 ]  | ...........+
[ OFFSET 2 ]  |
[ OFFSET 3 ]  +--- Page 4
[ OFFSET 4 ]  |
[ OFFSET 5 ]  |
[ OFFSET 6 ]__|
[ ... ]

Логическое адресное пространство процессора напрямую связано с длиной адреса. 32-разрядный адресный процессор имеет логическое адресное пространство из 2 ³² байтов. Физическое адресное пространство - это объем памяти, которую система может себе позволить.

Существует также обработка фрагментированной памяти, повторное выравнивание и т.д.

Это подводит нас к миру файлов подкачки. Если процесс запрашивает больше памяти затем физически доступно; одна или несколько страниц других процессов передаются на диск/своп, а их страницы "украдены" запрашивающим процессом. MMU отслеживает это; поэтому ЦП не должен беспокоиться о том, где память фактически расположена.

Это приводит нас к грязной памяти.

Если мы печатаем некоторую информацию из /proc/ [pid]/smaps, более конкретный диапазон наших массивов мы получаем что-то вроде:

Start:
b76f3000-b76f5000
Private_Dirty:         8 kB

Post calloc arr1:
aaeb8000-b76f5000
Private_Dirty:        12 kB

Post calloc arr2:
9e67c000-b76f5000
Private_Dirty:        20 kB

Post iterate 1/4 arr1
9e67b000-b76f5000
Private_Dirty:     51280 kB

Post iterate arr1:
9e67a000-b76f5000
Private_Dirty:    205060 kB

Post iterate arr2:
9e679000-b76f5000
Private_Dirty:    410096 kB

Post free:
9e679000-9e67d000
Private_Dirty:        16 kB
b76f2000-b76f5000
Private_Dirty:        12 kB

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

Ответ 4

Это просто вопрос, когда изображение памяти процесса расширяется на странице.

Ответ 5

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

Я не знаю достаточно о внутреннем распределении памяти в Linux. Но я немного изменил ваш script: я добавил третий массив и несколько дополнительных итераций на операции массива. И я принял во внимание замечание Old Pro о том, что время для распределения массивов не принималось во внимание.

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

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

Теперь, к вашему вопросу, последний выделенный массив с calloc, по-видимому, действительно выделен в памяти (не отложен). Поскольку arr1 и arr2 ведут себя точно так же (первая итерация медленная, последующие итерации быстрее). Arr3 быстрее для первой итерации, потому что память была выделена раньше. При использовании макроса A, это зависит от этого. Я предполагаю, что ядро ​​предварительно выделило массив в памяти для последнего calloc. Зачем? Я не знаю... Я тестировал его также только с одним массивом (поэтому я удалил все случаи arr2 и arr3), тогда у меня есть одно и то же время (примерно) для всех 10 итераций arr1.

Оба malloc и mmap ведут себя одинаково (результаты не показаны ниже), первая итерация медленная, последующие итерации быстрее для всех 3 массивов.

Примечание: все результаты были когерентными по различным флагам оптимизации gcc (от -O0 до -O3), поэтому не похоже, что корень поведения получен из некоторого оптимизатора gcc.

Примечание2: Тестирование на Ubuntu Precise Pangolin (ядро 3.2), с GCC 4.6.3

#include <stdlib.h>
#include <stdio.h>
#include <sys/mman.h>

#include <time.h>

#define SIZE 500002816
#define ITERATION 10

#if defined(USE_MMAP)
#  define ALLOC(a, b) (mmap(NULL, a * b, PROT_READ | PROT_WRITE,  \
                          MAP_PRIVATE | MAP_ANONYMOUS, -1, 0))
#elif defined(USE_MALLOC)
#  define ALLOC(a, b) (malloc(b * a))
#elif defined(USE_CALLOC)
#  define ALLOC calloc
#else
#  error "No alloc routine specified"
#endif

int main() {
  clock_t start, finish, gstart, gfinish;
  start = clock();
  gstart = start;
#ifdef A
  unsigned int *arr1 = ALLOC(sizeof(unsigned int), SIZE);
  unsigned int *arr2 = ALLOC(sizeof(unsigned int), SIZE);
  unsigned int *arr3 = ALLOC(sizeof(unsigned int), SIZE);
#else
  unsigned int *arr3 = ALLOC(sizeof(unsigned int), SIZE);
  unsigned int *arr2 = ALLOC(sizeof(unsigned int), SIZE);
  unsigned int *arr1 = ALLOC(sizeof(unsigned int), SIZE);
#endif
  finish = clock();
  unsigned int i, j;
  double intermed, finalres;

  intermed = ((double)(finish - start))/CLOCKS_PER_SEC;
  printf("Time to create: %.2f\n", intermed);

  printf("arr1 addr: %p\narr2 addr: %p\narr3 addr: %p\n", arr1, arr2, arr3);

  finalres = 0;
  for (j = 0; j < ITERATION; j++)
  {
    start = clock();
    {
      for (i = 0; i < SIZE; i++)
        arr1[i] = (i + 13) * 5;
    }
    finish = clock();

    intermed = ((double)(finish - start))/CLOCKS_PER_SEC;
    finalres += intermed;
    printf("Time A: %.2f\n", intermed);
  }

  printf("Time A (average): %.2f\n", finalres/ITERATION);


  finalres = 0;
  for (j = 0; j < ITERATION; j++)
  {
    start = clock();
    {
      for (i = 0; i < SIZE; i++)
        arr2[i] = (i + 13) * 5;
    }
    finish = clock();

    intermed = ((double)(finish - start))/CLOCKS_PER_SEC;
    finalres += intermed;
    printf("Time B: %.2f\n", intermed);
  }

  printf("Time B (average): %.2f\n", finalres/ITERATION);


  finalres = 0;
  for (j = 0; j < ITERATION; j++)
  {
    start = clock();
    {
      for (i = 0; i < SIZE; i++)
        arr3[i] = (i + 13) * 5;
    }
    finish = clock();

    intermed = ((double)(finish - start))/CLOCKS_PER_SEC;
    finalres += intermed;
    printf("Time C: %.2f\n", intermed);
  }

  printf("Time C (average): %.2f\n", finalres/ITERATION);

  gfinish = clock();

  intermed = ((double)(gfinish - gstart))/CLOCKS_PER_SEC;
  printf("Global Time: %.2f\n", intermed);

  return 0;
}

Результаты:

Использование USE_CALLOC

Time to create: 0.13
arr1 addr: 0x7fabcb4a6000
arr2 addr: 0x7fabe917d000
arr3 addr: 0x7fac06e54000
Time A: 0.67
Time A: 0.48
...
Time A: 0.47
Time A (average): 0.48
Time B: 0.63
Time B: 0.47
...
Time B: 0.48
Time B (average): 0.48
Time C: 0.45
...
Time C: 0.46
Time C (average): 0.46

С USE_CALLOC и A

Time to create: 0.13
arr1 addr: 0x7fc2fa206010
arr2 addr: 0xx7fc2dc52e010
arr3 addr: 0x7fc2be856010
Time A: 0.44
...
Time A: 0.43
Time A (average): 0.45
Time B: 0.65
Time B: 0.47
...
Time B: 0.46
Time B (average): 0.48
Time C: 0.65
Time C: 0.48
...
Time C: 0.45
Time C (average): 0.48

Использование USE_MMAP

Time to create: 0.0
arr1 addr: 0x7fe6332b7000
arr2 addr: 0x7fe650f8e000
arr3 addr: 0x7fe66ec65000
Time A: 0.55
Time A: 0.48
...
Time A: 0.45
Time A (average): 0.49
Time B: 0.54
Time B: 0.46
...
Time B: 0.49
Time B (average): 0.50
Time C: 0.57
...
Time C: 0.40
Time C (average): 0.43