Как перекладывать байты

Как перекладывать байты

Алексей Миловидов
Разработчик ClickHouse

Как писать быстрый код?

Высокоуровневая оптимизация:

— выбор правильного алгоритма;
— использование подходящих структур данных;
— выбор интерфейсов, соответствующих задаче;

Низкоуровневая оптимизация:

— избавиться от лишних копирований и аллокаций;
— проследить, чтобы генерировались правильные инструкции;
— проследить, чтобы данные в памяти были хорошо расположены;

Как писать быстрый код?

Профилировать его:

4,47%  libstdc++.so.6.0.28  [.] __dynamic_cast
1,42%  libstdc++.so.6.0.28  [.] __cxxabiv1::__vmi_class_type_info::__do_dyncast
1,37%  libstdc++.so.6.0.28  [.] std::operator>><char, std::char_traits<char>, std::allocator<char> >
1,18%  libstdc++.so.6.0.28  [.] __cxxabiv1::__si_class_type_info::__do_dyncast
0,83%  libstdc++.so.6.0.28  [.] std::basic_ios<char, std::char_traits<char> >::_M_cache_locale
0,75%  libstdc++.so.6.0.28  [.] std::locale::id::_M_id
0,73%  libstdc++.so.6.0.28  [.] std::use_facet<std::ctype<char> >
0,64%  libstdc++.so.6.0.28  [.] std::ios_base::_M_init
0,64%  libc-2.31.so         [.] __strcmp_avx2
0,63%  libstdc++.so.6.0.28  [.] std::ostream::_M_insert<unsigned long>

Как писать быстрый код?

Профилировать его:

4,47%  libstdc++.so.6.0.28  [.] __dynamic_cast
1,42%  libstdc++.so.6.0.28  [.] __cxxabiv1::__vmi_class_type_info::__do_dyncast
1,37%  libstdc++.so.6.0.28  [.] std::operator>><char, std::char_traits<char>, std::allocator<char> >
1,18%  libstdc++.so.6.0.28  [.] __cxxabiv1::__si_class_type_info::__do_dyncast
0,83%  libstdc++.so.6.0.28  [.] std::basic_ios<char, std::char_traits<char> >::_M_cache_locale
0,75%  libstdc++.so.6.0.28  [.] std::locale::id::_M_id
0,73%  libstdc++.so.6.0.28  [.] std::use_facet<std::ctype<char> >
0,64%  libstdc++.so.6.0.28  [.] std::ios_base::_M_init
0,64%  libc-2.31.so         [.] __strcmp_avx2
0,63%  libstdc++.so.6.0.28  [.] std::ostream::_M_insert<unsigned long>

Вопрос

Удалить std::stringstream из внутреннего цикла
— это высокоуровневая или низкоуровневая оптимизация?

Как писать быстрый код?

Профилировать его:

12,96%  clickhouse  [.] memcpy                                    - копирование
10,37%  [kernel]    [k] copy_user_generic_string                  - копирование
 5,73%  clickhouse  [.] DB::deserializeBinarySSE2<1>           - десериализация
 4,50%  clickhouse  [.] DB::deserializeBinarySSE2<4>           - десериализация
 4,47%  clickhouse  [.] LZ4::(anonymous namespace)::decompressImpl<32ul, false>
 4,34%  clickhouse  [.] LZ4::(anonymous namespace)::decompressImpl<8ul, true>
 4,10%  clickhouse  [.] LZ4::(anonymous namespace)::decompressImpl<16ul, false>
 3,96%  clickhouse  [.] LZ4::(anonymous namespace)::decompressImpl<16ul, true>
        

Как уменьшить затраты на memcpy?

memcpy — копирование данных.

Как убрать memcpy из профиля?

1. Меньше копировать данные.
Не всегда возможно.
Часто данные нужно переложить, чтобы всё ускорить.

2. Оптимизировать реализацию memcpy.
Но её уже все оптимизировали?

Важные факты про memcpy

«It's the world's most popular function — one all programmers love»

— Alexandra Justine Roberts Tunney.

Важные факты про memcpy

1. Компилятор может заменять memcpy на встроенную реализацию.
И делает это, если размер небольшой и известен во время компиляции.

memcpy(dst, src, 8);

movq    (%rsi), %rax
movq    %rax, (%rdi)

Это контролируется параметром -fbuiltin-memcpy, -fno-builtin-memcpy.

Встроенную реализацию можно указать явно:
__builtin_memcpy(dst, src, size).

Для неизвестных размеров она будет заменена на вызов memcpy.

Важные факты про memcpy

1. Компилятор может заменять memcpy на встроенную реализацию.
И делает это, если размер небольшой и известен во время компиляции.

memcpy(dst, src, 16):

movups  (%rsi), %xmm0
movups  %xmm0, (%rdi)
memcpy(dst, src, 15):

movq    (%rsi), %rax
movq    7(%rsi), %rcx
movq    %rcx, 7(%rdi)
movq    %rax, (%rdi)

Важные факты про memcpy

2. Компилятор может заменять ваш код на вызов memcpy.
И делает это, если вы пишете что-то похожее.

void f(char * __restrict dst, const char * __restrict src, size_t size)
{
    for (size_t i = 0; i < size; ++i)
        dst[i] = src[i];
}

f(char*, char const*, unsigned long):
        testq   %rdx, %rdx
        je      .LBB2_2
        pushq   %rax
        callq   memcpy@PLT
        addq    $8, %rsp
.LBB2_2:
        retq

Это контролируется параметром -fbuiltin-memcpy (clang)
или -ftree-loop-distribute-patterns (gcc).

Важные факты про memcpy

2. Компилятор может заменять ваш код на вызов memcpy.
И делает это, если вы пишете что-то похожее.

void memcpy(
    char * __restrict dst,
    const char * __restrict src,
    size_t size)
{
    for (size_t i = 0; i < size; ++i)
        dst[i] = src[i];
}

Segmentation fault (stack overflow).

Важные факты про memcpy

3. GLibc содержит много реализаций memcpy,
из которых выбирается подходящая под конкретный набор инструкций.

__memcpy_erms
__memcpy_sse2_unaligned
__memcpy_ssse3
__memcpy_ssse3_back
__memcpy_avx_unaligned
__memcpy_avx_unaligned_erms
__memcpy_avx512_unaligned
__memcpy_avx512_unaligned_erms
__memcpy_avx512_no_vzeroupper

Это происходит с помощью механизма GNU IFUNC (indirect functions)
во время первого использования функции из shared library,
с помощью dynamic loader.

Важные факты про memcpy

4. Функция memcpy встроена в процессор
и может быть выполнена за одну инструкцию!

rep movsb  %ds:(%rsi), %es:(%rdi)

Эта инструкция присутствует во всех x86 CPU с самого начала.

Если memcpy реализована в железе,
то почему бы эту реализацию не использовать?

Как оптимизировать memcpy?

Каждый уважающий себя разработчик
хотя бы раз в жизни пытался оптимизировать memcpy.

Перед тем, как начать...

Есть ли у вас воспроизводимые тесты производительности
под репрезентативной нагрузкой?

Можно ли оптимизировать код на высоком уровне,
убрав лишние копирования?

Может быть, нужна функция с немного другим интерфейсом?

На чём писать memcpy?

На языке Ассемблера:

memcpy.s

+ вы точно контролируете выбор инструкций и регистров,
  их порядок и даже выравнивание.

функция не инлайнится.

не работает link time optimization.

На чём писать memcpy?

— на языке Ассемблера;

— на C;

— на C++;

— на C или C++ с inline ассемблером;

Из чего состоит memcpy?

1. Копирование «хвостов» — маленьких невыровненных
 кусков данных в начале и в конце.

2. Развёрнутый цикл с использованием широких инструкций.

Производительность memcpy

Для маленьких размеров, неизвестных во время компиляции.
Пример: копирование std::string, размера ~50 байт.

Стоимость вызова функции:

— если функция расположена в shared library,
  то её вызов косвенный, через PLT;

— если функция расположена в отдельной единице трансляции,
  то она не может быть подставлена и должна вызываться
  (в случае asm не помогает LTO);

— сохранение регистров в месте вызова функции;

Производительность memcpy

Для больших размеров:

— Какие инструкции используются для копирования.

— Как развёрнут цикл.

— В каком порядке обходить данные.

— Используются ли выровненные инструкции.

— Non temporary stores.

— Сброс верхних половин регистров.

Производительность memcpy

Очень сильно зависит от:

— распределения данных и нагрузки;

— модели процессора;

Производительность memcpy

Пример: repne movsb.

Одна инструкция. Реализована с помощью микрокода.

Для большинства старых CPU — работает медленно в любом случае.

Для многих CPU — работает быстро, но большой оверхед на старт.

На новых процессорах Intel есть флаг erms (Enhanced Repne MovSb)
и она работает быстро во всех случаях... но не на AMD.

Производительность memcpy

Пример: копирование с AVX инструкциями.

Для большинства CPU работает быстрее, чем с SSE инструкциями.

Но если остальной код программы использует SSE,
то после AVX, все SSE инструкции замедляются навечно.

Чтобы было не дорогое, надо вызывать инструкцию vzeroupper.

Но инструкция vzeroupper сама дорогая.

Но на самых новых CPU переключение не дорогое
и vzeroupper вызывать не надо.

Производительность memcpy

Пример: копирование с AVX-512 инструкциями.

На не самых новых процессорах медленнее, чем AVX
и вызывает уменьшение частоты.

... если использовать одновременно на многих ядрах.

Но на новых процессорах уже не вызывает.

Но AVX-512 нет на AMD.

Производительность memcpy

Пример: копирование с non-temporary stores.

Функции _mm_stream*, инструкция movnt*, vmovnt*.

Записывает данные в память, минуя кэш.

Ускоряет memcpy для больших размеров в 1.5 раза.

Полностью бесполезно в продакшене.

Производительность memcpy

Лучше не пытайтесь оптимизировать memcpy!

На вашей машине и вашем бенчмарке всё ускорится.
А на продакшене у пользователей — замедлится.

... но я попробую.

Пишем бенчмарк memcpy

Используем разные размеры буфера.

Используем разные размеры для вызова memcpy.

Используем размеры из случайных распределений,
чтобы предсказателю переходов не было слишком хорошо.

Используем разное количество потоков.

Копируем между буферами в разнах направлениях.

Пишем бенчмарк memcpy

— 9 реализаций из glibc.

— Cosmopolitan libc.

— repne movsb.

— Реализация простым циклом:
  loop peeling, loop unrolling and vectorization — делает компилятор.

— «Китайский memcpy», 2 варианта.

— Моя реализация, издали похожая на остальные.

Пишем бенчмарк memcpy

Запускаем на разных машинах:

— Intel Cascade Lake;

— Intel Ivy Bridge;

— AMD EPYC;

— AMD Ryzen.

Пишем бенчмарк memcpy

https://github.com/ClickHouse/ClickHouse/tree/master
/utils/memcpy-bench

for size in 4096 16384 50000 65536 100000 1000000 10000000 100000000; do
  for threads in 1 2 4 $(($(nproc) / 2)) $(nproc); do
    for distribution in 1 2 3 4 5; do
      for variant in {1..13} {21..29}; do
        for i in {1..10}; do
          ./memcpy-bench --tsv --size $size --variant $variant \
            --threads $threads --distribution $distribution;
        done;
      done;
    done;
  done;
done | tee result.tsv

42 000 измерений с одной машины.

Пишем бенчмарк memcpy

Результат: нет одного лучшего memcpy.

Есть хорошие:

__memcpy_avx_unaligned из glibc;
  но его нельзя вставить inline в код из-за лицензии
  и надо приделывать свой CPU dispatch.

— MemCpy из Cosmopolitan libc ok,
  но проигрывает на маленьких размерах.

Всё ещё есть надежда сделать свой, лучший memcpy :)

Обобщённый memcpy

#define VEC_SIZE 16
#define VZEROUPPER 0
#include "memcpy_medium_every_unroll.inl.h"
#undef VEC_SIZE
#undef VZEROUPPER

#define VEC_SIZE 32
#define VZEROUPPER 1
#include "memcpy_medium_every_unroll.inl.h"
#undef VEC_SIZE
#undef VZEROUPPER

#define VEC_SIZE 64
#define VZEROUPPER 1
#include "memcpy_medium_every_unroll.inl.h"
#undef VEC_SIZE
#undef VZEROUPPER

Обобщённый memcpy

#define UNROLL_COUNT 1
#include "memcpy_medium.inl.h"
#undef UNROLL_COUNT

#define UNROLL_COUNT 2
#include "memcpy_medium.inl.h"
#undef UNROLL_COUNT

#define UNROLL_COUNT 3
#include "memcpy_medium.inl.h"
#undef UNROLL_COUNT

...

#define UNROLL_COUNT 15
#include "memcpy_medium.inl.h"
#undef UNROLL_COUNT

#define UNROLL_COUNT 16
#include "memcpy_medium.inl.h"
#undef UNROLL_COUNT

Обобщённый memcpy

#if VEC_SIZE == 16
    #define NAME_PART sse
    #define VEC_REGISTER "xmm"
    #define VEC_MOV_UNALIGNED "movdqu"
    #define VEC_MOV_ALIGNED "movdqa"
    #define VEC_SIZE_MINUS_1 "0x0f"
    #define VEC_SIZEx1 "0x10"
    ...
    #define VEC_SIZEx16 "0x100"
#elif VEC_SIZE == 32
    #define NAME_PART avx
    #define VEC_REGISTER "ymm"
    #define VEC_MOV_UNALIGNED "vmovdqu"
    #define VEC_MOV_ALIGNED "vmovdqa"
    #define VEC_SIZE_MINUS_1 "0x1f"
    #define VEC_SIZEx1 "0x20"
    ...
    #define VEC_SIZEx16 "0x200"
#elif VEC_SIZE == 64
    ...

Обобщённый memcpy

void * NAME_FORWARD_UNROLLED(void * __restrict destination, const void * __restrict source, size_t size)
{
    void * __restrict ret = destination;

    __asm__ __volatile__ (
    "mov %[dst], %[ret] \n"

    VEC_MOV_UNALIGNED " (%[src]), %%" VEC_REGISTER "15 \n"
    VEC_MOV_UNALIGNED " %%" VEC_REGISTER "15, (%[dst]) \n"

    "lea    -" VEC_SIZEx1 "(%[dst],%[size],1), %%rcx \n"
    "mov    %[dst], %%r8 \n"
    "and    $" VEC_SIZE_MINUS_1 ", %%r8 \n"
    "sub    $" VEC_SIZEx1 ", %%r8 \n"
    "sub    %%r8, %[src] \n"
    "sub    %%r8, %[dst] \n"
    "add    %%r8, %[size] \n"

"1: \n"
    VEC_MOV_UNALIGNED " (%[src]), %%" VEC_REGISTER "0 \n"
#if UNROLL_COUNT >= 2
    VEC_MOV_UNALIGNED " " VEC_SIZEx1 "(%[src]), %%" VEC_REGISTER "1 \n"
#endif
...

    "add    $" VEC_SIZExUNROLL ", %[src] \n"
    "sub    $" VEC_SIZExUNROLL ", %[size] \n"

    VEC_MOV_ALIGNED " %%" VEC_REGISTER "0, (%[dst]) \n"
#if UNROLL_COUNT >= 2
    VEC_MOV_ALIGNED " %%" VEC_REGISTER "1, " VEC_SIZEx1 "(%[dst]) \n"
#endif
...

    "add    $" VEC_SIZExUNROLL ", %[dst] \n"
    "cmp    $" VEC_SIZExUNROLL ", %[size] \n"
    "ja     1b \n"

    VEC_MOV_UNALIGNED " -" VEC_SIZEx1 "(%[src],%[size],1), %%" VEC_REGISTER "0 \n"
#if UNROLL_COUNT >= 2
    VEC_MOV_UNALIGNED " -" VEC_SIZEx2 "(%[src],%[size],1), %%" VEC_REGISTER "1 \n"
#endif
...

    VEC_MOV_UNALIGNED " %%" VEC_REGISTER "0, (%%rcx) \n"
#if UNROLL_COUNT >= 2
    VEC_MOV_UNALIGNED " %%" VEC_REGISTER "1, -" VEC_SIZEx1 "(%%rcx) \n"
#endif
...

    VZEROUPPER_INSTRUCTION

    : [dst]"+r"(destination), [src]"+r"(source), [size]"+r"(size), [ret]"=rax"(ret)
    :
    : "rcx", "r8", "r11",
      VEC_REGISTER "0", VEC_REGISTER "1", VEC_REGISTER "2", VEC_REGISTER "3",
      VEC_REGISTER "4", VEC_REGISTER "5", VEC_REGISTER "6", VEC_REGISTER "7",
      VEC_REGISTER "8", VEC_REGISTER "9", VEC_REGISTER "10", VEC_REGISTER "11",
      VEC_REGISTER "12", VEC_REGISTER "13", VEC_REGISTER "14", VEC_REGISTER "15",
      "memory");

    return ret;
}

Самооптимизирующийся memcpy

Идея: сделать так, чтобы для больших размеров,
memcpy сам выбирал лучший вариант на основе статистики!

Поставим порог 30 000 байт. Если меньше — обычная реализация.

Если больше — запускаем случайный вариант, собираем статистику.

memcpy в L1 кэше — 50..100 GB/sec,
то есть копирование 30 КБ — от 300 нс.

На сбор статистики хотелось бы тратить до нескольких процентов
максимум 10 наносекунд.

Самооптимизирующийся memcpy

Идея: сделать так, чтобы для больших размеров,
memcpy сам выбирал лучший вариант на основе статистики!

Сбор статистики и выбор варианта
— максимум 10 наносекунд.

https://github.com/ClickHouse/ClickHouse/blob/38d665
/utils/memcpy-bench/memcpy-bench.cpp#L497

ALWAYS_INLINE void * call(void * __restrict dst, const void * __restrict src, size_t size)
{
    size_t current_count = count++;

    if (likely(current_count % probability_distribution_buckets < exploration_probability_threshold))
    {
        /// Exploitation mode.
        return selected_variant.load(std::memory_order_relaxed)(dst, src, size);
    }
    else
    {
        /// Exploration mode.
        return explore(dst, src, size);
    }
}

void * explore(void * __restrict dst, const void * __restrict src, size_t size)
{
    size_t current_exploration_count = exploration_count++;

    size_t hash = current_exploration_count;
    hash *= 0xff51afd7ed558ccdULL;
    hash ^= hash >> 33;

    VariantWithStatistics & variant = variants[hash % num_cells];

    UInt32 time1 = rdtsc();
    void * ret = variant.func.load(std::memory_order_relaxed)(dst, src, size);
    UInt32 time2 = rdtsc();
    UInt32 time = time2 - time1;

    if (time < size)
    {
        ++variant.count;
        variant.bytes += size;
        variant.time += time;
    }

Самооптимизирующийся memcpy

Обучение на лету успешно работает в бенчмарке.

Выбирает лучший вариант и работает со скоростью лучшего.

Дальше я поставил самооптимизирующийся memcpy в ClickHouse
и стал тестировать на настоящих запросах...

Самооптимизирующийся memcpy

Обучение на лету успешно работает в бенчмарке.

Выбирает лучший вариант и работает со скоростью лучшего.

Дальше я поставил самооптимизирующийся memcpy в ClickHouse
и стал тестировать на настоящих запросах...

И ничего не ускорилось!

Самоооптимизирующийся memcpy не может стабильно
выбрать лучший вариант на настоящей нагрузке.

Самооптимизирующийся memcpy

Самооптимизирующийся memcpy

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

Самооптимизирующийся memcpy не может выбрать лучший вариант и запускает случайные. А это негативно влияет на кэш инструкций.

Вся работа бесполезна?

Не совсем :)

По итогам экспериментов, я всё-таки заменил один memcpy на другой.

Он показал преимущества в продакшене
за счёт более эффективной обработки маленьких размеров.

https://github.com/ClickHouse/ClickHouse/pull/21520

Выводы

Оптимизируйте ваш код.

Пробуйте безумные идеи.

Никогда не сдавайтесь.

Спасибо!

Алексей Миловидов
Разработчик ClickHouse