Собственно $subj В самом простом случае это может быть сделано следующим образом: Код (Text): mov esi,[ebx]Context.SrcBufferRdPtr mov ecx,[ebx]Context.SrcBufferSize BuildFreqTable: movzx eax,byte ptr [esi] add dword ptr [ebx]Context.FreqTable[4 * eax],1 add esi,1 sub ecx,1 jnz BuildFreqTable Приведенный цикл "стоит" в районе 5 тактов на каждый входной байт. Разворачивание цикла не изменяет его производительность. То же самое с перестановкой операндов, использованием нескольких регистров и т.д.
Я примерно 0,5-0,6 такта выиграл. Было 4,2 стало 3,7. Выиграш заметин только в том случае если N таково, что массив полностью поподает в кэш первого уровня. Код (Text): mov esi,offset a mov ecx,N/4 xor edx,edx mov eax, [esi] @BuildFreqTable: mov dl,al add dword ptr [table+4 * edx],1 mov dl,ah add dword ptr [table+4 * edx],1 shr eax,16 mov dl,al add dword ptr [table+4 * edx],1 mov dl,ah add dword ptr [table+4 * edx],1 add esi,4 mov eax, [esi] sub ecx,1 jnz @BuildFreqTable
А на какой входной последовательности меряем ? Возьмите регулярную последовательность 0, X, 2*X, 3*X ... и посмотрите, что будет при разных X. Например, на P4 при X=2 (+-1) простой разворот цикла на 2 дает заветные 3-3.5 тика, а вот при других X он ничего не дает - либо теже 4-6 тиков либо тормоза до 12-16 тиков. Вариант Pavia с загрузкой дворда принципиально ситуацию не меняет (при X=2 на Pentium D получается менее 3-х тиков, а при других X такие же тормоза). Вот это действительно грабли, которые в общем случае не обойдешь ( А связано это видимо с конфликтом банков L1. О наличи такой проблемы в P4 Intel вроде как умалчивает, но в P6 и AMD такая проблема есть, и P4 врядли является исключением. Суть в том, что все эти процы деклалрируют возможность одновременного выполнения операций записи и чтения в L1 (dual ported cache), но на деле это возможно только в случае, когда запись и чтение направлены в разные банки. Интерлив адресации банков обычно расчитан на последовательное чтение\запись с учетом того, что реальная запись в L1 происходит только после отставки mov m,r т.е. значительно позднее ее исполнения, поэтому при последовательном копировании обычно тормозов не возникает. А в случае с гистограммой, адреса записи определяются входными данными, поэтому возможны ситуации когда очередной load попадает в тот же банк, что и давно ожидающий store, и поэтому проц задерживает load на несколько тактов пока не выполнится store (причем если входные значения идут в регулярном порядке, то и такие ситуации возникают регулярно). Такие ситуации возможны и в P6 и AMD, но в P4 эти конфликты могут усугубляться реплеем, и как с эти бороться фиг его знает - можно только расчитывать на статистику - случайный разброс входных данных, при котором конфликты банков будут возникать не часто. PS. Кроме конфликта банков, в P4 в принципе возможны прибамбасы со store-to-load forwarding, когда на близком расстоянии производятся чтение-запись в одну и ту же ячейку гистограммы (последующий load может опережать предыдущий store)
Естественно, входные данные являются случайными - просто бинарный поток на сжатие. В текущей реализации счетчики являются двордами, однако переход на ворды так же ничего не дал. Да, вопрос с конфликтом по чтению/записи в L1 кэш мне в голову не приходил Похоже, моих 5 тактов на входной байт являются закономерным результатом в текущей реализации процессора. P.S. В железе гистограмму считать гораздо проще В нашем случае это заняло всего один такт на входной байт
