cresta > На Атлоне это получается 53 тика Вот видишь, значит Атлон тоже не "любит" shld. У каждого семейства свои прибамбасы. Поэтому чтобы не нарваться на проблемы, лучше избегать "тяжелых" инструкций, и поэтому же "туповатые" варианты часто показывают пусть не выдающиеся, но зато и не худшие результаты, приемлемые на всех популярных семействах. А вот твой второй вариант выглядит просто рекламной издевкой над "отстойными пеньками" Тебе удалось наступить на больные мозоли сразу и PIII и P4. Для PIII это известная проблема c partial register stall - почитай А.Фога, у него все варианты на примерах показаны, когда можно и когда нельзя (не нужно) оперировать раздельно с al и eax. А суть такова: в PIII для результата записи в al отводится отдельный temp-регистр и старшая часть eax в него не копируется, а когда вслед за add al идет shl eax проц начинает страшно материться на "нерадивых программеров" и лихорадочно комбинировать результаты из старого eax и нового al. В P4 интелы устранили эту проблему, но взамен добавили новую (но менее катастрофичную) - операции типа add al,dh со старшим и младшим байтами регистра требуют дополнительной микрооперации сдвига dh под al (в P6 это было реализовано аппаратно). Это то ладно, да вот в первых моделях P4 (< 3) еще и на сдвигах и bswap сэкономили (на блоке MMX_SHIFT реализовали) - сдвиги по 4 такта, bswap около 7. Поэтому shl eax,1 всегда следует заменять на add eax,eax (на P4 даже shl eax,4 может работать медленее чем сложения, но для других семейств это конечно будет проигрыш). Ну а bswap нужно просто избегать, как и shld (14 тактов на P4 моделей < 3). Вот такие дела... Ну а элементарные сложения\вычитания\логика везде быстрые, поэтому тупые алгоритмы и рулят с неплохой скоростью на всех процах PS: А еще P4 страшно не любит частичные установки флагов, например CLC\STC\CMC ~10 тактов, CLD\STD вообще не меряно, про inc и так все знают. Поэтому цепочка cmc+inc+rcl на P4 должна показать выдающиеся результаты PPS: да вообще-то "ниче" - всего 196 тиков, как и второй вариант cresta Вывод - пеньки это отстой, особенно если их провоцировать и наступать на больные места )
leo Так pentium получается вообще ничего не любит Куда не сунься - везде мозоли Это что ж, реально у программера остается пара десятков инструкций, которые не страдают недостатками ?
С умножением на PIII оптимальный вариант такой ~32 (imul минимум 4 такта * 8 проходов = 32) Код (Text): bin2hex: lea edx,[eax+32] mov ecx,-32 align 16 @@: imul ebx,[edx+ecx],0x80402010 sub ebx,0x10000000 ; или dec eax после shld shld eax,ebx,4 add ecx,4 jnz @b Но другим он тогда не понравится хотя у них и частота намного выше, по веремени может одинаково оказатся
Выкинули половину умножений и развернули, плюс ebx освободился, много инструкций можно заменить на другие, например с "shld edx,ecx,8" у меня ~25 (а так ~30 и на P4 ~48) Код (Text): bin2hex: xor edx,edx mov ecx,[eax+4*0] lea ecx,[ecx*8] add ecx,ecx add ecx,[eax+4*1] sub ecx,0x33333330 imul ecx,0x08040201 and ecx,0xFF000000 add edx,ecx mov ecx,[eax+4*2] lea ecx,[ecx*8] add ecx,ecx add ecx,[eax+4*3] sub ecx,0x33333330 imul ecx,0x08040201 and ecx,0xFF000000 shr ecx,8 add edx,ecx mov ecx,[eax+4*4] lea ecx,[ecx*8] add ecx,ecx add ecx,[eax+4*5] sub ecx,0x33333330 imul ecx,0x08040201 and ecx,0xFF000000 shr ecx,16 add edx,ecx mov ecx,[eax+4*6] lea ecx,[ecx*8] add ecx,ecx add ecx,[eax+4*7] sub ecx,0x33333330 imul ecx,0x08040201 and ecx,0xFF000000 shr ecx,24 lea eax,[edx+ecx]
leo > Ценой лишнего байта, в моём коде можно вынести cmc за цикл, заменив на not eax. rcl на adc наверное нет смысла менять
bogrus К твоему последнему варианту: 1) lea ecx,[ecx*8] + add ecx,ecx можно заменить на shl ecx,4 т.к. на P4 lea с масштабированием не оптимизирована и все равно выполняется как shl 2) если все таки обрабатывать с конца строки, то можно сдвигать не ecx, а edx - тогда shr edx,8 частично распараллеливается и на P4 получается чуть быстрее - 44 вместо 48 (сколько реальная прибавка трудно сказать - из-за дискретности м.б. от 1 до 7 )
Если совместить все imul в группу, они будут выполняться примерно за 10-12 тиков, а не за 20 (AMD AthlonXP). Вот код примерно на 37 тиков: Код (Text): push eax push ebx push ecx push edx push esi lea esi, bintext mov eax, [esi + 4 * 0] // 0x31313131 mov ecx, [esi + 4 * 2] mov edx, [esi + 4 * 4] // m.b. bank conflict mov ebx, [esi + 4 * 6] shl eax, 4 // 0x13131310 shl ecx, 4 shl edx, 4 shl ebx, 4 add eax, [esi + 4 * 1] // 0x43434341 (src=0x30303030) add edx, [esi + 4 * 3] add ecx, [esi + 4 * 5] add ebx, [esi + 4 * 7] sub eax, 0x33333330 // 0x10101010 sub edx, 0x33333330 sub ecx, 0x33333330 sub ebx, 0x33333330 imul eax, 0x08040201 // 8 тетрад - в 8 бит, за 5 тиков imul ecx, 0x08040201 imul edx, 0x08040201 imul ebx, 0x08040201 and eax, 0xFF000000 and ecx, 0xFF000000 and edx, 0xFF000000 // ebx no needs masking shr ecx, 8 shr edx, 16 shr ebx, 24 add edx, eax add ebx, ecx lea eax, [edx + ebx] pop esi pop edx pop ecx pop ebx pop eax
В принципе на пеньках рулит переименование регистров, т.е. когда мы пишим в любой РОН, то результату на самом деле назначается каждый раз новый временный регистр (которых более 40), в этих алгоритмаx 4 обработки не зависимы от друг друга и могут выполнятся не дожидаясь предыдущих (перегруппировка мопов), зависимость есть только по формированию результата ("add edx,reg" будет выполнятся в последнюю очередь что с группировкой imul, что без, т.ч. из-за push\pop это будет чуть медленнее, на PIII так точно) За другие камни не скажу, а у себя чуть ускорял заменив сдвиг и вычитание этим: Код (Text): mov ecx,[eax+4*0] add ecx,ecx lea ecx,[ecx*8-0x33333330] add ecx,[eax+4*1] А xor edx,edx на imul edx,ecx,0x08040201 з.ы. может покрутим теперь в обратную сторону (hex_dword > bin_str32) , вот тупой вариант: Код (Text): ;========================================= mov eax,0x87654321 mov edi,bin_str ;========================================= hex2bin: lea edi,[edi+32] mov ecx,-32 align 16 @@: add eax,eax mov dl,0 adc dl,0x30 mov byte[edi+ecx],dl add eax,eax mov dl,0 adc dl,0x30 mov byte[edi+ecx+1],dl add eax,eax mov dl,0 adc dl,0x30 mov byte[edi+ecx+2],dl add eax,eax mov dl,0 adc dl,0x30 mov byte[edi+ecx+3],dl add ecx,4 jnz @b ;=========================================
Во всяком случае эмулятор конвеера AthlonXP (CodeAnalyst) очень хорошо показывает, что явной зависимостью лучше не баловаться. Группировка imul дает прирост за счет того что dpi этой инструкции в группе все 2 тика, а не 5 когда она находится среди более быстрых операций. Я сейчас алгоритм оптимизирую - поиск всех вхождений байтовых значений в некоторую область памяти с результатами в виде набора множеств. Там тоже приходится делать упаковку результатов команды pcmpeqb (MMX). Поскольку алгоритмы похожие его в конце-концов и для этой задачи можно будет применить наверное. Хотя и не ясно зачем ее так предельно оптимизировать - гигабайты бинарных текстов что-ли лопатить?
bogrus На Атлоне это 68 тиков (hex2bin). Вот вариант, дающий на Атлоне 46 тиков: Код (Text): hex2bin: mov edx,eax shr edx,28 imul edx,204081h and edx,01010101h add edx,30303030h bswap edx mov [edi],edx mov edx,eax shr edx,24 and edx,0Fh imul edx,204081h and edx,01010101h add edx,30303030h bswap edx mov [edi+4],edx mov edx,eax shr edx,20 and edx,0Fh imul edx,204081h and edx,01010101h add edx,30303030h bswap edx mov [edi+8],edx mov edx,eax shr edx,16 and edx,0Fh imul edx,204081h and edx,01010101h add edx,30303030h bswap edx mov [edi+12],edx mov edx,eax shr edx,12 and edx,0Fh imul edx,204081h and edx,01010101h add edx,30303030h bswap edx mov [edi+16],edx mov edx,eax shr edx,8 and edx,0Fh imul edx,204081h and edx,01010101h add edx,30303030h bswap edx mov [edi+20],edx mov edx,eax shr edx,4 and edx,0Fh imul edx,204081h and edx,01010101h add edx,30303030h bswap edx mov [edi+24],edx and eax,0Fh imul eax,204081h and eax,01010101h add eax,30303030h bswap eax mov [edi+28],eax Тут bswap всё портит Без него получается вообще 28 тиков. Правда строка задом наперед получается. Надо как-то без bswap'а сделать. А пока ждем captain cobalt'a с картинкой
Цель не имеет задачи, просто дело было вечером, делать было нечего (такое редко, но случается), это как в DOOM играть, борьба за такты Ну может кому-то понадобится и такое, тогда лучше пересмотреть варианты на предмет использования таблицы и держать её в L1 cresta О, это уже гуд, на PIII ~40 вместо ~96, а я думал на что надо умножить чтоб получить обратное, captain cobalt'а можно уже не звать
Да вот же, одно число нашёл, чтобы разбросать биты по байтам - 204081h, а сейчас голова пухнет про другое число - может есть такое, чтобы байты разворачивало P.S. Пардон. Последний bswap в коде был для edx, естественно, нужно bswap eax. В коде уже исправил.
cresta Можно bswap (для бит полубайтов) сделать один раз, в самом начале попробуй вставить это, правда у меня особого выиграша не получилось, но на P4\Athlon'е кто знает ... Код (Text): mov ecx,eax and eax,0x11111111 shl eax,3 mov edx,ecx and edx,0x22222222 add edx,edx or eax,edx mov edx,ecx and edx,0x44444444 shr edx,1 or eax,edx mov edx,ecx and edx,0x88888888 shr edx,3 or eax,edx
bogrus, на атлоне это хуже чем bswap - получилось 52 тика. Видимо, атлон меньше нервничает из-за bswap.
Табличное преобразование hex2bin. По моим прикидкам около 35 тиков. Код (Text): char* tetrs = "0000000100100011010001010110011110001001101010111100110111101111"; _asm { push eax push ebx push ecx push edx push esi push edi mov esi, tetrs // table lea edi, bintext // result mov eax, 1111000010011011b // Example (debug) mov edx, eax mov ebx, eax shr edx, 18h shr ebx, 1Ch and edx, 15 and ebx, 15 mov ecx, [esi + ebx * 4] mov [edi + 00h], ecx mov ecx, [esi + edx * 4] mov [edi + 04h], ecx mov edx, eax mov ebx, eax shr edx, 10h shr ebx, 14h and edx, 15 and ebx, 15 mov ecx, [esi + ebx * 4] mov [edi + 08h], ecx mov ecx, [esi + edx * 4] mov [edi + 0Ch], ecx mov edx, eax mov ebx, eax shr edx, 08h shr ebx, 0Ch and edx, 15 and ebx, 15 mov ecx, [esi + ebx * 4] mov [edi + 10h], ecx mov ecx, [esi + edx * 4] mov [edi + 14h], ecx mov edx, eax shr eax, 4 and edx, 15 and eax, 15 mov ecx, [esi + eax * 4] mov [edi + 18h], ecx mov ecx, [esi + edx * 4] mov [edi + 1Ch], ecx pop edi pop esi pop edx pop ecx pop ebx pop eax }
cresta > "может есть такое, чтобы байты разворачивало" Конечно, запиши в обратном порядке - получишь разворот Код (Text): ;в eax 4 значащих бита imul eax,08040201h shr eax,3 and eax,01010101h or eax 30303030h
leo Этот вариант может на Pentium сработает, но на Атлоне это тоже медленее, чем с bswap - 50 тиков против 46.
cresta А ты еще считаешь пеньки капризными Кол-во инструкций одинаково, зависимость по данным одна и та же, так неужели на Атлоне популярная shr медленнее сравнительно редкой bswap ?! Или прибамбасы с декодером как в PIII ? Вопрос ес-но риторический
