Об истории реализаций memcpy и их производительности

    void * memcpy ( void * destination, const void * source, size_t num );
    Казалось бы, что там сложного? А о реализациях этой функции можно написать целую историю.

    Когда я смотрю на окно своего любимого рабочего инструмента — профилировщика Vtune XE, очень часто вижу, что он в очередной раз обнаружил, что значительное время потратилось на копирование памяти. Так и обычно и написано: clock ticks spent in libgcc/[g]libc/kernel memcpy — XX%.

    Наверное, поэтому memcpy часто переписывался, например в lkml частенько появляются подобные треды. (Больше реализаций, скорее всего, есть только у сортировок). Казалось бы, в отличие от сортировки, где есть много вариантов и алгоритмов с копированием памяти все просто. На самом деле, даже если говорить о корректности, а не производительности, возможны варианты. (В подтверждение тому — обсуждение эпического бага с участием Линуса Торвальдса и Ульриха Дреппера).

    Еще во времена 8086, то есть тридцать четыре года назад, внутри реализации memcpy был следующий код:
    mov [E]SI, src
    mov [E]DI, ptr_dst
    mov [E]CX, len
    rep movsb
    (все проверки и т.д. здесь и далее опущены для простоты)

    Что же изменилось с тех пор? Под катом ассемблерный код и ни одной картинки.

    В классической работе Агнера Фога Optimizing Assembly есть хорошее (но не очень подробное) объяснение большинства аспектов производительности memcpy.

    В середине 90-х программисты обнаружили, что, несмотря на то, что новые инструкции не всегда ускоряют интернет, использовать расширенные SIMD регистры можно, чтобы копировать память быстрее, чем это делает REP MOVS.

    Сначала в качестве промежуточного хранилища использовались MMx регистры, потом XMM. Забегая вперед скажу, что до YMM не дошло.
    movups XMM[0-4], [src] (x4, полная кэш линия)
    movups [dst], XMM[0-4]

    Потом добавились разные комбинации из [не]выровненного чтения, [выравнивания], и [не]выровненной записи в память, в лучшем случае(SSE4.1) получалось что-то вроде
    mov[nt]dqa XMM2, [src+i*2]
    mov[nt]dqa XMM1, [src+i*2+1]
    movdqa XMM1, XMM0
    movdqa XMM0, XMM3
    palignr XMM3, XMM2, shift
    palignr XMM2, XMM1, shift
    mov[nt]dqa [dst+i*2], XMM2
    mov[nt]dqa [dst+i*2+1], XMM3
    Небольшая сложность в том, что инструкция выравнивания существует только с immediate последним операндом (shift), из-за этого код хорошо так раздувается (см. glibc). Кстати, начиная с архитектуры «Nehalem», невыровненый доступ в память, с которым борется вышеприведенный код, больше не является важнейшей причиной тормозов, хотя и не бесплатен.

    Таким образом появилось несколько реализаций memcpy, каждая из которых работала быстрее на одних процессорах, но медленнее на остальных. Через какой-то время несколько вариантов и код, который выбирает, который из них вызывать, пробрались в glibc. Наверное, среды CLR и JVM тоже умеют выбирать эффективную реализацию System.arraycopy на лету. В отличие от glibc в ядро такой SSE код просто так не впендюрить. Там все еще интереснее, надо сохранять SIMD регистры, а дело это не такое быстрое. Что в Linux, что в Windows.

    А недавно вдруг раз, и все вернулось на круги своя. (Может быть, для того, чтобы не заставлять переписывать memcpy на AVX?) Для последних процессоров классическая реализация memcpy снова самая быстрая. Так что если кто-то проспал 34 года, самое время вытащить старый код, и победно посмотреть на коллег, которые переписывали memcpy последовательно на MMX, SSE2, SSE3, SSE4.1.

    Кстати, чтобы было еще интереснее тестировать производительность копирования (особенно в контексте реального софта), на нее могут влиять еще non temporal чтение и запись, ограничения скорости доступа к памяти, эффекты, связанные с общим кэшем последнего уровня, и промахи по DTLB.

    Выводы.
    1. Писать очередную реализацию теперь бесполезно, std::memcpy останется эффективной, используя rep movs.
    2. Для изучения истории вопроса и изучения производительности на старых платформах, см. эту статью и Agner Fog.
    3. На Атоме, других X86 платформах и старых (до Нехалема) процессорах rep mov все еще медленный.

    Upd:
    Как неоднократно просили в комментах, прогнал простую микробенчмарку с memcpy пары килобайт со всеми комбинациями выравнивания в цикле.
    Цифра — во сколько раз самый продвинутый SSE4.1 код быстрее, чем std::memcpy, реализованный через rep movs
    Bulldozer — 1.22x (спасибо stepmex за данные)
    Penryn — 1.6x
    Nehalem — 1.5x
    Sandy Bridge — 1.008x
    Этот бенчмарк не особенно точный, в реальном софте играют роль многие другие факторы, которые я вкраце перечислил выше.
    Intel
    201,00
    Компания
    Поделиться публикацией

    Комментарии 36

      +2
      Интересно, еще хотелось бы узнать и про не-x86 реализации.
        0
        Сорри, у меня в лабе куча всего, но по понятным причинам только Интел. Даже померять не начем. Может быть, кто-нибудь прокомментирует про ARM, MIPS, SPARC или POWER?
          0
          Есть доступ к машине на POWER, если бы был какой то тест…
          P.S. Сам я в asm не силен.
            0
            мои тесты не пойдут, у меня все на x86 assembly. Впрочем, на POWER, возможно и проблемы зоопарка memcpy нет — все таки RISC, все там должно быть аккуратненько.
              0
              На sandy bridge сегодня могу протестировать.

              у копирования через non temporal ограниченная применимость. Там, где применимо, оно, конечно, должно быть быстрее rep movs
            +1
            На архитектурах с явным параллелизмом команд используется SWP-версия memcpy, разанроленная на несколько итераций. Но если надо скопировать всего несколько байт, то быстрее будет обычная load/store реализация.
            В добавок, для больших массивов, надо использовать префетч данных в кеши разных уровней.
            С учётом этого, проверок на выровненность и т.п., memcpy разростается до нескольких сотен строк :)
              +1
              А что, там не простого h/w stride prefetcher'а?
                0
                В Итаниуме вообще нет h/w prefetcher'а, в Эльбрусе не знаю :)
            +11
            На мой взгляд, так и должно было быть всегда. Меня всегда удивляло, почему movsb не эффективен и программисты создают свои длинные и сложные функции копирования. Ведь раз есть процессорные инструкции, специально предназначенные для копирования памяти, то именно они и должны копировать память наиболее эффективно. Собственно не понятно, чем разработчикам процессоров не приглянулись инструкции rep movsb/movsw/movsd что их так долго не оптимизировали.
              +1
              Не знаю, но они это поняли наконец-то. Теперь, я думаю, такого зоопарка реализаций больше не будет.
                +5
                Не первопричина, но важный фактор — в x86 с каждым новым семейством процессоров становится все больше команд, процессор становится все сложнее, в том числе усложняется декодер (узел, который из x86 делает микроинструкции). Процессор уже настолько сложен, что не так просто в нем оптимизировать какую-то конкретную вещь. А поскольку приоритеты часто задает маркетинг, то и возникают такие несчастные случаи, когда достаточно очевидная проблема годами не решается.
                +2
                Интересно, как обстоят дела с rep movs у заклятых друзей Intel по x86-платформе.
                  0
                  Сорри, даже померять не на чем. Может, кто прокомментирует?
                    0
                    У Вас есть тесты? Только в исходниках ;)
                    Могу прогнать на Phenom X4 9650.
                      0
                      OS?
                        0
                        Windows 7 (32-разрядная).
                    0
                    См. коммент в конце треда.
                    0
                    Приветствую, Александр.
                    Таки хотелось бы посмотреть на цифры — насколько быстрее.
                    Детали на уровне микро — секрет? ;)
                      +1
                      очень уж большая таблица получается (каждый год по микроархитектуре, и штук 5 memcpy). разница получается в 2-3 раза между лучшей и худшей реализацией для каждого проца.

                      Кроме того, микробенчмарк только из memcpy не так интересен, в реальном приложении еще дополнительные факторы, которые я указал в статье вступают в силу.
                        0
                        Интересно другое:
                        1. последний нехалем (впрочем SandyBridge устроит ;) ) и насколько rep movs быстрее самой быстрой среди известных сложных реализций копирования.
                        2. Что rep movs стал даже быстрее чем копирование через non temporal?
                          0
                          На sandy bridge сегодня могу протестировать.

                          у копирования через non temporal ограниченная применимость. Там, где применимо, оно, конечно, должно быть быстрее rep movs
                            –1
                            Сергей, я запостил update.
                              +1
                              Ага. :) Так и хочется побурчать про оформление результата — бери пример с Леши. ;)
                              > Цифра — во сколько раз самый продвинутый SSE4.1 код быстрее, чем std::memcpy, реализованный через rep movs
                              > Penryn — 1.6x
                              > Nehalem — 1.5x
                              > Sandy Bridge — 1.008x

                              1. Таки на Нехалеме лучше юзать SSE код — полтора раза это полтора раза. ;)

                              2. Сразу же вопрос, а таки если для SandyBridge сдеать AVX код? ;)
                                –1
                                0. никогда не был силен в оформлении, ну, ты знаешь.
                                1 да.
                                2. не поможет, инфа 100%.
                        +1
                        А давайте вы как-то подтвердите свои слова хотя бы конкретными цифрами, не говоря уже о повторяемых бенчмарках?

                        Потому что опровержений им вагон и маленькая тележка. Пока простой memcpy жарит окружающих раскаленным процессором, копируя картинку из одной области в другую, оптимизированная SSE-версия успевает сделать это раз в 20 быстрее. В 20 раз, а не в 2-3.
                          0
                          Я специально написал, что есть особый случай для non temporals/write combined памяти (которые и используются для копирования картинок по фреймбуфферам и memory mapped IO). Действительно, там возможна такая разница.

                          Для наиболее употребительного копирования нескольких килобайт в обычной памяти, могу прислать простой микро бенчмарк в личку. для виндов устроит, найдется nehalem/westmere/sandy bridge чтобы проверить?
                            –2
                            при чём здесь какие-то фреймбуферы? О чём вы говорите?

                            Я писал про копирование картинки по обычной памяти для сжатия в H.264

                            Бенчмарки в личку — это просто какое-то неуважение. Впрочем, от виндового пользователя, который думает, что копированием нескольких килобайт можно что-то проверить ничего другого ждать и не приходится.

                              –1
                              Фреймбуфер — один из сценариев, в котором на Sandy Bridge и последующих процессорах код копирования, реализованный на SSE4 будет существенно быстрее, чем на rep movs.

                              Вы спросили про бенчмарк, т.к. вы считаете, что мои даные и/или микро бенчмарк некорректны. Я был готов прислать исходник. Где здесь неуважение? Еще пара человек спросили, выслал и им.

                              Если для виндов не подходит, то для какой ОС? И кстати, что не так с пользователями, которые в числе прочих ОС пользуются и виндами?

                              Основной тезис моей статьи был, что давно rep movs был эффективным, потом появились гораздо лучшие SSE реализации, но недавно, по сути с Sandy Bridge и последующих, копирование при помощи rep mov, которое используется в ядре Linux и некоторых других продуктов(MSVC stdlib и тд) сравнялось по скорости с сложным SIMD кодом.

                              Из двух ваших комментариев, если я их правильно понял, следует противоположный тезис — ничего не изменилось, на процессорах Sandy Bridge, которые вышли примерно год назад, SIMD реализация копирования в 20 раз быстрее, чем rep movs.
                              Я свой бенчмарк (которым, по-вашему, ничего проверить нельзя) описал. Можно узнать подробности вашего? В вашем бенчмарке, где вы копируете картинку для последующего сжатия, у вас просто
                              memcpu(kartinka_dest, kartinka_src, kartinka_len_in_bytes);
                              или вы копируете как-то по линиям или еще как-то? Какого размера область памяти? Находится ли она уже в LLC?
                                –3
                                Выложите проверяемые бенчмарки в статье с их результатами. Иначе все ваши слова с вашей недостатейкой в которой вы обманываете людей — полное фуфло. Впрочем, они и есть фуфло, потому что вы попросту не в теме и думаете, что копированием килобайта можно что-то намерять.

                            –1
                            Запостил update, могу прислать код u-benchmark'а.
                            +1
                            Во времена 8086 внутренняя реализация memcpy использовала 32-битные регистры esi, edi и ecx? ;)
                              0
                              DI, SI, CX конечно.
                              +2
                              По теме истории развития реализации есть интересная статейка Using Block Prefetch for Optimized Memory Performance.
                                –1
                                да, тоже очень интересно с исторической т.з. Один из выводов из статьи — в начале 2000х на AMD железные префетчеры не справлялись даже с линейным паттерном доступа. Впрочем, я не уверен, что в те времена и на Pentium4 все было с этим в порядке.
                                0
                                В русле обсуждения данной темы очень кстати может оказаться статья "Аппаратные и программные циклы: кто быстрее"?
                                  0
                                  Хорошие результаты, но все предсказуемо — при маленьких объемах вызов микрокода — относительно большие накладные расходы для фронт енда. При больших объемах — вызов амортизируется, фронт енду наоборот приходится декодировать лишние объемы кода, особенно если он не поместился в LSD.

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                Самое читаемое