Как возможно, что операция БИТОВОЕ И занимает больше тактов ЦП, чем операция АРИФМЕТИЧЕСКОЕ СЛОЖЕНИЕ в программе на языке C?

ладно, давайте возьмем это "измерение" и взорвем его, 100к это немного

#include<stdio.h>
#include<time.h>
#define limit 10000000000

int main() 
{
   int x=10, y=25, z;

   time_t start = clock();
   for(long long i=0;i<limit;i++)z=x+y;
   time_t stop = clock();
   printf("Arithmetic instructions take: %ld\n",stop-start);

   start = clock();
   for(long long i=0;i<limit;i++)z=x&y;
   stop = clock();
   printf("Logic instructions take: %ld\n",stop-start);
}

это будет работать немного дольше. Сначала попробуем без оптимизации:

thomas@TS-VB:~/src$ g++ -o trash trash.c 
thomas@TS-VB:~/src$ ./trash 
Arithmetic instructions take: 21910636
Logic instructions take: 21890332

видите, обе петли занимают примерно одинаковое время.

компиляция с -S показывает, почему (здесь показана только соответствующая часть файла .s):

// this is the assembly for the first loop
.L3:
    movl    32(%esp), %eax
    movl    28(%esp), %edx
    addl    %edx, %eax             // <<-- ADD
    movl    %eax, 40(%esp)
    addl    $1, 48(%esp)
    adcl    $0, 52(%esp)
.L2:
    cmpl    $2, 52(%esp)
    jl  .L3
    cmpl    $2, 52(%esp)
    jg  .L9
    cmpl    $1410065407, 48(%esp)
    jbe .L3

// this is the one for the second
.L9:
    movl    32(%esp), %eax
    movl    28(%esp), %edx
    andl    %edx, %eax             // <<--- AND
    movl    %eax, 40(%esp)
    addl    $1, 56(%esp)
    adcl    $0, 60(%esp)
.L5:
    cmpl    $2, 60(%esp)
    jl  .L6
    cmpl    $2, 60(%esp)
    jg  .L10
    cmpl    $1410065407, 56(%esp)
    jbe .L6
.L10:

просмотр набора инструкций процессора говорит нам, что и ADD, и AND будут занимать одинаковое количество циклов -> 2 цикла будут выполняться одинаковое количество времени

Теперь с оптимизацией:

thomas@TS-VB:~/src$ g++ -O3 -o trash trash.c 
thomas@TS-VB:~/src$ ./trash 
Arithmetic instructions take: 112
Logic instructions take: 74

Цикл был оптимизирован. Вычисленное значение никогда не понадобится, поэтому компилятор решил вообще его не запускать.

Вывод: Если вы выстрелите 3 раза в лес и попадете в 2 кабанов и 1 кролика, это не значит, что кабанов там в два раза больше, чем кроликов

Давайте начнем с просмотра вашего кода. Циклы на самом деле ничего не делают. Любой разумный компилятор увидит, что вы не используете переменную z после первого вызова printf, поэтому ее можно совершенно безопасно выбросить. Конечно, компилятор не обязан это делать, но это сделает любой разумный компилятор с разумными уровнями оптимизации.

Давайте посмотрим, что компилятор сделал с вашим кодом (стандартный clang с уровнем оптимизации -O2):

    leaq    L_.str(%rip), %rdi
    movl    $35, %esi
    xorl    %eax, %eax
    callq   _printf

Это первый printf ("Сумма..."), обратите внимание, что сгенерированный код на самом деле ничего не добавил, компилятор знает значения x и y и просто вычислил их сумму и вызывает printf с 35.

    callq   _clock
    movq    %rax, %rbx
    callq   _clock

Вызвать часы, сохранить результат во временном регистре, снова вызвать часы,

    movq    %rax, %rcx
    subq    %rbx, %rcx
    leaq    L_.str.1(%rip), %rdi
    xorl    %eax, %eax
    movq    %rcx, %rsi

Вычесть начало из конца, установить аргументы для printf,

    callq   _printf

Позвоните в printf.

Вторая петля снимается аналогично. Циклов нет, потому что компилятор делает разумную вещь - он замечает, что z не используется после того, как вы изменяете его в цикле, поэтому компилятор отбрасывает в него все сохранения. А так как в нем ничего не хранится, то можно и x+y выкинуть. И теперь, поскольку тело цикла ничего не делает, цикл можно выбросить. Таким образом, ваш код по существу становится:

printf("\n\nArithmetic instructions take: %d", clock() - clock());

Теперь, почему это актуально. Важно понимать некоторые важные понятия. Компилятор не переводит в код по одному оператору за раз. Компилятор читает весь (или максимально возможное) ваш код, пытается выяснить, что вы на самом деле имеете в виду, а затем генерирует код, который ведет себя так, как будто он выполнил все эти операторы. Язык и компилятор заботятся только о том, чтобы сохранить то, что мы могли бы назвать наблюдаемыми побочными эффектами. Если вычисление значения невозможно наблюдать, его не нужно вычислять. Время выполнения некоторого кода не является побочным эффектом, который нас волнует, поэтому компилятор не заботится о его сохранении, в конце концов, мы хотим, чтобы наш код был как можно быстрее, поэтому мы хотели бы, чтобы время выполнения чего-либо быть вообще незаметным.

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

LBB0_1:
        cmpl    $100000, -28(%rbp)
        jge     LBB0_4
        movl    -8(%rbp), %eax
        addl    -12(%rbp), %eax
        movl    %eax, -16(%rbp)
        movl    -28(%rbp), %eax
        addl    $1, %eax
        movl    %eax, -28(%rbp)
        jmp     LBB0_1
LBB0_4:

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

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

Затем мы переходим к вопросу о фактических инструкциях, которые вас интересуют. Они занимают одинаковое количество времени. Вот канонический источник всего, что связано с синхронизацией инструкций на x86.

Но. Очень трудно и почти бесполезно рассуждать об отдельных инструкциях. Почти каждый ЦП за последние несколько десятилетий был суперскалярным. Это означает, что он будет выполнять много инструкций одновременно. Что имеет значение для того, сколько времени требуется, так это больше зависимостей между инструкциями (невозможно начать выполнение инструкции до того, как ее входные данные будут готовы, если эти входные данные вычисляются предыдущими инструкциями), а не фактическая инструкция. Хотя вы можете выполнять десятки вычислений в регистрах за наносекунду, получение данных из основной памяти может занять сотни наносекунд. Таким образом, даже если мы знаем, что инструкция занимает один цикл, а ваш ЦП выполняет два цикла в наносекунду (обычно это около этого), это может означать, что количество инструкций, которые мы можем завершить за 100 нс, может быть где-то между 1 (если вам нужно подождать для основной памяти) и 12800 (настоящих точных цифр я не знаю, но помню, что Skylake может утилизировать 64 операции с плавающей запятой за такт).

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

Извините за такой бессвязный ответ, но я пытаюсь понять, почему, несмотря на то, что на ваш вопрос есть простой ответ: «ваш метод измерения плохой», а также реальный ответ: «они одинаковые», на самом деле есть интересные причины, по которым сам вопрос остается без ответа.

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

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

  400600:   8d 04 37                lea    (%rdi,%rsi,1),%eax
  400603:   c3                      retq  

для и

  400610:   89 f8                   mov    %edi,%eax
  400612:   21 f0                   and    %esi,%eax
  400614:   c3                      retq 

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

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

.balign 32
nop
.balign 256
.globl and_test
and_test:
    mov %edi,%eax
    and %esi,%eax
    sub $1,%edx
    jne and_test
    retq

.balign 32
nop
.balign 256
.globl add_test
add_test:
    mov %edi,%eax
    add %esi,%eax
    sub $1,%edx
    jne add_test
    retq

.balign 256
    nop

производное от твоего

#include<stdio.h>
#include<time.h>
unsigned int add_test ( unsigned int a, unsigned int b, unsigned int x );
unsigned int and_test ( unsigned int a, unsigned int b, unsigned int x );
int main() 
{
   int x=10;
   int y=25;
   time_t start,stop;
   for(int j=0;j<10;j++)
   {
       start = clock();
       add_test(10,25,2000000000);
       stop = clock();
       printf("%u %u\n",j,(int)(stop-start));

   }
   for(int j=0;j<10;j++)
   {
       start = clock();
       and_test(10,25,2000000000);
       stop = clock();
       printf("%u %u\n",j,(int)(stop-start));

   }
   return(0);
}

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

0 605678
1 520204
2 521311
3 520050
4 521455
5 520213
6 520315
7 520197
8 520253
9 519743
0 520475
1 520221
2 520109
3 520319
4 521128
5 520974
6 520584
7 520875
8 519944
9 521062

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

0 599558
1 515120
2 516035
3 515863
4 515809
5 516069
6 516578
7 516359
8 516170
9 515986
0 516403
1 516666
2 516842
3 516710
4 516932
5 516380
6 517392
7 515999
8 516861
9 517047

обратите внимание, что это 2 миллиарда циклов. четыре инструкции в. мои часы в секунду составляют 1000000 на частоте 3,4 ГГц, 0,8772 такта на цикл или 0,2193 такта на инструкцию, как это возможно? суперскейлерный процессор.

Можно было бы сделать НАМНОГО больше работы, здесь это заняло всего несколько минут, и, надеюсь, этого достаточно, чтобы продемонстрировать (как и другие уже), что вы не можете увидеть разницу с таким тестом.

Я мог бы сделать демонстрацию с чем-то более линейным, например, с рукой, и с чем-то, что мы могли бы считать регистром часов/таймера как частью тестируемого кода, поскольку вызов кода часов является частью тестируемого кода и может варьироваться здесь. Надеюсь, в этом нет необходимости, результаты гораздо более стабильны, несмотря на использование sram, управление всеми тестируемыми инструкциями и т. д., и с этим вы можете видеть различия в выравнивании, вы можете видеть стоимость кеша, считанного в первом цикле, но не в остальных и т. д. (всего несколько тактов, хотя 10 мс, как мы видим здесь, хм, может быть на одном уровне для системы x86, не знаю, бенчмаркинг x86 - это почти полная пустая трата времени, никакого удовольствия от этого, и результаты не переносятся на другие компы x86 это хорошо)

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

https://en.wikipedia.org/wiki/AND_gate
https://en.wikipedia.org/wiki/Adder_(electronics)

Предполагая, что подача математической / логической операции для сложения и и одинакова, и мы только пытаемся измерить разницу между ними, вы правы, И быстрее, не вдаваясь в подробности, вы можете видеть и имеет только один этап / ворота. Там, где полный сумматор занимает три уровня, обратная математика конверта, в три раза больше времени для установления сигналов после изменения входных сигналов, чем И .... НО .... Хотя есть некоторые исключения, микросхемы не предназначены для воспользуйтесь этим (хорошо, умножьте и разделите против добавления/и/исключающего или и т. д., да, они есть или, скорее всего, будут). Можно было бы спроектировать эти простые операции так, чтобы они выполнялись за один такт, на такте входы в комбинационную логику (фактическое И или Сложение) фиксируются, на следующем такте результат фиксируется с другого конца и начинает свое путешествие к зарегистрируйте файл или из ядра в память и т. д. В какой-то момент проекта вы выполняете синтез в воротах, доступных для литейного производства/процесса, который вы используете, затем проводите временной анализ/замыкание этого и ищете длинные полюса в палатка. Крайне маловероятно (невозможно), что добавление является длинным полюсом, и добавление, и очень короткие полюса, но в этот момент вы определяете, какова ваша максимальная тактовая частота, если вам нужен процессор 4 ГГц, но результат 2,7, ну вам нужно взять эти длинные полюса и превратить их в две или более часовых операций. время, необходимое для выполнения добавления по сравнению с тем, что должно варьироваться, добавление должно быть больше, настолько быстро и в шуме, что все это находится в пределах тактового цикла, поэтому даже если вы выполнили функциональное моделирование логического проекта, вы не увидите Разница в том, что вам нужно реализовать и и полный сумматор, скажем, в pspice, используя транзисторы и другие компоненты, затем подать ступенчатые изменения на входы и посмотреть, сколько времени потребуется, чтобы установить это, или собрать их из дискретных компонентов из радиолавки и попробовать, хотя результаты могут быть слишком быстрыми для вашей области, поэтому используйте pspice или другой.

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

this
a = b+c+d+e+f+g;
vs
x=b+c;
y=d+e;
z=f+g;
a=x+y;
a=a+z;

одни часы против 5 часов, но каждые из 5 часов могут быть быстрее, если это был самый длинный шест в палатке. вся остальная логика заключается в том, что это намного быстрее, чем это. (на самом деле x,y,z могут быть одними часами, затем либо a=x+y+z в следующем, либо сделайте еще два)

умножение и деление отличаются просто потому, что логика взрывается экспоненциально, нет никакой магии, чтобы умножить или разделить, они должны работать так же, как мы делаем вещи на карандаше и бумаге. вы можете использовать ярлыки с двоичным кодом, если вы думаете об этом. так как вы можете умножать только на 0 или 1 перед сдвигом и добавлением к аккумулятору. логические уравнения для одних часов все еще взрываются экспоненциально, и тогда вы можете делать параллельные вещи. он сжигает массу микросхем, поэтому вы можете сделать умножение и деление более чем на один такт и скрыть те, которые находятся в конвейере. или вы можете сжечь значительное количество недвижимости чипа ... Посмотрите документацию для некоторых ядер рук, которые вы можете во время компиляции (когда вы компилируете/синтезируете ядро) выбрать однотактовое или многотактовое умножение для баланса Размер чипа против производительности. x86 мы не покупаем IP и сами не производим чипы, так что это зависит от разведки, как они это делают, и, скорее всего, микрокодируется, поэтому, просто микрокодируя, вы можете настроить, как все происходит, или сделать это в операции типа alu.

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