Оптимизация и полиморфный код

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%! Можно добавить полезные команды, и скорость практически не изменится.







>

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

 

Как оказалось оба поиска работали не верно. После исправления оказалось что первый тратит аж 590мс на 64Mb.

Второй после исправления был развернут в 32 раза, и тратил соответственно 328мс.

Изначально код состоял из 32 таких кусков:

Код (Text):

1.  
2.   cmp           dword ptr [esi + 1], esp
3.   sete          al
4.   mov           ah, al
5.   shl           eax, 1
6.  

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

Код (Text):

1.  
2.   cmp           dword ptr [esi], esp
3.   sete          al
4.   mov           ah, al
5.   shl           eax, 4
6.  
7.   cmp           dword ptr [esi + 1], esp
8.   sete          cl
9.   mov           ch, cl
10.   shl           ecx, 4
11.  
12.   cmp           dword ptr [esi + 2], esp
13.   sete          dl
14.   mov           dh, dl
15.   shl           edx, 4
16.  
17.   cmp           dword ptr [esi + 3], esp
18.   sete          bl
19.   mov           bh, bl
20.   shl           ebx, 4
21.  

Приготовленные множества потом складывались.

Время поиска уменьшилось до 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. Количество проходов на первом этапе сокращено и нет считаваний невыровненных данных.



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





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

Код (Text):

1.   mov           eax, dword ptr [BuffSize]
2.   add           dword ptr [Limit], eax
3.   sub           dword ptr [Limit], 128

на

Код (Text):

1.   mov           eax, dword ptr [BuffSize]
2.   sub           eax, 128  
3.   add           dword ptr [Limit], eax

Код (Text):

1.   mov           ecx, edi
2.   add           ecx, MaxCount * 4
3.   sub           ecx, 256

на

Код (Text):

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

Код (Text):

1.   mov           ah, al
2.   shl           eax, 4

на

Код (Text):

1.   shl           eax, 12

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

 

2 > S_T_A_S_

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

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



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



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

Код (Text):

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

 

alpet >

Хм.. если отказ от MOV даёт выигрыш, то может быть стОит попробовать параллелить не на 4х регистрах, а на 2х, как-нибудь так: (можно сразу в 32бита упаковывать, а не в 2 по 16)

Код (Text):

1.  
2.   xor           eax, eax
3.   xor           ecx, ecx
4.   xor           edx, edx
5.   xor           ebx, ebx
6. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;
7.  
8.   cmp           dword ptr [esi], esp
9.   sete          al
10.   add           ebx, eax
11.   shl           ebx, 2
12.  
13.   cmp           dword ptr [esi + 1], esp
14.   sete          cl
15.   add           edx, ecx
16.   shl           edx, 2

Да, ещё

Код (Text):

1.   mov           ebp, dword ptr [esi + 32] // Упреждающее чтение

можно не портить регистр, применив команды test или cmp. Или использовать prefetchnta.





>

В принципе, указатели тоже можно "сжимать" каким-нибудь RLE. (это ещё и упростит анализ совпадений WORD & DWORD)

Можно использовать факт, что в win32 старший бит адреса всегда == 0

Например, если этот бит == 1, то следом идёт DWORD - количество последовательных совпадений.

 

S_T_A_S_>

Это скорее всего повредит, т.к в каждом куске явная зависимость от операндов, и соответсвенно кол-во регистров роли не играет, надо проверить. На Celerone, параллелить хорошо 3-4 регистра, на сколько хватит, а на Athlone и P4HT еще не пробывал, но наверное не более 4.

-------------------------------------------------------

Насчет сжатия, IMHO множества еще лучше сжимаются RLE, если в каждом 16 или 32 значения.

 

Альтернативный вариант распараллеливания:

Код (Text):

1.  
2. cmp    dword ptr [esi + 1], esp
3. sete   al
4. cmp    dword ptr [esi + 2], esp
5. sete   bl
6. or     ah, al
7. cmp    dword ptr [esi + 3], esp
8. set    cl
9. or     bh, bl
10. cmp    dword ptr [esi + 4], esp
11. sete   cl
12. shl    eax, 4
13. cmp    dword ptr [esi + 5], esp
14. sete   cl
15. shl    ebx, 4
16.  ... и т.д.
17.  

Зависимости нет от готовности операдов нет , надо только спарить команды получше, подскажите плиз как.



S_T_A_S_>

Регистр ebp ни в коем разе не портиться, значение из него пользуется в следующей итерации цикла (не экономно конечно, в условиях ограничений - но латентность IMHO несколько падает).

 

Решил с пересечением пакетных циклов бороться прежним образом: сдвигать два регистра для получения 3 последних 4-байтных слов. Пока еще не доделал - но скорость уже 156ms/64Mb.



S_T_A_S_>

Для относительного сравнения скорости алгоритмов, написал процедуру чтения памяти, изначально скопированную из memread2.asm. Оказалось запас в оптимизации еще есть, если опять же распараллелить команды. У кода состоящего из одних test ebx, [esi + ecx] тратилось 43,8ms на 64mb, а у кода с eax, edx, ebx - 37,5. Впрочем это небольшая прибавка. Для полного теста сделал развернутый цикл - читает одной предвыборкой по 4Kb за итерацию. Не знаю врет ли таймер - минимальный результат: 218ms / 10 итераций. Это 2935Мб/c, 91% от DDR3200 которая сейчас используется. Не исключаю что где-то есть ошибка, буду тестить. Цикл кстати очень хрупкий получился - изменишь команду скорость сразу падает, но не исключено и его оптимизировать. Кончено эффективной скоростью это назвать не можется - читается одно из 8 4-байтных слов.

Было бы неплохо его перенести в memread2, что он там покажет с использованием rdtsc.





337724290__fscanfrm.zip

 

Прилепил "развёрнутую" версию предваборки - результаты на AthlonXP - ни какой разницы с циклом.



>

Это IMHO странно - результат операции test не сохраняется, значит зависимостей быть не должно!



В дельфи нет оператора align?

Возможно причина всех этих "хрупкостей" - отсутствие выравнивания кода в циклах.





Вообще же, думаю код предвыборки измерять на скорость смысла мало - он сам по себе не несёт ни какого смысла, другое дело, что из-за него полезный код может выполняться быстрее. А может и не быстрее, как уже убедились. Иногда аппаратный префетчинг работает нормально, и разницы не видно. Хорошо на старых процах (PIII) это смотреть, там сразу заметно.



_434805317__read.zip

 

S_T_A_S_>

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



Новый memread показал результаты unrolled prefetch 3080Mb/s и prefetch 1334. Это означает что таймер не врет, и что узкое место у Celeron - считывание данных из кэша L1. Наверное даже сплошной поток prefetchnta не даст такого чтения в кеш. Попробую этот код использовать для быстрого копирования больших блоков.

 

В разогнаном до 3207 (память 266x2 = 533 = DDR4264?) выдает 3400 и 1400 mb/s соответственно.

 

Алгоритм копирования dword'ами, идеальный результат 484мс / 10 итераций по 64Мб = 1322Mb/s. Максимально достижимый наверное порядка 1490Мб/с (в память ведь можно обращаться последовательно). Интересно что полученый результат даже быстрее memread - prefetch/no prefetch (на момент сравнения 1062/1267 Mb/s). Попытаюсь дальше оптимизировать цикл, ведь используется только 4К кеша L1.



_1868397330__fscanfrm.zip

 

alpet >

Ну дык пускай выставляет, они же не используются, да ещё модифицируются следующим test.





>

Мдя.. что-то я начал в этом тесте сомневаться. Дело в том, что я попробовал совсем выкинуть префетч, и это странным образом повлияло на результат Точнее он не изменился.. Более странно то, что раньше как раз результаты менялись Прям тёмные силы электричества какие-то, наверно ея тоже что-то в БИОСе включил





Да, и вот ещё: копирование памяти (с чего всё начиналось): http://www.wasm.ru/forum/index.php?action=vthread&forum=17&topic=5049&page=1#6



Надо заметить, что в этом случае bandwidth считается как сумма чтение + запись, т.к. при копировании операций с памятью в 2 раза больше происходит.

 

Забыл аттач

_756072688__read.zip