Вопрос на скорость кода (Чтоб форум жил!!!) - Низкоуровневое программирование

Здравствуйте Алексей Петров, Вы писали:

АП>Хреново задачу я сформулировал

 .data
  i1 dq 1234567812345678h
  i2 dq 1224567102315670h
.code
    mov eax,dword ptr i1+4
    xor eax,dword ptr i2+4
    xor ecx,ecx
l1:    bswap eax
l2:    ror al,4
    inc ecx
    test al,0Fh
    jz @F
    Invoke OutInt, hWnd, ecx
@@:    inc ecx
    test al,0F0h
    jz @F
    Invoke OutInt, hWnd, ecx
@@:    shr eax,8
    jnz l2
    cmp ecx,16
    je l3
    mov ecx,8
    mov eax,dword ptr i1
    xor eax,dword ptr i2
    jmp l1
l3:

Вместо

Invoke OutInt, hWnd, ecx

поставь чего-нибудь свое. Если не сможешь — скажи.

Здравствуйте Алекс, Вы писали:

К тому-же я просил соссчитать колличество расхождений, а не выдавать их список

Задача соссчитать этим кодом не решается.

Здравствуйте Алексей Петров, Вы писали:

АП>Здравствуйте Алекс, Вы писали:

АП>К тому-же я просил соссчитать колличество расхождений, а не выдавать их список

Задача соссчитать этим кодом не решается.

Как не решается? Ну ты дал, блин! Вместо вызова OutInt поставь

inc miss_count

и все!

Здравствуйте Алексей Петров, Вы писали:

АП>Хреново задачу я сформулировал :crash:

АП>Уточняю:
АП>Каждая цифра одной строки сравнивается с цифрой на той-же позиции другой строки — считаем число расхождений.

АП>пример
АП>1234567 и 1243567 отличаются в 2-х символах (на 3-й и 4-й позиции).

ОК!!!

Сейчас уже ухожу :( , но задачка старая поэтому принесу два варианта.

Здравствуйте Алекс, Вы писали:

А>Здравствуйте Алексей Петров, Вы писали:

АП>>Здравствуйте Алекс, Вы писали:

АП>>К тому-же я просил соссчитать колличество расхождений, а не выдавать их список

Задача соссчитать этим кодом не решается.

А>Как не решается? Ну ты дал, блин! Вместо вызова OutInt поставь
А>

А>inc miss_count
А>

А>и все!

И хочешь сказать, это будет оптимальный вариант по скорости (если убрать ошибку, из за которой оно вообще зацикливается)?
Или просто написал абы как?
Ассемблер есть смысл использовать только тогда, когда уверен, что напишеш лучше компилятора. Твой код слабоват в этом плане, да еще и с ошибками

Здравствуйте Алексей Петров, Вы писали:

[skipped]

АП>И хочешь сказать, это будет оптимальный вариант по скорости (если убрать ошибку, из за которой оно вообще зацикливается)?
АП>Или просто написал абы как?
АП>Ассемблер есть смысл использовать только тогда, когда уверен, что напишеш лучше компилятора. Твой код слабоват в этом плане, да еще и с ошибками

В каком месте зацикливается? У меня все нормально. Приведи свой код. Весь.
Дальше. Я считаю, что мой код оптимален по показателю скорость/размер. Можно написать супер быстрый код, но занимать он будет больше.
Дальше. Никакой компилятор никогда не сгенерит такой код, просто потому что он не человек и творчески подойти к решению задачи не может. Для других задач он предназначен.

Плохо, когда амбиции и самоуверенность превышают возможности

А еще хуже, когда читать не желают некоторые, что другие пишут

Здравствуйте Алекс, Вы писали:

АП>>И хочешь сказать, это будет оптимальный вариант по скорости (если убрать ошибку, из за которой оно вообще зацикливается)?
АП>>Или просто написал абы как?
АП>>Ассемблер есть смысл использовать только тогда, когда уверен, что напишеш лучше компилятора. Твой код слабоват в этом плане, да еще и с ошибками

А>В каком месте зацикливается? У меня все нормально. Приведи свой код. Весь.
Зачем приводить мой код, если ошибка в твоем? Я на твой код внимательно смотрю, а использовать не стану никогда — ибо хреновый он.
А циклится он, например, если сторки совпадут. ecx=16 никогда не настанет — так и будет между 8 и 10 скакать...

А>Дальше. Я считаю, что мой код оптимален по показателю скорость/размер. Можно написать супер быстрый код, но занимать он будет больше.

Исходная постановка: В первом сообщении "необходима максимально возможная оптимизация скорости выполнения" — т.е. пофигу, сколько он занимать будет. Читать вопрос надо, прежде чем отвечать. К тому же утверждение не верно: есть совершенно не нужные для решения задачи комманды: bswap и mov ecx, 8 —
в первом случаи просто меняется порядок, в котором символы считаем (а от перестановки мест слагамых...)
во втором — в ecx и так 8 на первом проходе внешнего циклаю. А на втором туда поподать мы не должны (хотя и попадаем).

А>Дальше. Никакой компилятор никогда не сгенерит такой код, просто потому что он не человек и творчески подойти к решению задачи не может. Для других задач он предназначен.
Такой — да. Компилятор сгенерит более адекватный.

Смотри:
поручаю VC++ 7 вот такой код:

inline int __fastcall countDiffs(int a, int b)
{
    int Temp = a ^ b;
    int result = 0;
    while (Temp)
    {
        if (Temp & 0xF)
            result ++;
        Temp >>= 4;
    }
    return result;
}

int __fastcall countDiffs(__int64 a, __int64 b)
{ 
    return countDiffs(((int*)&a)[0], ((int*)&b)[0]) + countDiffs(((int*)&a)[1], ((int*)&b)[1]);
}

получается вот такой (при компиляции с оптимизацией под скорость):

  00000    8b 44 24 04     mov     eax, DWORD PTR _a$[esp-4]
  00004    33 44 24 0c     xor     eax, DWORD PTR _b$[esp-4]
  00008    ba 00 00 00 00     mov     edx, 0
  0000d    74 0d         je     SHORT $L1365
  0000f    90         npad     1
$L1364:
  00010    a8 0f         test     al, 15            ; 0000000fH
  00012    74 01         je     SHORT $L1366
  00014    42         inc     edx
$L1366:
  00015    c1 f8 04     sar     eax, 4
  00018    85 c0         test     eax, eax
  0001a    75 f4         jne     SHORT $L1364
$L1365:
  0001c    8b 4c 24 10     mov     ecx, DWORD PTR _b$[esp]
  00020    8b 44 24 08     mov     eax, DWORD PTR _a$[esp]
  00024    33 c1         xor     eax, ecx
  00026    b9 00 00 00 00     mov     ecx, 0
  0002b    74 0f         je     SHORT $L1380
  0002d    8d 49 00     npad     3
$L1372:
  00030    a8 0f         test     al, 15            ; 0000000fH
  00032    74 01         je     SHORT $L1374
  00034    41         inc     ecx
$L1374:
  00035    c1 f8 04     sar     eax, 4
  00038    85 c0         test     eax, eax
  0003a    75 f4         jne     SHORT $L1372
$L1380:
  0003c    8d 04 11     lea     eax, DWORD PTR [ecx+edx]
  0003f    c2 10 00     ret     16            ; 00000010H

посчитай такты, please, и сравни со своим решением (после исправления ошибки, естественно)

Конечно решение VC не оптимально и может быть еще на пару тактов улучшено, но он, зато, учитывает особенности поведения процессора при jmp на адрес, не выравненный на DWORD — что экономит по 1 такту на каждом jmp.

> Mr-Twister
Зачем за неверный код хорошую отметку поставил? ИМХО, этот код скорее "0" заслуживает.

Здравствуйте Алексей Петров, Вы писали:

[проигнорированно]

АП>Конечно решение VC не оптимально и может быть еще на пару тактов улучшено, но он, зато, учитывает особенности поведения процессора при jmp на адрес, не выравненный на DWORD — что экономит по 1 такту на каждом jmp.

Человек это с трудом может закодировать — нужно знать длину каждой команды.

>> Mr-Twister
АП>Зачем за неверный код хорошую отметку поставил? ИМХО, этот код скорее "0" заслуживает.

Ну так надо было поставить! Большого ума не надо написать на сях и показать всему миру его дизасемблированный код.
Что касается бага — действительно был и по фиксен.

    xor ebx,ebx
    xor ecx,ecx
    mov eax,dword ptr i1+4
    xor eax,dword ptr i2+4
    jnz l1    
l4:    inc ecx
    mov eax,dword ptr i1
    xor eax,dword ptr i2
    jz l3
l1:    bswap eax
l2:    ror al,4
    test al,0Fh
    jz @F
    inc ebx
@@:    test al,0F0h
    jz @F
    inc ebx
@@:    shr eax,8
    jnz l2
       jcxz l4
l3:

Размер кода 0x36. Даже учитывая 4 байта на выравнивание и 3 байта на возврат из процедуры, все равно получается у тебя больше. К тому же мой код может легко учитывать позицию отличных "символов". А ты сделай то же на С (если сам на асме не можешь) и посмотрим кто кого!

Здравствуйте Алекс.

я писал:
АП> Исходная постановка: В первом сообщении "необходима максимально возможная оптимизация АП> скорости выполнения" — т.е. пофигу, сколько он занимать будет.

а ты отвечаешь:
А>Размер кода 0x36. Даже учитывая 4 байта на выравнивание и 3 байта на возврат из процедуры, все равно получается у тебя больше. К тому же мой код может легко учитывать позицию отличных "символов". А ты сделай то же на С (если сам на асме не можешь) и посмотрим кто кого!
Мне не надо считать позиции. Есть конкретная задача — максимально быстро посчитать число различий. Ты её решить лучше VC не можешь — твой код медленнее. Вместо этого начинаешь разглагольствовать не по теме.

АП>>Конечно решение VC не оптимально и может быть еще на пару тактов улучшено, но он, зато, учитывает особенности поведения процессора при jmp на адрес, не выравненный на DWORD — что экономит по 1 такту на каждом jmp.

А>Человек это с трудом может закодировать — нужно знать длину каждой команды.
Понятно, что с трудом. Но это как раз аргумент против чрезмерного увлечения асм-ом. Asm полезен для оптимизации по скорости критичных участков. Но неумелое его применение (как в твоем случаи) приводит к замедлению.

А вопрос "кто кого" в рамках исходной постановки задачи — не в твою пользу пока. Посчитай такты сам.

А свое решение (на asm) я завтра приведу. Сегодня домой пора уже.

Здравствуйте Алексей Петров, Вы писали:

АП>т.е. пофигу, сколько он занимать будет.

А когда скорость будет одинаковой будет уже не пофигу.

АП>Понятно, что с трудом. Но это как раз аргумент против чрезмерного увлечения асм-ом. Asm полезен для оптимизации по скорости критичных участков. Но неумелое его применение (как в твоем случаи) приводит к замедлению.

???
Это в каком месте не умелое? Ниже лежит код, приведи пожалуйста строчки, которые можно улучшить.

АП>А свое решение (на asm) я завтра приведу. Сегодня домой пора уже.

Мне не лень расставить nop, это во первых, во-вторых никакой компилятор не сгенерит код лучше чем опытный программер. Я, конечно, не могу сказать, что я уж супер опытный, но исходный код уж сгенерю получше чем MSVC. Вот версия совсем легкая, без наворотов и с выровненными по dword адресами переходов.

    xor ecx,ecx
    mov eax,dword ptr i1+4
    xor eax,dword ptr i2+4
    jnz l1    
    nop
    nop
    nop
l4:    
    inc ecx
    mov eax,dword ptr i1
    xor eax,dword ptr i2
    jz l3
    nop
    nop
l1:    
    test al,0Fh
    jz @F
    inc ebx
    nop
    nop
    nop
@@:
    shr eax,4
    jnz l1
    jcxz l4
l3:

Тут я не учитывал, чего на каком конвеере исполнияется, да и программка по подсчету тактов куда-то делась. Код занимает 0х32 против твоих 0х42.

Здравствуйте Алексей Петров, Вы писали:

АП>Хреново задачу я сформулировал

АП>Уточняю:
АП>Каждая цифра одной строки сравнивается с цифрой на той-же позиции другой строки — считаем число расхождений.

АП>пример
АП>1234567 и 1243567 отличаются в 2-х символах (на 3-й и 4-й позиции).

Два вопроса, имеющих отношение к постаноке задачи:
1) Какова вероятность обнаружения несоотвествия двух цифр (оценочно)? ( Вероятно несовпадений мало, иначе просили бы подсчитать совпадения? )
2) Есть ли кореляции между несовпадающими символами? (т.е. какова вероятность встретить несовпадающею пару, если предыдущая пара цифр — несовпадающая)?

P.S. Это не обработчик аналогового сигнала?

Здравствуйте All

Код не очень оптимизирован, но уже поздно и голова не варит, длину строк принимаю по 64, результат в конце в ebx, если я, конечно, условие правильно понял

eq1 dq 0101010101010101h
wh dq 0

    mov esi, offset str1
    mov edi, offset str2
    mov ecx, 64
    shr ecx, 3
@@1:
    movq mm0, [esi]
    movq mm1, [edi]
    pcmpeqb mm0,mm1
    paddb mm0, eq1

    movq wh, mm0

    push ecx
    mov ecx, 4
    mov eax, dword ptr [wh]
    mov edx, dword ptr [wh+4]
@@2:
    test al, al
    jz @@not0eax
    inc ebx
@@not0eax:
    shr eax, 8
    test dl, dl
    jz @@not0edx
    inc ebx
@@not0edx:
    shr edx, 8
    dec ecx
    jnz @@2
    pop ecx
    add esi, 8
    add edi, 8
    dec ecx
    jnz @@1
; здесь уже готов результат
    emms

Здравствуйте Chorkov, Вы писали:

C>Здравствуйте Алексей Петров, Вы писали:

АП>>Хреново задачу я сформулировал

АП>>Уточняю:
АП>>Каждая цифра одной строки сравнивается с цифрой на той-же позиции другой строки — считаем число расхождений.

АП>>пример
АП>>1234567 и 1243567 отличаются в 2-х символах (на 3-й и 4-й позиции).

C>Два вопроса, имеющих отношение к постаноке задачи:
C>1) Какова вероятность обнаружения несоотвествия двух цифр (оценочно)? ( Вероятно несовпадений мало, иначе просили бы подсчитать совпадения? )
C>2) Есть ли кореляции между несовпадающими символами? (т.е. какова вероятность встретить несовпадающею пару, если предыдущая пара цифр — несовпадающая)?

C>P.S. Это не обработчик аналогового сигнала?

Это не обработчик аналогового сигнала. Исходные строки можно считать почти случайными.

Здравствуйте Алекс, Вы писали:

А>Здравствуйте Алексей Петров, Вы писали:

АП>>т.е. пофигу, сколько он занимать будет.
А>А когда скорость будет одинаковой будет уже не пофигу.
Все равно пофигу. Мне не нужно выпендриваться размером программы — это болезнь начинающих.

АП>>Понятно, что с трудом. Но это как раз аргумент против чрезмерного увлечения асм-ом. Asm полезен для оптимизации по скорости критичных участков. Но неумелое его применение (как в твоем случаи) приводит к замедлению.

А>???
А>Это в каком месте не умелое? Ниже лежит код, приведи пожалуйста строчки, которые можно улучшить.
ОК. Чисто по коду:
1) 3 однобайтных nop выполняются за 3 такта. MSVC++ генерит в таком случаи 1 3-х байтный.
2) Инструкция jcxz выполняется дольше, чем test cx,0; jz — MSVC++ об этом знает, ты — нет.

А>Мне не лень расставить nop, это во первых, во-вторых никакой компилятор не сгенерит код лучше чем опытный программер. Я, конечно, не могу сказать, что я уж супер опытный, но исходный код уж сгенерю получше чем MSVC.
Опытный — согласен, при желании сгенерит и лучше, но станет этим заниматься только на очень критичной по времени функции и тогда, когда на ЯВУ мысли выразить сложнее, чем на asm. В остальных случаях дополнительные затраты времени и сил на asm не окупаются. Но ты еще до того не дорос — твой код хуже, чем у MSVC (см. выше).
И причем в столь малом объеме кода ты не смог с первого раза не сделать ошибки. А текущий вариант я и проверять не стал.
Итог: рано тебе на асм-е писать. По крайней мере что-то серьезное.

А>Вот версия совсем легкая, без наворотов и с выровненными по dword адресами переходов.
А>

А>    xor ecx,ecx
А>    mov eax,dword ptr i1+4
А>    xor eax,dword ptr i2+4
А>    jnz l1    
А>    nop
А>    nop
А>    nop
А>l4:    
А>    inc ecx
А>    mov eax,dword ptr i1
А>    xor eax,dword ptr i2
А>    jz l3
А>    nop
А>    nop
А>l1:    
А>    test al,0Fh
А>    jz @F
А>    inc ebx
А>    nop
А>    nop
А>    nop
А>@@:
А>    shr eax,4
А>    jnz l1
А>    jcxz l4
А>l3:
А>

А>Тут я не учитывал, чего на каком конвеере исполнияется, да и программка по подсчету тактов куда-то делась. Код занимает 0х32 против твоих 0х42.

Ок. Лови мой вариант (я еще над алгоритмом немного подумал, а не пытался работать чисто компилятором:

Оптимизация на скорость (ты такты посчитай а не размер):

        mov  ecx, 0
        mov  edx, dword ptr i1
        xor  edx, dword ptr i2
        mov  eax, edx
        shr  edx, 1
        or   eax, edx
        shr  edx, 1
        or   eax, edx
        shr  edx, 1
        or   eax, edx
        ALIGN 4
@1:
        shr  eax, 1
        adc  cl, 0
        shr  eax, 4
        jnz  @1
        mov  eax, dword ptr i1+4
        xor  eax, dword ptr i2+4
        mov  edx, eax
        shr  edx, 1
        or   eax, edx
        shr  edx, 1
        or   eax, edx
        shr  edx, 1
        or   eax, edx
        ALIGN 4
@2:
        shr  eax, 1
        adc  cl, 0
        shr  eax, 4
        jnz  @2
        ; в cl результат

А размером с тобой меряться — нет у меня желания, т.к. 5 — 10 байт не имеет значения в 20мегабайтном проекте. Если конечно весь его переписать руками (только не такими кривыми, как у тебя), он из 20 станет 15 мегабайтным, но не за год, а за 10 — а это не приемлемо.

Здравствуйте Алексей Петров, Вы писали:

....

АП>Это не обработчик аналогового сигнала. Исходные строки можно считать почти случайными.

Прошу прощения за С-код в теме ассемблер, но в соседней ветке уже был пецидент

...

inline __fastcall int CountHelper (unsigned __int32 A)
{
    A|=A>>2;
    A|=A>>1;
    return (A&0x01010101)%15 + ((A/8)&0x01010101)%15;
};

inline __fastcall int Counter (__int64& a,__int64& b)
{
    return    CountHelper(    (*(unsigned __int32*)&a)    ^(*(unsigned __int32*)&b) )
    +    CountHelper(    (*(unsigned __int32*)(&a+4))    ^(*(unsigned __int32*)(&b+4)) );
};

Идея в том чтобы обойтись вообще без цикла.

Здравствуйте Алексей Петров, Вы писали:

АП>И хочешь сказать, это будет оптимальный вариант по скорости (если убрать ошибку, из за которой оно вообще зацикливается)?
АП>Или просто написал абы как?
АП>Ассемблер есть смысл использовать только тогда, когда уверен, что напишеш лучше компилятора.

Сейчас флеймить начну. Ассемблер имеет смысл использовать тогда, когда ты этого хочешь и тебе ничего не мешает это делать.

Здравствуйте Алексей Петров, Вы писали:

АП>Мне не надо считать позиции. Есть конкретная задача — максимально быстро посчитать число различий.

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

А>>Человек это с трудом может закодировать — нужно знать длину каждой команды.
АП>Понятно, что с трудом. Но это как раз аргумент против чрезмерного увлечения асм-ом.

Этот аргумент отдыхает. Сейчас настолько быстрые компьютеры, что небольшое замедление, вызванное (возможно) неоптимальным решением человека, не играет никакой роли (мой любимый аргумент, который я позаимстововал у дельфистов

Здравствуйте Алексей Петров, Вы писали:

АП>Все равно пофигу. Мне не нужно выпендриваться размером программы — это болезнь начинающих.

Флеймите, уважаемый. Но, как говорится, кто к нам с мечом придет, тот от оного и погибнет. Чай и сами не дураки и в местах пофлеймистей писали (гы — RU.OS.CMP).

АП>Опытный — согласен, при желании сгенерит и лучше, но станет этим заниматься только на очень критичной по времени функции и тогда, когда на ЯВУ мысли выразить сложнее, чем на asm.

Заметьте, (не)уважаемый, вы сейчас говорите не по делу. Такое впечатление, что вы так и ждете, как кинуться в бой с криком "Асм маздай! Дельфи рулит!". Мы находимся в форуме по ассемблеру. Решения на C++ следует приводить в _другом_ форуме.

>В остальных случаях дополнительные затраты времени и сил на asm не окупаются.

Слушай, я это где-то уже слышал

. Только вот к чему ты это пишешь?

АП>А размером с тобой меряться — нет у меня желания, т.к. 5 — 10 байт не имеет значения в 20мегабайтном проекте. Если конечно весь его переписать руками (только не такими кривыми, как у тебя), он из 20 станет 15 мегабайтным, но не за год, а за 10 — а это не приемлемо.

Нехорошо ты на человека наехал. Не по понятиям живешь.

Поправка...

А>

А>    xor ecx,ecx               ;; Лучше, чтобы команда инкримента ecx была несколько позже...
        xor ebx,ebx               ;;
        inc ecx                   ;; Поплавок...
А>    mov eax,dword ptr i1+4
А>    xor eax,dword ptr i2+4
А>    jnz l1                     
;;А>l4:    inc ecx                   ;; Это теперь не надо!!!
А>    mov eax,dword ptr i1
А>    xor eax,dword ptr i2
А>    jz l3
        ;;А>l1:    bswap eax                ;; Зачем так жестоко?
        
l1:    test al,0Fh              ;; 
А>    jz @F
А>    inc ebx
А>@@:    test al,0F0h
А>    jz @F
А>    inc ebx

А>@@:    shr eax,8                 ;; Очень плохо!!! Очень, тут надо что-то придумать!!!
    jz l2

;; Развернём цикл мы не жадные, тем более, что есть маленькая тонкость...

А>    test al,0Fh              ;; Так, а теперь внимание, если это ноль, значит последняя точно не ноль!!!
А>    jz @F
А>    inc ebx                  ;; Хе-хе
А>@@:    inc ebx

        dec ecx                   ;; Приём поплавка!!!
        jnz l2
.................................................
.................................................
l3:

Делаю исправления и поправки на все предыдущие случаи и бросаю рабочий пример.
На этом и камень забиваем!!!

          .386
          .model flat
          option casemap :none   ; case sensitive
   
         .data
     
     str1    db 22h,33h,33h,11h,34h,33h,55h,99h
     str2    db 33h,44h,77h,22h,34h,77h,44h,88h  
   
          .code
_start:
EXTERN  __imp__ExitProcess@4:dword
        
        xor        eax,eax
        mov        ecx,0        ;; Вместо mov ecx,eax это стоит за тем, чтобы
                            ;; метка @@loop1 и @@loop2 была выравненной

        mov        eax, dword ptr str1
        xor        eax, dword ptr str2
        jz        @@word2        ;; Редко выполняеться

@@loop1:
        test    al,al
        jz        short    @@next1 ;; То же не часто..., но под конец частенько
        test    al,0fh        ; Если есть совпадение (ноль),
                            ; значит вторая часть точно не ноль 
        jz        short    @@1
; если совпадения нет  ( не ноль), значит
        inc        ecx
        test    al,0f0h
        jz        @@next1
@@1:    inc        ecx
        

@@next1:
        shr        eax,8
        jnz        short    @@loop1
@@word2:
        mov        eax, dword ptr str1+4
        xor        eax, dword ptr str2+4
;        jz        short    @@end
        

@@loop2:
        test    al,al
        jz        @@next2


        test    al,0fh        ; Если есть совпадение (ноль),
                            ; значит вторая часть точно не ноль 
        jz        @@2
; если совпадения нет  ( не ноль), значит
        inc        ecx
        test    al,0f0h
        jz        @@next2
@@2:    inc        ecx
        

@@next2:
        shr        eax,8
        jnz        short    @@loop2

                
@@end:

          push    ecx


        call __imp__ExitProcess@4
          
          end _start

Здравствуйте Edmond, Вы писали:

E>Делаю исправления и поправки на все предыдущие случаи и бросаю рабочий пример.
E>На этом и камень забиваем!!!

А моя реализация с ММХ (см. посты выше ) не канает?

Здравствуйте masquer, Вы писали:

M>Здравствуйте Edmond, Вы писали:

E>>Делаю исправления и поправки на все предыдущие случаи и бросаю рабочий пример.
E>>На этом и камень забиваем!!!

M>А моя реализация с ММХ (см. посты выше ) не канает?

ХМ... Ну так вообще с MMX своя проблемма.
Но если б ты её немного доканал... то...

Здравствуйте Edmond, Вы писали:

E>ХМ... Ну так вообще с MMX своя проблемма.
E>Но если б ты её немного доканал... то...

То есть... А в чем там проблема?

Провожу тестирование разных вариантов.

Тестирование провожу следующим образом:
Все фрагменты кода привожу к виду функции с прототипом int __stdcall countDiffs(__int64 i1, __int64 i2) и с запретом inline.
и вызываю её 5 раз для проверки скорости выполнения на разных входных условиях:
Сравниваемые пары:
{0x1234567890123456, 0x1234567890123456}, // Полное совпадение
{0x8234567890123456, 0x1234567890123456}, // Отличае в 1-й цифре
{0x1234567890123459, 0x1234567890123456}, // Отличае в последней цифре
{0x2345678901234591, 0x1234567890123456}, // Нет совпадений
{0x1234568890123456, 0x1234567890123456} // Отличае в середине

Скорость меряю с помощью инструкции RDTSC процессора.

Вот результаты:

1) Эталон для замера накладных расходов:
volatile int Result=0;
int __stdcall DummyCall(__int64 a, __int64 b)
{
return Result;
}
Time=48, Result= 0 — OK
Time=46, Result= 0 — Fail
Time=48, Result= 0 — Fail
Time=46, Result= 0 — Fail
Time=46, Result= 0 — Fail
AvgTime=46.8

2) Вариант реализации "в лоб" на С:
int __stdcall countDiffs(__int64 a, __int64 b)
{
__int64 Temp = a ^ b;
int result = 0;
while (Temp)
{
if (Temp & 0xF)
result ++;
Temp >>= 4;
}
return result;
}
Оказался неудачным, т.к. >> транслируется как sar, а не shr (в отличаи от Delphi, на котором это когда-то работало),
что приводит зацикливанию при различаи в старшей цифре.

3) То-же на Delphi:
function Cmp(a, b: Int64): Integer; stdcall;
var
t: Int64;
begin
t := a xor b;
Result := 0;
while t<>0 do
begin
if t and $F<>0 then
Inc(Result);
t := t shr 4;
end;
end;
Time=79, Result= 0 — OK
Time=324, Result= 1 — OK
Time=95, Result= 1 — OK
Time=288, Result=16 — OK
Time=262, Result= 1 — OK
AvgTime=209.600000

4) пред-последний вариант от Алекс
Time=58, Result= 0 — OK
Time=105, Result= 1 — OK
Time=183, Result= 1 — OK
Time=249, Result=16 — OK
Time=139, Result= 1 — OK
AvgTime=146.800000

в последнем — опять ошибка. ebx, где потом результат накапливается не обнуляется предварительно. И работает он дольше.

5) Мой вариант на asm
Time=85, Result= 0 — OK
Time=172, Result= 1 — OK
Time=85, Result= 1 — OK
Time=234, Result=16 — OK
Time=102, Result= 1 — OK
AvgTime=135.600000

6) Вариант от Chorkov
не работает корректно:
Time=222, Result= 2 — Fail
Time=223, Result= 2 — Fail
Time=222, Result= 4 — Fail
Time=223, Result=10 — Fail
Time=223, Result= 2 — Fail
AvgTime=222.600000

6) Вариант от Edmond
Time=64, Result= 0 — OK
Time=133, Result= 1 — OK
Time=111, Result= 1 — OK
Time=256, Result=16 — OK
Time=73, Result= 1 — OK
AvgTime=127.400000

Что мне понравилось, так это обилие коментариев в коде, достаточное для понимания написанного, и выравнивание
на границу комманд, достигаемое путем выбора предшествующих операций из набора эквивалентных.
Мое почтение мастеру.

Вот и все.

Предлагаю всем поставить максимальный бал победителю в качестве награды.

Здравствуйте Алексей Петров, Вы писали:

АП>Вот и все.
Хотелось бы финальный аккорд на MMX предоставить, сонный был, немного не так задание понял

. А если не 5 проходов задать а, скажем. 5 000 000. Можно результаты.

    .686
    .MMX
    .model flat, stdcall
    option casemap :none
    include \masm32\include\windows.inc
    include \masm32\include\user32.inc
    include \masm32\include\kernel32.inc

    includelib \masm32\lib\user32.lib
    includelib \masm32\lib\kernel32.lib

    Diff PROTO :QWORD, :QWORD

.data
align 4
d0_1 dq 1234567890123456h
d0_2 dq 1234567890123456h

d1_1 dq 8234567890123456h
d1_2 dq 1234567890123456h

d2_1 dq 1234567890123459h
d2_2 dq 1234567890123456h

d3_1 dq 2345678901234591h
d3_2 dq 1234567890123456h

d4_1 dq 1234568890123456h
d4_2 dq 1234567890123456h

eq1 dq 0101010101010101h
msk0f dq 0f0f0f0f0f0f0f0fh
.code
start:
    invoke Diff, d3_1, d3_2
    invoke ExitProcess,0

;---------------------------------
Diff proc a:QWORD, b:QWORD
    movq mm0, a
    movq mm1, mm0
    movq mm2, b
    movq mm3, mm2
    movq mm4, msk0f
    movq mm5, eq1

    psllw mm0, 4
    psllw mm2, 4

    psrlw mm0, 4
    psrlw mm2, 4

    psrlw mm1, 4
    psrlw mm3, 4

    pand mm0, mm4
    pand mm1, mm4
    pand mm2, mm4
    pand mm3, mm4

    pcmpeqb mm0,mm2
    pcmpeqb mm1,mm3

    paddb mm0, mm5
    paddb mm1, mm5
    paddb mm0, mm1
    pxor mm1, mm1
    psadbw mm0, mm1
    movd eax, mm0
    emms
    ret
Diff endp
end start

Здравствуйте masquer, Вы писали:

M>Хотелось бы финальный аккорд на MMX предоставить, сонный был, немного не так задание понял

. А если не 5 проходов задать а, скажем. 5 000 000. Можно результаты.

Суперски:
Time=74, Result= 0 — OK
Time=72, Result= 1 — OK
Time=74, Result= 1 — OK
Time=72, Result=16 — OK
Time=72, Result= 1 — OK
AvgTime=72.800000

А 5 или 5000000 проходов — значения не имеет — RDTSC хорошая инструкция

Здравствуйте masquer, Вы писали:

M>Здравствуйте Алексей Петров, Вы писали:

АП>>Вот и все.
M>Хотелось бы финальный аккорд на MMX предоставить, сонный был, немного не так задание понял

. А если не 5 проходов задать а, скажем. 5 000 000. Можно результаты.

А не мог бы ты снабдить комментариями свое творение, чтоб всем стало ясно, как оно работает. MMX-овский набор инструкция мало кто знает

Здравствуйте Алексей Петров, Вы писали:

АП>А не мог бы ты снабдить комментариями свое творение, чтоб всем стало ясно, как оно работает. MMX-овский набор инструкция мало кто знает :-Не верю (с) Станиславский

    movq mm0, a    ; загружаем сравниваемые числа
    movq mm1, mm0
    movq mm2, b
    movq mm3, mm2
    movq mm4, msk0f ; и маски как 64-битные числа
    movq mm5, eq1 
;--------------------------------------
    psllw mm0, 4 ; сдвигаем каждое слово влево на 4 бита
    psllw mm2, 4

    psrlw mm0, 4 ; сдвигаем каждое слово вправо на 4 бита
    psrlw mm2, 4

    psrlw mm1, 4 ; опять :)
    psrlw mm3, 4

    pand mm0, mm4 ; ложим маску
    pand mm1, mm4
    pand mm2, mm4
    pand mm3, mm4
; смысл всего этого сделать из
; mm0=1234567890123456
; mm0=0103050709010305
; mm1=0204060800020406
;--------------------------------------

    pcmpeqb mm0,mm2 ; сравниваем побайтно, если байты равны, в mm0 и mm1 каждый
    pcmpeqb mm1,mm3 ; соответствующий байт = FF, иначе  00

    paddb mm0, mm5 ; добавим 01 к каждому байту, получится 01 если не рывны были
    paddb mm1, mm5
    paddb mm0, mm1 ; просуммируем полученные "неравности" для 16 mm0=0202020202020202
    pxor mm1, mm1 ; обнулим mm1 для следующей команды
    psadbw mm0, mm1 ; требует проц не ниже P3, суммирует абсолютные значения разницы
    ; соответствующих байт и результат помещает в нижнее слово mm0
    movd eax, mm0 ; которое мы и сохраняем в eax
    emms ; для предосторожности чистим стек сопроцессора

Здравствуйте masquer, Вы писали:

M>Здравствуйте Алексей Петров, Вы писали:

АП>>А не мог бы ты снабдить комментариями свое творение, чтоб всем стало ясно, как оно работает. MMX-овский набор инструкция мало кто знает :-Не верю (с) Станиславский
M>

M>    movq mm0, a    ; загружаем сравниваемые числа
M>    movq mm1, mm0
M>    movq mm2, b
M>    movq mm3, mm2
M>    movq mm4, msk0f ; и маски как 64-битные числа
M>    movq mm5, eq1 
M>;--------------------------------------
M>    psllw mm0, 4 ; сдвигаем каждое слово влево на 4 бита
M>    psllw mm2, 4

M>    psrlw mm0, 4 ; сдвигаем каждое слово вправо на 4 бита
M>    psrlw mm2, 4

M>    psrlw mm1, 4 ; опять :)
M>    psrlw mm3, 4

M>    pand mm0, mm4 ; ложим маску
M>    pand mm1, mm4
M>    pand mm2, mm4
M>    pand mm3, mm4
M>; смысл всего этого сделать из
M>; mm0=1234567890123456
M>; mm0=0103050709010305
M>; mm1=0204060800020406
M>;--------------------------------------

M>    pcmpeqb mm0,mm2 ; сравниваем побайтно, если байты равны, в mm0 и mm1 каждый
M>    pcmpeqb mm1,mm3 ; соответствующий байт = FF, иначе  00

M>    paddb mm0, mm5 ; добавим 01 к каждому байту, получится 01 если не рывны были
M>    paddb mm1, mm5
M>    paddb mm0, mm1 ; просуммируем полученные "неравности" для 16 mm0=0202020202020202
M>    pxor mm1, mm1 ; обнулим mm1 для следующей команды
M>    psadbw mm0, mm1 ; требует проц не ниже P3, суммирует абсолютные значения разницы
M>    ; соответствующих байт и результат помещает в нижнее слово mm0
M>    movd eax, mm0 ; которое мы и сохраняем в eax
M>    emms ; для предосторожности чистим стек сопроцессора
M>

	От:	Алексей Петров
	Дата:	17.07.02 05:09
	Оценка:	15 (2)

	От:	Edmond
	Дата:	17.07.02 05:56
	Оценка:

	От:	Алексей Петров
	Дата:	17.07.02 06:17
	Оценка:

От:	Алекс	http://wise-orm.com
Дата:	17.07.02 07:16
Оценка:	-1

	От:	Алексей Петров
	Дата:	17.07.02 07:33
	Оценка:

От:	Aquila	http://www.wasm.ru
Дата:	18.07.02 06:31
Оценка:

	От:	masquer
	Дата:	19.07.02 08:51
	Оценка:

	От:	masquer
	Дата:	19.07.02 11:50
	Оценка:

	От:	masquer
	Дата:	22.07.02 16:21
	Оценка:	15 (1)

	От:	masquer
	Дата:	23.07.02 05:44
	Оценка:	32 (3)