performance while doing string concatenation - algorithm string strings c#

Question

I was using the following code to append strings

string res = string.Empty;
int ite = 100000;
for(int i= 0; i < ite; i++)
{
    res += "5";
}

It was taking a lot of time, so I later changed the code to

string res = string.Empty;
int ite = 100000;
res = getStr(ite / 2) + getStr(ite - (ite / 2)); 

//body of getStr method
private static string getStr(int p)
{
    if (p == 1)
        return "5";
    else if (p == 0)
        return string.Empty;
    string r1 = getStr(p / 2); //recursive
    string r2 = getStr(p - (p / 2)); //recursive  
    return (r1 + r2);
}

which in my opinion does nothing actually as the number of times strings are concatenated is approximately the same as in previous approach.

But using this approach there was significant improvement in performance as the code which was taking around 2500 ms (on my machine) was now taking 10 ms.

I ran a profiler over cpu time and couldn't arrive at an understanding as to why there is an improvement in performance. Can anyone please explain this.

Note: I am intentionally not using StringBuilder, in order to understand the above.

Answer 1

You need to think about why string concatenation is slow. Strings are immutable, so when you do:

someString+= "5";

You have to copy the entire contents of someString and to another string that is one larger and then copy in the 5 part. If you think about it, this gets slower and slower the longer the string gets.

With your recursive function you are doing a divide and conquer strategy to help to minimize the number of big string concatenations you need. For example, if you had a length of 8, in the first case you'd be doing:

"5" + "5" 
"55" + "5"
"555" + "5"
"5555" + "5"
"55555" + "5"
"555555" + "5"
"5555555" + "5"    // 7 total concatenations

In your recursive model you are doing:

"5" + "5"         // Four times
"55" + "55"       // twice
"5555" + "5555"   // once 

So you are doing less big concatenations.

And, of course, I assume the OP knows this from their comment, but for anybody else; if you need to concatenate any non-trivial number of strings, use StringBuilder as it is optimized for building strings by Appending them together.