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

Есть пара строк, содержащих исключительно десятичные цифры длиной 16 цифр. Строки упакованы в int64 по 4 бита на цифру.
Нужно посчитать число различных цифр у 2-х строк.

Операция выполняется огромное число раз в связи с чем необходима максимально возможная оптимизация скорости выполнения.

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

АП>Есть пара строк, содержащих исключительно десятичные цифры длиной 16 цифр. Строки упакованы в int64 по 4 бита на цифру.
АП>Нужно посчитать число различных цифр у 2-х строк.

АП>Операция выполняется огромное число раз в связи с чем необходима максимально возможная оптимизация скорости выполнения.

То есть так 12...34 и 23....45..
1 нет в строке 2
2 есть в строке 2 или как?

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

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

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

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

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

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

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

Запросто!

 .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)) );
};

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

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

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

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

	От:	Алексей Петров
	Дата:	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
Оценка: