Практическое введение в строковые операции SSE4.2 (STTNI)

В рамках конкурса Accelerate 2012 нам всем пришлось хорошенько поработать со строками.
Сначала от участников, а затем и от организаторов прозвучала идея, что использование набора инструкций SSE4.2 может придать значительное ускорение.

Скажу честно, мы с некоторым недоверием посмотрели на эту идею:
- Как мы применим SSE в нашем, еще не существующем, решении?
Но внесли её в список todo и, когда код уже начал обретать законченный вид, мы нашли места "приложения рычага".
Потратив всего несколько часов (на чтение документации по STTNI, эксперименты и переписывание) нам удалось ускорить "тяжелые" фрагменты в два-три раза!

Небольшое предупреждение: не ожидайте что SSE инструкции превратят неэффективный алгоритм в конфетку. Уделяйте внимание прежде всего асимптотике и простоте. Затем беритесь за специальные инструменты для участков кода на которые указал профайлер.



Я постараюсь описать картину крупными мазками. За подробностями загляните в руководство по SSE4 для разработчиков. Хорошая документация по командам и параметрам лежит в MSDN. Оба ресурса на английском языке.

Что включает в себя SSE4.2

  • операции с парами строк - именно о них пойдет речь дальше

  • вычисление CRC32

  • подсчет количества установленных бит

  • операция "больше чем" упакованных 64-битных знаковых чисел (Compare Packed Signed 64-bit data For Greater Than)



Выбираем форму

Существует 4 инструкции процессора и целых 14 команд поддерживаемых компилятором.
Следующий рисунок поможет разобраться с ними:




  • e или i в середине команды говорит о том, как определена длина входных строк: explicit - длина указывается явно или implicit - процессор сам определит длину нуль-терминированной строки.

  • суффикс команды определяет тип результата: index - значение индекса или mask - битовая маска. Кроме этого, можно получить значение арифметических регистров (выделены синим), которые изменяются в зависимости от содержимого операндов и полученного результата. Это пригодится, если вам, к примеру, интересно не точное местоположение символа в строке, а сам факт его наличия.



... и содержание

Последний аргумент каждой из команд - управляющий байт (imm8 control byte) объясняет как нужно интерпретировать данные и что с ними нужно сделать.



Байт формируется комбинацией флагов которые определяют:

  • формат данных: знаковые или беззнаковые числа? Байты или пары байт (unicode)?

  • тип сравнения:

    • равенство любых символов - для поиска символов из набора (_SIDD_CMP_EQUAL_ANY)

    • равенство символов из диапазона - поиск символов из диапазона (_SIDD_CMP_RANGES)

    • посимвольное сравнение - сравнение строк (_SIDD_CMP_EQUAL_EACH)

    • упорядоченное сравнение - поиск подстрок (_SIDD_CMP_EQUAL_ORDERED)


  • промежуточное преобразование результата (polarity). Подробности в документации. Ниже будет пример с использованием этого флага

  • для результата-индекса - нужно ли вернуть наименьший (_SIDD_LEAST_SIGNIFICANT) или наибольший найденный индекс (_SIDD_MOST_SIGNIFICANT)

  • для результата-маски - вернуть битовое (_SIDD_BIT_MASK) или целочисленное (_SIDD_UNIT_MASK) её представление.



Примеры

Пара примеров прямо из нашего кода. Мы оперируем беззнаковыми байтами в силу специфики решения.

Поиск первого вхождения любого символа из строки:

int get_first_index_of_symbol(unsigned char * needle, int needle_length,

	unsigned char * haystack, int haystack_length)

{

	return _mm_cmpestri(

		_mm_loadu_si128((const __m128i*)needle), needle_length,

		_mm_loadu_si128((const __m128i*)haystack), haystack_length,

		_SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ANY | _SIDD_LEAST_SIGNIFICANT);

}



Длина строк известна и нам нужна позиция символа. Выбор падает на _mm_cmpestri.

Определяемся с флагами:

  • мы оперируем с беззнаковыми байтами - _SIDD_UBYTE_OPS

  • нужно найти вхождения символа в любом месте - _SIDD_CMP_EQUAL_ANY

  • нас интересует первое вхождение - _SIDD_LEAST_SIGNIFICANT



Все эти флаги можно опустить, поскольку они установлены по умолчанию.

Поиск первого несовпадающего символа для строк равной длины (используется для нахождения длины наибольшего общего префикса):

int get_first_unmatch(unsigned char * a, unsigned char * b, int length)

{

	return _mm_cmpestri(

		_mm_loadu_si128((const __m128i*)a), length,

		_mm_loadu_si128((const __m128i*)b), length,

		_SIDD_CMP_EQUAL_EACH | _SIDD_NEGATIVE_POLARITY);

}



Обратите внимание, что поменялись только управляющие флаги:

  • нужно посимвольное сравнение - _SIDD_CMP_EQUAL_EACH

  • нас интересует несовпадение - _SIDD_NEGATIVE_POLARITY



Что получится, если символ не был найден или строки совпадают? Мы получим в ответ 16 (или 8, если бы операции были над строками из двухбайтовых символов).

Чтобы не быть голословной, утверждая что STTNI дает преимущество, я замерила время выполнения участка кода для файла размером 200 Мб:

  • без SSE - 360 мс
    
    //i - текущее положение в строке buffer размера size
    
    while (i < size && buffer[i] != 'n' && buffer[i] != '>') i++;
    
    //i выходит за пределы строки или указывает на искомый символ
    
    


  • с SSE - 171 мс
    
    //i - текущее положение в строке buffer размера size
    
    char * needle = "n>";
    
    while (i + 15 < size)
    
    {
    
    	int r = get_first_index_of_symbol(
    
    		(unsigned char *)needle, 2,
    
    		(unsigned char *)(buffer + i),
    
    		16);
    
    	i += r;
    
    	if (r != 16) break;
    
    }
    
    while (i < size && buffer[i] != 'n' && buffer[i] != '>') i++;
    
    //i выходит за пределы строки или указывает на искомый символ
    
    




Результат налицо (:

Интересно, а кто еще использовал SSE4.2 в решении? Насколько быстрее оно сделало ваш код?
Для получения подробной информации о возможностях оптимизации компилятора обратитесь к нашему Уведомлению об оптимизации.