cresta Доделать может не проблема, но как ты предлагаешь обрабатывать ситуацию при передаче указателя на строку 0x00401FFE db "1",0 (страницы 0x00402000 нет), двордом тут не прочитаешь ... Них... себе ~190 на атлоне с 3-мя то alu! против ~16\~32 с 2-мя на пне3\4
Вариант с табличкой. 40 тиков на одной и той же строке, и порядка 60 для 4 приведенных. Ввиду большой латентности и большого размера таблички (232 байта), алгоритм пригоден только для массовой конвертации строк. Тестирование проводил на iCel4 @2400. Код (Text): <font face="fixedsys] <font size=1> char* hdig [4] = { "12340AB", "ADD50503", "Ed1Ad114", "abcdef1" }; // 0xF, 0x4F DWORD hash [0x3A]; memset (hash, 0, sizeof (hash)); for (int x = 0x31; x < 0x39; x ++) hash [x] = x & 0x0F; for (int x = 0x41; x < 0x47; x ++) hash [x & 0x3F] = (x & 0x0F) + 0x09; for (int x = 0x61; x < 0x67; x ++) hash [x & 0x3F] = (x & 0x0F) + 0x09; for (int a = 10000000; a--;) _asm { push eax push ebx push ecx push edx // push esi push edi mov eax, [a] and eax, 3 mov edi, [hdig + eax * 4] xor eax, eax xor ecx, ecx xor edx, edx xloop: shl eax, 8 movzx ebx, byte ptr [edi] and ebx, 03Fh or eax, dword ptr [hash + ebx * 4] cmp byte ptr [edi + 1], 30h jb lbreak ;; 2 shl edx, 8 movzx ebx, byte ptr [edi + 1] and ebx, 03Fh or edx, dword ptr [hash + ebx * 4] cmp byte ptr [edi + 2], 30h jb lbreak ;; 3 shl eax, 8 movzx ebx, byte ptr [edi + 2] and ebx, 03Fh or eax, dword ptr [hash + ebx * 4] cmp byte ptr [edi + 3], 30h jb lbreak ;; 4 shl edx, 8 movzx ebx, byte ptr [edi + 3] and ebx, 03Fh add edi, 4 or edx, dword ptr [hash + ebx * 4] cmp byte ptr [edi], 30h jnb xloop shl eax, 4 jmp complete lbreak: shl edx, 4 complete: or eax, edx pop edi //pop esi pop edx pop ecx pop ebx pop eax } </font><!--size--></font><!--face-->
leo Нет сотен тиков загрузки из озу, результаты практически те же, что и с разносом 8 байт. Пробовал и по одной процедуре за 1 запуск программы выполнять - ничего не меняется, после одной процедуры перед выполнением другой производится довольно большое количество разных действий, вытесняющих и код, и данные из кэша, тут беспокоится нечего, последующий тест опять с нуля начинает. Ещё и wintest'ом проверил - цифры другие, пропорции те же. bogrus Это на 8 строк 190 А вот быстро положить строку на маску нулей не получается С генерацией строки таким способом получаются примерно те же цифры, что и для других алгоритмов. alpet А почему табличка 232, а не 220 байт? Если таблицу не двордов, а байт сделать, не пробовал?
cresta 1. Максимальное значение с учетом маскировки - 39h, соответственно табличка - 3Ah * 4 = 0E8h, что вроде равно 232. Впрочем если маскировать по 1Fh (блин, как я сразу не догадался - символы \x30..\x39 попадают в диапазон 10h..19h, а буквы соответственно в 01h..06h), то табличка получается небольшой - 1Ah * 4 = 68h байт, или до 4-х кэш-линеек по 32 байта. Скорость кстати возросла до 48 тиков для меняющихся строк. 2. Пробовал - практически особой разницы не заметил (не намного медленнее), но имхо не стоит - в таких делах конфликт банков обойдется дороже чем память, плюс еще может пенальти быть по partial stall.
По типу buliaNaza, но без sbb (~60 на п3) Код (Text): mov esi,buffer ;=================================== h2d: xor eax,eax xor ecx,ecx @@: movzx edx,byte[esi] shl eax,4 and ecx,0x0F shr edx,6 add eax,ecx movzx ecx,byte[esi] lea edx,[edx*8+edx] add ecx,edx lea esi,[esi+1] jnz @b ;===================================
bogrus Не работает. Результат выдает неверный. И очень долго - более 2000 тактов на 8 строк. Вот вариант с таблицей: таблица маленькая - 55 байт, и процедура тоже маленькая. Код (Text): h_tbl db 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0, 0 db 0,10,11,12,13,14,15, 0, 0, 0, 0, 0, 0, 0, 0, 0 db 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 db 0,10,11,12,13,14,15 mov edx,[esp+4] xor eax,eax xor ecx,ecx jmp _st _add: movzx ecx,byte ptr[offset h_tbl+ecx] shl eax,4 inc edx add eax,ecx _st:movzx ecx,byte ptr[edx] sub ecx,30h jns _add retn 4 376 тиков на 8 строк. Ограничений по регистру букв и длине строки нет.
На том наборе из 8 строк по 7 символов, что предлагал leo На строку "3ccD24c" выдаёт 1521179033, хотя остальные 3 процедуры выдают 63754828. И время 2780 тиков. Чёто там поломаное. Делаю так: Код (Text): push esi mov esi,[esp+4] xor eax,eax xor ecx,ecx @@: movzx edx,byte ptr[esi] shl eax,4 and ecx,0Fh shr edx,6 add eax,ecx movzx ecx,byte ptr[esi] lea edx,[edx*8+edx] add ecx,edx lea esi,[esi+1] jnz @b pop esi retn 4 ;---------------------- push offset h_str1 call h2d
Вот вариант с предыдущей таблицей (55 байт) - ещё короче и ещё быстрее: Код (Text): mov edx,[esp+4] xor eax,eax xor ecx,ecx jmp _st _add: shl eax,4 inc edx or al,byte ptr[offset h_tbl+ecx] _st:movzx ecx,byte ptr[edx] sub ecx,30h jns _add retn 4 На предложенном leo наборе из 8 строк 360 тиков (в среднем 45 тиков). P.S. Если воспользоваться обстоятельством, что jmp _st - безусловный, можно после него воткнуть align 16 и выравнять метку _add. Так ещё быстрее - 340 тиков.
cresta Я б и сам удивился, если вместо ascii2hex получилось ascii2dec , ты поставил "mov esi,[esp+4]" (надо 8)
Народ, хватит esi/edi/ebx использовать ! Такие оплошности из-за этого ) Еще вариант с табличкой + регистр ebx: Код (Text): mov edx,[esp+4] push ebx xor eax,eax jmp _st _add:shl eax,4 add edx,2 or al,byte ptr[offset h_tbl+ecx] shl eax,4 or al,byte ptr[offset h_tbl+ebx] _st: movzx ecx,byte ptr[edx] sub ecx,30h movzx ebx,byte ptr[edx+1] js _end sub ebx,30h jns _add shl eax,4 or al,byte ptr[offset h_tbl+ecx] _end:pop ebx retn 4 266 тиков на 8 проходов. P.S. Забыл: h2d заработала 406 тиков.
Еще один табличный вариант. Порядка 45 тиков / цикл, при тесте в 50 млн. циклов, в случае с одной строкой - 30 тиков. Процессор - iCel@2400. Положительный момент - нет сдвигов, что должно нравится интеловским процессорам (моему домашнему Athlon вроде без разницы). Код (Text): <font face="fixedsys] <font size=1> DWORD hash [0x1A]; char* hdig [4] = { "12340AB", "ADD50503", "Ed1Ad114", "abcdef1" }; const int loops = 50000000; memset (hash, 0, sizeof (hash)); for (int x = 0x30; x < 0x3A; x ++) hash [x & 0x1F] = (x & 0x0F); for (int x = 0x61; x < 0x67; x ++) hash [x & 0x1F] = (x & 0x0F) + 0x09; SetThreadPriority (GetCurrentThread (), THREAD_PRIORITY_HIGHEST); DWORD ticks = 0; nticks = GetTickCount (); __int64 ntc = rdc (); // rdtsc _asm { push eax push ebx mov edi, 0 xor ebx, ebx mov esi, loops ;; loops = 50 millions. neg esi bbtest: push eax mov edx, [hdig + edi * 4] add edi, 1 xor eax, eax and edi, 3 lstart: movzx ebx, word ptr [edx + 0] and ebx, 1Fh jz lbreak movzx ecx, byte ptr [edx + 1] add eax, eax // second half-byte mov ebx, dword ptr [hash + ebx * 4] add edx, 2 lea eax, [ebx + eax * 8] and ecx, 1Fh jz lbreak add eax, eax mov ecx, dword ptr [hash + ecx * 4] lea eax, [ecx + eax * 8] jmp lstart lbreak: pop eax add esi, 1 jnz bbtest pop ebx pop eax } ntc = rdc () - ntc; </font><!--size--></font><!--face--> <font face="arial]<font size=1> На байтовой табличке - скорость падает до 50-55 тиков/цикл, как впрочем и при смешивании кода с 8-битными / 32-битными регистрами. </font><!--size--> </font><!--face-->
cresta [01h..06h] = 10..15 [11h..19h] = 0..9 hash dd 0, 10, 11, 12, 13, 14, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Может зря отказался от расширения таблицы до диапазона маленьких букв? Наверное было бы быстрее. Сейчас показывает 354 тика на 8 строк. И lea разве быстрее получится, чем shl? Кстати, на байтовой таблице не очень много и теряется: 370 тиков (46 на одну строку). P.S. Попробовал для своего последнего варианта двордовую таблицу - с ней хуже, чем с байтовой Стало 280 тиков. Видимо переходы в цикле стали по неоптимальным адресам.
cresta 1. Табличка и так жирная, а без маскировки как ее юзать. 2. Дык я и не пытался ее оптимизировать, надо добраться до Атлона, который к сожалению пока недееспособен. Просто направление - способ показал. С другой стороны твой последний алгоритм дает в среднем 50 тиков, может у нас оценки по разному выставляются. У меня вычисляется через кол-во тактов, за очень большое количество проходов (50 млн.), по 4 строкам. 3. У меня получалось быстрее во всяком случае - на Celeron сдвиг на 4 с сложением так быстрее получается. 4. Но и не много обретается - 1Ah * 4 = 104 байта не так уж и много для хэш-таблички, а вот конфликт банков в этом алгоритме зависит от данных.
Я своей программой меряю время исполнения. Вроде дееспособная, щас засомневался, проверил в wintest'е by A.Fog - 272 тика. Разница есть с 266, почему - хрен знает, но примерно совпадают показания. Надо еще с одной голой процедурой сделать exe, посмотреть.
alpet Я считаю через rdtsc с поправкой на время, необходимое для опроса самого счетчика. Строк - 8 штук, те, что приводил leo, за один замер поочередно преобразуются эти восемь строк по одному разу и тест заканчивается. С другой стороны твой последний алгоритм дает в среднем 50 тиков, может у нас оценки по разному выставляются. Не удивлюсь, если ты меряешь приведенную мною процедуру в виде ассемблерной вставки в сях )). Процедура ведь очень короткая и быстротечная, а обрамление в виде вызова процедуры, передачи данных, формирование стекового фрейма и т.п. занимают много времени. Для примера: вот твоя процедура, вернее то, что от неё осталось. С твоего позволения я её слегка отрихтовал, не меняя логику работы. Код (Text): alpet_proc: mov edx,[esp+4] push ebx xor eax,eax align 16 lstart: movzx ebx, word ptr [edx + 0] movzx ecx, byte ptr [edx + 1] and ebx, 1Fh jz lbreak add eax, eax mov ebx, dword ptr [offset hash + ebx * 4] add edx, 2 lea eax, [ebx + eax * 8] and ecx, 1Fh jz lbreak add eax, eax mov ecx, dword ptr [offset hash + ecx * 4] lea eax, [ecx + eax * 8] jmp lstart lbreak: pop ebx retn 4 В таком виде она выполняется у меня за 294 тика, а было первоначально 354. 60 тиков ушло вместе с мусором ненужных инструкций Тут и сейчас есть, что поковырять. Например, цикл длинный. 14 инструкций. На одну инструкцию уходит с учетом всяких пенальти 2,205 тика. У меня на одну инструкцию уходит больше времени - 2,420 тика. Только цикл у меня из 11 инструкций, поэтому выполняются в сумме более медленные инструкции быстрее: 26,62 на цикл против 30,87. Это объясняет почему быстрее процедура в целом. Естественно, на другом проце и цифры другие, какие не скажу, у меня только Атлон.
Наверное твой алгоритм медленно выполняется у меня из-за того что код в вставке не выравнивается, да и сдвиги у Атлона побыстрее работают. Соберу в скором времени свой Атлон и буду смотреть на нем, без CodeAnalyst здесь сложно. Можно получить весь код теста целиком для FASM?
