Не могу найти ветку с SSE-поиском символа (strlen)

Если не ошибаюсь, на этом форуме была большая ветка, где осуществляли разные реализации поиска символа (производная от strlen). Суть алгоритма в чтении нескольких байт в один регистр и, благодаря математическим операциям, вычисления позиции в этом регистре. В обычных регистрах знаю как делать, как делали в SSE - хочу посмотреть и поучиться.

Вот в качестве примера реализация на Delphi:

Код (Text):

1. function LStrLen(S: PAnsiChar): NativeUInt;
2. label
3.   done;
4. const
5.   CHARS_IN_CARDINAL = SizeOf(Cardinal) div SizeOf(Byte);
6.   SUB_MASK  = Integer(-$01010101);
7.   OVERFLOW_MASK = Integer($80808080);
8. var
9.   Start: PAnsiChar;
10.   Align: NativeInt;
11.   X, V: NativeInt;
12. begin
13.   Start := S;
14.   if (S = nil) then goto done;
15.  
16.   Align := NativeInt(S) and (CHARS_IN_CARDINAL - 1);
17.   if (Align <> 0) then
18.   repeat
19.     if (Byte(S^) = 0) then goto done;
20.     Inc(Align);
21.     Inc(S);
22.   until (Align = CHARS_IN_CARDINAL);
23.  
24.   repeat
25.     X := PCardinal(S)^;
26.     Inc(S, CHARS_IN_CARDINAL);
27.  
28.     V := X + SUB_MASK;
29.     X := not X;
30.     X := X and V;
31.  
32.     if (X and OVERFLOW_MASK = 0) then Continue;
33.     Dec(S, CHARS_IN_CARDINAL);
34.     Inc(S, Byte(Byte(X and $80 = 0) + Byte(X and $8080 = 0) + Byte(X and $808080 = 0)));
35.     Break;
36.   until (False);
37.  
38. done:
39.   Result := NativeUInt(S) - NativeUInt(Start);
40. end;

 

DevilDevil,

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

IA v.1

> была большая ветка, где осуществляли разные реализации поиска символа

Да, лаб. работы": https://wasm.in/threads/studentam-s-voprosami-o-laboratornyx-rabotax-sjuda.7669/

 

Indy_,

Я не студент, и лабу не делаю
Здесь была хорошая ветка, и я пытаюсь её найти

 

DevilDevil,

Эта та ветка, которую вы ищите. А поиск по ней затруднён из за размера. Я не говорил что вы студент.

 

Пример:

Код (ASM):

1. mov eax,0A0Dh
2. movd xmm0,eax
3. mov eax,2          ;размер подстроки в xmm0
4. mov edi,адрес где искать
5. mov edx,размер области поиска в edi
6. поиск: pcmpestri xmm0,[edi],0Ch    ;поиск подстроки из xmm0 с размером eax в [edi] с размером edx, результат в ecx: 0-15 найдено по смещению CF=1, 16-не найдено CF=0
7. add edi,ecx
8. sub edx,ecx
9. jbe ничего не найдено
10. cmp ecx,17-2 ;2 размер подстроки в xmm0
11. jnc поиск
12. ;сюда попадаем если найдено - edi=адресу

 

pcmpestri появился в SSE 4.2
А мне нужно посмотреть SSE2 или даже SSE1
Просто там было много интересных идей, на которых стоит поучиться

Indy_,

Спасибо
Может подскажешь, где эта вся штука начинается? А то ветка и правда очень большая

 

Для SSE1 не найдёте, а вот для SSE2 например так:

Код (ASM):

1. pcmpeqb xmm0,[esi]
2. pmovmskb eax,xmm0
3. bsf ecx,eax

 

DevilDevil,

> Может подскажешь, где эта вся штука начинается?

Я помню что это там всегда обсуждалось, воспользуйтесь гуглом, он найдёт. Но мнение моё иное - не нужно ничего искать, следует открыть доки по архитектуре и изучать. Какие то примеры вам будут абсолютно бесполезны. Почему вы не откроете IA док по этому набору, не понимаю.

 

Олег,

Вот поэтому и хочу найти те посты. Там было множество вариантов решения на разных SSE
С замерами производительности.
Но пока не нашёл

 

Из больших тем с разными вариантами и замерами производительности на ум приходит лишь древняя тема Оптимизация подсчёта количества строк в файле. Но это хоть и похожая задача, но не совсем (а для "кого-то" и совсем) не то.
Что касается конкретно оптимизации strlen, то больших спец.веток на эту тему я что-то не припомню - все было как-то эпизодически и "между прочим" (например, тут есть битая ссылка на "пример векторизации strlen").

PS: Я так вообще никогда не понимал (и сейчас не понимаю) зачем нужны все эти самопальные (рутинные) навороты с огромными оверхедами на выравнивание, обработку голов\хвостов и т.д., если есть готовые неплохо оптимизированные варианты (в той же ntdll).

 

Слил всю ветку через HTTrack далее попытался найти упоминание инструкций SSE по шаблонам: movdq, mova, movu, pcmp, pxor, xorp. Ничего нет.

linasm использует SSE, исходники открыты, но там задача решается в общем виде и код учитывает все исключительные ситуации.

Гугл находит это

 

Посмотрел набор инструкций simd, для данной задачи пригодны видимо только несколько PCMPxx.