Differences in division and multiplication vs bit shifting

Question

DISCLAIMER

I do not want to know when or if to use shift operators in my code, I am interested in why multiplication is faster than shifting bits to the left whereas division is not.

As I was just wandering around SO I came across this question regarding efficiency and speed of division and bit shifting. It basically states that although one might save a few seconds when performing bit shifts on powers of 2, it is not some difference one has to worry about.

Intrigued by this I decided to check how much faster bit shifting in C# actually is and realised something strange:

Bit shifting instead of dividing is faster, as I expected, but the "normal" multiplication method is faster than bit shifting.

My question is simple: Why is the multiplication of two numbers faster than bit shifting, although bit shifting is a primitive operation for the processor?

Here are the results for my test case:

           Division: | Multiplication:
Bit shift:   315ms   |   315ms
   normal:   406ms   |   261ms

The times are the averages of 100 cases with each case consisting of 10 operations per number on 10000000 random positive numbers ranging from 1 to int.MaxValue. The operations ranged from dividing/multiplying by 2 to 1024 (in powers of 2) and bit shifting from 1 to 10 digits.

EDIT

@usr: I am using .NET version 4.5.1

I updated my results because I realised I only computed a tenth of the numbers I stated... facepalm

My Main:

static Main(string[] args)
{
    Fill(); // fills the array with random numbers
    Profile("division shift:", 100, BitShiftDiv);
    Profile("division:", 100, Div);
    Profile("multiplication shift:", 100, BitShiftMul);
    Profile("multiplication:", 100, Mul);
    Console.ReadKey();
}

This is my profiling method:

static void Profile(string description, int iterations, Action func)
{
    GC.Collect()
    GC.WaitForPendingFinalizers();
    GC.Collect();

    func();

    Stopwatch stopWatch = Stopwatch.StartNew();
    for (int i = 0; i < iterations; i++)
    {
        func();
    }
    stopWatch.Stop();

    Console.WriteLine(description);
    Console.WriteLine("total: {0}ms", stopWatch.Elapsed.TotalMilliseconds);
    Console.WriteLine("  avg: {0}ms", stopWatch.Elapsed.TotalMilliseconds / (double)iterations);
}

The Actions containing the operations are structured like this:

static void <Name>()
{
    for (int s = 1; s <= 10; s++)    /* for shifts */
    for (int s = 2; s <= 1024; s++)  /* for others */ 
    {
        for (int i = 0; i < nums.Length; i++)
        {
            var useless = nums[i] <shift> s;    /* shifting  */
            var useless = nums[i] <operator> s; /* otherwise */
        }
    }
}

nums is a public array containing 10000000 ints, which is filled by the Fill() method.

@SLaks Still even then I would expect it to be as fast as bit shifting and not faster. — ThreeFx, Jun 15 '14 at 18:32
Multiplication is also a primitive operation for the processor. — Oliver Charlesworth, Jun 15 '14 at 18:32
You're probably measuring wrongly; microbenchmarks are hard. — SLaks, Jun 15 '14 at 18:32
@Slaks Testing 50000000 random numbers yields a clearer result: about 195ms for bit shifting and about 175ms for multiplication. — ThreeFx, Jun 15 '14 at 18:38
You're probably still measuring wrongly. Beware the JITter. http://www.yoda.arachsys.com/csharp/benchmark.html — SLaks, Jun 15 '14 at 18:41
*"might save a few seconds when performing bit shifts"*... you are still using an i386? — , Jun 15 '14 at 18:46
The idea that shifting is faster than multiplying was true in some badly optimized C compilers on 1970s hardware. Let the optimizer do it's job. — Eric Lippert, Jun 15 '14 at 18:54
I'm not convinced about the compiler optimization argument, since we're using randomly-generated multiplicands here. I'm more inclined to believe that the multiplication is amortized due to instruction-level parallelism (superscalar pipelining). — Douglas, Jun 15 '14 at 18:56
Post the C# code and the generated x64 code. Release mode without debugger. What .NET version? — usr, Jun 15 '14 at 19:56
This kind of micro-optimizations are as good as out of reach for assembly programmers on modern hardware. From C# there are 2 compilers in front of that pipelined CPU. With _although bit shifting is a primitive operation for the processor_ you're already a mile off. — H H, Jun 15 '14 at 22:16
@HenkHolterman Thank you that is (finally) a comment which actually answers the question I asked. — ThreeFx, Jun 15 '14 at 22:17
Shifts have extra overhead in C#, explained in [this answer](http://stackoverflow.com/a/9906638/17034). Not running with the optimizer enabled is a standard benchmark mistake. Use Agner Fog's instruction timing manual to get insight. Cycle times are an estimate: shifting a memory value by an arbitrary amount roughly takes 4 cycles, multiplication takes 1, dividing takes between 11 and 18 cycles. These big differences are blurred by the for(;;) loop overhead. — Hans Passant, Jun 15 '14 at 22:33

score 1 · Accepted Answer · edited Jul 14 '17 at 17:14

To sum up the answers already mentioned in the comments:

Multiplication, as well as bit shifting, is faster because is a native operation for the CPU too. It takes one cycle while bit shifting takes about four which is why it is faster. Division takes something between 11 and 18 cycles.
Using C# I cannot get close enough to the CPU to get diagnostically conclusive results because many optimizations take place between my code and the CPU.
Also, microbenchmarking is hard and can produce erroneous results, which also can happen because of the above mentioned reason.

If I forgot anything, please comment and tell me!

Differences in division and multiplication vs bit shifting

DISCLAIMER

EDIT

1 Answers1