3

in C#, What is the Complexity of StringBuilder.ToString()? Is it O(1), O(N), or something else?

Taryn
  • 242,637
  • 56
  • 362
  • 405
yazanpro
  • 4,512
  • 6
  • 44
  • 66
  • 6
    Look at the source and you'll know everything you need: http://referencesource.microsoft.com/#mscorlib/system/text/stringbuilder.cs#5a97da49a158a3c9 – MarcinJuraszek Jun 16 '14 at 19:12
  • @MarcinJuraszek code is quite interesting for me according to straight C# codes. So Do you think it is O(N) because chunking? – Murat Can OĞUZHAN Jun 18 '22 at 21:17

1 Answers1

2

It varies between framework version; in older versions StringBuilder works on a string directly, so there is no additional cost in .ToString(): it just hands you the data directly (which can mean oversized, but it makes it work); so O(1).

In newer framework version, it uses a char[] backing buffer, so now when you .ToString() it will probably need to copy 2 x Length bytes, making it O(N).

Marc Gravell
  • 1,026,079
  • 266
  • 2,566
  • 2,900
  • Interesting. When did it change? Which versions use `string` directly? – MarcinJuraszek Jun 16 '14 at 19:17
  • @MarcinJuraszek I think 3.5 vs 4.0, but I'd need to check – Marc Gravell Jun 16 '14 at 19:19
  • What was the reason for that change? – MarcinJuraszek Jun 16 '14 at 19:20
  • @MarcinJuraszek almost certainly ;p – Marc Gravell Jun 16 '14 at 19:21
  • @MarcinJuraszek It makes each `Append` faster, because it defers its work until the string is actually generated. It also means that the memory doesn't need to be contiguous (until/unless) you generate an actual string, reducing the odds of the SB being on the LOH, fragmenting memory less, and being less vulnerable to OOM due to fragmented memory rather than simply insufficient memory. – Servy Jun 16 '14 at 19:24
  • @Servy appending to an oversized `string` is pretty much the same as appending to an oversized `char[]` - not much difference in terms of `Append`. Likewise, since the implementation is IIRC a `char[]`, it still has the same contiguous requirements – Marc Gravell Jun 16 '14 at 19:26
  • 1
    @MarcGravell You misunderstand the complexity of what SB does. It is *not* just a wrapper for one big giant buffer. It is, in effect, a linked list of char arrays, because each SB also has a reference to a "previous" string builder. Basically when any given buffer runs out of space it doesn't make a new buffer and copy over the existing content (the pre 4.0 approach), it makes a new buffer *copies over none of the content*, and then holds onto a reference to the "previous" buffer. `ToString` goes through the current, and all previous, buffers and appends them all to one big giant buffer. – Servy Jun 16 '14 at 19:29
  • Well according to your discussion, in the 'concatenation applications', the time I'd save by using Append with the StringBuilder will be wasted later when calling .ToString(). Even worse, ToString() creates a new instance which means allocating double the size in the memory (until the scope is done). So why would I use StringBuilder in the first place? – yazanpro Jun 18 '14 at 01:21
  • @yazanpro because it is a **lot** cheaper than creating lots of intermediate strings – Marc Gravell Jun 18 '14 at 07:13
  • You will be creating intermediate strings anyway. (StringBuilder.Append("test") VS string+="test") Both create the intermediate string "test" – yazanpro Jun 18 '14 at 16:01
  • 3
    @yazanpro now put it in a loop, and consider the unnecessary "footest", "footesttest" and "footesttesttest" – Marc Gravell Jun 18 '14 at 16:07