На размышления меня натолкнула статья об использовании «странной» инструкции popcount в современных процессорах. Речь пойдет не о подсчете числа единичек, а об обнаружении признака окончания Си строки (нуль-терминированная строка).
Нуль-терминированная строка — способ представления строк в языках программирования, при котором вместо введения специального строкового типа используется массив символов, а концом строки считается первый встретившийся специальный нуль-символ (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.
;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 |
* вынуждаем компилятор вызвать библиотечную функцию 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;
//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;
}
#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));
}
/*
len_result = strlen_sse4("abcdefghijklmnopqrstu1234567890");
len_result = strlen_sse4("123456789101112656g");
*/
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 << "nnTime: " << 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;
//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;
Код
while (((size_t(str+length)) & (sizeof(__m128i) - 1)) != 0)
{
if (str[length] == 0)
return length;
length++;
}
Служит для выравнивания адреса загружаемой строки, адрес нужен кратным 16 для работы SSE большинства инструкций.
Код:
while (str[length])
length++;
«Добирает» размер строки, если обнаружен ее конец (так как я не до конца уверен в алгоритме работы _mm_cmpistri).
Возможно ли нарушить права доступа к памяти оперируя блоками по 16 байт и словить сегфолт вылезши за неалоцированную область? – Нет, у нас же страницы по 4K, кратны 16.
Сделали ли мы самую быструю strlen? – К сожалению, нет, ребята с https://www.strchr.com/sse2_optimised_strlen сделали еще быстрее и не используя SSE4.2.
Таблица 2 – время работы бенча strlen в секундах (Release)
| MS побайтовое сравнение | MS strlen | SSE 4.2 | SSE 2 | |
|---|---|---|---|---|
| 10 элементов | 0.15 | 0.12 | 0.18 | 0.14 |
| 1K | 9.0 | 3.9 | 1.68 | 1.47 |
Выводы:
Мне кажется MS-у всегда нужно вызывать библиотечную strlen, а не делать подстановку побайтового сравнения.
Автор: Виталий
