Memcpy принимает то же время, что и memset

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

В частности, я запускаю более 1 ГБ массивов a и b (выделено будет calloc) 100 раз со следующими операциями.

operation             time(s)
-----------------------------
memset(a,0xff,LEN)    3.7
memcpy(a,b,LEN)       3.9
a[j] += b[j]          9.4
memcpy(a,b,LEN)       3.8

Обратите внимание, что memcpy только немного медленнее, чем memset. Операции a[j] += b[j] (где j проходит [0,LEN)) должны занимать три раза дольше, чем memcpy, поскольку он работает в три раза больше данных. Однако это примерно на 2,5 меньше, чем memset.

Затем я инициализировал b до нуля с помощью memset(b,0,LEN) и снова проверил:

operation             time(s)
-----------------------------
memcpy(a,b,LEN)       8.2
a[j] += b[j]          11.5

Теперь мы видим, что memcpy примерно в два раза медленнее, чем memset, а a[j] += b[j] примерно в три раза медленнее, чем memset, как я ожидаю.

По крайней мере, я ожидал, что до memset(b,0,LEN), что memcpy будет медленнее, поскольку ленивое выделение (первое касание) на первом 100 итераций.

Почему я получаю только время, ожидаемое после memset(b,0,LEN)?

test.c

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

void tests(char *a, char *b, const int LEN){
    clock_t time0, time1;
    time0 = clock();
    for (int i = 0; i < 100; i++) memset(a,0xff,LEN);
    time1 = clock();
    printf("%f\n", (double)(time1 - time0) / CLOCKS_PER_SEC);

    time0 = clock();
    for (int i = 0; i < 100; i++) memcpy(a,b,LEN);
    time1 = clock();
    printf("%f\n", (double)(time1 - time0) / CLOCKS_PER_SEC);

    time0 = clock();
    for (int i = 0; i < 100; i++) for(int j=0; j<LEN; j++) a[j] += b[j];
    time1 = clock();
    printf("%f\n", (double)(time1 - time0) / CLOCKS_PER_SEC);

    time0 = clock();
    for (int i = 0; i < 100; i++) memcpy(a,b,LEN);
    time1 = clock();
    printf("%f\n", (double)(time1 - time0) / CLOCKS_PER_SEC);

    memset(b,0,LEN);
    time0 = clock();
    for (int i = 0; i < 100; i++) memcpy(a,b,LEN);
    time1 = clock();
    printf("%f\n", (double)(time1 - time0) / CLOCKS_PER_SEC);

    time0 = clock();
    for (int i = 0; i < 100; i++) for(int j=0; j<LEN; j++) a[j] += b[j];
    time1 = clock();
    printf("%f\n", (double)(time1 - time0) / CLOCKS_PER_SEC);
}

main.c

#include <stdlib.h>

int tests(char *a, char *b, const int LEN);

int main(void) {
    const int LEN = 1 << 30;    //  1GB
    char *a = (char*)calloc(LEN,1);
    char *b = (char*)calloc(LEN,1);
    tests(a, b, LEN);
}

Скомпилируйте с помощью (gcc 6.2) gcc -O3 test.c main.c. Clang 3.8 дает практически тот же результат.

Система тестирования: [email protected] (Skylake), 32 ГБ DDR4, Ubuntu 16.10. В моей системе Haswell полосы пропускания имеют смысл до memset(b,0,LEN) т.е. я вижу только проблему в своей системе Skylake.

Я впервые обнаружил эту проблему из a[j] += b[k] операций в этом ответе, которая переоценивала пропускную способность.

Я придумал более простой тест

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

void __attribute__ ((noinline))  foo(char *a, char *b, const int LEN) {
  for (int i = 0; i < 100; i++) for(int j=0; j<LEN; j++) a[j] += b[j];
}

void tests(char *a, char *b, const int LEN) {
    foo(a, b, LEN);
    memset(b,0,LEN);
    foo(a, b, LEN);
}

Эти выходы.

9.472976
12.728426

Однако, если я выполняю memset(b,1,LEN) в main после calloc (см. ниже), то он выдает

12.5
12.5

Это заставляет меня думать, что это проблема выделения ОС, а не проблема с компилятором.

#include <stdlib.h>

int tests(char *a, char *b, const int LEN);

int main(void) {
    const int LEN = 1 << 30;    //  1GB
    char *a = (char*)calloc(LEN,1);
    char *b = (char*)calloc(LEN,1);
    //GCC optimizes memset(b,0,LEN) away after calloc but Clang does not.
    memset(b,1,LEN);
    tests(a, b, LEN);
}

Ответы

Ответ 1

Дело в том, что malloc и calloc на большинстве платформ не выделяют память; они выделяют адресное пространство.

malloc и т.д. работайте по:

  • если запрос может быть выполнен фрилистом, вырезать кусок из него
    • в случае calloc: выдается эквивалент memset(ptr, 0, size)
  • если нет: попросите ОС расширить адресное пространство.

Для систем с пейджингом спроса (COW) (здесь может помочь MMU), второй вариант отключается:

  • создать достаточно записей таблицы страниц для запроса и заполнить их ссылкой (COW) на /dev/zero
  • добавьте эти PTE в адресное пространство процесса

Это не будет содержать физической памяти, кроме только для таблиц страниц.

  • Как только новая память будет указана для чтения, чтение будет производиться с /dev/zero. Устройство /dev/zero - очень специальное устройство, в этом случае отображается на каждую страницу новой памяти.
  • но, если новая страница записана, логика COW запускается (через ошибку страницы):
    • выделена физическая память
    • страница /dev/zero скопирована на новую страницу
    • новая страница удалена с главной страницы
    • и вызывающий процесс может, наконец, сделать обновление, которое запустило все это

Ответ 2

Ваш массив b, вероятно, не был записан после mmap -ing (огромные запросы на распределение с помощью malloc/calloc обычно преобразуются в mmap). И весь массив был смонтирован на единственную "нулевую страницу только для чтения" (часть механизм COW). Чтение нулей с одной страницы происходит быстрее, чем чтение со многих страниц, поскольку одна страница будет храниться в кеше и в TLB. Это объясняет, почему тест до memset (0) был быстрее:

Эти выходы. 9.472976 12.728426

Однако, если я делаю memset(b,1,LEN) в main после calloc (см. ниже), то он выдает: 12.5 12.5

И еще об оптимизации gcc malloc + memset/calloc + memset в calloc (расширенный из мой комментарий)

//GCC optimizes memset(b,0,LEN) away after calloc but Clang does not.

Эта оптимизация была предложена в https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57742 (дерево-оптимизация PR57742) в 2013-06-27 гг. Marc Glisse (https://stackoverflow.com/users/1918193?), как планировалось для версии 4.7/5.0 GCC:

memset (malloc (n), 0, n) → calloc (n, 1)

calloc иногда может быть значительно быстрее, чем malloc + bzero, потому что он имеет особые знания о том, что некоторая память уже равна нулю. Когда другие оптимизации упрощают некоторый код до malloc + memset (0), было бы неплохо заменить его calloc. К сожалению, я не думаю, что есть способ сделать подобную оптимизацию в С++ с новым, где именно этот код наиболее легко появляется (например, создание std::vector (10000)). И там также будет усложнение, что размер memset будет немного меньше, чем размер malloc (использование calloc все равно будет прекрасным, но становится все труднее узнать, является ли это улучшением).

Реализовано в 2014-06-24 (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57742#c15) - https://gcc.gnu.org/viewcvs/gcc?view=revision&revision=211956 (также https://patchwork.ozlabs.org/patch/325357/)

  • tree-ssa-strlen.c... (handle_builtin_malloc, handle_builtin_memset): новые функции.

Текущий код в gcc/tree-ssa-strlen.c https://github.com/gcc-mirror/gcc/blob/7a31ada4c400351a35ab65f8dc0357e7c88805d5/gcc/tree-ssa-strlen.c#L1889 - если memset(0) получить указатель от malloc или calloc, он преобразует malloc в calloc, а затем memset(0) будет удален:

/* Handle a call to memset.
   After a call to calloc, memset(,0,) is unnecessary.
   memset(malloc(n),0,n) is calloc(n,1).  */
static bool
handle_builtin_memset (gimple_stmt_iterator *gsi)
 ...
  if (code1 == BUILT_IN_CALLOC)
    /* Not touching stmt1 */ ;
  else if (code1 == BUILT_IN_MALLOC
       && operand_equal_p (gimple_call_arg (stmt1, 0), size, 0))
    {
      gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt1);
      update_gimple_call (&gsi1, builtin_decl_implicit (BUILT_IN_CALLOC), 2,
              size, build_one_cst (size_type_node));
      si1->length = build_int_cst (size_type_node, 0);
      si1->stmt = gsi_stmt (gsi1);
    }

Это обсуждалось в списке рассылки gcc-patches с 1 марта 2014 года по 15 июля 2014 года с темой "calloc = malloc + memset"

с заметным комментарием от Andi Kleen (http://halobates.de/blog/, https://github.com/andikleen): https://gcc.gnu.org/ml/gcc-patches/2014-06/msg01818.html

FWIW Я считаю, что преобразование приведет к разрыву большого разнообразия микро тесты.

calloc внутренне знает, что память, обновленная от ОС, обнуляется. Но память еще не может быть повреждена.

memset всегда ошибки в памяти.

Итак, если у вас есть тест вроде

   buf = malloc(...)
   memset(buf, ...) 
   start = get_time();
   ... do something with buf
   end = get_time()

Теперь время будет полностью отключено, так как измеренное время включает ошибки страницы.

Марк ответил "Хороший вопрос. Думаю, работа над оптимизацией компилятора является частью игры для микро-тестов, и их авторы будут разочарованы если компилятор не испортил это регулярно и новыми развлекательными способами;-)" и Анди спросил: "Я бы предпочел не делать этого Я не уверен, что это принесет большую пользу. Если вы хотите сохранить его, убедитесь, что есть простой способ отключить его.

Марк показывает, как отключить эту оптимизацию: https://gcc.gnu.org/ml/gcc-patches/2014-06/msg01834.html

Любой из этих флагов работает:

  • -fdisable-tree-strlen
  • -fno-builtin-malloc
  • -fno-builtin-memset (предполагая, что вы явно написали "memset" в своем коде)
  • -fno-builtin
  • -ffreestanding
  • -O1
  • -Os

В коде вы можете скрыть, что указатель, переданный в memset, является один возвращается malloc, сохраняя его в переменной volatile или любой другой трюк, чтобы скрыть от компилятора, что мы делаем memset(malloc(n),0,n).