alpet > „Насчет "shl eax, 12" правильно“

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

  xor           eax, eax
  xor           ecx, ecx
  xor           edx, edx
  xor           ebx, ebx
;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  cmp           dword ptr [esi], esp
  sete          al
  add           ebx, eax
  shl           ebx, 2

  cmp           dword ptr [esi + 1], esp
  sete          cl
  add           edx, ecx
  shl           edx, 2

Да, ещё

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

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


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

В принципе, указатели тоже можно "сжимать" каким-нибудь RLE. (это ещё и упростит анализ совпадений WORD & DWORD)
Можно использовать факт, что в win32 старший бит адреса всегда == 0 :-)
Например, если этот бит == 1, то следом идёт DWORD - количество последовательных совпадений.

S_T_A_S_>
„... параллелить не на 4х регистрах, а на 2х...“
Это скорее всего повредит, т.к в каждом куске явная зависимость от операндов, и соответсвенно кол-во регистров роли не играет, надо проверить. На Celerone, параллелить хорошо 3-4 регистра, на сколько хватит, а на Athlone и P4HT еще не пробывал, но наверное не более 4.
-------------------------------------------------------
Насчет сжатия, IMHO множества еще лучше сжимаются RLE, если в каждом 16 или 32 значения.

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

cmp    dword ptr [esi + 1], esp
sete   al
cmp    dword ptr [esi + 2], esp
sete   bl
or     ah, al
cmp    dword ptr [esi + 3], esp
set    cl
or     bh, bl
cmp    dword ptr [esi + 4], esp
sete   cl
shl    eax, 4
cmp    dword ptr [esi + 5], esp
sete   cl
shl    ebx, 4
 ... и т.д.

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

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

Регистр 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 - ни какой разницы с циклом.

> „У кода состоящего из одних test ebx, [esi + ecx] тратилось 43,8ms на 64mb, а у кода с eax, edx, ebx - 37,5.“

Это 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 мне еще не все понятно, эта инструкция флажки выставляет, а значит процессор может все последующие попридержать“

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


> „Новый memread показал результаты unrolled prefetch 3080Mb/s и prefetch 1334.“

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


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

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

Забыл аттач :(

_756072688__read.zip

S_T_A_S_>
Скорости нового memread2 unrolled:2560 и prefetch: 1084

Что касается memcopy2, на Athlone пока проверить не могу, на Celeron результаты не плохие: 1279Мб/c MMX optimized x 16Mb. Тем не менее проигрывает. Копирование DWORD'ами отстает в 2 раза. Скоро попробую на Athlon 2000XP + 512DDR333 обе проги. Меня заинтересовал результат 1821Мб, это реально! На какой памяти не скажешь?

См. аттач memcopy в действии.

_38519057__memcopy.jpg

S_T_A_S_ можешь для сравнения в memcopy мой код копирования перенести? Я надеюсь адреса источника/приемника выровнены по кэш линейкам, иначе максимум небудет показан.

Да и ещё :-) я тут пару раз упоминал одну доку, но ссылу оказывается так и не дал =)

Добавил код для сравнения :-)
Сначала получились просто сказачные результаты, ~2500Mb/sec, но здраво рассудив, что это не реально на моей машине, нашёл пару мелких и один баг по-больше ;-)
Теперь больше похоже на правду - MOVNTQ не обгонишь, т.к. эта команда работает в обход кеша.

---------------------------
  memcopy benchmark by S.T.A.S.
---------------------------
CPU AuthenticAMD @ 1664 MHz
Test results:

copy method    bytes to copy / bandwidth
		16,0 Mb		1,0 Mb		64 Kb

fscanfrm.zip:	707 Mb/sec	672 Mb/sec	522 Mb/sec
mov w/GPRs:	739 Mb/sec	712 Mb/sec  572 Mb/sec
mmx (8*qwords):	784 Mb/sec	751 Mb/sec	584 Mb/sec
mmx/movntq:	1160 Mb/sec	1009 Mb/sec	755 Mb/sec
optimized mmx:	1859 Mb/sec	1416 Mb/sec	n/a

---------------------------
ОК   
---------------------------

ЗЫ
Память 266MHz и 333MHz - разницы практически нет, т.к. шина FSB ==266MHz

ЗЫЫ
С MessageBox можно копировать Ctrl+V (gj краёней мере в XP)

1729394837__memcopy2.zip

Показывает 615 Mb/s . Надо посмотреть отладчиком адреса источника-назначения, если не кратны 32, проблема в известном месте.

205385691__mcpy2.jpg