Эта проблема векторизована с SIMD для набора символов ASCII.
Сравнение ускорений:
Предварительное тестирование с x86-64 gcc 5.2 -O3 -march=native на Core2Duo (Merom). Одна и та же строка из 120 символов (смешанный ASCII в нижнем и нижнем регистре), преобразованная в цикле 40M раз (без встраивания между файлами, поэтому компилятор не может оптимизировать его или вывести из цикла). Одинаковые буферы source и dest, поэтому никаких накладных расходов malloc или эффектов памяти / кэша: данные все время находятся в кеше L1, и мы полностью привязаны к процессору.
boost::to_upper_copy<char*, std::string>(): 198,0 с . Да, Boost 1.58 на Ubuntu 15.10 действительно такой медленный. Я профилировал и пошагово asm в отладчике, и это действительно, действительно плохо: есть динамическая переменная локали, происходящая на символ !!! (dynamic_cast принимает несколько вызовов strcmp). Это происходит с LANG=C и с LANG=en_CA.UTF-8.
Я не тестировал использование RangeT, кроме std :: string. Может быть, другая форма to_upper_copy оптимизирует лучше, но я думаю, что для копии всегда будет new / malloc, поэтому тестировать сложнее. Возможно, что-то, что я сделал, отличается от обычного варианта использования, и, возможно, обычно остановленный g ++ может вывести настройки локали из цикла для каждого символа. Мой цикл чтения из std::string и записи в char dstbuf[4096] имеет смысл для тестирования.
цикл вызова glibc toupper: 6.67s (хотя не проверяется результат int для потенциального многобайтового UTF-8. Это важно для турецкого языка.)
- Цикл только для ASCII: 8,79 с (моя базовая версия для результатов ниже.) Очевидно, поиск в таблице быстрее, чем
cmov, с горячей таблицей в L1 в любом случае.
- ASCII-только авто-векторизация: 2.51s . (120 символов - это на полпути между наихудшим и лучшим случаями, см. Ниже)
- ASCII-только векторизация вручную: 1,35 с
См. Также этот вопрос о том, что toupper() работает медленно в Windows, когда задан языковой стандарт .
Я был шокирован, что Boost на порядок медленнее, чем другие варианты. Я дважды проверил, что у меня включен -O3, и даже пошагово прошел asm, чтобы увидеть, что он делает. Это почти точно такая же скорость с Clang ++ 3.8. Это имеет огромные накладные расходы внутри цикла за символ. Результат perf record / report (для события cycles perf):
32.87% flipcase-clang- libstdc++.so.6.0.21 [.] _ZNK10__cxxabiv121__vmi_class_type_info12__do_dyncastElNS_17__class_type_info10__sub_kindEPKS1_PKvS4_S6_RNS1_16
21.90% flipcase-clang- libstdc++.so.6.0.21 [.] __dynamic_cast
16.06% flipcase-clang- libc-2.21.so [.] __GI___strcmp_ssse3
8.16% flipcase-clang- libstdc++.so.6.0.21 [.] _ZSt9use_facetISt5ctypeIcEERKT_RKSt6locale
7.84% flipcase-clang- flipcase-clang-boost [.] _Z16strtoupper_boostPcRKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE
2.20% flipcase-clang- libstdc++.so.6.0.21 [.] strcmp@plt
2.15% flipcase-clang- libstdc++.so.6.0.21 [.] __dynamic_cast@plt
2.14% flipcase-clang- libstdc++.so.6.0.21 [.] _ZNKSt6locale2id5_M_idEv
2.11% flipcase-clang- libstdc++.so.6.0.21 [.] _ZNKSt6locale2id5_M_idEv@plt
2.08% flipcase-clang- libstdc++.so.6.0.21 [.] _ZNKSt5ctypeIcE10do_toupperEc
2.03% flipcase-clang- flipcase-clang-boost [.] _ZSt9use_facetISt5ctypeIcEERKT_RKSt6locale@plt
0.08% ...
Автовекторизация
Gcc и clang будут автоматически векторизовывать циклы только тогда, когда счетчик итераций будет известен перед циклом. (то есть поисковые циклы, такие как реализация strlen на обычном языке C, не будут автоматически векторизованы.)
Таким образом, для строк, достаточно маленьких для размещения в кэше, мы получаем значительное ускорение для строк длиной ~ 128 символов при выполнении strlen вначале. Это не будет необходимо для строк с явной длиной (например, C ++ std::string).
// char, not int, is essential: otherwise gcc unpacks to vectors of int! Huge slowdown.
char ascii_toupper_char(char c) {
return ('a' <= c && c <= 'z') ? c^0x20 : c; // ^ autovectorizes to PXOR: runs on more ports than paddb
}
// gcc can only auto-vectorize loops when the number of iterations is known before the first iteration. strlen gives us that
size_t strtoupper_autovec(char *dst, const char *src) {
size_t len = strlen(src);
for (size_t i=0 ; i<len ; ++i) {
dst[i] = ascii_toupper_char(src[i]); // gcc does the vector range check with psubusb / pcmpeqb instead of pcmpgtb
}
return len;
}
Любой приличный libc будет иметь эффективный strlen, который намного быстрее, чем зацикливание байта за раз, поэтому отдельные векторизованные циклы strlen и toupper быстрее.
Базовая линия: цикл, который проверяет завершающий 0 на лету.
Время для 40M итераций на Core2 (Merom) 2,4 ГГц. GCC 5,2 -O3 -march=native. (Ubuntu 15.10). dst != src (поэтому мы делаем копию), но они не пересекаются (и не находятся рядом). Оба выровнены.
- 15 символьная строка: базовая линия: 1,08 с. Autovec: 1,34 с
- 16 символьных строк: базовый уровень: 1,16 с. Autovec: 1,52 с
- 127 символьная строка: базовая линия: 8,91 с. autovec: 2.98s // не векторная очистка имеет 15 символов для обработки
- 128 символьная строка: базовая линия: 9,00 с. Autovec: 2,06 с
- 129 символьная строка: базовая линия: 9.04 с. autovec: 2.07s // не векторная очистка имеет 1 символ для обработки
Некоторые результаты немного отличаются от clang.
Цикл микробенчмарка, который вызывает функцию, находится в отдельном файле. В противном случае он встроен, и strlen() выводится из цикла, и он работает значительно быстрее, особенно. для 16 строк символов (0,187 с).
Это имеет основное преимущество, заключающееся в том, что gcc может автоматически векторизовать его для любой архитектуры, но главный недостаток в том, что он медленнее для обычно распространенного случая небольших строк.
Так что есть большие ускорения, но авто-векторизация компилятора не делает большой код, особенно. для очистки последних до 15 символов.
Ручная векторизация со встроенными SSE:
Основано на моей функции переключения регистра , которая инвертирует регистр каждого буквенного символа. Он использует «трюк сравнения без знака», при котором вы можете выполнить low < a && a <= high с одним сравнением без знака путем сдвига диапазона, так что любое значение меньше low переносится в значение, которое больше high. (Это работает, если low и high не слишком далеко друг от друга.)
SSE имеет только подписанное сравнение-большее, но мы все еще можем использовать «без знака»
сравните трюк путем смещения диапазона до нижней части диапазона со знаком: вычтите «a» + 128, чтобы диапазон букв алфавита составлял от -128 до -128 + 25 (-128 + 'z' - 'a')
Обратите внимание, что сложение 128 и вычитание 128 - это то же самое для 8-битных целых чисел. Керри некуда деваться, так что это просто xor (добавление без переноса), переворачивающее старший бит.
#include <immintrin.h>
__m128i upcase_si128(__m128i src) {
// The above 2 paragraphs were comments here
__m128i rangeshift = _mm_sub_epi8(src, _mm_set1_epi8('a'+128));
__m128i nomodify = _mm_cmpgt_epi8(rangeshift, _mm_set1_epi8(-128 + 25)); // 0:lower case -1:anything else (upper case or non-alphabetic). 25 = 'z' - 'a'
__m128i flip = _mm_andnot_si128(nomodify, _mm_set1_epi8(0x20)); // 0x20:lcase 0:non-lcase
// just mask the XOR-mask so elements are XORed with 0 instead of 0x20
return _mm_xor_si128(src, flip);
// it's easier to xor with 0x20 or 0 than to AND with ~0x20 or 0xFF
}
Учитывая, что эта функция работает для одного вектора, мы можем вызвать ее в цикле для обработки всей строки. Поскольку мы уже нацелены на SSE2, мы можем одновременно выполнять векторизованную проверку конца строки.
Мы также можем сделать намного лучше для «очистки» последних до 15 байтов, оставшихся после выполнения векторов 16B: верхний регистр идемпотентен, поэтому повторная обработка некоторых входных байтов в порядке. Мы делаем невыровненную загрузку последних 16B источника и сохраняем ее в буфере dest, перекрывающем последнее 16B хранилище из цикла.
Единственный раз, когда это не работает, это когда вся строка меньше 16B: даже если dst=src, неатомарное чтение-изменение-запись это не то же самое, что не трогать некоторые байты и может нарушать многопоточный код.
Для этого у нас есть скалярный цикл, а также выравнивание src. Так как мы не знаем, где будет завершающий 0, не выровненная загрузка из src может перейти на следующую страницу и вызвать ошибку. Если нам нужны какие-либо байты в выровненном фрагменте 16B, всегда безопасно загрузить весь выровненный фрагмент 16B.
Полный источник: в github gist .
// FIXME: doesn't always copy the terminating 0.
// microbenchmarks are for this version of the code (with _mm_store in the loop, instead of storeu, for Merom).
size_t strtoupper_sse2(char *dst, const char *src_begin) {
const char *src = src_begin;
// scalar until the src pointer is aligned
while ( (0xf & (uintptr_t)src) && *src ) {
*(dst++) = ascii_toupper(*(src++));
}
if (!*src)
return src - src_begin;
// current position (p) is now 16B-aligned, and we're not at the end
int zero_positions;
do {
__m128i sv = _mm_load_si128( (const __m128i*)src );
// TODO: SSE4.2 PCMPISTRI or PCMPISTRM version to combine the lower-case and '\0' detection?
__m128i nullcheck = _mm_cmpeq_epi8(_mm_setzero_si128(), sv);
zero_positions = _mm_movemask_epi8(nullcheck);
// TODO: unroll so the null-byte check takes less overhead
if (zero_positions)
break;
__m128i upcased = upcase_si128(sv); // doing this before the loop break lets gcc realize that the constants are still in registers for the unaligned cleanup version. But it leads to more wasted insns in the early-out case
_mm_storeu_si128((__m128i*)dst, upcased);
//_mm_store_si128((__m128i*)dst, upcased); // for testing on CPUs where storeu is slow
src += 16;
dst += 16;
} while(1);
// handle the last few bytes. Options: scalar loop, masked store, or unaligned 16B.
// rewriting some bytes beyond the end of the string would be easy,
// but doing a non-atomic read-modify-write outside of the string is not safe.
// Upcasing is idempotent, so unaligned potentially-overlapping is a good option.
unsigned int cleanup_bytes = ffs(zero_positions) - 1; // excluding the trailing null
const char* last_byte = src + cleanup_bytes; // points at the terminating '\0'
// FIXME: copy the terminating 0 when we end at an aligned vector boundary
// optionally special-case cleanup_bytes == 15: final aligned vector can be used.
if (cleanup_bytes > 0) {
if (last_byte - src_begin >= 16) {
// if src==dest, this load overlaps with the last store: store-forwarding stall. Hopefully OOO execution hides it
__m128i sv = _mm_loadu_si128( (const __m128i*)(last_byte-15) ); // includes the \0
_mm_storeu_si128((__m128i*)(dst + cleanup_bytes - 15), upcase_si128(sv));
} else {
// whole string less than 16B
// if this is common, try 64b or even 32b cleanup with movq / movd and upcase_si128
#if 1
for (unsigned int i = 0 ; i <= cleanup_bytes ; ++i) {
dst[i] = ascii_toupper(src[i]);
}
#else
// gcc stupidly auto-vectorizes this, resulting in huge code bloat, but no measurable slowdown because it never runs
for (int i = cleanup_bytes - 1 ; i >= 0 ; --i) {
dst[i] = ascii_toupper(src[i]);
}
#endif
}
}
return last_byte - src_begin;
}
Время для 40M итераций на Core2 (Merom) 2,4 ГГц. GCC 5,2 -O3 -march=native. (Ubuntu 15.10). dst != src (поэтому мы делаем копию), но они не пересекаются (и не находятся рядом). Оба выровнены.
- 15 символьная строка: базовая линия: 1,08 с. Autovec: 1,34 с. инструкция: 1,29 с
- 16 символьная строка: базовая линия: 1,16 с. Autovec: 1,52 с. инструкция: 0,335 с
- 31 символьная строка: руководство: 0,479 с
- 127 символьная строка: базовая линия: 8,91 с. Autovec: 2,98 с. инструкция: 0,925 с
- 128 символьная строка: базовая линия: 9,00 с. Autovec: 2,06 с. инструкция: 0,931 с
- 129 символьная строка: базовая линия: 9.04 с. Autovec: 2,07 с. инструкция: 1.02 с
(Фактически приурочено к _mm_store в цикле, а не _mm_storeu, потому что storeu медленнее на Merom, даже когда адрес выровнен. Это нормально для Nehalem и позже. Я также оставил код как есть для теперь вместо исправления ошибки в некоторых случаях копировать завершающий 0, потому что я не хочу все время менять.)
Таким образом, для коротких строк длиннее 16В это значительно быстрее, чем векторизация. Длина на единицу меньше ширины вектора не представляет проблемы. Они могут быть проблемой при работе на месте из-за остановки магазина. (Но учтите, что все же нормально обрабатывать наш собственный вывод, а не исходный, потому что toupper является идемпотентом).
Существует множество возможностей для настройки этого для различных вариантов использования, в зависимости от того, что хочет окружающий код, и целевой микроархитектуры. Заставить компилятор выдавать хороший код для части очистки довольно сложно. Использование ffs(3) (которое компилируется в bsf или tzcnt на x86) кажется хорошим, но очевидно, что этот бит нуждается в переосмыслении, так как я заметил ошибку после написания большей части этого ответа (см. Комментарии FIXME).
Векторные ускорения для еще меньших струн могут быть получены с помощью movq или movd загрузок / накопителей. Настройте по мере необходимости для вашего варианта использования.
UTF-8
Мы можем определить, когда наш вектор имеет какие-либо байты с установленным старшим битом, и в этом случае вернуться к скалярному циклу с поддержкой utf-8 для этого вектора. Точка dst может выдвинуться на величину, отличную от указателя src, но как только мы вернемся к выровненному указателю src, мы все равно будем просто делать невыровненные векторные хранилища в dst.
Для текста, который является UTF-8, но в основном состоит из подмножества ASCII UTF-8, это может быть хорошо: высокая производительность в общем случае с корректным поведением во всех случаях. Когда много не ASCII, это, вероятно, будет хуже, чем постоянно находиться в скалярном цикле с поддержкой UTF-8.
Ускорение английского за счет других языков не является решением на будущее, если недостаток существенный.
локали известно:
В турецком языке (tr_TR) правильный результат из toupper('i'): 'İ' (U0130), а не 'I' (обычный ASCII). См. комментарии Мартина Боннера по вопросу о том, что tolower() работает медленно в Windows.
Мы также можем проверить список исключений и откат к скаляру, например, для многобайтовых символов ввода UTF8.
С такой большой сложностью SSE4.2 PCMPISTRM или что-то еще может сделать много наших проверок за один раз.