alpet
„Использование шаблонов в Це например, было бы неплохо переложить на динамический код, но это потребует другой процессорной архитектуры.“
А она(другая процессорная архитектура) уже неплохо
вырисовывается. Т.е. нужен процессор, где были бы
флажки для модификации выполняемых сходных команд.
Т.е. в твоем случае понадобилось бы не переписывать
коды команд, а просто поставить нужные флажки.
В идеале можно было сделать программирование
с минимумом переходов, т.к. программа была бы
почти линейной, ну кроме циклов конечно.

Делать отдельную оптимизированую функцию для каждого варианта, может и увеличит скорость поиска, но по моему на разных процессорах, эта оптимизиция отзовется по разному, так что стоит ли овчинка выделки.

А неплохо бы было иметь набор программируемых инструкций. Можно было бы получить код типа:

 setinstr 80h, 01h  ; dmov копирует байты
 setinstr 30h, 01h  ; dcmp сравнивает однобайтные значения
 setinstr 78h, 15h  ; dskip префикс пропуска команды, на ZF
 
@loop:
 dmov     rbx, [esi] 
 dcmp     rax, rbx  ; На самом деле al, bl
 dskip jmp    @skip ; Если значения не равны, данная команда будет пропущена 
  .... ; сохранение адреса
@skip: 
 dinc    esi        ; на 1 в данном случае
 cmp     esi, [limit]
 jb      @loop

Весьма компактный и универсальный код бы получился.

Если идеально оптимизировать поиск, надо цикл развернуть до 16 раз. Это подходит для алгоритма побитовой упаковки найденых результатов: в два байта умещается 16 смещений.

В теле цикла будет нечто вроде:

 @loop:  
   cmp  ecx, [esi]  ; Сравнить с образцом
   sete al          ; Установить в 1 если равно  
   or   bl, al
   shl  ebx
   inc  esi
   ... и так 16 раз. 
   mov  [edi], bx  ; сохранить множество
   add  edi, 4 
   cmp  esi, 12345678h
   jb  @loop

Нет ни jmp'ов, ни call'ов - благодать для конвейера. Для AMD64 цикл соответсвенно можно до 64 раз развернуть, но будут издержки на хвосты буфера, их придется искать отдельно, или забивать значениями не совпадающими с критериями поиска.

alpet > „проверил на iCel2400: макс. результат - 1605Ms/s. Скорость поиска колеблется от 100 до 115Мб/с.“

К слову.
Разница между 2мя вариантами кода в тесте - используется предвыборка (сам код различается всего 2мя командами).
И это даёт прирост скорости в ~2 раза.
Код из теста конечно далёк от реальности, поскольку ничего полезного не делат, но показывает тот порог, с которого нужно думать о низкоуровневой оптимизации.
Поке же скорость работы имеет другой порядок, IMHO логичнее думать о других способах оптимизации, например, алгоритмических.


> „Делать отдельную оптимизированую функцию для каждого варианта, может и увеличит скорость поиска, но по моему на разных процессорах, эта оптимизиция отзовется по разному, так что стоит ли овчинка выделки. “

Можно не строить догадки, а проверить.
Например, сравнить 2 варианта поиска байта == 0

A)
mov al,0
rep scasb

B)
\masm32\M32LIB\STRLEN.ASM (см. аттач).

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

_1854888455__STRLEN.ASM

S_T_A_S_ Использовать цепочечные команды в прнципе можно. Но есть следующие ограничения:

1. Все смещения придется упаковывать отдельным кодом, который пока тоже не оптимизирован. Если же развернуть цикл, то параллельно с упаковкой можно будет достичь лучших результатов, особенно в случаях когда искомые значения встречаются регулярно.
2. Цепочечные команды допускают поиск значений по критериям "равно", либо "не равно", то есть ограничивается поливариантность поиска.
3. Если искать что либо больше байта, не выровненые значения будут игнорироваться, а разработчики игр такие значения могут пользовать из соображений защиты от читерства (глупо конечно).

.

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

IMHO При поиске с запоминанием позиций вхождений значения, лучше использовать setcc команды. Это несколько уменьшит количество ветвлений в циклах, и процессору не придется их предсказывать.
Впрочем надуманный алгоритм требует строгой проверки, чем я и займусь когда поставлю Delphi, с переездом в Moscow, оставил дома все дистрибутивы.

Получился пока следующий код (см. вложение).
По скорости обычный поиск (с частыми jmp'ами) на iCell2400 где-то в два раза медленее (110 и 200 ticks / 64Mb). Суть алгоритма, при сканировании дв. слов с инкрементом 1, чтение производится только по смежным словам (инкремент 4), а промежуточные слова получаются с помощью циклических сдвигов. Код пока не динамический, и оптимизировать я его не стал.
Пока работаю над улучшением алгоритма, хочется повыкидывать из кода много комманд.
Перезапись кода думаю осуществить за один проход, скопировав модифицированную функцию целиком из области данных (rep movsd).

_1017914719__FScan.zip

[edited]
Извиняюсь код неправильный делает 5 сравнений для пакета в 16 байт. Правильный код пока работает в 1,5 медленнее чем обычный. Выложу его попозже, может и оптимизирую.

2 > S_T_A_S_
Скорости чтения как в memread недостигнуть все равно, потому что производится еще и запись результатов, и хорошо если транзакции не перекрываются. Интересно как в коде чтения будет выполнятся repnz lodsd, вместо xor ebx, [esi + ecx + nn].

По теории (и на пракитке тоже) предельный bandwidth (это запись + чтение) памяти составляет где-то ~85% от физической скорости шины процессор-память.

Например, есть память DDR266 или PC2100, так вот, скорость копирования памяти будет ~1800 Mb/sec.
Эта скорость очень мало (!) зависит от частоты процессора. Например Athlon1000 и Athlon2000+ (1666Mhz) копируют память с одной скоростью (это я проверял сам).
Так что говорить о том, что процессор обрабатывает блок памяти за N тактов - говорить ни о чём, это не показатель в данном случае.
Причём, если память работает на 400Mhz, а шина процессора 266Mhz, то в расчётах нужно принимать именно последню (меньшую) цифру.
Как достигнуть этого предела, хорошо написано в документе от AMD, линк на который я приводил выше..

Увеличение сорости происходит именно из-за объединения нескольких транзакций чтения а потом нескольких транзакций записи.
Процессор никогда не читает данные по байту или dword'у.

К чему это:
Оптимизировать internal loop нужно уже после того как работа с памятью ведётся оптимальным образом.
Оптимально - это считывать, например, 64К данных в кеш, а потом уже работать именно с ним.
(или хотя бы команду prefetch использовать)
Так же и для записи.
Если всего этого нет, то остальные ухищрения мало помогут.. (хотя ухудьшить ситуацию можно легко)
Пример memread - это всего лишь иллюстрация важности такого подхода - как раз один способ испольует предвыборку данных а второй - нет.
Но в обоих случаях ядро процессора не загружено на 100%! Можно добавить полезные команды, и скорость практически не изменится.



> „Интересно как в коде чтения будет выполнятся repnz lodsd, вместо xor ebx, [esi + ecx + nn].“

В несколько раз медленнее. lodsd не спаривается с другими командами, и выполняется сама по себе долго.

Как оказалось оба поиска работали не верно. После исправления оказалось что первый тратит аж 590мс на 64Mb.
Второй после исправления был развернут в 32 раза, и тратил соответственно 328мс.
Изначально код состоял из 32 таких кусков:

 
  cmp           dword ptr [esi + 1], esp
  sete          al
  mov           ah, al
  shl           eax, 1
 

Сразу увидел зависимости и переписал код в 8 кусков такого плана:

  cmp           dword ptr [esi], esp
  sete          al
  mov           ah, al
  shl           eax, 4

  cmp           dword ptr [esi + 1], esp
  sete          cl
  mov           ch, cl
  shl           ecx, 4

  cmp           dword ptr [esi + 2], esp
  sete          dl
  mov           dh, dl
  shl           edx, 4

  cmp           dword ptr [esi + 3], esp
  sete          bl
  mov           bh, bl
  shl           ebx, 4

Приготовленные множества потом складывались.
Время поиска уменьшилось до 187мс. Для iCell хватило бы и 3 регистров (он больше вроде не может параллельно вычислять), но их не удобно складывать.
Проблема в коде следующая: последние 3 куска в каждой итерации цикла, читают слова которые находятся по разным линейкам кэша и считываются за два пакетных цикла. Подскажите плиз, как это можно победить?



_999966093__FScan.zip

2 > S_T_A_S_
Разогнал проц по шине до 3200. Твоя прога стала показывать странные результаты: no prefetch 1796, prefetch 1531. Раньше было наоборот. Вернул все на место получилось 1340 и 1163 соотвественно. Надо поковырять БИОС - тут что-то не так.

При разгоне моя прога выдает 125мс/64Мб = 512Мб/с - 1/4 для DDR2100.
[edited]
Вернуть пока ничего не удалось. Если запустить сразу три экземпляра memread2, первый выдает соотношение no prefetch/prefetch = 1600/1300, два вторых 900/51. Получается в случае большой загрузки проца, prefetch проигрывает в 18 раз ??

Скриншот для memread2.exe

_2098053508__1.jpg

Скриншот для 2 из 3 одновременно запущенных экземпляров memread2.exe

1705223748__2.jpg

По поводу теста: новые процы умеют аппаратный префетч делать, иногда он мешает, иногда помогает (кстати, включается обычно в биосе).
На PIII (и раньше) такого не было, появился на athlon (XP ?) и PIV. К последнему у меня доступа просто нет, так что изучать этот вопрос до сих пор не довелось :(

Кстати, на скорость влияет размер кеша - в моём тесте используются 128Kb блоки, для Celeron это видимо слишком много, т.к. при переключении задач, кэш портится.
Именно с этим и вызвано сильное снижение скорости при запуске нескольких экземпляров теста. методика расчитана на эксклюзивное использование ресурсов.


По поводу поиска:
не пойму до сих пор, зачем искать DWROD'ы?
Я бы далел так:
- ищем совпадения байтов (для этого хорощо подходит алгоритм поиска по 4 байта, который я приводил раньше)
- если байт совпадает, сохраняем указатель на него. "упаковка" 32->1 IMHO более расточительно использует память. Да и на 2м этапе обрабатывать меньший по объёму блок - значит выиграть в скорости (алгоритм на 2м этапе - более сложный, так что выигрыш IMHO заметен будет)
- на 2м этапе смотрим полученные указатели - если 2 подряд - совпадение WORD, 4 подряд - совпадение DWROD. Количество проходов на первом этапе сокращено и нет считаваний невыровненных данных.

На сравнениях вида > < этот метод тоже работает.


ЗЫ: ещё несколько возможных замен в коде:

  mov           eax, dword ptr [BuffSize]
  add           dword ptr [Limit], eax
  sub           dword ptr [Limit], 128

на

  mov           eax, dword ptr [BuffSize]
  sub           eax, 128  
  add           dword ptr [Limit], eax

  mov           ecx, edi
  add           ecx, MaxCount * 4
  sub           ecx, 256

на

  lea           ecx, dword ptr [edi + MaxCount * 4 - 256]

  mov           ah, al
  shl           eax, 4

на

  shl           eax, 12

хотя на 4м пне это возможно будет и медленнее, т.к. там сдвиги плохо работают :-/

2 > S_T_A_S_
На счет предложенного алгоритма - обязательно попробую, может будет выигрыш на редко-встречающихся-значениях. Главное чтобы пост-отсев работал с наименьшими затратами (тут не плохо определять до начала поиска самый значимый байт, а то для чисел меньших 0ffffffh, будут нули искаться, а их может быть довольно много).
Сжатие в множества - еще не предел, после этого все 2-байтные слова множества группируются по одинаковости (очень эффективная упаковка потому что регулярны множества 0xffff и 0x0000). Так что в идеале и эту упаковку сделать на лету (этим сейчас я и занимаюсь).

Насчет "shl eax, 12" правильно - команды же распараллелены, поэтому кол-во тактов менее существенно размера кода. В самом деле время выполнения упало с 187мс до 172мс (372Mb/s) = спасибо.

На то что до начала цикла внимание не обращайте, все равно переписывать на динамический код. Способ избежания штрафных тактов описаный ниже, похоже работает, поэтому многажды обруганный SMC рулит (экономия регистров опять таки). Тиражировать же код все-равно будет нереально, потому что будут и такие команды переписываться:

 
 cmp [esi + 1], eax ;; Compare with example
на
 cmp [esi + 1], 12345678h ;; Changed to example by SMC, before function call