Более быстрая альтернатива memcpy?
У меня есть функция, которая выполняет memcpy, но она занимает огромное количество циклов. Есть ли более быстрый альтернативный подход / подход, чем использование memcpy для перемещения фрагмента памяти?
19 ответов
memcpy скорее всего, это самый быстрый способ скопировать байты в памяти. Если вам нужно что-то быстрее - попробуйте найти способ не копировать вещи, например, только указатели подкачки, а не сами данные.
Это ответ для x86_64 при наличии набора инструкций AVX2. Хотя что-то подобное может применяться для ARM/AArch64 с SIMD.
На Ryzen 1800X с одним полностью заполненным каналом памяти (2 слота, 16 ГБ DDR4 в каждом) следующий код в 1,56 раза быстрее, чем memcpy() на компиляторе MSVC++2017. Если вы заполняете оба канала памяти двумя модулями DDR4, т. Е. У вас заняты все 4 слота DDR4, вы можете в 2 раза быстрее копировать память. Для трех-(четырех-) канальных систем памяти вы можете получить в 1,5(2,0) раза более быстрое копирование памяти, если код будет расширен до аналогичного кода AVX512. В трехканальных / четырехканальных системах только с AVX2 со всеми занятыми слотами не ожидается, что они будут быстрее, потому что для их полной загрузки необходимо загружать / хранить более 32 байтов одновременно (48 байтов для трех- и 64-байтовых для четырехканального). систем), а AVX2 может загружать / хранить не более 32 байтов одновременно. Хотя многопоточность в некоторых системах может облегчить это без AVX512 или даже AVX2.
Итак, вот код копирования, который предполагает, что вы копируете большой блок памяти, размер которого кратен 32, а блок выровнен по 32 байта.
Для не кратного размера и не выровненных блоков код пролога / эпилога может быть записан с уменьшением ширины до 16 (SSE4.1), 8, 4, 2 и, наконец, 1 байта за раз для головки и хвоста блока. Также в середине локальный массив из 2-3 __m256i Значения могут использоваться как прокси между выровненными чтениями из источника и выровненными записями в место назначения.
#include <immintrin.h>
#include <cstdint>
/* ... */
void fastMemcpy(void *pvDest, void *pvSrc, size_t nBytes) {
assert(nBytes % 32 == 0);
assert((intptr_t(pvDest) & 31) == 0);
assert((intptr_t(pvSrc) & 31) == 0);
const __m256i *pSrc = reinterpret_cast<const __m256i*>(pvSrc);
__m256i *pDest = reinterpret_cast<__m256i*>(pvDest);
int64_t nVects = nBytes / sizeof(*pSrc);
for (; nVects > 0; nVects--, pSrc++, pDest++) {
const __m256i loaded = _mm256_stream_load_si256(pSrc);
_mm256_stream_si256(pDest, loaded);
}
_mm_sfence();
}
Ключевой особенностью этого кода является то, что он пропускает кэш процессора при копировании: когда задействован кэш процессора (т.е. инструкции AVX без _stream_ используются), скорость копирования в моей системе падает в несколько раз.
Моя память DDR4 составляет 2,6 ГГц CL13 . Поэтому при копировании 8 ГБ данных из одного массива в другой я получил следующие скорости:
memcpy(): 17 208 004 271 bytes/sec.
Stream copy: 26 842 874 528 bytes/sec.
Обратите внимание, что в этих измерениях общий размер входного и выходного буферов делится на количество прошедших секунд. Поскольку для каждого байта массива есть 2 обращения к памяти: один для чтения байта из входного массива, другой для записи байта в выходной массив. Другими словами, копируя 8 ГБ из одного массива в другой, вы выполняете операции доступа к памяти на 16 ГБ.
Умеренная многопоточность может дополнительно улучшить производительность примерно в 1,44 раза, поэтому общее увеличение по сравнению с memcpy() достигает 2,55 раза на моей машине. Вот как производительность потокового копирования зависит от количества потоков, используемых на моем компьютере:
Stream copy 1 threads: 27114820909.821 bytes/sec
Stream copy 2 threads: 37093291383.193 bytes/sec
Stream copy 3 threads: 39133652655.437 bytes/sec
Stream copy 4 threads: 39087442742.603 bytes/sec
Stream copy 5 threads: 39184708231.360 bytes/sec
Stream copy 6 threads: 38294071248.022 bytes/sec
Stream copy 7 threads: 38015877356.925 bytes/sec
Stream copy 8 threads: 38049387471.070 bytes/sec
Stream copy 9 threads: 38044753158.979 bytes/sec
Stream copy 10 threads: 37261031309.915 bytes/sec
Stream copy 11 threads: 35868511432.914 bytes/sec
Stream copy 12 threads: 36124795895.452 bytes/sec
Stream copy 13 threads: 36321153287.851 bytes/sec
Stream copy 14 threads: 36211294266.431 bytes/sec
Stream copy 15 threads: 35032645421.251 bytes/sec
Stream copy 16 threads: 33590712593.876 bytes/sec
Код является:
void AsyncStreamCopy(__m256i *pDest, const __m256i *pSrc, int64_t nVects) {
for (; nVects > 0; nVects--, pSrc++, pDest++) {
const __m256i loaded = _mm256_stream_load_si256(pSrc);
_mm256_stream_si256(pDest, loaded);
}
}
void BenchmarkMultithreadStreamCopy(double *gpdOutput, const double *gpdInput, const int64_t cnDoubles) {
assert((cnDoubles * sizeof(double)) % sizeof(__m256i) == 0);
const uint32_t maxThreads = std::thread::hardware_concurrency();
std::vector<std::thread> thrs;
thrs.reserve(maxThreads + 1);
const __m256i *pSrc = reinterpret_cast<const __m256i*>(gpdInput);
__m256i *pDest = reinterpret_cast<__m256i*>(gpdOutput);
const int64_t nVects = cnDoubles * sizeof(*gpdInput) / sizeof(*pSrc);
for (uint32_t nThreads = 1; nThreads <= maxThreads; nThreads++) {
auto start = std::chrono::high_resolution_clock::now();
lldiv_t perWorker = div((long long)nVects, (long long)nThreads);
int64_t nextStart = 0;
for (uint32_t i = 0; i < nThreads; i++) {
const int64_t curStart = nextStart;
nextStart += perWorker.quot;
if ((long long)i < perWorker.rem) {
nextStart++;
}
thrs.emplace_back(AsyncStreamCopy, pDest + curStart, pSrc+curStart, nextStart-curStart);
}
for (uint32_t i = 0; i < nThreads; i++) {
thrs[i].join();
}
_mm_sfence();
auto elapsed = std::chrono::high_resolution_clock::now() - start;
double nSec = 1e-6 * std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count();
printf("Stream copy %d threads: %.3lf bytes/sec\n", (int)nThreads, cnDoubles * 2 * sizeof(double) / nSec);
thrs.clear();
}
}
Пожалуйста, предложите нам более подробную информацию. На архитектуре i386 вполне возможно, что memcpy - самый быстрый способ копирования. Но на другой архитектуре, для которой компилятор не имеет оптимизированной версии, лучше переписать функцию memcpy. Я сделал это на пользовательской архитектуре ARM, используя язык ассемблера. Если вы передаете БОЛЬШИЕ куски памяти, то DMA, вероятно, является ответом, который вы ищете.
Пожалуйста, предложите более подробную информацию - архитектура, операционная система (при необходимости).
Обычно стандартная библиотека, поставляемая с компилятором, реализует memcpy() самый быстрый способ для целевой платформы уже.
На самом деле, memcpy - НЕ самый быстрый способ, особенно если вы вызываете его много раз. У меня также был некоторый код, который мне действительно нужен для ускорения, и memcpy работает медленно, потому что в нем слишком много ненужных проверок. Например, он проверяет, перекрываются ли блоки памяти назначения и источника, и должно ли оно начинать копирование с задней части блока, а не с лицевой стороны. Если вас не волнуют такие соображения, вы, безусловно, можете добиться значительно лучших результатов. У меня есть некоторый код, но вот, пожалуй, лучшая версия:
Очень быстрый memcpy для обработки изображений?,
Если вы ищете, вы можете найти и другие реализации. Но для истинной скорости вам нужна сборочная версия.
Agner Fog имеет быструю реализацию memcpy http://www.agner.org/optimize/
Вот альтернативная версия memcpy для C, которая является встроенной, и я считаю, что она превосходит memcpy для GCC для Arm64 примерно на 50% в приложении, для которого я ее использовал. Это 64-битная платформа, независимая. Хвостовая обработка может быть удалена, если экземпляр использования не нуждается в нем для большей скорости. Копирует массивы uint32_t, меньшие типы данных не проверены, но могут работать. Может быть в состоянии адаптироваться к другим типам данных. 64-битное копирование (два индекса копируются одновременно). 32-разрядный также должен работать, но медленнее. Кредиты для проекта Neoscrypt.
static inline void newmemcpy(void *__restrict__ dstp,
void *__restrict__ srcp, uint len)
{
ulong *dst = (ulong *) dstp;
ulong *src = (ulong *) srcp;
uint i, tail;
for(i = 0; i < (len / sizeof(ulong)); i++)
*dst++ = *src++;
/*
Remove below if your application does not need it.
If console application, you can uncomment the printf to test
whether tail processing is being used.
*/
tail = len & (sizeof(ulong) - 1);
if(tail) {
//printf("tailused\n");
uchar *dstb = (uchar *) dstp;
uchar *srcb = (uchar *) srcp;
for(i = len - tail; i < len; i++)
dstb[i] = srcb[i];
}
}
Этому вопросу 12 лет, когда я пишу еще один ответ. Но затем он все еще всплывает в результатах поиска, и ответы постоянно развиваются.
Удивлен, что никто еще не упомянул asmlib Agner Fog .
Отказ от замены memcpy() , а также многие другие оптимизированные для SIMD замены C lib, такие как memmove(), memset(), strlen() и т. д.
Автоматически будет использовать лучшее, что поддерживает ваш ЦП, вплоть до набора инструкций AVX-512. Поставляется с готовыми библиотеками для нескольких платформ x86/AMD64.
Как правило, быстрее вообще не делать копию. Можете ли вы адаптировать свою функцию, чтобы не копировать, я не знаю, но это стоит посмотреть.
Иногда такие функции, как memcpy, memset,... реализуются двумя различными способами:
- однажды как настоящая функция
- когда-то как сборка, которая сразу же
Не все компиляторы принимают версию встроенной сборки по умолчанию, ваш компилятор может использовать вариант функции по умолчанию, что приводит к некоторым издержкам из-за вызова функции. Проверьте ваш компилятор, чтобы увидеть, как использовать встроенный вариант функции (опция командной строки, прагма, ...).
Изменить: см. http://msdn.microsoft.com/en-us/library/tzkfha43%28VS.80%29.aspx для объяснения встроенных функций компилятора Microsoft C.
Вы должны проверить код сборки, созданный для вашего кода. То, что вы не хотите, это иметь memcpy вызов генерировать вызов к memcpy Функция в стандартной библиотеке - вам нужно иметь повторный вызов лучшей инструкции ASM для копирования наибольшего объема данных - что-то вроде rep movsq,
Как вы можете достичь этого? Ну, компилятор оптимизирует вызовы memcpy заменив его простым movДо тех пор, пока он знает, сколько данных он должен скопировать. Вы можете увидеть это, если напишите memcpy с хорошо определенным (constexpr) значение. Если компилятор не знает значение, ему придется вернуться к реализации на уровне байтов memcpy - проблема в том, что memcpy должен уважать однобайтовую гранулярность. Он по-прежнему будет перемещаться по 128 бит за раз, но после каждого 128 b он должен будет проверить, достаточно ли у него данных для копирования как 128 b или он должен вернуться к 64 битам, а затем к 32 и 8 (я думаю, что 16 может быть неоптимальным во всяком случае, но я не знаю точно).
Итак, что вы хотите, так это либо иметь возможность сказать memcpy Каков размер ваших данных с выражениями const, которые компилятор может оптимизировать. Таким образом, нет вызова memcpy выполняется. То, что вы не хотите, это перейти к memcpy переменная, которая будет известна только во время выполнения. Это приводит к вызову функции и множеству тестов для проверки лучшей инструкции копирования. Иногда простой цикл лучше, чем memcpy по этой причине (исключая один вызов функции). И что вы действительно не хотите, это передать memcpy нечетное количество байтов для копирования.
Проверьте ваше руководство по компилятору / платформе. Для некоторых микропроцессоров и DSP-комплектов использование memcpy намного медленнее, чем встроенные функции или операции DMA.
Если ваша платформа поддерживает это, посмотрите, можете ли вы использовать системный вызов mmap(), чтобы оставить ваши данные в файле... обычно ОС справляется с этим лучше. И, как все говорили, избегайте копирования, если это возможно; указатели - ваш друг в таких случаях.
Вот несколько тестов Visual C++/Ryzen 1700.
Тест копирует 16 КиБ (неперекрывающихся) фрагментов данных из 128-мегабайтного кольцевого буфера 8*8192 раз (всего копируется 1 ГиБ данных).
Затем я нормализую результат, здесь мы представляем время настенных часов в миллисекундах и значение пропускной способности для 60 Гц (т.е. сколько данных может обработать эта функция за 16,667 миллисекунд).
memcpy 2.761 milliseconds ( 772.555 MiB/frame)
Как видите, встроенный memcpy быстро, но насколько быстро?
64-wide load/store 39.889 milliseconds ( 427.853 MiB/frame)
32-wide load/store 33.765 milliseconds ( 505.450 MiB/frame)
16-wide load/store 24.033 milliseconds ( 710.129 MiB/frame)
8-wide load/store 23.962 milliseconds ( 712.245 MiB/frame)
4-wide load/store 22.965 milliseconds ( 743.176 MiB/frame)
2-wide load/store 22.573 milliseconds ( 756.072 MiB/frame)
1-wide load/store 35.032 milliseconds ( 487.169 MiB/frame)
Выше приведен только код ниже с вариациями n.
// n is the "wideness" from the benchmark
auto src = (__m128i*)get_src_chunk();
auto dst = (__m128i*)get_dst_chunk();
for (int32_t i = 0; i < (16 * 1024) / (16 * n); i += n) {
__m128i temp[n];
for (int32_t i = 0; i < n; i++) {
temp[i] = _mm_loadu_si128(dst++);
}
for (int32_t i = 0; i < n; i++) {
_mm_store_si128(src++, temp[i]);
}
}
Это мои лучшие предположения относительно результатов, которые у меня есть. Основываясь на том, что я знаю о микроархитектуре Zen, она может извлекать только 32 байта за цикл. Вот почему мы используем максимум 2x 16-байтовых загрузки / сохранения.
- 1x загружает байты в
xmm0, 128 бит - 2x загружает байты в
ymm0, 256 бит
Вот почему он примерно в два раза быстрее, а внутри как раз то, что memcpy делает (или что он должен делать, если вы включите правильную оптимизацию для своей платформы).
Также невозможно сделать это быстрее, так как теперь мы ограничены пропускной способностью кеша, которая не работает быстрее. Я думаю, что это очень важный факт, на который стоит обратить внимание, потому что, если вы ограничены памятью и ищете более быстрое решение, вы будете искать очень долго.
Я предполагаю, что у вас должны быть огромные области памяти, которые вы хотите скопировать, если производительность memcpy стала для вас проблемой?
В этом случае я бы согласился с предложением nos найти какой-то способ НЕ копировать материал..
Вместо того, чтобы копировать один огромный блок памяти всякий раз, когда вам нужно его изменить, вам, вероятно, следует попробовать некоторые альтернативные структуры данных.
Не зная ничего о вашей проблемной области, я бы посоветовал хорошенько взглянуть на постоянные структуры данных и либо внедрить собственную, либо повторно использовать существующую реализацию.
Вы можете взглянуть на это:
http://www.danielvik.com/2010/02/fast-memcpy-in-c.html
Другая идея, которую я бы попробовал, состоит в том, чтобы использовать методы COW для дублирования блока памяти и позволить ОС обрабатывать копирование по требованию, как только страница будет записана. Здесь есть несколько советов, используя mmap(): Могу ли я сделать копию при записи memcpy в Linux?
Эта функция может вызвать исключение сброса данных, если один из указателей (входных аргументов) не выровнен по 32-битам.
Нос прав, ты слишком много это называешь.
Чтобы увидеть, откуда вы это вызываете и почему, просто приостановите его несколько раз под отладчиком и посмотрите на стек.
Память в память обычно поддерживается в наборе команд процессора, и memcpy обычно использует это. И это обычно самый быстрый способ.
Вы должны проверить, что именно делает ваш процессор. В Linux следите за входом и выходом swapi и эффективностью виртуальной памяти с помощью sar -B 1 или vmstat 1 или заглядывая в /proc/memstat. Вы можете увидеть, что ваша копия должна вытолкнуть много страниц, чтобы освободить место, или прочитать их и т. Д.
Это означает, что ваша проблема не в том, что вы используете для копирования, а в том, как ваша система использует память. Возможно, вам придется уменьшить кэш файлов или начать запись раньше, или заблокировать страницы в памяти и т. Д.