Арифметические операции над булевыми операциями

Ответ 1

В стандарте C ничего не говорится о производительности. Вопрос о том,

if ( a * b * c * d == 0 )

быстрее, чем

if (a == 0 || b == 0 || c == 0 || d == 0)

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

Тем не менее, мы можем размышлять о том, какова будет производительность.

Как вы сказали, a, b, c и d являются объектами типа int. Вы также сказали, что они находятся в диапазоне [-100, + 100] - но компилятор не обязательно это знает.

Компилятор может заменить любое выражение кодом, который делает то же самое.

Умножение является относительно сложной операцией и, вероятно, будет медленнее, чем, скажем, сложение или сравнение. Компилятор мог бы признать, что первое условие будет истинным, если какая-либо из четырех переменных имеет значение 0 и заменит умножения тем, что происходит быстрее. Но каждая оптимизация, выполняемая компилятором, должна быть явно запрограммирована разработчиками компилятора, и эта конкретная модель вряд ли будет достаточно распространена, так как она будет стоить усилий для ее распознавания.

Вы говорите, что значения достаточно малы, что переполнение не является проблемой. На самом деле вы не можете переносить это предположение; INT_MAX может быть меньше 32767. Но компилятор знает, насколько большой int в системе, для которой он генерирует код. Тем не менее, если у него нет информации о значениях a, b, c и d, он не может предположить, что переполнения не будет.

За исключением того, что да, на самом деле, это может сделать это предположение. Поведение знакового целочисленного переполнения undefined. Это дает оптимизирующему разрешению компилятора предположить, что переполнение не может произойти (если это так, любое поведение, которое показывает программа, все равно).

Итак, да, компилятор может заменить умножения чем-то более простым, но вряд ли это сделает.

Что касается другого выражения, a == 0 || b == 0 || c == 0 || d == 0, оператор || имеет короткозамкнутую семантику; если левый операнд имеет значение true (отличное от нуля), то правый операнд не оценивается. И такой условный код может создавать проблемы с производительностью из-за проблем с конвейером CPU. Поскольку ни один из подвыражений не имеет побочных эффектов (при условии, что ни одна из переменных не объявлена ​​volatile), компилятор может оценить все четыре подвыражения, возможно, параллельно, если это быстрее.

Быстрый эксперимент показывает, что gcc -O3 для x86 не выполняет ни оптимизации. Для первого выражения он генерирует код, который выполняет три умножения. Во-вторых, он генерирует условные ветки, реализуя канонические оценки короткого замыкания (я не знаю, будет ли избегать этого быстрее или нет).

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

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

Первое правило оптимизации программы: не делайте этого. Второе правило оптимизации программ (только для экспертов!): Не делайте этого еще.

- Майкл А. Джексон

Ответ 2

Эти два не эквивалентны. Например, на моей машине (32-разрядный x86 MSVC), если a, b, c и d равны 0x100, тогда первый тест пройдет, но второе условие не будет.

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

EDIT: Код, сгенерированный для первой версии:

00401000 8B 44 24 04      mov         eax,dword ptr [esp+4] 
00401004 0F AF 44 24 08   imul        eax,dword ptr [esp+8] 
00401009 0F AF 44 24 0C   imul        eax,dword ptr [esp+0Ch] 
0040100E 0F AF 44 24 10   imul        eax,dword ptr [esp+10h] 
00401013 85 C0            test        eax,eax 
00401015 75 07            jne         f1+1Eh (40101Eh) 
00401017 ...

Код, сгенерированный для второй версии:

00401020 83 7C 24 04 00   cmp         dword ptr [esp+4],0 
00401025 74 15            je          f2+1Ch (40103Ch) 
00401027 83 7C 24 08 00   cmp         dword ptr [esp+8],0 
0040102C 74 0E            je          f2+1Ch (40103Ch) 
0040102E 83 7C 24 0C 00   cmp         dword ptr [esp+0Ch],0 
00401033 74 07            je          f2+1Ch (40103Ch) 
00401035 83 7C 24 10 00   cmp         dword ptr [esp+10h],0 
0040103A 75 07            jne         f2+23h (401043h) 
0040103C ...

Тесты на моей машине (в наносекундах): первая версия работает примерно в 1,83 нс, а вторая - около 1,39 нс. Значения a, b, c и d не изменялись во время каждого прогона, поэтому, по-видимому, предсказатель ветвления мог предсказать 100% ветвей.

Ответ 3

Как обычно, с чем возникают более быстрые вопросы, что вы пробовали? Вы собирали и разбирали и видели, что происходит?

unsigned int mfun ( unsigned int a, unsigned int b, unsigned int c, unsigned int d )
{
    if ( a * b * c * d == 0 ) return(7);
    else return(11);
}

unsigned int ofun ( unsigned int a, unsigned int b, unsigned int c, unsigned int d )
{
    if (a == 0 || b == 0 || c == 0 || d == 0) return(7);
    else return(11);
}

для компилятора arm one дает это

00000000 <mfun>:
   0:   e0010190    mul r1, r0, r1
   4:   e0020291    mul r2, r1, r2
   8:   e0110293    muls    r1, r3, r2
   c:   13a0000b    movne   r0, #11
  10:   03a00007    moveq   r0, #7
  14:   e12fff1e    bx  lr

00000018 <ofun>:
  18:   e3500000    cmp r0, #0
  1c:   13510000    cmpne   r1, #0
  20:   0a000004    beq 38 <ofun+0x20>
  24:   e3520000    cmp r2, #0
  28:   13530000    cmpne   r3, #0
  2c:   13a0000b    movne   r0, #11
  30:   03a00007    moveq   r0, #7
  34:   e12fff1e    bx  lr
  38:   e3a00007    mov r0, #7
  3c:   e12fff1e    bx  lr

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

mips дали мне это

00000000 <mfun>:
   0:   00a40018    mult    a1,a0
   4:   00002012    mflo    a0
    ...
  10:   00860018    mult    a0,a2
  14:   00002012    mflo    a0
    ...
  20:   00870018    mult    a0,a3
  24:   00002012    mflo    a0
  28:   10800003    beqz    a0,38 <mfun+0x38>
  2c:   00000000    nop
  30:   03e00008    jr  ra
  34:   2402000b    li  v0,11
  38:   03e00008    jr  ra
  3c:   24020007    li  v0,7

00000040 <ofun>:
  40:   10800009    beqz    a0,68 <ofun+0x28>
  44:   00000000    nop
  48:   10a00007    beqz    a1,68 <ofun+0x28>
  4c:   00000000    nop
  50:   10c00005    beqz    a2,68 <ofun+0x28>
  54:   00000000    nop
  58:   10e00003    beqz    a3,68 <ofun+0x28>
  5c:   00000000    nop
  60:   03e00008    jr  ra
  64:   2402000b    li  v0,11
  68:   03e00008    jr  ra
  6c:   24020007    li  v0,7

Если ветки слишком дороги, равные и орлы выглядят быстрее.

Openrisc 32

00000000 <mfun>:
   0:   e0 64 1b 06     l.mul r3,r4,r3
   4:   e0 a3 2b 06     l.mul r5,r3,r5
   8:   e0 c5 33 06     l.mul r6,r5,r6
   c:   bc 26 00 00     l.sfnei r6,0x0
  10:   0c 00 00 04     l.bnf 20 <mfun+0x20>
  14:   9d 60 00 0b     l.addi r11,r0,0xb
  18:   44 00 48 00     l.jr r9
  1c:   15 00 00 00     l.nop 0x0
  20:   44 00 48 00     l.jr r9
  24:   9d 60 00 07     l.addi r11,r0,0x7

00000028 <ofun>:
  28:   e0 e0 20 02     l.sub r7,r0,r4
  2c:   e0 87 20 04     l.or r4,r7,r4
  30:   bd 64 00 00     l.sfgesi r4,0x0
  34:   10 00 00 10     l.bf 74 <ofun+0x4c>
  38:   e0 80 18 02     l.sub r4,r0,r3
  3c:   e0 64 18 04     l.or r3,r4,r3
  40:   bd 63 00 00     l.sfgesi r3,0x0
  44:   10 00 00 0c     l.bf 74 <ofun+0x4c>
  48:   e0 60 30 02     l.sub r3,r0,r6
  4c:   e0 c3 30 04     l.or r6,r3,r6
  50:   bd 66 00 00     l.sfgesi r6,0x0
  54:   10 00 00 08     l.bf 74 <ofun+0x4c>
  58:   e0 60 28 02     l.sub r3,r0,r5
  5c:   e0 a3 28 04     l.or r5,r3,r5
  60:   bd 85 00 00     l.sfltsi r5,0x0
  64:   0c 00 00 04     l.bnf 74 <ofun+0x4c>
  68:   9d 60 00 0b     l.addi r11,r0,0xb
  6c:   44 00 48 00     l.jr r9
  70:   15 00 00 00     l.nop 0x0
  74:   44 00 48 00     l.jr r9
  78:   9d 60 00 07     l.addi r11,r0,0x7

это зависит от реализации умножения, если это один такт, то умножения имеют его.

Если ваше оборудование не поддерживает многократное умножение, вы должны сделать вызов, чтобы он имитировал

00000000 <mfun>:
   0:   0b 12           push    r11     
   2:   0a 12           push    r10     
   4:   09 12           push    r9      
   6:   09 4d           mov r13,    r9  
   8:   0b 4c           mov r12,    r11 
   a:   0a 4e           mov r14,    r10 
   c:   0c 4f           mov r15,    r12 
   e:   b0 12 00 00     call    #0x0000 
  12:   0a 4e           mov r14,    r10 
  14:   0c 49           mov r9, r12 
  16:   b0 12 00 00     call    #0x0000 
  1a:   0a 4e           mov r14,    r10 
  1c:   0c 4b           mov r11,    r12 
  1e:   b0 12 00 00     call    #0x0000 
  22:   0e 93           tst r14     
  24:   06 24           jz  $+14        ;abs 0x32
  26:   3f 40 0b 00     mov #11,    r15 ;#0x000b
  2a:   39 41           pop r9      
  2c:   3a 41           pop r10     
  2e:   3b 41           pop r11     
  30:   30 41           ret         
  32:   3f 40 07 00     mov #7, r15 ;#0x0007
  36:   39 41           pop r9      
  38:   3a 41           pop r10     
  3a:   3b 41           pop r11     
  3c:   30 41           ret         

0000003e <ofun>:
  3e:   0f 93           tst r15     
  40:   09 24           jz  $+20        ;abs 0x54
  42:   0e 93           tst r14     
  44:   07 24           jz  $+16        ;abs 0x54
  46:   0d 93           tst r13     
  48:   05 24           jz  $+12        ;abs 0x54
  4a:   0c 93           tst r12     
  4c:   03 24           jz  $+8         ;abs 0x54
  4e:   3f 40 0b 00     mov #11,    r15 ;#0x000b
  52:   30 41           ret         
  54:   3f 40 07 00     mov #7, r15 ;#0x0007
  58:   30 41    

Вы надеетесь, что эти два эквивалентны, и из чистого математического смысла они должны быть, чтобы получить результат умножения равным нулю, один операнд должен быть равен нулю. проблема в том, что это программное обеспечение для процессора, вы можете легко переполняться с размножением и иметь ненулевые операнды и по-прежнему получать нуль, чтобы должным образом реализовать код, который должен произойти.

из-за стоимости mul и деления, в частности, вы должны избегать их как можно больше в своем программном обеспечении, ваше многократное решение в этом случае для эквивалентных двух решений потребует еще большего кода для обнаружения или предотвращения случаев переполнения что может привести к ложному положительному результату. Да, многие процессоры выполняют mul за один такт и делят также, почему вы не видите разделить, а иногда и не видите, что mul, реализованный в наборе команд, - это потому, что требуется чип-недвижимость, теперь расход - это мощность, тепло, стоимость части и т.д. Таким образом, mul и divide остаются дорогими, не ограничиваясь ими, но они создают длинные полюса в палатке, так как производительность партии, тактовая частота, люди хотят, чтобы одна операционная система не понимала, что одна инструкция может замедлить весь чип, позволяя ему работать с несколькими часами, что может привести к увеличению общей тактовой частоты. так много вещей - длинные полюса в палатке, поэтому удаление мула может не повлиять на производительность, все зависит от...

Ответ 4

Да, когда команда if терпит неудачу, в этом случае мы делаем at most 4 comparisons (Operations) во второй инструкции, а для первой команды всегда делаем 4 operations.

Изменить: Объяснение

Вторая команда if всегда быстрее первой:

Предположим, что: a = 1, b = 2, c = 0 и d = 4, в этом случае:

• Для первой инструкции: у нас есть 3 умножения и сравнение = 4 операции

• Для второй инструкции: мы сравниваем a с 0 (результат KO), затем b с 0 (опять KO) и c с 0 (OK) = 3 операции.

Это простая программа, которая выводит время выполнения для этих двух инструкций, вы можете изменить a, b, c и d и передать номер инструкции в качестве аргумента.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* This is a test program to demonstrate that the second if is faster always than the first one*/
int main(int argc, char **argv)
{
        int i;
        int a = 1;
        int b = 2;
        int c = 0;
        int d = 4;
        int instruction_number;
        clock_t begin, end;
        double time_spent;

        begin = clock();

        if (argc != 2)
        {
                fprintf(stderr, "Usage : ./a.out if_instruction_number (1 or 2)\n");

                exit(EXIT_FAILURE);
        }

        instruction_number = atoi(argv[1]);

        for (i = 1; i < 100000; i++)
        {
                switch (instruction_number)
                {
                        case 1:
                                fprintf(stdout, "First if instruction : \n");
                                if (a * b * c * d == 0)
                                        fprintf(stdout, "1st instruction\n");
                                break;
                        case 2:
                                fprintf(stdout, "Second if instruction : \n");
                                if (a == 0 || b == 0 || c == 0 || d == 0)
                                        fprintf(stdout, "2nd instruction\n");
                                break;
                        default:
                                break;
                }
        }
        end = clock();
        time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
        fprintf(stdout, "Time to accomplish %d instruction ---> %f\n", instruction_number, time_spent);

        return 0;
} 

Надеюсь на эту помощь.

С уважением.

Ответ 5

if ( a * b * c * d == 0 ) компилируется (без оптимизации)

movl   16(%esp), %eax
imull  20(%esp), %eax
imull  24(%esp), %eax
imull  28(%esp), %eax
testl  %eax, %eax
jne .L3

и if (a == 0 || b == 0 || c == 0 || d == 0) компилируется в

cmpl   $0, 16(%esp)
je  .L2
cmpl    $0, 20(%esp)
je  .L2
cmpl    $0, 24(%esp)
je .L2
cmpl    $0, 28(%esp)
jne .L4