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

Тема в разделе "WASM.BEGINNERS", создана пользователем DevilDevil, 20 янв 2018.

  1. DevilDevil

    DevilDevil Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2007
    Сообщения:
    83
    Если не ошибаюсь, на этом форуме была большая ветка, где осуществляли разные реализации поиска символа (производная от 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;
     
  2. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    1.516
    DevilDevil,

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

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

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

    DevilDevil Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2007
    Сообщения:
    83
    Indy_,

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

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    1.516
    DevilDevil,

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

    Олег New Member

    Публикаций:
    0
    Регистрация:
    1 сен 2017
    Сообщения:
    7
    Пример:
    Код (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=адресу
     
    Последнее редактирование модератором: 21 янв 2018
  6. DevilDevil

    DevilDevil Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2007
    Сообщения:
    83
    pcmpestri появился в SSE 4.2
    А мне нужно посмотреть SSE2 или даже SSE1
    Просто там было много интересных идей, на которых стоит поучиться :)

    Indy_,

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

    Олег New Member

    Публикаций:
    0
    Регистрация:
    1 сен 2017
    Сообщения:
    7
    Для SSE1 не найдёте, а вот для SSE2 например так:
    Код (ASM):
    1. pcmpeqb xmm0,[esi]
    2. pmovmskb eax,xmm0
    3. bsf ecx,eax
     
  8. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    1.516
    DevilDevil,

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

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

    DevilDevil Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2007
    Сообщения:
    83
    Олег,

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

    Mikl___ Супермодератор Команда форума

    Публикаций:
    7
    Регистрация:
    25 июн 2008
    Сообщения:
    2.551
    DevilDevil,
    а вы в той ветке про SSE отвечали? Ну или фразы какие-то запомнили? Или год когда это обсуждалось?
     
  11. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    Из больших тем с разными вариантами и замерами производительности на ум приходит лишь древняя тема Оптимизация подсчёта количества строк в файле. Но это хоть и похожая задача, но не совсем (а для "кого-то" и совсем) не то.
    Что касается конкретно оптимизации strlen, то больших спец.веток на эту тему я что-то не припомню - все было как-то эпизодически и "между прочим" (например, тут есть битая ссылка на "пример векторизации strlen").

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

    murder Member

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

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

    Гугл находит это
     
    Последнее редактирование: 11 фев 2018
  13. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    7
    Регистрация:
    25 июн 2008
    Сообщения:
    2.551
    DevilDevil,
    возможно, то что вы ищите было на WASM.RU между 2012 и 2016, поэтому "множество вариантов решения на разных SSE" и нельзя найти
     
  14. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    1.516
    Посмотрел набор инструкций simd, для данной задачи пригодны видимо только несколько PCMPxx.