Which operator will run faster among << and * in loop?

Question

I am learning c/c++ code optimization. Writing a simple for loop program, which part of for loop will faster than other w.r.t << and * operator. Code snippet below.

#include <iostream>
#define MAX 1000
int main()
{
int i;

for(i=1; i<= MAX; i= i<<1)
    {
    std::cout<<i <<" ";
    }   

for(i=1; i<= MAX; i= i*2)
    {
    std::cout<<i <<" ";
    }

return 0;
}

Answer 1

First, here is the assembly of using the multiplication operator (I added the comments):

.LC0:
        .string " "
main:
        pushq   %rbp
        movl    $10, %ebp          // Part of loop
        pushq   %rbx
        movl    $1, %ebx           // Part of loop
        subq    $8, %rsp
.L2:
        movl    %ebx, %esi
        movl    std::cout, %edi
        addl    %ebx, %ebx         // Part of loop
        call    std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
        movl    $1, %edx
        movl    $.LC0, %esi
        movq    %rax, %rdi
        call    std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
        subl    $1, %ebp           // Part of loop
        jne     .L2                // Part of loop
        addq    $8, %rsp 
        xorl    %eax, %eax
        popq    %rbx
        popq    %rbp
        ret
        subq    $8, %rsp
        movl    std::__ioinit, %edi
        call    std::ios_base::Init::Init()
        movl    $__dso_handle, %edx
        movl    std::__ioinit, %esi
        movl    std::ios_base::Init::~Init(), %edi
        addq    $8, %rsp
        jmp     __cxa_atexit

And here is the assembly using the shift operator:

.LC0:
        .string " "
main:
        pushq   %rbp
        movl    $10, %ebp
        pushq   %rbx
        movl    $1, %ebx
        subq    $8, %rsp
.L2:
        movl    %ebx, %esi
        movl    std::cout, %edi
        addl    %ebx, %ebx
        call    std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
        movl    $1, %edx
        movl    $.LC0, %esi
        movq    %rax, %rdi
        call    std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
        subl    $1, %ebp
        jne     .L2
        addq    $8, %rsp
        xorl    %eax, %eax
        popq    %rbx
        popq    %rbp
        ret
        subq    $8, %rsp
        movl    std::__ioinit, %edi
        call    std::ios_base::Init::Init()
        movl    $__dso_handle, %edx
        movl    std::__ioinit, %esi
        movl    std::ios_base::Init::~Init(), %edi
        addq    $8, %rsp
        jmp     __cxa_atexit

Which is exactly the same (I only compiled with GCC 5.3 for x86 using -O3, so this may not be the case with other compilers and other architectures).

After looking at the link posted in the comments by Chris, the automatic highlighting makes it seems as if the shift operator requires additional instructions:

subl    $1, %ebp
jne     .L2
movl    $10, %ebp    // Actually not part of loop
movl    $1, %ebx     // Actually not part of loop

Compared to the multiplication, which is:

subl    $1, %ebp
jne     .L3

Which is different to the original assembly I posted (since both were exactly the same).

As mentioned in the comments by Revolver_Ocelot, the instructions

movl    $10, %ebp    
movl    $1, %ebx     

Are just setting the counters for the next loop, so the loop components actually compile to same assembly (for this compiler and architecture), as was shown by the separate comparison.

Update: Based on Flikk's comment saying the assembly will be different, here is an unoptimised version, which shows that they are the same.

Answer 2

You are trying micro-optimisations. When I started out the saying was that beginners save microseconds, real programmers save milliseconds. Nowadays beginners save nanoseconds, real programmers save microseconds :-)

You are outputting i to std::cout. At that point, how i has been calculated is so totally irrelevant because the output takes a few thousand times longer.

Now let's look at what the program does. At some point you get an overflow, which gives you undefined behaviour, which means anything can happen. Correct programs are thousand times more important than fast ones. So any attempt at optimisation is absolutely pointless when your code is already broken.

Now let's look at what you are doing. Ask yourself: Does the compiler figure out what you are doing? The compiler will obviously see that each variant multiplies i by 2. The compiler will then use the fastest way to multiply i by 2, whatever method that is. Probably adding i to itself :-) So what you are doing is again pointless; the compiler is more clever than that.

Back to micro-optimisations: They are utterly ineffective, because the compiler is ten times better at micro-optimisations than you are. Real programmers don't try to make an operation a tiny weeny bit faster; they develop data structures and algorithms that take a lot fewer operations to begin with! They measure first to find out what takes time and optimise where it counts instead of trying to optimise random bits. And they measure afterwards to see if any attempt at optimisation actually worked.

Answer 3

I can give you a simple idea which will help you in judging which is faster between i *= 2 and i = i<<1.

Update MAX = 10¹⁸ and use long long int as data type. Now use time() function to measure the running time of both the for loops independently. And just find out the difference in running time.

Note : Since there will be at max 60 iterations so it might be possible that the difference in the running time would not be comparable so in this case you can use BigInteger library.

Result : Bit operations are faster.