Как не сделать самый быстрый strlen и найти недоработку в Visual Studio 2019 Community / forpes.ru

Главная
Как не сделать самый быстрый strlen и найти недоработку в Visual Studio 2019 Community

Как не сделать самый быстрый strlen и найти недоработку в Visual Studio 2019 Community +27

17.09.2019 07:03

v1tos 10 5400 Источник

На размышления меня натолкнула статья об использовании «странной» инструкции 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.

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++;

~~«Добирает» размер строки, если обнаружен ее конец (так как я не до конца уверен в алгоритме работы _mm_cmpistri).~~
удален после комментария 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

Комментарии (10)

maksqwe
17.09.2019 12:07
#20631211
Насколько я понял, вот баг-репорт.
developercommunity.visualstudio.com/content/problem/734414/it-seems-that-visual-studios-cpp-compiler-creates.html

Буду следить, но не думаю что успеют пофиксить до выхода 16.3 версии, скорее всего пофиксят уже в 16.4.

picul
17.09.2019 12:31
#20631331
Судя по документации третий цикл заменяется на: length += res;
Также не совсем понятно зачем первый цикл — можно прочитать без выравнивания с помощью _mm_loadu_si128 и сделать то же, что в основном цикле.
Еще стоит попробовать заменить _mm_cmpistri на _mm_cmpestri — может, станет быстрее.
1. Antervis
  17.09.2019 16:25
  #20633011
  когда loadu попадает на границу страницы, это в лучшем случае медленно, в худшем — segfault.
  1. picul
    17.09.2019 16:52
    #20633157
    Ладно, можно прочитать по выровненному вниз адресу, и проверить как в статье про «самый быстрый» strlen, правильно сдвинув результат movemask-а.
    
    Antervis
    17.09.2019 17:42
    #20633375
    есть у меня подозрение, что выфильтровывание нулей перед невыровненным участком того не стоит для коротких строк
1. v1tos Автор
  17.09.2019 18:01
  #20633483
  Интринсики
  
  __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
  
  Замена на _mm_cmpestri делает код медленнее, почти в 2 раза.
  Выровненная память быстрее на 2-3%, исключения misaligned нет, и да видимо выровнить предварительно лучше, что бы не боятся в основном цикле выхода за границу страницы.
  1. picul
    17.09.2019 18:56
    #20633707
    На счет _mm_cmpestri — странно. Но все равно спасибо за тесты.

Antervis
17.09.2019 13:08
#20631573
Сделали ли мы самую быструю strlen? – К сожалению, нет, ребята с www.strchr.com/sse2_optimised_strlen сделали еще быстрее и не используя SSE4.2.

А за счет чего, если не секрет? Вроде как по latency/throughput pcmpstri обходит pcmpeqb + pmovmskb + not + bsf для всех актуальных процов. Или они сами итерации грамотнее реализовали?

IvUs
17.09.2019 19:32
#20633839
А пробовали ли вы x64 вместо устаревшего x86?
У меня 17я студия, ваш бенч показывает такое:
x86 debug — 8.5
x86 release (все оптимизации) — 3.1
x64 debug — 6.77
x64 release (все оптимизации) — 1.7
То есть x86 и x64 довольно по-разному себя ведут.
1. v1tos Автор
  18.09.2019 13:21
  #20636597
  Добавил тесты для x64. Поведение компилятора VS аналогично.

Как не сделать самый быстрый strlen и найти недоработку в Visual Studio 2019 Community +27

Комментарии (10)

v1tos Автор

v1tos Автор