Алексей Миловидов
Разработчик 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 из профиля?
1. Меньше копировать данные.
Не всегда возможно.
Часто данные нужно переложить, чтобы всё ускорить.
2. Оптимизировать реализацию memcpy.
Но её уже все оптимизировали?
«It's the world's most popular function — one all programmers love»
— Alexandra Justine Roberts Tunney.
1. Компилятор может заменять memcpy на встроенную реализацию.
И делает это, если размер небольшой и известен во время компиляции.
memcpy(dst, src, 8); movq (%rsi), %rax movq %rax, (%rdi)
Это контролируется параметром -fbuiltin-memcpy, -fno-builtin-memcpy.
Встроенную реализацию можно указать явно:
__builtin_memcpy(dst, src, size).
Для неизвестных размеров она будет заменена на вызов 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)
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).
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).
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.
4. Функция memcpy встроена в процессор
и может быть выполнена за одну инструкцию!
rep movsb %ds:(%rsi), %es:(%rdi)
Эта инструкция присутствует во всех x86 CPU с самого начала.
Если memcpy реализована в железе,
то почему бы эту реализацию не использовать?
Каждый уважающий себя разработчик
хотя бы раз в жизни пытался оптимизировать memcpy.
Есть ли у вас воспроизводимые тесты производительности
под репрезентативной нагрузкой?
Можно ли оптимизировать код на высоком уровне,
убрав лишние копирования?
Может быть, нужна функция с немного другим интерфейсом?
На языке Ассемблера:
memcpy.s
+ вы точно контролируете выбор инструкций и регистров,
их порядок и даже выравнивание.
− функция не инлайнится.
− не работает link time optimization.
— на языке Ассемблера;
— на C;
— на C++;
— на C или C++ с inline ассемблером;
1. Копирование «хвостов» — маленьких невыровненных
кусков данных в начале и в конце.
2. Развёрнутый цикл с использованием широких инструкций.
Для маленьких размеров, неизвестных во время компиляции.
Пример: копирование std::string, размера ~50 байт.
Стоимость вызова функции:
— если функция расположена в shared library,
то её вызов косвенный, через PLT;
— если функция расположена в отдельной единице трансляции,
то она не может быть подставлена и должна вызываться
(в случае asm не помогает LTO);
— сохранение регистров в месте вызова функции;
Для больших размеров:
— Какие инструкции используются для копирования.
— Как развёрнут цикл.
— В каком порядке обходить данные.
— Используются ли выровненные инструкции.
— Non temporary stores.
— Сброс верхних половин регистров.
Очень сильно зависит от:
— распределения данных и нагрузки;
— модели процессора;
Пример: repne movsb.
Одна инструкция. Реализована с помощью микрокода.
Для большинства старых CPU — работает медленно в любом случае.
Для многих CPU — работает быстро, но большой оверхед на старт.
На новых процессорах Intel есть флаг erms (Enhanced Repne MovSb)
и она работает быстро во всех случаях... но не на AMD.
Пример: копирование с AVX инструкциями.
Для большинства CPU работает быстрее, чем с SSE инструкциями.
Но если остальной код программы использует SSE,
то после AVX, все SSE инструкции замедляются навечно.
Чтобы было не дорогое, надо вызывать инструкцию vzeroupper.
Но инструкция vzeroupper сама дорогая.
Но на самых новых CPU переключение не дорогое
и vzeroupper вызывать не надо.
Пример: копирование с AVX-512 инструкциями.
На не самых новых процессорах медленнее, чем AVX
и вызывает уменьшение частоты.
... если использовать одновременно на многих ядрах.
Но на новых процессорах уже не вызывает.
Но AVX-512 нет на AMD.
Пример: копирование с non-temporary stores.
Функции _mm_stream*, инструкция movnt*, vmovnt*.
Записывает данные в память, минуя кэш.
Ускоряет memcpy для больших размеров в 1.5 раза.
Полностью бесполезно в продакшене.
Лучше не пытайтесь оптимизировать memcpy!
На вашей машине и вашем бенчмарке всё ускорится.
А на продакшене у пользователей — замедлится.
... но я попробую.
Используем разные размеры буфера.
Используем разные размеры для вызова memcpy.
Используем размеры из случайных распределений,
чтобы предсказателю переходов не было слишком хорошо.
Используем разное количество потоков.
Копируем между буферами в разнах направлениях.
— 9 реализаций из glibc.
— Cosmopolitan libc.
— repne movsb.
— Реализация простым циклом:
loop peeling, loop unrolling and vectorization — делает компилятор.
— «Китайский memcpy», 2 варианта.
— Моя реализация, издали похожая на остальные.
Запускаем на разных машинах:
— Intel Cascade Lake;
— Intel Ivy Bridge;
— AMD EPYC;
— AMD Ryzen.
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_avx_unaligned из glibc;
но его нельзя вставить inline в код из-за лицензии
и надо приделывать свой CPU dispatch.
— MemCpy из Cosmopolitan libc ok,
но проигрывает на маленьких размерах.
Всё ещё есть надежда сделать свой, лучший 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
#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
#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 ...
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 сам выбирал лучший вариант на основе статистики!
Поставим порог 30 000 байт. Если меньше — обычная реализация.
Если больше — запускаем случайный вариант, собираем статистику.
memcpy в L1 кэше — 50..100 GB/sec,
то есть копирование 30 КБ — от 300 нс.
На сбор статистики хотелось бы тратить до нескольких процентов
— максимум 10 наносекунд.
Идея: сделать так, чтобы для больших размеров,
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 в ClickHouse
и стал тестировать на настоящих запросах...
Обучение на лету успешно работает в бенчмарке.
Выбирает лучший вариант и работает со скоростью лучшего.
Дальше я поставил самооптимизирующийся memcpy в ClickHouse
и стал тестировать на настоящих запросах...
И ничего не ускорилось!
Самоооптимизирующийся memcpy не может стабильно
выбрать лучший вариант на настоящей нагрузке.
На реальной нагрузке, при использовании многих потоков, memcpy упирается в пропускную способность памяти, поэтому между разными тестируемыми вариантами отсутствует заметная разница.
Самооптимизирующийся memcpy не может выбрать лучший вариант и запускает случайные. А это негативно влияет на кэш инструкций.
Не совсем :)
По итогам экспериментов, я всё-таки заменил один memcpy на другой.
Он показал преимущества в продакшене
за счёт более эффективной обработки маленьких размеров.
Оптимизируйте ваш код.
Пробуйте безумные идеи.
Никогда не сдавайтесь.
Алексей Миловидов
Разработчик ClickHouse