У меня есть функция, которая выполняет memcpy, но она занимает огромное количество циклов. Есть ли более быстрая альтернатива / подход, чем использование memcpy для перемещения фрагмента памяти?
более быстрая альтернатива memcpy?
Ответы (16)
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 байта для четырехканальных). system), тогда как 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();
}
}
prefetch
или чего-то подобного, но я не смог вспомнить, что именно ... какое совпадение, только что найденное в этой ветке, @ 2009004, последняя ссылка stackoverflow.com/questions/ 1715224 /
- person http8086; 03.04.2020
Расскажите, пожалуйста, подробнее. На архитектуре i386 очень возможно, что memcpy - самый быстрый способ копирования. Но для другой архитектуры, для которой у компилятора нет оптимизированной версии, лучше всего переписать свою функцию memcpy. Я сделал это на пользовательской архитектуре ARM с использованием языка ассемблера. Если вы переносите БОЛЬШИЕ фрагменты памяти, то, вероятно, вы ищете ответ DMA.
Предложите подробнее - архитектуру, операционную систему (если актуально).
Обычно стандартная библиотека, поставляемая с компилятором, уже реализует memcpy()
самый быстрый способ из возможных для целевой платформы.
На самом деле memcpy - НЕ самый быстрый способ, особенно если вы вызываете его много раз. У меня также был код, который мне действительно нужно было ускорить, а memcpy работает медленно, потому что в нем слишком много ненужных проверок. Например, он проверяет, перекрываются ли целевой и исходный блоки памяти и следует ли начинать копирование с задней стороны блока, а не с передней. Если вас не заботят такие соображения, вы, безусловно, можете добиться большего. У меня есть код, но, возможно, это еще лучшая версия:
Очень быстрый memcpy для обработки изображений?.
Если поискать, можно найти и другие реализации. Но для истинной скорости нужна сборочная версия.
memmove
должен проверять и обрабатывать перекрытие, memcpy
этого делать не требуется. Более серьезная проблема заключается в том, что для эффективного копирования больших блоков реализации memcpy
должны выбрать подход к копированию, прежде чем они смогут начать работу. Если код должен иметь возможность копировать произвольное количество байтов, но это число будет одним в 90% случаев, двумя в 9% случаев, тремя в 0,9% случаев и т. Д. И значениями count
, dest
, и src
впоследствии не понадобится, тогда встроенная if (count) do *dest+=*src; while(--count > 0);
может быть лучше, чем более умная рутина.
- person supercat; 16.03.2015
memcpy
может быть не самым быстрым подходом заключается в том, что контроллер DMA может иногда копировать блок памяти с меньшими накладными расходами, чем ЦП, но наиболее эффективным способом копирования может быть запустите DMA, а затем выполните другую обработку во время работы DMA. В системе с отдельным внешним кодом и шинами данных можно настроить DMA так, чтобы он копировал данные в каждом цикле, когда ЦП не нуждается в шине данных ни для чего другого. Это может обеспечить гораздо лучшую производительность, чем использование ЦП для копии, используя ...
- person supercat; 05.04.2015
await_memcpy_complete()
, но любой код обычно должен быть настроен для конкретных требований приложения, и ничего подобного не включено в стандартную библиотеку.
- person supercat; 05.04.2015
Как правило, быстрее вообще не делать копию. Я не знаю, сможете ли вы адаптировать свою функцию, чтобы не копировать, но на это стоит посмотреть.
Вы должны проверить код сборки, созданный для вашего кода. Чего вы не хотите, так это чтобы вызов memcpy
генерировал вызов функции memcpy
в стандартной библиотеке - вам нужно, чтобы повторяющийся вызов лучшей инструкции ASM для копирования наибольшего количества данных - что-то вроде rep movsq
.
Как этого добиться? Что ж, компилятор оптимизирует вызовы memcpy
, заменяя его простыми mov
s, если он знает, сколько данных он должен скопировать. Вы можете увидеть это, если напишете memcpy
с четко определенным (constexpr
) значением. Если компилятор не знает значения, ему придется вернуться к реализации memcpy
на уровне байтов - проблема в том, что memcpy
должен соблюдать однобайтовую гранулярность. Он по-прежнему будет перемещать 128 бит за раз, но после каждых 128b ему придется проверять, достаточно ли у него данных для копирования как 128b, или он должен вернуться к 64 битам, затем к 32 и 8 (я думаю, что 16 может быть неоптимальным все равно, но точно не знаю).
Итак, вам нужно либо указать memcpy
, какой размер ваших данных, с помощью константных выражений, которые компилятор может оптимизировать. Таким образом, вызов memcpy
не выполняется. Чего вы не хотите, так это передавать memcpy
переменную, которая будет известна только во время выполнения. Это переводится в вызов функции и множество тестов, чтобы проверить лучшую инструкцию копирования. Иногда по этой причине простой цикл for лучше, чем memcpy
(исключение одного вызова функции). И что вам действительно не нужно, так это передать memcpy
нечетное количество байтов для копирования.
Иногда такие функции, как memcpy, memset, ... реализуются двумя разными способами:
- однажды как реальная функция
- один раз как некоторая сборка, которая сразу встраивается
Не все компиляторы принимают версию встроенной сборки по умолчанию, ваш компилятор может использовать вариант функции по умолчанию, вызывая некоторые накладные расходы из-за вызова функции. Проверьте свой компилятор, чтобы узнать, как использовать внутренний вариант функции (параметр командной строки, директивы, ...).
Изменить: см. http://msdn.microsoft.com/en-us/library/tzkfha43%28VS.80%29.aspx для объяснения встроенных функций компилятора Microsoft C.
Вот альтернативная версия 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];
}
}
Ознакомьтесь с руководством по компилятору / платформе. Для некоторых микропроцессоров и наборов DSP использование memcpy намного медленнее, чем встроенные функции или операции DMA.
Если ваша платформа поддерживает это, посмотрите, можете ли вы использовать системный вызов mmap (), чтобы оставить свои данные в файле ... обычно ОС может справиться с этим лучше. И, как все говорили, избегайте копирования, если это вообще возможно; указатели - ваш друг в таких случаях.
Я предполагаю, что у вас должны быть огромные области памяти, которые вы хотите скопировать, если производительность memcpy стала для вас проблемой?
В этом случае я бы согласился с предложением NOS найти способ НЕ копировать материал ..
Вместо того, чтобы копировать один огромный кусок памяти всякий раз, когда вам нужно его изменить, вам, вероятно, следует попробовать альтернативные структуры данных.
Не зная ничего о своей проблемной области, я бы посоветовал внимательно изучить постоянные структуры данных и либо реализуя свою собственную, либо повторно используя существующую реализацию.
Вы можете взглянуть на это:
http://www.danielvik.com/2010/02/fast-memcpy-in-c.html
Еще одна идея, которую я хотел бы попробовать, - это использовать методы COW для дублирования блока памяти и позволить ОС обрабатывать копирование по запросу, как только страница будет записана. Здесь есть несколько подсказок с использованием mmap()
: Могу ли я сделать копирование при записи memcpy в Linux?
Эта функция может вызвать исключение прерывания данных, если один из указателей (входных аргументов) не выровнен по 32 битам.
память в память обычно поддерживается в наборе команд ЦП, и memcpy обычно использует это. И это обычно самый быстрый способ.
Вы должны проверить, что именно делает ваш процессор. В Linux следите за входом и выходом подкачки и эффективностью виртуальной памяти с помощью sar -B 1 или vmstat 1 или просматривая / proc / memstat. Вы можете увидеть, что ваша копия должна вытолкнуть много страниц, чтобы освободить место, или прочитать их и т. Д.
Это означало бы, что ваша проблема не в том, что вы используете для копии, а в том, как ваша система использует память. Возможно, вам потребуется уменьшить файловый кеш или начать запись раньше, или заблокировать страницы в памяти и т. Д.
Вот несколько тестов 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
(или то, что он должен делать, если вы включите правильную оптимизацию для своей платформы).
Также невозможно сделать это быстрее, так как теперь мы ограничены пропускной способностью кеша, которая не работает быстрее. Я думаю, что это очень важный факт, на который стоит обратить внимание, потому что, если вы ограничены памятью и ищете более быстрое решение, вы будете искать очень долго.