Приветствую всех. В masm32lib есть процедура IsString, да и по сайту нашел несколько примеров, но в них есть некоторые особенности (например, регистрозависимые, удаляющие пробелы, возвращающие ошибку, если искомая строка равна по длине той в которой ищут), которые меня не устраивают, поэтому написал сам процедуру поиска подстроки. Для сравнения взял InString. Вот сама процедура: Код (Text): InStringI proc uses ebx esi edi Start:DWORD, StrAddr:DWORD, MatchAddr:DWORD, MatchLen:DWORD ;-------------------------------------------- mov ecx,Start ;стартовая позиция (поиск с начала строки - 1) mov esi,StrAddr ;начало строки @StartPos: ;поиск нуля в куске строки от начало+старт.позиция cmp byte ptr [esi+ecx-1],0 ;до начала строки je @OutOfString ;если встречен ноль - старт. позиция задана за пределами строки loopnz @StartPos ;-------------------------------------------- cmp Start,0 ;"защита от дурака" jle @InvalidStart mov ecx,MatchLen ;кол-во символов, которое должно совпасть dec Start add esi,Start ;абсолютный стартовый адрес mov edi,MatchAddr ;стартовый адрес MatchString xor eax,eax ;для выхода с eax==0 align 16 ;на всякий случай :) @Loop: mov al,byte ptr[esi] mov bl,byte ptr[edi] test al,al ;если строка просмотрена до конца jz @Ret ;выход с нулём в eax ;------- кусок для обеспечения case insensitive ---------- ;.if al >= 'А' && al <='Я' ; add al,32 ;.elseif al >= 'A' && al <= 'Z' ; add al,32 ;.endif ;.if bl >= 'А' && bl <= 'Я' ; add bl,32 ;.elseif bl >= 'A' && bl <= 'Z' ; add bl,32 ;.endif ;--------------------------------------------------------- cmp al,bl ;поиск совпадения je @Next mov ecx,MatchLen ;если символы не совпадают, длина искомой цепочки=MatchLen inc esi ;следующий байт строки mov edi,MatchAddr ;Match-строку будем смотреть с начала jmp @Loop @Next: ;если символы совпали dec ecx ;уменьшаем кол-во оставшихся в "очереди совпадения" jnz @F sub esi,MatchLen ;если "очередь совпадения" закончилась, inc esi ;вычисление позиции, с которой начинается mov eax,StrAddr ;последовательность символов, совпадающая sub esi,eax ;с MatchString inc esi xchg eax,esi ;выход. В eax- позиция вхождения jmp @Ret @@: inc esi ;просмотр следующих байтов inc edi jmp @Loop @InvalidStart: mov eax,-1 ret @OutOfString: mov eax,-2 @Ret: ret InStringI endp При сравнении с InString получается, что если искать с позиций в начале строки (Start=1), то моя процедура работает на 20-25% быстрее, если искать с позиции где-нибудь в конце строки, то уже InString быстрее на те же 20-25%. Можно ли ещё выжать скорости из этой процедуры, сам сколько смог, уже сделал? P.S. Закомментированный кусок, обеспечивающий регистронезависимость, можно пока не рассматривать.
Некоторые мысли: регистр edx не используется, можно хранить в нём, например, MatchLen. Переходы вперёд предсказываются как not taken, наиболее вероятные лучше делать назад. Немного подредактировал, в основном по размеру, не знаю будет ли работать =) Код (Text): @Loop: mov al,byte ptr[esi] mov bl,byte ptr[edi] test al,al ;если строка просмотрена до конца jz @Ret ;выход с нулём в eax inc esi ;следующий байт строки inc edi dec ecx cmp al,bl ;поиск совпадения cmovne ecx,MatchLen ;если символы не совпадают, длина искомой цепочки=MatchLen cmovne edi,MatchAddr ;Match-строку будем смотреть с начала test ecx,ecx jnz @Loop sub esi,MatchLen ;если "очередь совпадения" закончилась, inc esi ;вычисление позиции, с которой начинается mov eax,StrAddr ;последовательность символов, совпадающая sub esi,eax ;с MatchString xchg eax,esi ;выход. В eax- позиция вхождения @Ret: ret @InvalidStart: stc ; CF - признак ошибки sbb eax,eax ; при анализе делаем: jmp @Ret ; inc eax @OutOfString: ; jz InvalidStart xor eax,eax ; js OutOfString sub eax,2 jmp @Ret IMHO основным тормозом тут будет кусок для обеспечения case insensitive, поскольку там куча Jcc. Может СтОит сделать табличное преобразование регистра ?
S_T_A_S_ Практически такие же мысли, вот только с переходами старался сделать и вперед и назад как not taken. А чем различатся направление перехода? Если переход not taken? И избавился от пары jmp-ов. А вот mov edx,MatchLen дивидендов не принесло. Ну и ещё align16 потыкал в разных местах, экспериментально подобрал оптимальное. Код (Text): align 16 mov edx,MatchLen ;кол-во символов, которое должно совпасть xor eax,eax ;для выхода с eax==0 dec Start add esi,Start ;абсолютный стартовый адрес dec esi @Loop1: mov edi,MatchAddr ;стартовый адрес MatchString mov ecx,edx @Loop: inc esi mov al,byte ptr[esi] mov bl,byte ptr[edi] test al,al ;если строка просмотрена до конца jz @Ret ;выход с нулём в eax ;------- кусок для обеспечения case insensitive ---------- cmp al,'A' ;eng jl @F cmp al,'Z' jg @F add al,32 @@: cmp al,'А' jl @MM cmp al,'Я' jg @MM add al,32 @MM: cmp bl,'A' ;eng jl @F cmp bl,'Z' jg @F add bl,32 @@: cmp bl,'А' jl @MM1 cmp bl,'Я' jg @MM1 add bl,32 @MM1: ;--------------------------------------------------------- cmp al,bl ;поиск совпадения jne @Loop1 inc edi dec ecx ;уменьшаем кол-во оставшихся в "очереди совпадения" jnz @Loop sub esi,edx ;если "очередь совпадения" закончилась, inc esi ;вычисление позиции, с которой начинается mov eax,StrAddr ;последовательность символов, совпадающая sub esi,eax ;с MatchString inc esi mov eax,esi ;выход. В eax- позиция вхождения ret @InvalidStart: mov eax,-1 ret @OutOfString: mov eax,-2 @Ret: ret В итоге в наиболее типичной ситуации: case insensitive поиск в начале строки длина MatchLen = 10 почти уравнял скорость в сравнении с InString : 1050 тиков против 1030. В регистрозависимом варианте получается где-то в 2 раза быстрее. А что за табличное преобразование регистра? Что за зверь такой? Можно чуть подробней? А то регистронезависимость пожирает ровно половину времени
S_T_A_S_ Доработал чуть напильником твой вариант, а то не хотел работать: вставил jne @Loop Код (Text): cmovne ecx,MatchLen cmovne edi,MatchAddr jne @Loop test ecx,ecx jnz @Loop чуть медленнее моего: 670:580 в регистрозависимом варианте Описания cmovne у меня нет, но по смыслу догадался, так она похоже тяжеловатая на подъём. По-моему лучше делать mov и два разных места входа в цикл, как в предыдущем посте: один для ne: jne @Loop1 другой для nz: jnz @Loop
cresta > Когда проц встречает условный переход первый раз, если это переход назад (т.е. в сторону младших адресов, смещение перехода - отрицательное), то считается, что условие перехода (следовательно и сам переход) выполняется, если вперёд - то нет. Потом конечно вычисляется это условие, и если оно не совпадает с предсказанным - то приходится заново выполнять другую ветвь.. Во 2й раз проц уже помнит предыдущее поведение Jcc и выполныет его, поэтому на циклах с большим кол-вом итерраций эффект "сглаживается", а если условие будет меняться каждый 2й раз? > Заполняешь массивчик 256 байт: Код (Text): xor eax, eax @@: mov byte[char_map+eax],al ; cmp al, "А" ; jb case_Ok ; cmp al, "Я" ; ja case_Ok ; add byte[char_map+eax],20h ;case_Ok: inc al jnz @b Теперь каждый элемент массива соответствует ASCII коду буквы. К элементам, соответствующим ЗАГЛАВНЫМ буквам прибавляешь 20h, например раскомментировав строчки выше. Использовать так: Код (Text): movzx eax,byte ptr[esi] mov al,byte ptr[char_map + eax] > Я подозревал, что мой код не рабочий, как всегда =) Тока не пойму, как jne @Loop может повлиять... Если в результате cmp al,bl флаг Z установлен (AL == BL), то значение ECX командой cmovne изменено не будет. и дальнейший test ecx,ecx + jnz @Loop эквивалентен ветке je @Next + jnz @F. Иначе (AL != BL) в ECX загружается MatchLen и test ecx,ecx + jnz @Loop эквивалентен ветке с не выполненным je @Next. MatchLen же не может быть равно 0? Хотя щас твой вариант даже наверное лучше. Тут imho всё равно сильно не наоптимизируешь, я просто пытался уйти от множества условных переходов. Ещё, обрати внимание, как можно делать выход из функции - каждый ret - это несколько pop, leave и ret N. Можно съэкономить пару байт. xor + sub - это 5 байт, как и mov eax,-2. но помимо этого устанавливает флаг переноса. Eстановка -1 в EAX чуть короче. Ты же пишешь на асме, а не на HLL, поэтому по выходу из функции можно просто посмотреть флаги, а не сравнивать возвращаемое значение с -2 или -1 -- эконимим ещё немного времени и места.
S_T_A_S_ По идее правильно, одного jnz @Loop должно было хватить, но я может намудрил чего, кучу вариантов пробовал, и забыл откуда и куда шёл Про выход с флагами, как индикаторами ошибок - это хорошо, принимается С предсказанием перехода тоже понятно, только надо посмотреть, в зависимости от String и MatchString, куда наиболее вероятны переходы. С таблицей так и делал, кучу байт. Первоначально использовал xlat, но что-то с ним тормозит Переделал на такую штуку (xlat разложил вручную): lea ebx,Table mov al,byte ptr[edi] mov dl,byte ptr[ebx+eax] mov al,byte ptr[esi] mov al,byte ptr[ebx+eax] Так получается заметно быстрее. Пока имею такое: Код (Text): ;-------------------------------------------- mov ecx,Start mov esi,StrAddr @StartPos: cmp byte ptr [esi+ecx-1],0 je @OutOfString loopnz @StartPos ;-------------------------------------------- cmp Start,0 jle @InvalidStart ;-------------------------------------------- lea ebx,Table align 16 xor eax,eax dec Start add esi,Start dec esi @Loop1: mov ecx,MatchLen mov edi,MatchAddr @Loop: inc esi mov al,byte ptr[edi] mov dl,byte ptr[ebx+eax] mov al,byte ptr[esi] mov al,byte ptr[ebx+eax] test al,al jz @Ret ;--------------------------------------------------------- cmp al,dl jne @Loop1 inc edi dec ecx jnz @Loop sub esi,MatchLen inc esi mov eax,StrAddr sub esi,eax inc esi mov eax,esi ret ;-------------------------------------------- @InvalidStart: mov eax,-1 ret @OutOfString: mov eax,-2 @Ret: ret ;------- case insensitive Table ---------- Table: db 0,1,2,3..... В принципе уже неплохо. При типичных для моего случаях String и MatchString работает быстрее, чем InString даже с case insensitive. Ну и флаги ещё привяжу. ОК, S_T_A_S_ спасибо за помощь
cresta Можно попробовать не занимать регистр ebx под адрес таблицы: mov dl,byte ptr[Table+eax] хотя врядли это чего прибавит, кроме размеру Только вместо: lea ebx,Table лучше делать: mov ebx,offset Table это меньше на байт (хотя пресловутый intel C compiler использует почему-то lea)
Алгоритм для поиска подстрок с запоминанием смещений(в аттаче файл под tasm). Для ускорения размножил количество проверок первого символа образца, эдакий unroll. Это хорошо действует, когда сам символ встречается не очень часто. Думаю что поможет больший unroll (х32), поскольку можно будет делать префетч. Для безразличия к регистру символов, наверно лучше делать два сравнения, чем преобразования, типа: Код (Text): mov cl, 1 cmp [esi + 0], bl ; cmp cc[0], 'a' je @cmpNextChar cmp [esi + 0], bh ; cmp cc[0], 'A' je @cmpNextChar add cl, 1 cmp [esi + 1], bl ; cmp cc[1], 'a' ... _1792888953__scantxt.asm
