XNA/C# – StringBuilder to String with no garbage

23 March, 2010 at 9:50pm | XNA / C#

String Garbage

In my day job I’m a bit of a stickler with memory. I’m at times approaching borderline OCD I think with budgets and fragmentation. :) Having a good handle on memory usage on a game is very important; once you start pushing a console’s limits you can cause a lot of headaches down the road if you’re not mindful of things like memory budgets. Forgetting about fragmentation until it’s a big problem is also a bad idea. Once you’ve started bad practices like this on a game, they tend to snowball and you’re in for a hard uphill battle once they become a problem that needs fixing.

With working in C# and XNA now, the big enemy on the memory front isn’t really fragmentation or running out of available memory. The Xbox 360 has plenty of memory for any project I’d try and tackle myself; coder art for the win! The problem is one of performance, more specifically the lack of performance of the garbage collection system. Garbage collection on the 360 isn’t as full featured as on the full .NET Framework on Windows. It lacks the ‘generational’ model that the full Framework offers, meaning a full collection is performed whenever the system deems it necessary to do one.

Having random CPU spikes in your game is a nightmare. More so that in the case of garbage collection on 360 there’s little control other than being able to invoke a collection yourself manually. If you’re generating garbage at runtime during gameplay, you are going to see spikes in your frame times. With just a little garbage generated, and if your game isn’t CPU-bound, you may be able to get away with not giving this any attention. However given my nature with this sort of thing, I want to run a tight ship with this being a potential future headache if I don’t do so.

That said, I think for any sort of menu system I’d have, I’d probably be happy to let it generate garbage and then just call GC.Collect() when we go back to gameplay. Giving it a different treatment entirely to how I’d handle the regular runtime gameplay of the game. It’s all about where it’s important to concentrate efforts to avoid garbage.

Profiling

For profiling any garbage my game might generate I use CLRProfiler for Windows. It gives a nice in-depth analysis of memory usage, it’s pretty much invaluable for dealing with garbage collection problems. It’s almost worth keeping your game always running on a Windows target just so that you can make use of it!

On 360 I use the ‘Remote Performance Monitor’ that comes with the Game Studio SDK. It’s nowhere near as detailed, but it does give a good indication of the severity of any garbage collection issues with your game. Discussing how I use these tools is beyond the scope of this blog post, Google is your friend. :)

The String and StringBuilder problem

The StringBuilder class in C# is the preferred way of working with string manipulation if performance is important. You can avoid it entirely, but you’ll be very likely to end up generating garbage at runtime if you’re exclusively using the string type.

For example, avoid using the ‘+’ operator to concatenate strings. Strings in C# are immutable, meaning they cannot be modified. If you perform this kind of operation, your resultant string will be allocated on the heap. It’s very easy to generate lots of garbage with this sort of code. Something like this monstrosity, which could be run every frame:

string show_world_details =[ FPS :+ GetFPS() + “ P1 Health:+ GetHealth() + “  ];

StringBuilder allows you to work with a mutable string. It provides functionality to concatenate other strings, and other types onto your mutable string. Many of the functions of StringBuilder are completely garbage-free. Many however are not. I’ve a future post in the works which will cover that particular problem in more detail. For now, concatenating other strings onto the StringBulder is garbage-free. So that’s the method I’ll stick to for the sake of this post.

What I wanted to discuss was the conversion of your built up StringBuilder to a string type. There are many functions within the .NET library which only take strings as parameters. Thankfully on the XNA side, the DrawString() rendering routines do take a StringBuilder argument natively. However other functions such as those that write debugging output to Visual Studio or the console, only take string parameters. So in walks StringBuilder.ToString()…

ToString() code

So does calling ToString() generate garbage? My first expectation was that of course it would, it’d just copy what the string is into a new immutable string object created on the heap. This however is not the case, or at least sometimes it isn’t the case. To avoid beating around the bush here I’ll show you the actual source code of the ToString() method:

public override String ToString() {
 
    String currentString =  m_StringValue;
    IntPtr currentThread = m_currentThread;
 
    if (currentThread != Thread.InternalGetCurrentThread()) {
 
        return String.InternalCopy(currentString);
 
    }
 
    if ((2 *  currentString.Length) < currentString.ArrayLength) {
 
        return String.InternalCopy(currentString);
 
    }
 
    currentString.ClearPostNullChar();
    m_currentThread = IntPtr.Zero;
 
    return  currentString;
}

Bit hairy, no? InternalCopy() is the function which will allocate a copy of the string on the heap and return it. The function can actually return the internal string without making any copies. Specifically the first time it’s called, and if the string makes use of at least 50% of the StringBuilder capacity. The ‘m_currentThread’ member being set to zero will effectively mean that the next time any sort of mutable operation is performed on the StringBuilder; be it clearing the string, or appending to it. The StringBuilder will allocate a new string on the heap. Each of the mutable methods of StringBuilder check the ‘m_currentThread’ and ensure that the StringBuilder owns the particular string. The way ToString() works, it’s effectively giving away ownership of that string and will start with a fresh one on the next mutable operation.

The reasoning behind this thread noting, as well as keeping the String returned by ToString() completely immutable, is to keep StringBuilder thread-safe. There’s comments within the code that detail the potential race condition that could occur, which I have omitted above. You can see them in full here.

The other reason for making the copy is in the case that the user is making inefficient use of memory. If we’re only using a tiny portion of the StringBuilder capacity, the .NET authors deemed that it’s more efficient to return a copy instead of making reference to the full big string.

If I want to re-use a StringBuilder object, say for some kind of readout I might want Visual Studio to display in the debugging output window. I’m out of luck garbage-wise. I may avoid generating a copy of the string the first time I call it, but if I’m reusing the StringBuilder, it’s going allocate a new string on the heap for me when I call the next mutable method on it.

The solution

What I wanted was direct access to the string that the StringBuilder works with. Doing this on Windows with ‘unsafe’ code is most likely straightforward, but I want to target 360 so that’s a non-starter. On the 360 you’re bound by the shackles of the Compact Framework, if it’s not in there, you can’t use it.

Thanks to this article though, I was able to track down a method to be able to access that internal string object which the StringBuilder works with. It’s effectively doing something the .NET library authors don’t want you to do, grabbing that private member (oo-er). Thankfully this also works on 360!

Here’s the code:

string my_string = (string)my_stringbuilder.GetType().GetField(
    "m_StringValue",
    System.Reflection.BindingFlags.NonPublic |
    System.Reflection.BindingFlags.Instance ).GetValue( my_stringbuilder );

Reflection isn’t too pretty, eh? But here it’s a nice devious means to an end. Reflection isn’t too hot performance-wise, so I’d recommend grabbing the internal string just the once for the StringBuilder you’ll be working with. Stash it away as a member of a class or something, and you’ll then have the string to pass along to whatever function you wish. Now we’re no longer worrying about the ToString() generating garbage for us; success!

Here’s a bit of sample code:

StringBuilder my_stringbuilder = new StringBuilder( 32, 32 );
string my_string = (string)my_stringbuilder.GetType().GetField(
	"m_StringValue", BindingFlags.NonPublic | BindingFlags.Instance )
	.GetValue( my_stringbuilder );
 
my_stringbuilder.Append( "This " );
my_stringbuilder.Append( "Is " );
my_stringbuilder.Append( "A " );
my_stringbuilder.Append( "Test!" );
 
// my string will be "This Is A Test!"
Console.Write( my_string );
 
// This second append would have resulted in a new heap allocation
// if I'd used ToString() above.
my_stringbuilder.Append( " Yay!" );
Console.Write( my_string );

I’d advise creating your StringBuilder objects with the two integer parameters contructor. As well as preallocating the string, you’ll also be putting a cap on the capacity:

// Creates an empty StringBuilder with a minimum capacity of capacity
// and a maximum capacity of maxCapacity.
public StringBuilder(int capacity, int maxCapacity)

Meaning it’ll never grow in size, or make any more heap allocations after it’s initially constructed. If that were to happen, the string object you grabbed is no longer linked to the StringBuilder. You’d need to redo the reflection call to grab the new string that the StringBuilder owns.

So by using that constructor, this means if you grab the internal string you’re guaranteed to keep the reference to the StringBuilder’s mutable string forever. The one key exception here though is if you work with the StringBuilder on another thread. In that case, you’ll be subject to the same issues as before.

I’ll revisit StringBuilder here again in future, to cover some of it’s other shortcomings with regard to generating garbage.

References

Addendum: XNA 4.0

Under XNA 4.0 the technique described doesn’t work for Windows Phone 7, nor for PC Windows. It does however still function correctly for the Xbox 360.

See this blog post for more information about the state of play under XNA 4.0.

Comments

Pingback from gavpugh.com… » XNA/C# – Avoiding garbage when working with StringBuilder
Time: April 1, 2010, 7:23 am

[...] my previous coding post, I spoke about some issues with converting a mutable StringBuilder string back to a regular [...]

Comment from Stephen Styrchak
Time: April 1, 2010, 11:07 am

Why does this article imply that unsafe code isn’t allowed on Xbox 360 or the .NET Compact Framework? Unsafe code is perfectly legit on Xbox 360.

Comment from Gavin
Time: April 1, 2010, 11:12 am

Thanks! That was news to me, I just assumed given that facilities such as stackalloc() and what have you aren’t allowed (http://forums.xna.com/forums/p/11504/61137.aspx), that unsafe code was out of the question.

Comment from Jim Eddy
Time: April 24, 2010, 10:07 am

This article is great. Thank you for it. Is there any danger that the keepers of .NET will consider this an insult to the integrity of StringBuilder and close this back door?

Comment from Gavin
Time: April 27, 2010, 12:33 pm

Cheers, you’re welcome!

The article in which I found the reflection technique was dated back in 2002, for I’d presume the initial version of the .NET libraries. Considering it’s decently well publicized, and that Microsoft have likely known about it throughout their updates to .NET over the years… I think it’s pretty safe.

I’d also imagine that disallowing private/protected members from being grabbed via reflection, would likely break a lot of people’s ‘legitimate’ reflection systems. It’d force many to declare everything as publically accessible, which would defeat the point of using the access modifiers in the first place.

Comment from Dave
Time: May 10, 2010, 12:20 pm

I am just in the process of optimizing my game and reducing the allocations in run-time. It’s working great thanks to this article. I am also using your other StringBuilder article about garbage-free concat and I removed nearly all of my String garbage. Thanks!

Comment from Gavin
Time: May 17, 2010, 9:52 am

Thanks, glad it was useful to you!

Nice blog btw: (http://www.frozax.com/blog/) … I’d stumbled across it a few weeks ago. The profiler articles are very cool; yours looks pretty comparable to the profilers on a few AAA console game engines I’ve worked with.

Pingback from 3 Simple Tips to Avoid Memory Allocations with XNA/C# | Frozax Games Dev Blog
Time: May 21, 2010, 2:30 pm

[...] awesome tips (and source code) about StringBuilder on Gavin Pugh’ blog. Especially this and this. You have everything you need [...]

Comment from Matt
Time: September 21, 2010, 4:23 am

It seems to me like the internals of StringBuilder have changed in the last couple of months or something. Trying to get the m_StringValue field from typeof(StringBuilder) as above, I’m getting null on PC (on compact framework 4 it still works), and looking at StringBuilder in reflector, I’m not seeing the member at all and the actual ToString implementation appears to be allocating a new string every time it’s called, and copying the contents of an inner char array into it. Is this code still working for you?

Comment from Matt
Time: September 21, 2010, 4:43 am

Actually, I spoke too soon.. While the field does exist in CF4, calling GetValue on it results in a FieldAccessException.

Comment from Gavin
Time: September 21, 2010, 8:31 am

Thanks for the headsup Matt! I’ve not yet tried this stuff under C#/.Net 4.0. Hopefully in the near future I’ll get a chance to see what’s up here.

Out of interest, what’s your platform for CF4? Windows Phone, something else? After a quick Google search I’m reading a few conflicting posts about what version of the CF is used for the Xbox 360 under the newly released XNA4.

Poor form by Microsoft if this has been deliberately blocked. For working with the poor-man’s GC on Xbox 360, for certain projects it can be pretty invaluable.

Comment from Gavin
Time: September 21, 2010, 9:55 pm

Had a go at this stuff, with the newly released XNA 4.0 installed. I’m seeing new Windows projects using the ‘System’ assembly version 4.0.0.0, and Xbox 360 projects using 2.0.5.0.

For me, Xbox 360 works fine with the above code in this article. Windows however, does not. I found this article which details the changes made in .NET 4.0 to StringBuilder:
http://www.nesterovsky-bros.com/weblog/2010/08/25/StringAndStringBuilderInNET4.aspx
It is indeed possible to access the interior char[] of the new StringBuilder with the same reflection method in my article. However, it’s of char[] type, NOT System.String. There’s a technique I played with which still lets you use System.String… I’ll write about it on here soon.

Comment from Matt
Time: September 22, 2010, 12:46 am

Hi Gavin, we’re on WP7 (check out my blog for the project I’m on) which is of course XNA4, I don’t know if the XNA team has brought Xbox up to speed with that yet. I saw the internal char array in reflector, but the change of having have to copy the contents into a pre-allocated string’s internal char array- and considering this would only solve the problem on PC which is just a test platform for us anyway- meant it wasn’t a worthwhile change given our timeline. On Phone, and I assume soon on Xbox too, it looks like the security model may have been tightened up so you can’t invoke private member functions through reflection (which I suppose is more correct-but sucks in this case).
Your articles on perf have been great by the way, thanks a stack :)

Pingback from XNA/C# – StringBuilder changes in XNA 4.0 « gavpugh.com
Time: December 21, 2010, 11:00 am

[...] one was inspired by some comments on a previous blog post of mine: “StringBuilder to String with no garbage”. A developer named Matt, who was targeting Windows 7 Phones, pointed out that this particular trick [...]

Comment from Brian Lawson
Time: February 19, 2011, 6:50 pm

Awesome stuff. Thanks for sharing. I’ve been employing this technique for the past few weeks with great results.

However, the past few days I’ve been making the necessary changes to put the render loop on its own thread and today I encountered something I don’t understand. It seems like the cached String that references the StringBuilder’s internal String, somehow changes. Is that possible? Is there something thread specific with respect to the reflection, etc? All attempts by the render thread to reference a cached String that was cached on the main thread, result in seeing the last String that was built on the main thread.

At this point I’m just kind of grasping at straws and unfortunately, it’s the only thing holding me up from having garbage free threaded rendering. Any ideas?

Thanks.

Pingback from No more memory allocation! | Michael Pullman Games
Time: February 19, 2011, 11:12 pm

[...] that StringBuilder isn’t good enough to completely avoid memory allocations.  According to this guy (and confirmed on CLR Profiler), StringBuilder’s ToString() method will return an internal [...]

Comment from Gavin
Time: February 20, 2011, 9:40 pm

Hi Brian,

Glad this was useful to you!

I don’t think there’s anything thread-specific with regard to the reflection part. The reflection in this case just gives you a reference to that internal string. I’d imagine the problem is likely to be you mutating the contents of the StringBuilder in two different threads. If you look at the source here:
http://labs.developerfusion.co.uk/SourceViewer/view/SSCLI/System.Text/StringBuilder/
You’ll see that when working with the string, the function GetThreadSafeString() is called, which will allocate a new internal string if a different thread than created that string attempts to mess with it.

In my experience I’ve just used StringBuilders across threads with TLS, so each has their own copy, see here:
http://www.gavpugh.com/2010/11/29/xnac-thread-local-storage-on-xbox-360/
I’ve not tried writing to them across different threads.

If you absolutely have to have multiple threads modifying the same StringBuilder, it might be an idea to use unsafe code and poke at the char[] array the string references directly.

Cheers.

Pingback from » Eureka! Garbage-free string manipulation in Unity!Defective Studios Devblog
Time: May 28, 2014, 7:34 am

[…] After some (more) research, I finally came upon the solution! Oddly enough, it took finding two different articles, both from the same blog: http://www.gavpugh.com/2010/04/05/xnac-a-garbage-free-stringbuilder-format-method/ http://www.gavpugh.com/2010/03/23/xnac-stringbuilder-to-string-with-no-garbage/ […]

Write a comment



 (not shown when published)



 (comments will appear after moderation)

*