суббота, 11 апреля 2015 г.

Fastest memcpy

В Сети полно тредов с обсуждением, можно ли обогнать memcpy из С lib. Из спортивного интереса я тоже решил поэкспериментировать с этим, зная что многие пытаются использовать SSE для копирования памяти через регистры xmm. Сделаем несколько допущений:

1) Большой кусок памяти (мегабайты).
2) Память выровненна по границе 16 байт.
3) Таргет CPU с обязательным наличием SSE2.
4) Соревнуемся с memcpy из VS 2012.

Можно попробовать написать максимально упрощённую под эти условия функцию, тогда как memcpy вынуждена проверять cpuid, производить проверку на выравнивание, на размер, чтобы выполнить оптимальный код, дописывать хвостики и т. д.

После различных попыток я в конце-концов остановился на комбинации SSE интринсиков _mm_stream_load_si128 / _mm_stream_si128 для копирования блоков памяти и _mm_prefetch(_MM_HINT_NTA) для указания процессору о том, что не нужно загрязнять кэш данными, так как они используются только короткое время. В x64 используются дополнительные регистры xmm8-xmm15, чтобы сократить кол-во блоков (итераций цикла) копирования. Тестовая программа состоит из 1000 циклов копирования кусков памяти размером 16Mb. Каждый цикл повторяется 10 раз чтобы удостовериться в правильности времени выполнения.

Результаты для процессора AMD FX-8320, release x86 и x64:


Судя по тому, что время отличается незначительно для x64, можно сделать вывод что CRT версия проигрывает из-за универсальности. Если бы не было 1000 циклов, эффект от ускорения был-бы несущественным. В x86 ускорение уже значительное, возможно Microsoft не удосужились оптимизировать runtime для архитектуры Bulldozer.

Кроме этого, я решил реализовать мультипоточную версию функции копирования и посмотреть, исполняется ли она эффективнее на многоядерном процессоре. Мультипоточная версия очень проста: она использует функции API Windows CreateThread/Semaphore, а также WaitForMultipleObjects для ожидания окончания работы множества потоков основным потоком. Это обеспечивает ясность над процессом распределения инструкций. Блок памяти делится на равные (по возможности) части и каждая часть копируется отдельным потоком.

Результаты для x64.
2 потока:
4 потока:
 8 потоков:

Как видно, использование самописного SSE и двух потоков в сумме даёт прирост в скорости около 40%. Дальнейшее увеличение кол-ва потоков практически не имеет смысла, т. к. прирост ни разу не линейный, а ядра становятся заняты. Уже после того, как код был написан и протестирован, выяснилось, что обычная память не допускает одновременного доступа к разным адресам, и что это умеет делать только Dual Port RAM.

Для чистоты эксперимента - x86 build, 8 потоков:


Максимальный прирост в скорости копирования - приблизительно двукратный. Да, x86 memcpy оказалась медленнее всего!

Наконец проверим загруженность ядер CPU копированием через xmm регистры.
2 потока:
 4 потока:
 8 потоков:

Масштабирование идеальное.
Выводы:

1) Обогнать memcpy из MSVCR (на AMD) можно.
2) В общем случае многопоточное копирование всё же имеет смысл.
3) Задействование большого кол-во ядер (> 2-4) бессмысленно, из-за того что память не допускает одновременного доступа к разным ядресам.

Update.

Результаты на Core i7-4790:


Результаты на Core i7-3770:



Комментариев нет:

Отправить комментарий