memset против обнуления через простой цикл
Подскажите пожалуйста, что это за особенность такая странная?
Вот простенький код: VS2019, x64, release.
-0.Создаю вектор, заполняю его рандомными значениями.
-1.Создаю указатель и выделяю память через malloc, память не инициализирую и через цикл копирую данные из вектора в выделенную память.
-2.Создаю указатель и выделяю память через malloc, инициализирую выделенную память 0 через Memset и через цикл копирую данные из вектора в выделенную память.
-3.Создаю указатель и выделяю память через malloc, инициализирую выделенную память 1 через Memset и через цикл копирую данные из вектора в выделенную память.
-4.Создаю указатель и выделяю память через malloc, инициализирую выделенную память 0через Цикл и через цикл копирую данные из вектора в выделенную память.
-5.Создаю указатель и выделяю память через malloc, инициализирую выделенную память 1 через Цикл и через цикл копирую данные из вектора в выделенную память.
А теперь меряю время каждой секции с 1 по 5:
1: 31 мс
2: 33 мс
3: 33 мс
4: 32 мс
5: 12 мс
То есть все вариант заполнения память кроме п.5 имеют одинаковое время и только п.5 - где память инициализируется через цикл и единичками - только этот вариант более, чем в два раза быстрее. Почему так ??
PS:Изменение порядка вариантов на результат не влияет! То есть я переставлял 5ый цикл в самое начало - результат тот же.
#include <vector>
#include <iostream>
int main()
{
size_t num = 9999999;
//-----------------Наполнение вектора произвольными значениями--------
std::vector<size_t>my_vector_rand;
my_vector_rand.resize(num);
for (size_t i = 0; i < num; i++)
{
my_vector_rand[i] = rand() % 100;
}
//-----------------------------------------------------------------------------------
int clock1;
int clock2;
//-----------------------------------------------------------------
size_t* my_sizet_pionter1 = (size_t*)malloc(num * sizeof(size_t));
clock1 = clock();
for (size_t i = 0; i < num; i++)
{
memcpy(&my_sizet_pionter1[i], &my_vector_rand[i], sizeof(size_t));
}
clock2 = clock();
std::cout << "time_memcpy_without_all:" << clock2 - clock1 << std::endl;
std::cout << my_sizet_pionter1[num - 1] << std::endl;
//-----------------------------------------------------------------
//-----------------------------------------------------------------
size_t* my_sizet_pionter2 = (size_t*)malloc(num * sizeof(size_t));
memset(my_sizet_pionter2, 0, num * sizeof(size_t));
std::cout << my_sizet_pionter2[num - 1] << std::endl; //Нужен, чтобы компилятор не оптимизировал вышестоящий memset.
clock1 = clock();
for (size_t i = 0; i < num; i++)
{
memcpy(&my_sizet_pionter2[i], &my_vector_rand[i], sizeof(size_t));
}
clock2 = clock();
std::cout << "time_memcpy_memset_zero:" << clock2 - clock1 << std::endl;
std::cout << my_sizet_pionter2[num - 1] << std::endl;
//-----------------------------------------------------------------
//-----------------------------------------------------------------
size_t* my_sizet_pionter3 = (size_t*)malloc(num * sizeof(size_t));
memset(my_sizet_pionter3, 1, num * sizeof(size_t));
std::cout << my_sizet_pionter3[num - 1] << std::endl; //Нужен, чтобы компилятор не оптимизировал вышестоящий memset.
clock1 = clock();
for (size_t i = 0; i < num; i++)
{
memcpy(&my_sizet_pionter3[i], &my_vector_rand[i], sizeof(size_t));
}
clock2 = clock();
std::cout << "time_memcpy_memset_one:" << clock2 - clock1 << std::endl;
std::cout << my_sizet_pionter3[num - 1] << std::endl;
//-----------------------------------------------------------------
//-----------------------------------------------------------------
size_t* my_sizet_pionter4 = (size_t*)malloc(num * sizeof(size_t));
for (size_t i = 0; i < num; i++)
{
my_sizet_pionter4[i] = 0;
}
std::cout << my_sizet_pionter4[num - 1] << std::endl; //Нужен, чтобы компилятор не оптимизировал вышестоящий цикл.
clock1 = clock();
for (size_t i = 0; i < num; i++)
{
memcpy(&my_sizet_pionter4[i], &my_vector_rand[i], sizeof(size_t));
}
clock2 = clock();
std::cout << "time_memcpy_cycle_zero:" << clock2 - clock1 << std::endl;
std::cout << my_sizet_pionter4[num - 1] << std::endl;
//-----------------------------------------------------------------
//-----------------------------------------------------------------
size_t* my_sizet_pionter5 = (size_t*)malloc(num * sizeof(size_t));
for (size_t i = 0; i < num; i++)
{
my_sizet_pionter5[i] = 1;
}
std::cout << my_sizet_pionter5[num - 1] << std::endl; //Нужен, чтобы компилятор не оптимизировал вышестоящий цикл.
clock1 = clock();
for (size_t i = 0; i < num; i++)
{
memcpy(&my_sizet_pionter5[i], &my_vector_rand[i], sizeof(size_t));
}
clock2 = clock();
std::cout << "time_memcpy_cycle_one:" << clock2 - clock1 << std::endl;
std::cout << my_sizet_pionter5[num - 1] << std::endl;
//-----------------------------------------------------------------
}
Дизассемблированный код memset и цикла установки 0 или 1:
memset(my_sizet_pionter2, 0, num * sizeof(size_t));
00007FF798DC5A36 mov rax,qword ptr [num]
00007FF798DC5A3A shl rax,3
00007FF798DC5A3E mov r8,rax
00007FF798DC5A41 xor edx,edx
00007FF798DC5A43 mov rcx,qword ptr [my_sizet_pionter2]
00007FF798DC5A4A call memset (07FF798DC1460h)
memset(my_sizet_pionter3, 1, num * sizeof(size_t));
00007FF798DC5B80 mov rax,qword ptr [num]
00007FF798DC5B84 shl rax,3
00007FF798DC5B88 mov r8,rax
00007FF798DC5B8B mov edx,1
00007FF798DC5B90 mov rcx,qword ptr [my_sizet_pionter3]
00007FF798DC5B97 call memset (07FF798DC1460h)
for (size_t i = 0; i < num; i++)
00007FF798DC5CCD mov qword ptr [rbp+1A8h],0
00007FF798DC5CD8 jmp main+46Bh (07FF798DC5CEBh)
00007FF798DC5CDA mov rax,qword ptr [rbp+1A8h]
00007FF798DC5CE1 inc rax
00007FF798DC5CE4 mov qword ptr [rbp+1A8h],rax
00007FF798DC5CEB mov rax,qword ptr [num]
00007FF798DC5CEF cmp qword ptr [rbp+1A8h],rax
00007FF798DC5CF6 jae main+490h (07FF798DC5D10h)
{
my_sizet_pionter4[i] = 0;
00007FF798DC5CF8 mov rax,qword ptr [my_sizet_pionter4]
00007FF798DC5CFF mov rcx,qword ptr [rbp+1A8h]
00007FF798DC5D06 mov qword ptr [rax+rcx*8],0
}
for (size_t i = 0; i < num; i++)
00007FF798DC5E41 mov qword ptr [rbp+208h],0
00007FF798DC5E4C jmp main+5DFh (07FF798DC5E5Fh)
00007FF798DC5E4E mov rax,qword ptr [rbp+208h]
00007FF798DC5E55 inc rax
00007FF798DC5E58 mov qword ptr [rbp+208h],rax
00007FF798DC5E5F mov rax,qword ptr [num]
00007FF798DC5E63 cmp qword ptr [rbp+208h],rax
00007FF798DC5E6A jae main+604h (07FF798DC5E84h)
{
my_sizet_pionter5[i] = 1;
00007FF798DC5E6C mov rax,qword ptr [my_sizet_pionter5]
00007FF798DC5E73 mov rcx,qword ptr [rbp+208h]
00007FF798DC5E7A mov qword ptr [rax+rcx*8],1
}
ДОПОЛНЕНИЕ:
Если после каждого memset`а, который заполняет выделенную память 1 или 0.
И если после цикла, который заполняет выделенную память 0 - добавить вот эти строки:
size_t summ_memset_0;
for (size_t i = 0; i < num; i++)
{
summ_memset_0 = summ_memset_0 + my_sizet_pionter2[i];
}
std::cout << summ_memset_0 << std::endl;
То теперь время выполнения у всех вариантов кроме 1-го, у которого память не инициализировалась - время выполнения становится одинаковым.
1: 31 мс
2: 11 мс
3: 12 мс
4: 13 мс
5: 12 мс
То есть не точно, но вероятно компилятор, все таки оптимизировал код, и похоже выбрасывал инициализацию выделенной памяти через memset и через цикл. Но инициализацию выделенной памяти через цикл 1-ками - почему то оставлял.
Вот итоговый код:
#include <vector>
#include <iostream>
#include <ctime>
int main()
{
size_t num = 9999999;
//-----------------Filling a vector random values--------
std::vector<size_t>my_vector_rand;
my_vector_rand.resize(num);
for (size_t i = 0; i < num; i++)
{
my_vector_rand[i] = rand() % 100;
}
//-----------------------------------------------------------------------------------
int clock1;
int clock2;
//-----------------------------------------------------------------
size_t* my_sizet_pionter1 = (size_t*)malloc(num * sizeof(size_t));
clock1 = clock();
for (size_t i = 0; i < num; i++)
{
memcpy(&my_sizet_pionter1[i], &my_vector_rand[i], sizeof(size_t));
}
clock2 = clock();
std::cout << "time_memcpy_without_all:" << clock2 - clock1 << std::endl;
std::cout << my_sizet_pionter1[num - 1] << std::endl;
//-----------------------------------------------------------------
//-----------------------------------------------------------------
size_t* my_sizet_pionter2 = (size_t*)malloc(num * sizeof(size_t));
memset(my_sizet_pionter2, 0, num * sizeof(size_t));
std::cout << my_sizet_pionter2[num - 1] << std::endl; //It is necessary that the compiler does not optimize memset. it didn't help.
size_t summ_memset_0;
for (size_t i = 0; i < num; i++)
{
summ_memset_0 = summ_memset_0 + my_sizet_pionter2[i];
}
std::cout << summ_memset_0 << std::endl; //It is necessary that the compiler does not optimize memset. It works.
clock1 = clock();
for (size_t i = 0; i < num; i++)
{
memcpy(&my_sizet_pionter2[i], &my_vector_rand[i], sizeof(size_t));
}
clock2 = clock();
std::cout << "time_memcpy_memset_zero:" << clock2 - clock1 << std::endl;
std::cout << my_sizet_pionter2[num - 1] << std::endl;
//-----------------------------------------------------------------
//-----------------------------------------------------------------
size_t* my_sizet_pionter3 = (size_t*)malloc(num * sizeof(size_t));
memset(my_sizet_pionter3, 1, num * sizeof(size_t));
std::cout << my_sizet_pionter3[num - 1] << std::endl; //It is necessary that the compiler does not optimize memset. it didn't help.
size_t summ_memset_1;
for (size_t i = 0; i < num; i++)
{
summ_memset_1 = summ_memset_1 + my_sizet_pionter3[i];
}
std::cout << summ_memset_1 << std::endl; //It is necessary that the compiler does not optimize memset. It works.
clock1 = clock();
for (size_t i = 0; i < num; i++)
{
memcpy(&my_sizet_pionter3[i], &my_vector_rand[i], sizeof(size_t));
}
clock2 = clock();
std::cout << "time_memcpy_memset_one:" << clock2 - clock1 << std::endl;
std::cout << my_sizet_pionter3[num - 1] << std::endl;
//-----------------------------------------------------------------
//-----------------------------------------------------------------
size_t* my_sizet_pionter4 = (size_t*)malloc(num * sizeof(size_t));
for (size_t i = 0; i < num; i++)
{
my_sizet_pionter4[i] = 0;
}
std::cout << my_sizet_pionter4[num - 1] << std::endl; //It is necessary that the compiler does not optimize cycle. it didn't help.
size_t summ_loop_0;
for (size_t i = 0; i < num; i++)
{
summ_loop_0 = summ_loop_0 + my_sizet_pionter4[i];
}
std::cout << summ_loop_0 << std::endl; //It is necessary that the compiler does not optimize memset. It works.
clock1 = clock();
for (size_t i = 0; i < num; i++)
{
memcpy(&my_sizet_pionter4[i], &my_vector_rand[i], sizeof(size_t));
}
clock2 = clock();
std::cout << "time_memcpy_cycle_zero:" << clock2 - clock1 << std::endl;
std::cout << my_sizet_pionter4[num - 1] << std::endl;
//-----------------------------------------------------------------
//-----------------------------------------------------------------
size_t* my_sizet_pionter5 = (size_t*)malloc(num * sizeof(size_t));
for (size_t i = 0; i < num; i++)
{
my_sizet_pionter5[i] = 1;
}
std::cout << my_sizet_pionter5[num - 1] << std::endl; //It is necessary that the compiler does not optimize cycle.
clock1 = clock();
for (size_t i = 0; i < num; i++)
{
memcpy(&my_sizet_pionter5[i], &my_vector_rand[i], sizeof(size_t));
}
clock2 = clock();
std::cout << "time_memcpy_cycle_one:" << clock2 - clock1 << std::endl;
std::cout << my_sizet_pionter5[num - 1] << std::endl;
//-----------------------------------------------------------------
}
Ответы (2 шт):
Хороший вопрос. Сразу скажу, что достоверного ответа у меня нет.
Похоже тут дело не только в оптимизациях компилятора, а в системе (ОС + реализация malloc).
Я откомпилировал g++ -O3 ttt.cpp и позапускал вот в такой системе
avp@avp-xubu2:~/hashcode$ uname -a
Linux avp-xubu2 5.4.0-84-generic #94-Ubuntu SMP Thu Aug 26 20:27:37 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux
avp@avp-xubu2:~/hashcode$ g++ --vers
g++ (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
avp@avp-xubu2:~/hashcode$ grep CPU /proc/cpuinfo | head -1
model name : Intel(R) Core(TM) i5-2500 CPU @ 3.30GHz
avp@avp-xubu2:~/hashcode$
(сам линукс установлен на VirtualBox под Windows7)
Немного модифицировал программу.
Добавил вызов функции void dummy (size_t *x) {}, которая компилируется раздельно, перед и после циклов копирования вектора в динамически получаемые массивы для того, чтобы гарантировано заставить компилятор всегда генерить код для инициализации массива и копирования вектора.
Также добавил измерение полного времени каждого теста (в миллисекундах), начиная с malloc и заканчивая концом копирования вектора.
Поскольку измеряемое время меняется от запуска к запуску в ощутимых пределах, я сделал внешнюю программу, которая запускает в цикле данную программу и считает среднее время выполнения каждого теста.
Получились вот такие результаты:
.........
time_memcpy_cycle_zero:45 46
time_memcpy_cycle_one:15 54
time_memcpy_without_all:43 43
time_memcpy_memset_zero:43 43
time_memcpy_memset_one:15 46
time_memcpy_cycle_zero:38 38
time_memcpy_cycle_one:16 54
time_memcpy_without_all:41 41
time_memcpy_memset_zero:37 37
time_memcpy_memset_one:15 51
time_memcpy_cycle_zero:38 38
time_memcpy_cycle_one:17 47
time_memcpy_without_all:39 39
time_memcpy_memset_zero:40 40
time_memcpy_memset_one:23 59
time_memcpy_cycle_zero:47 47
time_memcpy_cycle_one:16 48
--- avg for 30 loops total msec ---
time_memcpy_without_all 38
time_memcpy_memset_zero 40
time_memcpy_memset_one 51
time_memcpy_cycle_zero 40
time_memcpy_cycle_one 49
avp@avp-xubu2:~/hashcode$
(тут первое число это время копирования вектора, а второе -- общее время теста, вместе с malloc)
Т.е. мы видим, что общее время тестов без инициализации динамического массива и с инициализацией его нулями составляет порядка 40 мсек, а время выполнения тестов с инициализацией такого же массива единичками существенно больше (порядка 50 мсек).
Анализ ассемблерного кода показал:
во всех тестах при копировании элементов вектора компилятор распознает функцию memcpy и заменяет ее на эквивалентный цикл (копируя по 8 байт за итерацию)
movq (%rsp), %rcx movq %rax, %r12 xorl %eax, %eax .p2align 4,,10 .p2align 3 .L30: movq (%rcx,%rax,8), %rdx movq %rdx, 0(%rbp,%rax,8) addq $1, %rax cmpq $9999999, %rax jne .L30в тестах с обнулением массива компилятор меняет malloc на calloc и выбрасывает как memset (в первом случае), так и обнуление в цикле (во втором).
Собственно, теперь надо понять, почему тесты с обнулением работают с той же скоростью, что и без него, а тесты с инициализацией не нулем на 25% дольше?
Вероятно (как уже указал в своем ответе @Ariox) здесь имеет место следующий сценарий, основанный на том, что современная ОС при первом обращении к выделенной странице памяти обнуляет ее (в целях безопасности).
malloc/calloc при запросе на большой (мы запрашиваем 76 Mбайт для каждого массива) объем памяти выполняют системный вызов mmap, т.е. каждый раз мы получаем набор виртуальных страниц, которые будут привязаны к физическим при первом обращении. При этом связывании ОС обнуляет страницу памяти (ядро будет проводить обнуление в рамках текущего процесса, затраченное на это время будет засчитано ему) и очевидно, что malloc и calloc в таком случае работают одинаково. Вот тут и тратится одинаковое время на инициализацию массива как в тесте без его прописывания, так и в тестах с его инициализацией нулями.
Очевидно, что это же обнуление имеет место и перед прописыванием массива единичкой, т.е. в этих 2-х тестах выполняется лишняя, не нужная нам работа.
Пожалуй, все.
Думаю, что предыдущие версии данного ответа ("прогрев" с изменением величины preload и кэширования таблиц MMU) можно считать ошибочными и я их из текста удаляю.
(впрочем, желающие могут прочесть их, посмотрев историю редактирования)
Вставил ваш изначальный код в godbolt.org с msvc 2019. Все пять циклов были заменены на идентичный код:
call malloc
mov rsi, rax
xor edx, edx
lea rcx, OFFSET FLAT:std::basic_ostream<char,std::char_traits<char> > std::cout ; std::cout
call std::basic_ostream<char,std::char_traits<char> > & std::basic_ostream<char,std::char_traits<char> >::operator<<(unsigned __int64) ; std::basic_ostream<char,std::char_traits<char> >::operator<<
mov rcx, rax
call std::basic_ostream<char,std::char_traits<char> > & std::endl<char,std::char_traits<char> >(std::basic_ostream<char,std::char_traits<char> > &) ; std::endl<char,std::char_traits<char> >
call clock
mov ebx, eax
mov r8d, 79999992 ; 04c4b3f8H
mov rdx, QWORD PTR my_vector_rand$[rsp]
mov rcx, rsi
call memcpy
call clock
Никаких лишних операций тут нет, массив обрабатывается только в memcpy.
Т.е. как минимум, ваши предположения о причинах происходящего неверны. Также вероятно, что вы не включили нормальную оптимизацию, или установили какие-то дополнительные флаги компилятора, искажающие результат.
UPD: Не заметил, во всех циклах оптимизирован memset, но в последней реализации что-то похожее на инициализацию перед измерением времени осталось, а удаление memset в итоге почему-то ухудшает производительность.
Перезагрузился в винду и собрал у себя: наблюдается поведение из вопроса. Лечится заменой
size_t num = 99999999;
на
size_t num = std::stoi("99999999"); // или другая реализация черного ящика
После избавления от константы time_memcpy_without_all работает медленнее остальных. Это либо промахи кэша (что сомнительно, т.к. на больших массивах тоже проявляется), либо инициализация таблиц виртуальной памяти - для больших массивов windows вроде бы не выделяет физическую память непосредственно в malloc, в выделяет виртуальную, которая инициализируемый при первом обращении. Но могу ошибаться.