Wednesday, December 20, 2006

I started working on Mono.XNA today. For those of you that don't know what it is, it's a cross platform implementation of the Microsoft XNA framework. So in a good few months, it should be possible to write a game once and then play it on MacOS, Windows, Linux, Xbox 360 and if you're really lucky, the PS3 aswell.

At the moment i'm just getting up to speed on the status of things. There's been a little bit of implementation done, and a lot of class stubbing. My aim over the next few days is to run some tools over both the Mono.XNA libs and the Microsoft.XNA libs and start creating a chart of what has been stubbed, what has been implemented and what hasn't been touched yet. This will help both existing devs and new devs figure out what's going on.

I'm just going to finish on one important note which came to my attention when looking at some of the Mono.XNA implemented classes.

String arithmetic is bad!

I came across the following (single) line of code in the ToString() method of the matrix class. While i have to admit, it was technically right, i just had to get rid of it asap. Here's the line:

return ("{ " + string.Format(info1, "{{M11:{0} M12:{1} M13:{2} M14:{3}}} ", new object[] { this.M11.ToString(info1), this.M12.ToString(info1), this.M13.ToString(info1), this.M14.ToString(info1) }) + string.Format(info1, "{{M21:{0} M22:{1} M23:{2} M24:{3}}} ", new object[] { this.M21.ToString(info1), this.M22.ToString(info1), this.M23.ToString(info1), this.M24.ToString(info1) }) + string.Format(info1, "{{M31:{0} M32:{1} M33:{2} M34:{3}}} ", new object[] { this.M31.ToString(info1), this.M32.ToString(info1), this.M33.ToString(info1), this.M34.ToString(info1) }) + string.Format(info1, "{{M41:{0} M42:{1} M43:{2} M44:{3}}} ", new object[] { this.M41.ToString(info1), this.M42.ToString(info1), this.M43.ToString(info1), this.M44.ToString(info1) }) + "}");

Yes, that huge block of code was written in one single line. Now, the main problem with this code is not the fact that it was written in one line, but that the amount of strings and objects generated is HUGE. Far beyond what is needed.

Let me dissect it in a little more detail. As soon as that long line of code is hit, it generates (by my count) 24 instances of the string class and 4 object arrays. Now, as strings are immutable, every time you "add" a string, what happens is a brand new string is created in memory and the old string is dumped, waiting to be garbage collected. So, once you take the string.Format() calls into account, you have a sizeable amount of strings being created per call. The overhead in this is massive!

Now, what should've been done is a StringBuilder should've been used. This would have cut the number of string instances created right down to just 1 per call, along with a single instance of the stringbuilder class.

So lets whip out the benchmarking utils and prove my point.

Original Method:
With the original method being called 10,000 times we had the following stats from my profiler:
Allocated bytes: 21,699,068
Relocated bytes: 17,864
Final Heap bytes: 897,800

This method allocated a whopping 2.11 kB of memory per call to Matrix.ToString(), give or take. That's a *lot* of memory when all you want to create is a 100-150 byte string! The execution time was approximately 4.41 seconds.

StringBuilder Method:
I changed to code to use a StringBuilder with default capacity of 140 bytes and called it 10,000 times. This had the following stats:
Allocated bytes: 6,479,100
Relocated bytes: 8,764
Final Heap bytes: 254,218

As you can see, this method reduced memory allocations by 66% straight off. The average memory allocation per call to Matrix.ToString() is now 0.630kB. Final heap wa reduced from 897kB to a mere 254kB, a 72% reduction in the heap size. The execution time was 2.58 seconds, that's nearly 50% faster. That change took me about 3 minutes to make (once i created an NUnit test to verify that the existing code was right before i ripped it apart ;) ).

The lesson for today, when creating strings, use the StringBuilder class. It helps performance hugely.


RichB said...

Of course there are exceptions to "always use a string builder". And those are in where the number of strings to be combined are 3 or less.

Anonymous said...

I created a very simular test back in the .NET 1.0 days, the difference is huge indeed.

Anonymous said...

In this example I think you're still right to rewrite this function, but you have to ask yourself: does this function need to perform quickly? Matrix.ToString() would typically only be used in debugging, it doesn't matter if it goes slowly

Alan said...

richb: Absolutely right, i should have mentioned that. When only adding a small amount of strings, it doesn't really help much to use a string builder.

paul betts: I did think of that before i made the changes, but you either have the attitude that you're going to write the best code possible, or you don't. I do agree that i can't really see ToString being called often at all, but it was still worth it for those cases when it will be.

Since XNA is such a new project, and so little code has been written, it's now that we need to start making sure things are optimised in ways that are easy to do.

I made a few other performance changes which i never benchmarked. So i'll benchmark those and see what difference they actually made and blog em. These changes i would consider *much* more important than optimising ToString(), but will probably have much less of an impact.

Anonymous said...

I still think it's necessary to optimize from the start on.
Many people use ToString() for debug output, and in a typical game this might get called 60 times per second or even more. This may cause a significant performance hit.

C.J. Adams-Collier said...

Yay for Alan! Thank you for your hard work on Mono.Xna. I'd love to see these charts of API comparisons!

Hit Counter