Memcpy занимает столько же времени, сколько memset

Question

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 дает практически тот же результат.

Тестовая система: i7-6700HQ@2.60 ГГц (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) в основном после 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);
}

4

c linux memory x86 malloc

Источник

user2542702 02 апр '17 в 12:56

2 ответа

Решение

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

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

И еще об оптимизации gloc 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?), Как и планировалось для версии GCC 4.9 / 5.0:

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

Осуществлено в 2014-06-24 ( https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57742) - 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 "

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

Я верю, что трансформация сломает большое количество микро-тестов.
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),

1

Источник

user196561 03 апр '17 в 11:05

Другие вопросы по тегам c linux memory x86 malloc

user905902 02 апр '17 в 22:22 2017-04-02 22:22 · Accepted Answer · 2017-04-02 22:22

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

malloc и т. д. работают:

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

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

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

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

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