Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.9k views
in Technique[技术] by (71.8m points)

assembly - How is it possible that BITWISE AND operation to take more CPU clocks than ARITHMETIC ADDITION operation in a C program?

I wanted to test if bitwise operations really are faster to execute than arithmetic operation. I thought they were.

I wrote a small C program to test this hypothesis and to my surprise the addition takes less on average than bitwise AND operation. This is surprising to me and I cannot understand why this is happening.

From what I know for addition the carry from the less significant bits should be carried to the next bits because the result depends on the carry too. It does not make sense to me that a logic operator is slower than addition.

My cod is below:

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

int main() 
{
   int x=10;
   int y=25;
   int z=x+y;
   printf("Sum of x+y = %i", z);
   time_t start = clock();
   for(int i=0;i<100000;i++)z=x+y;
   time_t stop = clock();

   printf("

Arithmetic instructions take: %d",stop-start);
   start = clock();
   for(int i=0;i<100000;i++)z=x&y;
   stop = clock();

   printf("

Logic instructions take: %d",stop-start);
}

Some of the results:

Arithmetic instructions take: 327
Logic instructions take: 360

Arithmetic instructions take: 271
Logic instructions take: 271

Arithmetic instructions take: 287
Logic instructions take: 294

Arithmetic instructions take: 279
Logic instructions take: 266

Arithmetic instructions take: 265
Logic instructions take: 296

These results are taken from consecutive runs of the program.

As you can see on average the logic operator takes longer on average than the arithmetic operator.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

ok, let's take this "measuring" and blow it up, 100k is a bit few

#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
",stop-start);

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

this will run a bit longer. First let's try with no optimization:

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

you see, both loops take about the same time.

compiling with -S reveals why (only relevant part of .s file shown here) :

// 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:

looking into the CPUs instruction set tells us, both ADD and AND will take the same amount of cycles --> the 2 loops will run the same amount of time

Now with optimization:

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

The loop has been optimized away. The value calculated is never needed, so the compiler decided to not run it at all

conclusion: If you shoot 3 times into the forest, and hit 2 boars and 1 rabbit, it doesn't mean there a twice as much boars than rabbits inside


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...