Почему memcpy() и memmove() быстрее, чем приращение указателя?
Я копирую N байт из pSrc в pDest, Это можно сделать за один цикл:
for (int i = 0; i < N; i++)
*pDest++ = *pSrc++
Почему это медленнее, чем memcpy или же memmove? Какие трюки они используют, чтобы ускорить это?
9 ответов
Поскольку memcpy использует указатели слов вместо байтовых указателей, также реализации memcpy часто пишутся с инструкциями SIMD, что позволяет перетасовывать 128 бит за раз.
SIMD-инструкции - это инструкции по сборке, которые могут выполнять одну и ту же операцию для каждого элемента в векторе длиной до 16 байтов. Это включает в себя инструкции загрузки и хранения.
Процедуры копирования памяти могут быть намного сложнее и быстрее, чем простая копия памяти с помощью указателей, таких как:
void simple_memory_copy(void* dst, void* src, unsigned int bytes)
{
unsigned char* b_dst = (unsigned char*)dst;
unsigned char* b_src = (unsigned char*)src;
for (int i = 0; i < bytes; ++i)
*b_dst++ = *b_src++;
}
улучшения
Первое улучшение, которое можно сделать, это выровнять один из указателей на границе слова (под словом я имею в виду собственный целочисленный размер, обычно 32 бита /4 байта, но может быть 64 бита /8 байт на более новых архитектурах) и использовать перемещение размером слова / скопировать инструкцию. Это требует использования байта для копирования байтов, пока указатель не будет выровнен.
void aligned_memory_copy(void* dst, void* src, unsigned int bytes)
{
unsigned char* b_dst = (unsigned char*)dst;
unsigned char* b_src = (unsigned char*)src;
// Copy bytes to align source pointer
while ((b_src & 0x3) != 0)
{
*b_dst++ = *b_src++;
bytes--;
}
unsigned int* w_dst = (unsigned int*)b_dst;
unsigned int* w_src = (unsigned int*)b_src;
while (bytes >= 4)
{
*w_dst++ = *w_src++;
bytes -= 4;
}
// Copy trailing bytes
if (bytes > 0)
{
b_dst = (unsigned char*)w_dst;
b_src = (unsigned char*)w_src;
while (bytes > 0)
{
*b_dst++ = *b_src++;
bytes--;
}
}
}
Различные архитектуры будут работать по-разному в зависимости от того, правильно ли выровнены указатель источника или назначения. Например, на процессоре XScale я получил лучшую производительность, совместив указатель назначения, а не указатель источника.
Для дальнейшего повышения производительности может быть выполнено некоторое развертывание цикла, так что большее количество регистров процессора загружается данными, и это означает, что инструкции загрузки / сохранения могут чередоваться и их задержка скрывается дополнительными инструкциями (такими как подсчет циклов и т. Д.). Преимущество, которое это приносит, сильно зависит от процессора, так как задержки загрузки / сохранения команд могут быть совершенно разными.
На этом этапе код заканчивается написанием на ассемблере, а не на C (или C++), поскольку вам необходимо вручную разместить инструкции загрузки и сохранения, чтобы получить максимальную выгоду от сокрытия задержки и пропускной способности.
Обычно целую строку данных кэша следует копировать за одну итерацию развернутого цикла.
Что подводит меня к следующему улучшению, добавляя предварительную выборку. Это специальные инструкции, которые говорят кеш-системе процессора загружать определенные части памяти в кеш. Поскольку существует задержка между выдачей инструкции и заполнением строки кэша, инструкции должны быть размещены таким образом, чтобы данные были доступны, когда они должны быть скопированы, и не раньше / позже.
Это означает размещение инструкций предварительной выборки в начале функции, а также внутри основного цикла копирования. С инструкциями предварительной выборки в середине цикла копирования извлекаются данные, которые будут скопированы за несколько итераций.
Я не помню, но также может быть полезно предварительно выбрать адреса назначения, а также адреса источника.
факторы
Основными факторами, влияющими на скорость копирования памяти, являются:
- Задержка между процессором, его кэшами и основной памятью.
- Размер и структура строк кэша процессора.
- Инструкции перемещения / копирования памяти процессора (задержка, пропускная способность, размер регистра и т. Д.).
Поэтому, если вы хотите написать эффективную и быструю процедуру управления памятью, вам нужно много знать о процессоре и архитектуре, для которой вы пишете. Достаточно сказать, что если вы не пишете на какой-либо встроенной платформе, было бы намного проще просто использовать встроенные процедуры копирования в память.
memcpy может копировать более одного байта одновременно, в зависимости от архитектуры компьютера. Большинство современных компьютеров могут работать с 32 битами или более в одной инструкции процессора.
00026 * Для быстрого копирования оптимизируйте общий случай, когда оба указателя
00027 * и длина выровнены по словам, и вместо этого копируйте слово за раз
00028 * байт за раз. В противном случае, копировать байтами.
Вы можете реализовать memcpy() используя любой из следующих методов, некоторые из которых зависят от вашей архитектуры для повышения производительности, и все они будут намного быстрее, чем ваш код:
Используйте большие единицы, такие как 32-битные слова вместо байтов. Вы также можете (или, возможно, должны) иметь дело с выравниванием здесь. Вы не можете читать / записывать 32-разрядное слово в нечетную область памяти, например, на некоторых платформах, а на других платформах вы платите огромные потери производительности. Чтобы исправить это, адрес должен делиться на единицу, делимую на 4. Вы можете сделать это до 64-битных для 64-битных процессоров или даже выше, используя инструкции SIMD (одна команда, несколько данных) ( MMX, SSE и т. Д.)
Вы можете использовать специальные инструкции процессора, которые ваш компилятор может не оптимизировать из C. Например, на 80386 вы можете использовать инструкцию префикса "rep" + инструкция "movsb", чтобы переместить N байтов, продиктованных путем помещения N в счетчик. регистр. Хорошие компиляторы просто сделают это для вас, но вы можете быть на платформе, в которой нет хорошего компилятора. Обратите внимание, что этот пример, как правило, является плохой демонстрацией скорости, но в сочетании с выравниванием + более крупными инструкциями юнитов он может быть быстрее, чем все остальное на определенных процессорах.
Развертывание циклов - ветви могут быть довольно дорогими на некоторых процессорах, поэтому развертывание циклов может уменьшить количество ответвлений. Это также хороший метод для объединения с инструкциями SIMD и очень крупными единицами измерения.
Например, http://www.agner.org/optimize/ имеет memcpy реализация, которая бьет больше всего там (очень незначительное количество). Если вы прочитаете исходный код, он будет полон тонн встроенного ассемблерного кода, который использует все три вышеупомянутых метода, выбирая, какой из этих методов зависит от того, на каком процессоре вы работаете.
Обратите внимание, что существуют похожие оптимизации для поиска байтов в буфере. strchr() и друзья часто будут быстрее, чем ваш эквивалент, брошенный рукой. Это особенно верно для .NET и Java. Например, в.NET встроенный String.IndexOf() намного быстрее, чем даже поиск строки Бойера – Мура, потому что он использует вышеупомянутые методы оптимизации.
Я не знаю, действительно ли он используется в каких-либо реальных реализациях memcpy, но я думаю, что Устройство Даффа заслуживает упоминания здесь.
Из Википедии:
send(to, from, count)
register short *to, *from;
register count;
{
register n = (count + 7) / 8;
switch(count % 8) {
case 0: do { *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
} while(--n > 0);
}
}
Обратите внимание, что выше не является memcpy поскольку он намеренно не увеличивает to указатель. В нем реализована немного другая операция: запись в регистр с отображением в памяти. См. Статью Wikipedia для деталей.
Короткий ответ:
- заполнение кеша
- передача по размеру слова вместо байтовых, где это возможно
- SIMD магия
Как и другие, говорят, что копии memcpy больше 1-байтовых кусков. Копирование кусками размером в слово происходит намного быстрее. Однако большинство реализаций делают шаг вперед и запускают несколько инструкций MOV (word) перед циклом. Преимущество копирования, скажем, блоков из 8 слов в цикле состоит в том, что сам цикл является дорогостоящим. Этот метод уменьшает количество условных ветвлений в 8 раз, оптимизируя копию для гигантских блоков.
Ответы отличные, но если вы все еще хотите реализовать быстрый memcpy сами, есть интересное сообщение в блоге о fast memcpy, Fast memcpy в C.
void *memcpy(void* dest, const void* src, size_t count)
{
char* dst8 = (char*)dest;
char* src8 = (char*)src;
if (count & 1) {
dst8[0] = src8[0];
dst8 += 1;
src8 += 1;
}
count /= 2;
while (count--) {
dst8[0] = src8[0];
dst8[1] = src8[1];
dst8 += 2;
src8 += 2;
}
return dest;
}
Даже лучше с оптимизацией доступа к памяти.
Потому что, как и многие библиотечные процедуры, она была оптимизирована для архитектуры, на которой вы работаете. Другие опубликовали различные методы, которые могут быть использованы.
Если у вас есть выбор, используйте библиотечные процедуры, а не свои собственные. Это разновидность DRY, которую я называю DRO (не повторяйте других). Кроме того, библиотечные процедуры менее вероятны, чем ваши собственные реализации.
Я видел, как контролеры доступа к памяти жалуются на недопустимые чтения в памяти или строковые буферы, которые не кратны размеру слова. Это результат используемой оптимизации.
Вы можете посмотреть на реализацию memset, memcpy и memmove в MacOS.
Во время загрузки ОС определяет, на каком процессоре она работает. Он имеет встроенный специально оптимизированный код для каждого поддерживаемого процессора и во время загрузки сохраняет инструкцию jmp для нужного кода в фиксированном месте только для чтения.
Реализации C memset, memcpy и memmove - это всего лишь переход к этому фиксированному месту.
Реализации используют различный код в зависимости от выравнивания источника и назначения для memcpy и memmove. Очевидно, они используют все доступные векторные возможности. Они также используют варианты без кеширования при копировании больших объемов данных и имеют инструкции по минимизации ожидания таблиц страниц. Это не просто код ассемблера, это код ассемблера, написанный кем-то, кто очень хорошо знает архитектуру каждого процессора.
Intel также добавила инструкции ассемблера, которые могут ускорить строковые операции. Например, с инструкцией для поддержки strstr, которая выполняет сравнение 256 байт за один цикл.