How come for loops in C# are so slow when concatenating strings?

Question

I wrote a program that runs a simple for loop in both C++ and C#, yet the same thing takes dramatically longer in C#, why is that? Did I fail to account for something in my test?

C# (13.95s)

static double timeStamp() {
    return (double)(DateTime.UtcNow.Subtract(new DateTime(1970, 1, 1))).TotalSeconds;
}

static void Main(string[] args) {
    double timeStart = timeStamp();

    string f = "";
    for(int i=0; i<100000; i++) {
        f += "Sample";
    }

    double timeEnd = timeStamp();
    double timeDelta = timeEnd - timeStart;
    Console.WriteLine(timeDelta.ToString());
    Console.Read();
}

C++ (0.20s)

long int timeStampMS() {
    milliseconds ms = duration_cast<milliseconds> (system_clock::now().time_since_epoch());
    return ms.count();
}

int main() {
    long int timeBegin = timeStampMS();

    string test = "";

    for (int i = 0; i < 100000; i++) {
        test += "Sample";
    }


    long int timeEnd = timeStampMS();
    long double delta = timeEnd - timeBegin;

    cout << to_string(delta) << endl;
    cin.get();
}

Try doing what you're doing twice in the loop. It might just get twice as slow. — Millie Smith, Apr 27 '18 at 22:37
I'm not familiar with C#, but it seems likely to me that `string` is immutable in C#. It's mutable in C++. That would require a lot of copying for the C# code, but not nearly as much for the C++ code — Justin, Apr 27 '18 at 22:37
@Justin That is correct. The shown code is is a relatively inefficient way to concat N-strings in C#/.NET - StringBuilder (or even a string.Join over a collection) would be "much faster". — user2864740, Apr 27 '18 at 22:38
It's also very possible you are measuring unoptimized code. IIUC, C# is run on a VM, which works similar to Java. It starts out by interpreting the code, not by running compiled code. — Justin, Apr 27 '18 at 22:41
You don't need to call `ToString` when passing an argument to `Console.WriteLine`. — NetMage, Apr 27 '18 at 22:44
That way of calculating elapsed time in c# is very weird. Why not just `var start = DateTime.UtcNow;` and `var end = DateTime.UtcNow`? — Camilo Terevinto, Apr 27 '18 at 22:50
@CamiloTerevinto: If you need meaningfull results you have to use StopWatch. DateTime has actually a lot less accuracy then precision (https://blogs.msdn.microsoft.com/ericlippert/2010/04/08/precision-and-accuracy-of-datetime/). Differences less then 10-50 ms seconds are actually not properly done (and the time span is not deterministic). With the inefficiency DateTime was enough. But 200 ms are well within the range of significant measurement errors. — Christopher, Apr 27 '18 at 22:56
@CamiloTerevinto I just had a Python mentality when calculating the time elapsed, I'm used to calling the .time() function before and after whatever I'm calculating, and then measuring the delta. I don't really know much about C#'s libraries, let alone what StringBuilder was until now. — Shayna, Apr 27 '18 at 22:57
@Christopher Yes, I'm very aware of that, still not a reason for such a weird calculation and the OP might not know of Stopwatch — Camilo Terevinto, Apr 27 '18 at 22:59
Do you have optimizations on? The C++ version runs in 0.001s on my not-so-new machine. — HolyBlackCat, Apr 27 '18 at 23:03

NetMage · Accepted Answer · 2018-04-27T23:15:01.567

On my PC, changing the code to use StringBuilder and converting to a String at the end, the execution time went from 26.15 seconds to 0.0012 seconds, or over 20,000 times faster.

var fb = new StringBuilder();
for (int i = 0; i < 100000; ++i) {
    fb.Append("Sample");
}
var f = fb.ToString();

As explained in the .Net documentation, the StringBuilder class is a mutable string object that is useful for when you are making many changes to a string, as opposed to the String class, which is an immutable object that requires a new object creation every time you e.g. concatenate two Strings together. Because the implementation of StringBuilder is a linked list of character arrays, and new blocks are added up to 8000 characters at a time, StringBuilder.Append is much faster.

Yeah, that was stupid of me to be honest. For a moment I genuinely thought it was the fault of the for loop x.x — Shayna, Apr 27 '18 at 22:53

Jimi · Answer 2 · 2022-02-24T16:06:54.073

Since Strings are immutable, each concatenation creates a new string.
The used strings are left for dead, awaiting garbage collection.

StringBuider is instantiated once and new chunks of data can be added when needed, expanding its capacity to MakeRoom (.NET source).

Test it using a StringBuilder:

string stringToAppend = "Sample";
int iteratorMaxValue = 100000;

StringBuilder sb = new StringBuilder(stringToAppend.Length * iteratorMaxValue);

Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();

for (int i = 0; i < iteratorMaxValue; i++) {
    sb.Append(stringToAppend);
}
stopwatch.Stop();
Console.WriteLine(stopwatch.ElapsedMilliseconds);

4 Milliseconds on my machine.

oh wow, I had a process which handled 160k records doing some string concatenation that took many minutes, lol, it was milliseconds switching to String Builder, defintely a better approach. — edencorbin, Feb 24 '22 at 15:59

eerorika · Answer 3 · 2018-04-27T23:11:44.370

C++ loop may be fast because it doesn't actually need to do anything. A good optimizer will be able to prove that removing the entire loop makes no observable difference in the behaviour of the program (execution time doesn't count as observable). I don't know if C# runtime is allowed to do similar optimization. In any case, to guarantee sensible measurements, you must always use the result in a way that is observable.

Assuming the optimizer didn't remove the loop, appending a constant length string into std::string has amortized constant complexity. Strings in C# are immutable, so the operation creates a new copy of the string every time, and so it has linear complexity. The longer the string becomes, the more significant this difference in asymptotic complexity becomes. You can achieve same asymptotic complexity by using the mutable StringBuilder in C#.

We got the JiT doing that and it can be scarily good at dead code detection. I literally had issues running into a OOM Excpetions when trying, because the JiT kept cutting out all the code. An output usually fixes that of course. Of course in this case is turned out to be a string issue. C# strings are inmutable, wich is quite a problem for conaction operations. Especially in loops. — Christopher, Apr 27 '18 at 22:59

How come for loops in C# are so slow when concatenating strings?

3 Answers3

Linked