wiki:ru/SIMDStringProcessing

Version 1 (modified by vadim.godunko, 7 years ago) ( diff )

--

Обработка строк с использованием SIMD

Описываемые алгоритмы обработки строк с использованием SIMD ориентированы в первую очередь на архитектуру и систему команд процессоров Intel. Минимально необходимый поддерживаемый процессором набор команд SSE2.

Общие замечания

Index (поиск символа в строке)

Операция Index выполняет поиск позиции первого вхождения символа в строку начиная с некоторой позиции и до конца строки.

В зависимости от исходных параметров используются разные реализации:

  • для символов более 0xFFFF используется обычный алгоритм посимвольного прохода, поскольку эти символы представляются в виде суррогатных пар символов;
  • в случае попадания положения первого и последнего символа среза в границы одного вектора используется специализированная модификация;
  • в оставшихся случаях используется трёхкомпонентная реализация; индивидуальным образом обрабатывают..ся:
    • вектор в котором находится первый символ среза;
    • вектор в котором находится последний символ среза;
    • вектора между предыдущими двумя.

Обработка вектора, общие концепции

Поиск осуществляется используя вектор, каждая из позиций которого заполнена искомым символом. Полученный результат сравнения преобразуется в 16-битну целочисленную величину.

  H G F E  D C B A  - вектор строки "ABCDEFG"
eq
  E E E E  E E E E  - вектор шаблона
  -----------------
  00000011 00000000 - результат поиска

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

При вычислении позиции символа необходимо каждую суррогатную пару принимать за один символ. Это выполняется путём наложения вектора, содержащего маску верхних суррогатных символов и сравнения полученного вектора с вектором верхних суррогатных символов.

  X X L H  X L H X  - вектор строки "XHLXHLXX"
and
  M M M M  M M M M  - вектор маски верхних суррогатных символов
eq
  H H H H  H H H H  - вектор верхних суррогатных символов
  -----------------
  00000011 00001100 - результат поиска

Все кодовые позиции, содержащие '11' в результате необходимо пропускать при расчёте индекса символа. Примечание: возможно использовать инструкцию POPCNT для подсчёта числа единичных бит в маске. Однако, эта инструкция отсутствует в наборе команд SSE2 и её невозможно использовать в типовой реализации.

Обработка вектора, содержащего первый символ среза

Note: See TracWiki for help on using the wiki.