На размышления меня натолкнула статья об использовании «странной» инструкции popcount в современных процессорах. Речь пойдет не о подсчете числа единичек, а об обнаружении признака окончания Си строки (нуль-терминированная строка).
Для определения длины таких срок применяется стандартная функция
Алгоритм работы которой можно описать на языке Си как:
Посмотрим, во что его превращает компилятор MS Visual Studio 2019 community (Release, x86):
То есть происходит загрузка из памяти одного байта и сравнение его с нулем. Такой же код подставляется в места вызовов strlen если собирать проект в Release, алгоритм корректен, но скорость, его как мне кажется, не достаточна. Что же произойдет, если откомпилировать код с вызовом стандартной strlen в Debug? – Будет вызвана библиотечная функция strlen, как и ожидается, но написанная человеком вручную на assembler.
Таблица 1 – время работы бенча strlen в секундах (MS VS 2019 community, C++ cl version: 19.22.27905)
* вынуждаем компилятор вызвать библиотечную функцию strlen
Таким образом можно сделать вывод, что подстановка компилятором MS VS побайтового сравнения неэффективна даже на строках малого размера, а на строках большого, Debug опережает Release!
Строка
Debug в: вызов библиотечной функции strlen;
Release в: побайтовое сравнение.
Если ее закомментировать и написать
где
мы вынудим компилятор всегда вызывать библиотечную функцию.
За счет чего достигнуто ускорение библиотечной функции перед побайтовым сравнением в 2,3 раза (для Release, x86, 1k)?
За счет сравнения не по одному байту, а сразу по 4. Вся магия здесь:
Можно ли сделать быстрее, используя векторные инструкции современных процессоров? Попробуем.
Пользуясь Intel Intrinsics guide, находим интринсик _mm_cmpistri SSE4.2, предназначенный как раз для работы со строками. На вход подается 2 вектора длины 128 бит и маска операций. В качестве маски используем: _SIDD_UBYTE_OPS=0 – тип данных, _SIDD_CMP_EQUAL_EACH=8 – операция побайтового равнения, а сравнивать будем с нулевым вектором. Возвращаемым значением будет число первых попарно неравных элементов (то есть если элемент совпал при проверке слева-направо счет останавливается, буду рад, если кто-то подтвердит поведение).
Код
Служит для выравнивания адреса загружаемой строки, адрес нужен кратным 16 для работы большинства SSE инструкций. Для инструкции pcmpistri, используемой нами, выравнивание строго не нужно, исключение доступа не будет вызвано.
Интринсики
Компилируются в:
Однако, выравнивание по 16 полезно и в нашем случае, дает небольшой прирост быстродействия и так мы точно уверены, что цикл чтения по 16 байт не выйдет на потенциально не аллоцированную страницу (страница памяти по 4K).
Цикл:
«Добирает» размер строки, если обнаружен ее конец (так как я не до конца уверен в алгоритме работы _mm_cmpistri).
удален после комментария picul, что дало прирост на строках небольшого размера.
Сделали ли мы самую быструю strlen? – К сожалению, нет, ребята с https://www.strchr.com/sse2_optimised_strlen сделали еще быстрее и не используя SSE4.2.
Таблица 2 – время работы бенча strlen в секундах (Release)
Выводы:
Мне кажется, MS-у всегда нужно вызывать библиотечную strlen, а не делать подстановку побайтового сравнения.
UPD.
Добавлен тест x64.
Удален последний цикл в strlen_SSE4
Нуль-терминированная строка — способ представления строк в языках программирования, при котором вместо введения специального строкового типа используется массив символов, а концом строки считается первый встретившийся специальный нуль-символ (NUL из кода ASCII, со значением 0).
Для определения длины таких срок применяется стандартная функция
size_t __cdecl strlen(char const* str)
Алгоритм работы которой можно описать на языке Си как:
size_t strlen_algo(const char* str) { size_t length = 0; while (*str++) length++; return length; }
Посмотрим, во что его превращает компилятор MS Visual Studio 2019 community (Release, x86):
08811F7h: mov al,byte ptr [ecx] inc ecx test al,al jne main+0D7h (08811F7h)
То есть происходит загрузка из памяти одного байта и сравнение его с нулем. Такой же код подставляется в места вызовов strlen если собирать проект в Release, алгоритм корректен, но скорость, его как мне кажется, не достаточна. Что же произойдет, если откомпилировать код с вызовом стандартной strlen в Debug? – Будет вызвана библиотечная функция strlen, как и ожидается, но написанная человеком вручную на assembler.
Cпойлер кода стандартной функции strlen в MS Visual Studio
;strlen.asm - contains strlen() routine ; ; Copyright (c) Microsoft Corporation. All rights reserved. ; ;Purpose: ; strlen returns the length of a null-terminated string, ; not including the null byte itself. ; ;******************************************************************************* .xlist include cruntime.inc .list page ;*** ;strlen - return the length of a null-terminated string ; ;Purpose: ; Finds the length in bytes of the given string, not including ; the final null character. ; ; Algorithm: ; int strlen (const char * str) ; { ; int length = 0; ; ; while( *str++ ) ; ++length; ; ; return( length ); ; } ; ;Entry: ; const char * str - string whose length is to be computed ; ;Exit: ; EAX = length of the string "str", exclusive of the final null byte ; ;Uses: ; EAX, ECX, EDX ; ;Exceptions: ; ;******************************************************************************* CODESEG public strlen strlen proc \ buf:ptr byte OPTION PROLOGUE:NONE, EPILOGUE:NONE .FPO ( 0, 1, 0, 0, 0, 0 ) string equ [esp + 4] mov ecx,string ; ecx -> string test ecx,3 ; test if string is aligned on 32 bits je short main_loop str_misaligned: ; simple byte loop until string is aligned mov al,byte ptr [ecx] add ecx,1 test al,al je short byte_3 test ecx,3 jne short str_misaligned add eax,dword ptr 0 ; 5 byte nop to align label below align 16 ; should be redundant main_loop: mov eax,dword ptr [ecx] ; read 4 bytes mov edx,7efefeffh add edx,eax xor eax,-1 xor eax,edx add ecx,4 test eax,81010100h je short main_loop ; found zero byte in the loop mov eax,[ecx - 4] test al,al ; is it byte 0 je short byte_0 test ah,ah ; is it byte 1 je short byte_1 test eax,00ff0000h ; is it byte 2 je short byte_2 test eax,0ff000000h ; is it byte 3 je short byte_3 jmp short main_loop ; taken if bits 24-30 are clear and bit ; 31 is set byte_3: lea eax,[ecx - 1] mov ecx,string sub eax,ecx ret byte_2: lea eax,[ecx - 2] mov ecx,string sub eax,ecx ret byte_1: lea eax,[ecx - 3] mov ecx,string sub eax,ecx ret byte_0: lea eax,[ecx - 4] mov ecx,string sub eax,ecx ret strlen endp end
Таблица 1 – время работы бенча strlen в секундах (MS VS 2019 community, C++ cl version: 19.22.27905)
| Большой блок, 1K | Большой блок, 1K, *вызов strlen | Малый блок, 10 элементов | Малый блок, 10 элементов, *вызов strlen | |
|---|---|---|---|---|
| Debug, x86 | 7.25 | 7.25 | 3.06 | 3.06 |
| Release, x86 | 9.0 | 3.9 | 0.15 | 0.12 |
| Debug, x64 | 6.0 | 6.0 | 3.4 | 3.4 |
| Release, x64 | 8.5 | 2.3 | 0.15 | 0.11 |
* вынуждаем компилятор вызвать библиотечную функцию strlen
Таким образом можно сделать вывод, что подстановка компилятором MS VS побайтового сравнения неэффективна даже на строках малого размера, а на строках большого, Debug опережает Release!
Код бенча
#include <iostream> #include <string> #include <vector> #include <chrono> #include <nmmintrin.h> inline size_t strlen_algo(const char* str) { size_t length = 0; while (*str++) length++; return length; } inline size_t strlen_sse4(const char* str) { size_t length = 0; int res = 0; //align to 16 bytes while (((size_t(str+length)) & (sizeof(__m128i) - 1)) != 0) { if (str[length] == 0) return length; length++; } __m128i z128 = _mm_setzero_si128(); for(; ; length += 16) { __m128i data = _mm_load_si128((__m128i*)(str + length)); if ((res = _mm_cmpistri(z128, data, _SIDD_CMP_EQUAL_EACH)) != 16) break; } /*while (str[length]) length++;*/ return length + res; } #define _DISABLE_ASM_BSF //https://www.strchr.com/sse2_optimised_strlen #ifndef WORDS_BIGENDIAN #if 0 #elif 0 #else static inline int count_bits_to_0(unsigned int x) // counting trailing zeroes, by Nazo, post: 2009/07/20 03:40 { // this is current winner for speed static const unsigned char table[256] = { 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, }; if ((unsigned char)x) return table[(unsigned char)x]; return table[x >> 8] + 8; // t[x / 256] + 8 } #endif #else #if 0 static inline int count_bits_to_0(unsigned int x) // counting trailing zeroes { register int i = 0; if (!(x & (1 << 15))) i++; else return i; if (!(x & (1 << 14))) i++; else return i; if (!(x & (1 << 13))) i++; else return i; if (!(x & (1 << 12))) i++; else return i; if (!(x & (1 << 11))) i++; else return i; if (!(x & (1 << 10))) i++; else return i; if (!(x & (1 << 9))) i++; else return i; if (!(x & (1 << 8))) i++; else return i; if (!(x & (1 << 7))) i++; else return i; if (!(x & (1 << 6))) i++; else return i; if (!(x & (1 << 5))) i++; else return i; if (!(x & (1 << 4))) i++; else return i; if (!(x & (1 << 3))) i++; else return i; if (!(x & (1 << 2))) i++; else return i; if (!(x & (1 << 1))) i++; else return i; if (!(x & (1 << 0))) i++; return i; } #else static inline int count_bits_to_0(unsigned int x) // counting trailing zeroes { // http://www.hackersdelight.org/: nlz1() shortened for 16-bit mask register int n = 0; if (x <= 0x000000FFU) { n = n + 8; x = x << 8; } if (x <= 0x00000FFFU) { n = n + 4; x = x << 4; } if (x <= 0x00003FFFU) { n = n + 2; x = x << 2; } if (x <= 0x00007FFFU) { n = n + 1; } return n; } #endif #endif size_t strlen2(const char* str) { register size_t len = 0; // align to 16 bytes while ((((intptr_t)str) & (sizeof(__m128i) - 1)) != 0) { if (*str++ == 0) return len; ++len; } // search for 0 __m128i xmm0 = _mm_setzero_si128(); __m128i xmm1; int mask = 0; for (;;) { xmm1 = _mm_load_si128((__m128i*)str); xmm1 = _mm_cmpeq_epi8(xmm1, xmm0); if ((mask = _mm_movemask_epi8(xmm1)) != 0) { // got 0 somewhere within 16 bytes in xmm1, or within 16 bits in mask // find index of first set bit #ifndef _DISABLE_ASM_BSF // define it to disable ASM #if (_MSC_VER >= 1300) // make sure <intrin.h> is included unsigned long pos; _BitScanForward(&pos, mask); len += (size_t)pos; #elif defined(_MSC_VER) // earlier MSVC's do not have _BitScanForward, use inline asm __asm bsf edx, mask; edx = bsf(mask) __asm add edx, len; edx += len __asm mov len, edx; len = edx #elif ((__GNUC__ >= 4) || ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))) // modern GCC has built-in __builtin_ctz len += __builtin_ctz(mask); #elif defined(__GNUC__) // older GCC shall use inline asm unsigned int pos; asm("bsf %1, %0" : "=r" (pos) : "rm" (mask)); len += (size_t)pos; #else // none of choices exist, use local BSF implementation len += count_bits_to_0(mask); #endif #else len += count_bits_to_0(mask); #endif break; } str += sizeof(__m128i); len += sizeof(__m128i); } return len; } int main() { std::vector<std::string> vstr; const int str_num = 1024; const int str_size = 1024; size_t len_result = 0; srand(0); for (int i = 0; i < str_num; i++) { std::string str1; for (int j = 0; j < str_size; j++) { str1.push_back('0' + rand() % 78); } vstr.push_back(std::move(str1)); } auto strlen_func = strlen; //auto strlen_func = strlen_algo; //auto strlen_func = strlen_sse4; //auto strlen_func = strlen2; auto time_std = std::chrono::steady_clock::now(); for (int k = 0; k < 10*1000; k++) { for (int i = 0; i < str_num; i++) { const char* str_for_test = vstr[i].c_str(); len_result += strlen_func(str_for_test); //len_result += strlen(str_for_test); } for (int i = 0; i < str_num; i++) { const char* str_for_test = vstr[i].c_str(); len_result -= strlen_func(str_for_test); //len_result -= strlen(str_for_test); } } auto finish = std::chrono::steady_clock::now(); double elapsed_seconds = std::chrono::duration_cast<std::chrono::duration<double>>(finish - time_std).count(); std::cout << "\n" << len_result; std::cout << "\n\nTime: " << elapsed_seconds; return 0; }
Строка
компилируетсяlen_result += strlen(str_for_test);
Debug в: вызов библиотечной функции strlen;
Release в: побайтовое сравнение.
Если ее закомментировать и написать
len_result += strlen_func(str_for_test);
где
auto strlen_func = strlen;
мы вынудим компилятор всегда вызывать библиотечную функцию.
За счет чего достигнуто ускорение библиотечной функции перед побайтовым сравнением в 2,3 раза (для Release, x86, 1k)?
За счет сравнения не по одному байту, а сразу по 4. Вся магия здесь:
main_loop: mov eax,dword ptr [ecx] ; read 4 bytes mov edx,7efefeffh add edx,eax xor eax,-1 xor eax,edx add ecx,4 test eax,81010100h je short main_loop
Можно ли сделать быстрее, используя векторные инструкции современных процессоров? Попробуем.
Пользуясь Intel Intrinsics guide, находим интринсик _mm_cmpistri SSE4.2, предназначенный как раз для работы со строками. На вход подается 2 вектора длины 128 бит и маска операций. В качестве маски используем: _SIDD_UBYTE_OPS=0 – тип данных, _SIDD_CMP_EQUAL_EACH=8 – операция побайтового равнения, а сравнивать будем с нулевым вектором. Возвращаемым значением будет число первых попарно неравных элементов (то есть если элемент совпал при проверке слева-направо счет останавливается, буду рад, если кто-то подтвердит поведение).
size_t length = 0; int res = 0; //align to 16 bytes while (((size_t(str+length)) & (sizeof(__m128i) - 1)) != 0) { if (str[length] == 0) return length; length++; } __m128i z128 = _mm_setzero_si128(); for(; ; length += 16) { __m128i data = _mm_load_si128((__m128i*)(str + length)); if ((res = _mm_cmpistri(z128, data, _SIDD_CMP_EQUAL_EACH)) != 16) break; } /*while (str[length]) length++;*/ return length + res;
Код
while (((size_t(str+length)) & (sizeof(__m128i) - 1)) != 0) { if (str[length] == 0) return length; length++; }
Служит для выравнивания адреса загружаемой строки, адрес нужен кратным 16 для работы большинства SSE инструкций. Для инструкции pcmpistri, используемой нами, выравнивание строго не нужно, исключение доступа не будет вызвано.
Интринсики
__m128i data = _mm_load_si128((__m128i*)(str + length)); if ((res = _mm_cmpistri(z128, data, _SIDD_CMP_EQUAL_EACH)) != 16)
Компилируются в:
pcmpistri xmm1,xmmword ptr [eax+edx],8
Однако, выравнивание по 16 полезно и в нашем случае, дает небольшой прирост быстродействия и так мы точно уверены, что цикл чтения по 16 байт не выйдет на потенциально не аллоцированную страницу (страница памяти по 4K).
Цикл:
while (str[length]) length++;
удален после комментария picul, что дало прирост на строках небольшого размера.
Сделали ли мы самую быструю strlen? – К сожалению, нет, ребята с https://www.strchr.com/sse2_optimised_strlen сделали еще быстрее и не используя SSE4.2.
Таблица 2 – время работы бенча strlen в секундах (Release)
| Число символов | MS побайтовое сравнение | MS strlen | SSE 4.2 | SSE 2 |
|---|---|---|---|---|
| 10, x86 | 0.15 | 0.12 | 0.12 | 0.125 |
| 1K, x86 | 9.0 | 3.9 | 1.65 | 1.42 |
| 10, x64 | 0.15 | 0.11 | 0.08 | 0.1 |
| 1K, x64 | 8.5 | 2.3 | 1.6 | 1.32 |
Выводы:
Мне кажется, MS-у всегда нужно вызывать библиотечную strlen, а не делать подстановку побайтового сравнения.
UPD.
Добавлен тест x64.
Удален последний цикл в strlen_SSE4
