Monday, October 3, 2011

How much faster is multiplication than division?

This is one of those things I learned a long time ago when I used to write a lot of animations, games, etc -- multiplication is faster than division. Intel has a reference manual that delves into this much deeper. But I can't remember ever testing this to see exactly how much of a performance gap there was. I figured division might be 2 or 3 times slower. In fact, the difference is much greater than that.

I performed a little benchmark in C# on my AMD 3.0GHz quad core processor to see what's what. As always, I performed my test with a release build of a console application and I ran it without debugging.

Here's my code:

static void Main(string[] args)
{
	Stopwatch sw = new Stopwatch();

	int iterations = 20000000;
	double num;

	sw.Start();
	for (int i = 0; i < iterations; i++)
	{
		num = 1024;
		num /= 2;
		num /= 2;
		num /= 2;
		num /= 2;
		num /= 2;
	}
	sw.Stop();
	Console.WriteLine("Division: " + sw.ElapsedMilliseconds + " ms");

	sw.Reset();
	sw.Start();
	for (int i = 0; i < iterations; i++)
	{
		num = 1024;
		num *= 0.5;
		num *= 0.5;
		num *= 0.5;
		num *= 0.5;
		num *= 0.5;
	}
	sw.Stop();
	Console.WriteLine("Multiplication: " + sw.ElapsedMilliseconds + " ms");
}

And here are the results:

So multiplication is 41x faster in this case. This is going to vary depending on the processor, of course. But it's somewhat surprising that the compiler doesn't optimize for this. I mean, dividing by 2 and multiplying by 0.5 is exactly the same thing, isn't it? Couldn't the compiler automatically convert "num /= 2" to the much faster "num *= 0.5"? In any case, it obviously doesn't do this and we as programmers should use multiplication instead of division whenever possible.

UPDATE (October 8th, 2011) So this is crazy. I just changed the platform target from "Any CPU" to x86 and division is now much faster. In fact, it's about the same speed as multiplication. Incidentally having the "Optimize code" option checked actually slows down multiplication in this case. Definitely some weird stuff going on. But it would appear that there's something about running as a 64-bit app which is negatively impacting performance on my 64-bit quad core AMD CPU.

3 comments:

Distantsound said...

I ran the same code with the same debug settings and the times were roughly the same.

Division: 26ms
Multiplication: 20ms

I have a 3ghz i3 quad core. Could the processor be the difference?

Distantsound said...
This comment has been removed by the author.
Steve Wortham said...

Strange. Perhaps the .NET Framework is exploiting an optimization on the Intel chip and not for AMD. I wouldn't expect such a drastic difference, but there you go.