Skip to content

Pointing Out the Obvious for Strings

May 1, 2011

Recently I discovered that the performance of an application I work on consumed a significant portion of CPU in the garbage collector (consistently over 10% and sometimes up to 60% for sustained periods of time). So using Visual Studio, I profiled the memory use to determine why the garbage collector was so busy.

The offending function that made the most memory allocations came from a 3rd party, open-source library (I won’t name the guilty library here). The function does the following:

string AddChars(string str, int num, char ch, bool isLeading)
{
    for (int i = num - str.Length; i > 0; i--)
    {
        if (isLeading)
        {
            str = ch + str;
        }
        else
        {
            str = str + ch;
         }
    }
    return str;
}

This function pads either the front or end of a string with repeated characters. It makes sense that this is inefficient, because it creates a new string for every character appended.

This function commits two crimes that I hope not to find in an open-source library, because often others depend on these libraries to help them: first it forgets that because strings are immutable, string append operations can be expensive, and second it overlooks other built-in string functions that manage strings more efficiently.

The two methods for dealing with multiple string appends that come to mind are the StringBuilder class, and the String.Format function. StringBuilder applies all changes to a string in a single buffer, so you can manipulate it multiple times without creating a new string object for each operation. It manages the buffer length used to build the string by growing exponentially as it runs out of room.

String.Format allows a string to be constructed from multiple substrings, optionally with extra formatting parameters. Under the hood, String.Format uses a StringBuilder, so their cost is somewhat similar, however the formatting may incur slightly more overhead.

There’s an even better approach because padding is a special case of appending to a string, but before I get to that, let’s just evaluate this first approach a bit further.

In the library, the way AddChars is used is when constructing string that contains an octal representation of an array length, padded by zeros in the front so that the fixed length of the field is 11 bytes:

string SizeString
{
    get { return AddChars(Convert.ToString(myArray.Length, 8), 11, '0', true); }
}

String.Format seems like a logical choice, because there are built-in integer and string padding formatting options. However, the only integer format that does base conversion produces hexadecimal. Octal conversion must happen outside of String.Format, by using the Convert.ToString function.

One way to still use String.Format for octal is to brute-force convert each section of the integer, as suggested by this blog, which does this conversion for a single byte. Since our input is an integer not a byte, and requires 11 characters, not 3, I extended the function to include all the bits:

private static string SizeStringFormat
{
    get
    {
        in len = myArray.Length;
        return string.Format(
            @"{0}{1}{2}{3}{4}{5}{6}{7}{8}{9}{10}",
            ((len >> 30) & 7),
            ((len >> 27) & 7),
            ((len >> 24) & 7),
            ((len >> 21) & 7),
            ((len >> 18) & 7),
            ((len >> 15) & 7),
            ((len >> 12) & 7),
            ((len >> 9) & 7),
            ((len >> 6) & 7),
            ((len >> 3) & 7),
            (sizeInBytes & 7)
        );
    }
}

But why even use a format function? Since there is no special formatting going on, the same may be accomplished directly, and more succinctly, with a StringBuilder:

private static string SizeStringStringBuilder
{
    get
    {
        var sb = new StringBuilder(11);
        for(shift = 30; shift >=0; shift-=3)
            sb.Append((myArray.Length >> shift) & 0x7);
        return sb.ToString();
    }
}

These approaches are not ideal but get the job done. One thing silly about them is they do work already provided by Convert.ToString. Also, they are not general purpose enough, because as soon as I need to fill a buffer with 20 0-padded characters instead of 11, it falls apart.

Which brings me to the better approach: padding happens to be already provided by .NET functions String.PadLeft and String.PadRight. The simplest way is to combine the provided conversion and padding functions together like so:

string SizeStringBest
{
    get { return Convert.ToString(sizeInBytes, 8).PadLeft(11, '0'); }
}

Here’s the sampled data from the memory and CPU profilers for the above versions of SizeString function:

FunctionInclusive AllocationsInclusive MemoryPercent CPU%
SizeString204,0404,012,6729.24%
SizeStringFormat260,0327,320,74816.58%
SizeStringStringBuilder140,0002,740,00014.95%
SizeStringBest20,000461,2804.35%


The SizeStringBest approach is not only simplest, it saves memory by roughly a factor of 10 over the original version, in terms of both the number of objects the garbage collector must clean up and the combined size of those objects. It also outperforms the other functions in terms of CPU use.

Another interesting find is to compare the String.Format vs. StringBuilder. Although String.Format uses StringBuilder under the hood, it does a bunch of extra things that increase its memory footprint substantially (and also calling it boxes the integer arguments), so if you don’t actually need special formatting, it may be cheaper to use StringBuilder, or even string concatenation.

This has been a long-winded way to say you should always look for the built-in functions of the .NET libraries before rolling your own. Often they have optimized versions of what you need. Another lesson is to not trust open-source developers or bloggers (myself excluded, of course!) to always do the right thing.

Addendum

While on this memory profiling kick, I decided to revisit my premature optimization post to discover if the memory impact is as bad as I speculated. In that article I guessed at how much memory overhead might be incurred, but I didn’t measure it.

Well now here is some data:

FunctionInclusive AllocationsInclusive MemoryPercent CPU%
Array Copy60,0111,770,24835.89%
LINQ90,0002,530,00036.52%


Using a LINQ expression was more “elegant” looking but incurred 50% more overhead in the number of memory allocations it creates under the hood. While the original function had an allocation for the output array, I guessed that the LINQ version would have in the best case two allocations to produce that array, and possibly more, and this turns out to be correct. The profiler indicates the CPU performance differs by only 3% (compared to the 9% I measured using stopwatch timers, which I trust more than the sampling approach used by profilers).

No comments yet

Leave a Reply

Your email address will not be published. Required fields are marked *