Efficient string concatenation algorithm implements String.Join() method

Introduction

This article describes an alternative algorithm of string concatenation using the String.Join() method instead of the StringBuilder object Append() method and provides performance estimates of both algorithms.

Background

The following code snippets implements two string concatenation algorithms:

1. Using the StringBuilder object Append() method.
2. Using the String.Join() static method.

In both test settings, the array of strings (1,000,000 items) was pre-populated, thus the stopwatch counts only the elapsed time spent on the actual string concatenation (please note that in the original article the loop includes a i.ToString() conversion, which is included in the elapsed time estimates, thus affecting the result and distorting the performance statistics). Also, a stopwatch object provides much more accurate time measurement (it is a part of the System.Diagnostics object library).

The Insert() method addressing the Prefixing/Suffixing issue as described in the original article is off consideration provided that "in-real-life" scenarios it's possible to just reverse the order of operation if necessary and then apply the Append() method, which is more efficient than Insert() (based on the performance estimates included in the original article).

The main goal of the article and corresponding test settings is to introduce more efficient solution for string concatenation utilizing String.Join() static method instead of StringBuilder Append() method, and to provide empirically obtained performance estimates.

Using the code

Both algorithms apply the following sample string delimiter:

", " 

#region String Concatenation Using StringBuilder.Append() method
/// <summary>
/// StringBuilder.Append() method performance estimate
/// </summary>
/// <param name="LoopCounter">Int64</param>
/// <returns>double</returns>
public static double ConcatenateUsingAppend(Int64 LoopCounter)
{
    StringBuilder _sb = new StringBuilder();

    // array of string to concatenate
    string[] _arTemp = new string[LoopCounter];

    // populate array with sample strings
    for (Int64 i = 0; i < LoopCounter; i++)
    {
        _arTemp[i] = i.ToString();
    }

    // stopwatch obj (ref: System.Diagnostics)
    Stopwatch _sw = new Stopwatch();

    // start count ticks
    _sw.Start();

    // concatenate using Append()
    for (Int64 i = 0; i < LoopCounter; i++)
    {
        _sb.Append(_arTemp[i]);
        _sb.Append(", ");
    }

    // result string
    string _result = _sb.ToString();

    // stop count
    _sw.Stop();

    // duration measured in ticks
    Int64 _ticks = _sw.ElapsedTicks;

    // stopwatch frequency in kHZ
    double _frequency = Stopwatch.Frequency;

    // time per tick
    double _secPerTick = 1 / _frequency;

    // duration in msec (rounded)
    return Math.Round((1000 * _ticks * _secPerTick), 1);
}
#endregion

/// <summary>
/// String.Join() method performance estimate
/// </summary>
/// <param name="LoopCounter">Int64</param>
/// <returns>double</returns>
public static double StringJoin(Int64 LoopCounter)
{
            
    // array of string to concatenate
    string[] _arTemp = new string[LoopCounter];

    // populate array with sample strings
    for (Int64 i = 0; i < LoopCounter; i++)
    {
        _arTemp[i] = i.ToString();
    }

    // stopwatch obj (ref: System.Diagnostics)
    Stopwatch _sw = new Stopwatch();

    // start count ticks
    _sw.Start();

    // get result string using String.Join()
    string _result = String.Join(", ", _arTemp);

    // stop count
    _sw.Stop();

    // duration measured in ticks
    Int64 _ticks = _sw.ElapsedTicks;

    // stopwatch frequency in kHZ
    double _frequency = Stopwatch.Frequency;

    // time per tick
    double _secPerTick = 1 / _frequency;

    // duration in msec (rounded)
    return Math.Round((1000 * _ticks * _secPerTick),1);
}

private void button1_Click(object sender, EventArgs e)
{
    Int64 _iterations = 1000000; // 1 million
    label1.Text = "Duration using Append(), msec: " + ConcatenateUsingAppend(_iterations).ToString();
    label2.Text = "Duration using String.Join(), msec: " + StringJoin(_iterations).ToString();
}

Points of interest

Empirically obtained results demonstrate almost three times performance improvement by utilizing the static String.Join() method (elapsed time about 36 msec for 1,000,000 strings) vs. StringBuilder object Append() method (took about 100 msec for the same test settings).

String.Join and String.Split methods (.NET)

Thanks to reader's input and thoughtful comments, I found it relevant to elaborate further on the usage of String.Join and also, String.Split, as some of our fellow programmers may be not quite familiar with these methods.

The static method String.Join has been a part of .NET Framework since version 1.1, though in most current forms it was introduced in V.2.0 (see ref [1]) as shown below (C# syntax):

public static string Join (string separator, string[] value)

Responding to the comments: separator (the first parameter) can be an empty string, thus pertinent to the example in Listing 2, the concatenation line can be written like the following (joining all strings together):

string _result = String.Join(String.Empty, _arTemp);

but even more efficient way pertinent to this just concatenation case (without delimiters) will be to use the String.Concat method as described later in the article.

Serialization/De-serialization

The String.Join method can be used, for example, in order to serialize the array of strings converting it to a single delimited one. Another operator String.Split does exactly the opposite (see ref [2]), returning the array of strings extracted from a single delimited one. Important to mention that if the original array of strings contain empty strings or blank spaces, then the String.Join() method will still add specified delimiters, so the reverse operation based on String.Split() will return the array of the same structure and content.

It's relevant to mention (even though this is typically a quite known fact) that the "+" operator when applied to strings is very inefficient performance-wise, thus the Append() method is recommended in general for that type of string operations. But for a special purpose of concatenating strings array with a specified delimiter added as described in the article, the String.Join() method outperforms the "+" operator and the Append() method as well.

Prefixing/Suffixing is simple with the String.Join() method

If prefixing (which is semantically equal to "inserting a delimiter before") is required for all elements of the string array, then the specified prefix should be added only once in front of just the first array's element (index of 0) before running the String.Join() concatenation; the rest of the code remains the same. Correspondingly, the suffix should be added (if necessary) to the last element of the string array before applying the String.Join() method.

String.Concat method

As discussed above, the String.Join() method provides the ability to concatenate an array of strings with an added prefix, suffix, or both (they can all be included in a separator string along with the actual delimiting char). But in case strings delimiting is not required, then another static method namely: String.Concat() [3] can do the job even more efficiently than String.Join(): the additional performance boost was calculated as approx. 20% vs. String.Join() applying the same test settings (run time about 29 ms vs. 36 ms), and just replacing a single line of code with the following one:

string _result = String.Concat(_arTemp);

History

• Posted on: Sep. 22, 2012.
• Updated on Sep. 23, 2012.

References

• String.Join Method (MSDN)
• String.Split Method (MSDN)
• String.Concat Method  (MSDN)