Performance: Don't rely on the C# compiler to optimize your math...

The C# compiler generally does a good job of optimizing your math, but it isn't always the case. I was going through some interesting code in the .NET Terrarium where we approximated the magnitude of a vector by using a Taylor series. What I found strange was that the true magnitude and the approximation were coming up to the same speed.

time(Math.Sqrt(x*x + y*y)) = time(absX + absY - absX / 2)

I always thought that numeric literals involved in division would be turned into multiplication instead. Multiplication is a hell of a lot faster than division. We can drastically increase the speed of the function by taking note of this.

time(absX + absY - absX * 0.5D) // This is about 3 times faster now

Note there is some extra work involved in the approximation where we pick absolute values, etc... And there is a branch instruction that controls whether or not we subtract half of absX or half of absY... We can go one step further to simplify the equation and get rid of one of the subtractions.

time(absX * 0.5D + absY), time(absX + absY * 0.5D)

The function will be selected depending on the branch instruction. The morale of the story is that at some point we had to do some testing and find out that the Taylor series function was faster at computing the magnitude of the vector. However, at some point later the JIT changed, or maybe something else changed and all of the performance of the function was lost. Of course we based the performance on an assumption of optimization instead of a real optimization. By simply changing the algorithm a bit we get all of the performance back.

The really sad thing is that the approximated magnitude caused some major issues for people playing the game. In fact we eventually created a series of properties so you could get the approximate magnitude but also the real magnitude. Too bad the engine continued to use the slow approximate method rather than upgrading to the more accurate measure.

Published Sunday, September 05, 2004 1:01 AM by Justin Rogers
Filed under: ,

Comments

Sunday, September 05, 2004 7:38 AM by Denny Figuerres

# re: Performance: Don't rely on the C# compiler to optimize your math...

much like some different code I am tuning...

in my case it's a webservice that does a an sql transaction.

I can call a ws func() that does a sql open conn, exec and close in less than 1 second.

avg is about 00.035 or 1/3 of one second.

but the code for the sql trans call is having poor runtime perf. it's based on code that worked as a direct sql in the app so I am looking for some induced gc from adding strings.

and a possible chnage to an array that was an arrqay of strings that was sorted.

may chnage how it gets done as It may be better as an array of Byte or short int.

just cause the old version worked in one case when you chnage the code you need to test for new problems....
Wednesday, September 15, 2004 7:50 AM by Steve

# re: Performance: Don't rely on the C# compiler to optimize your math...

Where can I get more information about optimizing mathematical function?
Wednesday, September 15, 2004 6:56 PM by Justin Rogers

# re: Performance: Don't rely on the C# compiler to optimize your math...

Steve: Great question, and really no answer. You have to check the small blogs and various resources tediously and slowly build up a list of gems that can help you make your math that much faster.

Math optimizations come in a number of different formats, so you might miss some of them. For instance, the above is a compiler optimization or lock thereof. To us, division and multiplication mean the same thing, to the computer it is something drastically different.

Then there are ways to throw out various portions of the work. Something like n!/(n-1)! actually means n divided by 1 or n. The lower expansion cancels out all but one term in the upper expansion.

And finally there are preallocation otpmizations. Here you move math out of work loops and do all of the computations before hand. sin/cos look-up tables were brilliant at this back in the 90's in many 3D DOS games. I also posted a discrete fourier transform algorithm in the physics section that originally had 10 or 15 mathematical operations in various levels of the loop structure and I was able to remove most of them entirely, remove them to a parent loop so they were evaluated less frequently, or move them outside of the loop so they are only calculated once.

Asking questions never hurts. If you have specific math that you think might make a good posting, let me know and I'll talk about it. Contact me through the blog contact link in the upper left. I find it hard to continuously come up with content that people like.
Thursday, September 16, 2004 4:02 AM by Steve

# re: Performance: Don't rely on the C# compiler to optimize your math...

Thanks for your offer. I'll take a rain check on it. I'll get in depth of genetic algorithms, neural net algorithms, etc. Much place for math optimization.
I am currently working with GDI+ which don't let much place for significant optimization I think. In most cases the limits are the internal GDI+ methods.
Getting back to the division/multiplication example: I checked it out. Using 32-Bit-Int results a speed ratio of 2:1. Using a long value results 1:1. The speed enhancement is gone. It might be easy to understand if I whould know the cpu works. :-)
Thursday, September 16, 2004 9:00 PM by Justin Rogers

# re: Performance: Don't rely on the C# compiler to optimize your math...

GDI+: There are plenty places for performant math algorithms when working with GDI+. Check the Math series that I've posted over the month of August/September and you'll see some great uses of math in GDI+ in terms of custom layout logic and path drawn text.

Mult vs Div: Since I didn't post a full testing scenario there are a number of issues that could cause a false or different reading. The JIT often optimizes based on context and at times even optimizes out unused calculations.
Wednesday, September 29, 2004 10:48 AM by Steve

# re: Performance: Don't rely on the C# compiler to optimize your math...

Mhhh, I got a hint to change my VisualStudio configuration from "debug mode" to "release mode". The result is very interesting. Division is now 2 times faster than multiplication. From now on I always let the compiler optimizing my code. :-)
Wednesday, September 29, 2004 11:58 AM by Justin Rogers

# re: Performance: Don't rely on the C# compiler to optimize your math...

I'd be very skeptical of results where division is actually 2 times faster. If you are using literals in division, then it is possible the JIT is optimizing base 2 divisors into shift operations. Ideally it would do the same thing for multiplication.

There are other circumstances as well, including the intermediate result modes. It is actually possible to run benchmarks where the FPU is scheduled allowing other instructions to run concurrently, kind of like a freebie. If you aren't storing the result of the div/mul in your test, or you aren't using it, then the JIT might just run your branch logic (looping construct) while the division is running and be ready for the next division by the time the instruction has completed. Even worse, if you don't use the result of the division, you may not be doing any work at all, since the JIT can remove code that doesn't appear to be doing any work. My recommendations are:

a) store the result in a variable scoped outside of the loop.
b) use the variable in a method call, such as Console.WriteLine so the JIT knows the value is going to be used.
c) never compare using absolute timings, but instead relative timings

You already appear to be doing c. The point here is that the JIT seems really unstable. I run performance tests all day long and I my results are constantly fluctuating, even with small changes to the source. Often times growing a method by a few instructions will drastically change the performance (drastic being +/- 5% or more).
Wednesday, September 29, 2004 3:55 PM by Steve

# re: Performance: Don't rely on the C# compiler to optimize your math...

Ok, I will do some more tests tomorrow and consider your recommendations. Thanks for your help, I have less experiences testing performance of source code. I will sent you the source code to analyse it, if I'll get clear results.
Tuesday, October 23, 2007 9:48 AM by Mark

# re: Performance: Don't rely on the C# compiler to optimize your math...

What happens if you use 2.0 instead of 2 as your division literal?

Friday, January 04, 2008 3:48 AM by sim

# re: Performance: Don't rely on the C# compiler to optimize your math...

I am just wondering if any one knows how to use distcc with visual studio c# ?

I want to programattically change the compile command that the Visual

Studio creates so that it includes distcc

Leave a Comment

(required) 
(required) 
(optional)
(required)