Gavin Pugh - A Videogame Programming Blog

So, another entry in this StringBuilder and garbage series… This time I’m exploring the Format() method, and implementing a new alternative that does not generate any garbage. The existing AppendFormat() method on StringBuilder generates a significant amount of garbage.

So in what way does the .NET one generate garbage? Well, the parameter type is ‘object’, so you’ll get boxing and unboxing of value types. Since integers and floats are pretty oft-used with Format(), that’s not good news. With CLRProfiler I also see temporary allocations made in ‘String::ToCharArray()’, and ‘String::CtorCharArrayStartLength()’. There’s also more garbage if you use more than three arguments; for that it requires a temporary array to be created.

All in all, it’s not a pretty picture if you want to avoid garbage collections in your game.

Variable arguments

The AppendFormat() method takes a string parameter, then a series of parameter arguments. The amount of these can vary, and they can be of a different types too. So how best pass these in? Well, there are a number of different methods. Take a look at the ones StringBuilder provides as standard:

• StringBuilder AppendFormat( string format, params object[] args );
• StringBuilder AppendFormat( IFormatProvider provider, string format, params object[] args );
• StringBuilder AppendFormat( string format, object arg0 );
• StringBuilder AppendFormat( string format, object arg0, object arg1 );
• StringBuilder AppendFormat( string format, object arg0, object arg1, object arg2 );

Each of these uses object params. Object params are subject to boxing and unboxing with value types. Since I’d want to pass integers and floats through, this isn’t good. The other thing I noticed was that array parameters using the ‘params’ keyword cause a temporary allocation too. Even without using the object type, take this simplified example:

public void TestMethod( params int[] args );

Any call to this method generates garbage. The ‘params’ keyword essentially converts any params you might specify into an array. The array of integers in this case is allocated as a temporary and then destroyed. The same thing happens when using class types too, not just value types. A different tact is required here.

There were two approaches I explored to support a variable set of arguments, without generating garbage. One of these I went with and will explain now, the other one I explain later on this article in the ‘Things to try’ section. The approach I chose uses generics, and unfortunately a method is required to be implemented for each number of parameters I’d want to support. Other than that though, it’s a really good fit for this problem.

The implementation

So, there are two main problems to solve here:

• Support a variable number of arguments of arbitrary types
• Be able to use these types, perform any conversion required and concatenate them onto a StringBuilder

For the former, I’m just using generics. For each number of parameters I need to support, I’ll need to write a new method. This multiple versions of the same method, but with a different number of parameters isn’t too pretty. It reminds me of C++ template abuse, stuff like the sig_slot library.

But here it gets the job done, and it’s kind of your classic C# stuff in a way. There’s no support for default parameters in C#. So for different arguments you generally have to have wrapper methods to support different sets of parameters.

Casting generics is not like C++. My first thought was something like:

static public void FormatArgument( StringBuilder string_builder, T arg )
{
    if ( arg.GetType() == typeof(int) )
    {
        int int_arg = (int)arg;
        string_builder.Concat( int_arg );
    }
}

But the straight casting like this is not allowed. There does seem to be a couple of methods to convert types though. At least these were the two I found, both these examples are with integers:

• Convert.ToInt32( arg )
• Arg.ToInt32( System.Globalization.NumberFormatInfo.CurrentInfo )

Both have their downfalls. Convert.ToInt32() generates garbage, which makes it unusable for my purpose. The latter one though doesn’t generate garbage, but it is only available on types that implement IConvertible. Fortunately all the types I wanted to use (string, int, float) all implement IConvertible. However some other types that would be nice to support, such as Math.Vector don’t. I went with this method, and in turn had to limit the arguments to IConvertibles using the ‘where’ keyword.

That’s about it for the nitty-gritty on some of my decisions. The rest of the code is just a classic char-by-char over the formatted string. It’ll look for the ‘{‘ open curly bracket character and then use the Concat() methods from my previous article to push in the parameters. So, here’s the code:

StringBuilderExtFormat.zip

Performance

I was definitely curious as to how my code performs. There’s certainly more scope for optimization, but I’m not keen on spending time on it unless it’s something to worry about. Using the Stopwatch class I measured the runtime of this piece of code:

string_builder.ConcatFormat(
    "Test {0:0.0000} Test {1:X} Test {2} {3}",
    3.45111111f, 0xBEEF, 12345678, "Hello World" );

A nice taxing formatted string with varied parameters. Here’s a table of the performance figures, they are measured from a loop calling this method 1,000,000 times.

 
For both times and garbage, smaller is better! 🙂

The notable thing is that the native AppendFormat() performs the same when optimized or not. I’m not entirely familiar with the in’s and out’s of .NET assemblies just yet. But I do wonder if I could put these routines in a separate library. Then whether I can set things up so that they are jit-ed, regardless of whether my main code module is ran in the debugger or not. Not something I’m too interested in right now, but just throwing it out there. I’m sure google is my friend on this one!

Anyhow, I’m happy that on the final build of the game I’ll have better performance than the stock .NET method. Also with significantly less garbage of course. There’s plenty of scope for optimization on my methods too, they’re pretty much a naïve first-go in all cases. With a little time and effort I think a good chunk could come off these times. Knowing it performs well though is good enough for me right now, I’ll give it more attention down the road if I need to.

Things to try

A Format() that does everything?

Obviously the version I’ve written doesn’t offer anywhere near the same fully-featured functionality as the stock .NET Format(). I don’t envision myself needing any more features for a game though to be honest. If I did come across something I wanted it wouldn’t be too much of a pain to implement I’m sure. But, take a look at the .NET docs, and the AppendFormat() source code:

http://labs.developerfusion.co.uk/SourceViewer/view/SSCLI/System.Text/StringBuilder/

The AppendFormat() in StringBuilder is the one that is also used by System.String and I’d assume the rest of the .NET code. Using this source and any documentation for the formatting specifiers, it’d be possible to implement the same level of functionality but using my techniques to avoid garbage. Quite a task though I’d think!
 

Supporting arbitrary parameter types

Another thing to give a go, is a second method of variable arguments I played around with. A method that doesn’t use generics, but instead uses a base class. For an example, here’s a method prototype with two arguments:

public static StringBuilder ConcatFormat( this StringBuilder string_builder,
    String format_string, FormatArgument arg1, FormatArgument arg2 )

The ‘FormatArgument’ class is an abstract base class. What you’d do is implement subclasses for each supported type, i.e.:

public class FormatArgumentInt : FormatArgument

Then have a virtual method for appending the type into the StringBuilder. The crux of this whole technique is in the use of implicit constructors. So that depending on the argument you specify to ConcatFormat(), you’ll get it converted into a new FormatArgument type. Here’s an example:

public static implicit operator FormatArgument( int value )
{
    FormatArgumentInt arg = new FormatArgumentInt( value );
    return arg;
}

Hey, this example allocates a temporary class therefore generates garbage when used? Indeed it does, but you can use a pool container to deal with this. Pre-allocating all of these and dealing out pool items when they’re created solves the garbage issue. You’ll also need to manually dispose of them and add them back to the pool.

It’s a lot of work. The big upside is that you can support any types, such as Math.Matrix and Vector. It’d be cool to be able to use those if you’re using Format() for debugging. In my experiments though, performance wasn’t too hot, it was in the region of 1.5-2 times slower than the generics method I detailed earlier. The code also becomes a lot more unwieldy; the generics method looked like a work of art by comparison!

Maybe there’s a way of using the generics method on arbitrary non-IConvertible types? Without incurring garbage on the conversions too of course.
 

Printf

I like the positional arguments of C#’s Format. C/C++’s printf() stipulates that the argument list has to be used in the same order that the params are specified in the formatting string. This makes the .NET way useful for localizations particularly, where something like:

Player {0} got {1} points!

Could become:

Allez {1} punts spiele {0}!  << Just a made-up foreign language

Essentially the translation requires those parameters to appear in a different order. With printf() it’s painful to do this correctly.

That said though if you’ve used printf() for over a decade like I have, switching to Format() might not be quite as fun. So why not implement printf() in C#? It’s really only a minor modification over the code I provide above. I was a little tempted myself, but I really want to stick with doing things the C# way for now. 🙂

References

• http://msdn.microsoft.com/en-us/library/system.iconvertible.aspx
• http://msdn.microsoft.com/en-us/library/system.convert%28VS.71%29.aspx
• http://blog.stevex.net/string-formatting-in-csharp/
• http://www.codeproject.com/KB/cs/Csharp_implicit_operator.aspx