Hacker News Reader

Comment by goto11 | Hacker News Reader

I was wondering about it in the context of "yet, other languages would do the right thing by default". Repeatedly concatenating to the same string (as opposed to concatenating an array of strings in one go) would be slow in any language I know of, unless you allocate a larger buffer up front, which is what StringBuilder does.

Some languages have mutable strings, but you would still need to allocate a sufficiently larger buffer if you want to add strings in a loop.

View on HN

In languages that have immutable string semantics and can detect that they are the exclusive owner of a string, they can modify them in place. For reference counting languages like Python, they can easily determine they are the exclusive owner by checking for a reference count of 1. See:

https://github.com/python/cpython/blob/main/Objects/unicodeo...

Rust's ownership system ensures that there cannot exist mutable and immutable references to the same object at the same time. So if you have a mutable reference to a string it is ok to modify in place.

I have not confirmed either the Python example or the Rust example too deeply, since I'm replying to 5 day old comment. But the general principal holds. GC languages like C# and Java don't have easy ways to check ownership so they always copy strings when mutating them. Maybe I'll write a blogpost on this in the future.

I don't think StringBuilder is faster specifically because it allocates a large buffer. Pretty much every language with growable data structures can already grow any such structure pretty fast, including arrays, maps, and mutable strings. They already have a bunch of pre-set constants about stuff like how big to allocate for the initial empty one and how much more to allocate every time you overflow to balance speed and memory efficiency. It's faster because it's mutable and keeps adding new data to the existing buffer until it gets too large.

The cost is not the allocation per se, the cost is copying the bytes. When concatenating two strings, the bytes from both strings are copied into the new string. If you repeatedly concatenate, the bytes end up getting copied many times. E.g if you concatenate 100 strings by appending one by one, the bytes in the first string is copied 99 times, the bytes in the second string is copied 98 times and so on.

Using a StringBuilder, the strings are only copied once when copied into the buffer. If the buffer need to grow, the whole buffer is copied into a larger buffer, but if the buffer grows by say doubling the size, then this cost is amortized, so each string on average is still only copied twice at worst.

Faster yet is concatenating an array of strings in a single concat operation. This avoids the buffer resize issue, since the necessary buffer size is known up front. But this leads to the subtle issue where a single concat is faster than using a StringBuilder, while the cost for multiple appends grows exponentially for concat but only lineary for StringBuilder.

Repeatedly concatting a string is the fastest way I am aware of to build a longer one in Javascript. (This has been deliberately optimized for) I believe PHP this might also be the case for, or at least very fast. Perl might be pretty fast at this but I could be wrong.

I know JS's case somewhat well and the lesson there is not the comment such as above that "it just does the right thing". JS doesn't use a "String Builder" under the hood with a lot of string + calls, but instead that JS does subtly the "wrong" thing as an optimization: in the .NET CLR strings are always, always immutable (or they are not strings according to guarantees that the CLR makes). JS lives in a single language VM that makes no such guarantees, and often lives in strictly single threaded worlds where the VM doesn't have to guarantee the immutability of strings to anyone at the binary memory layout level, so most JS VMs are free to do the "wrong thing" (from the .NET CLR perspective) and just mutably alter strings under the hood as a deliberate optimization.

There's a lot of interesting conflations of "right" versus "wrong" in this this thread. There's the C# "best practices" "right" versus "wrong" of knowing when to choose things like StringBuilder over string.Concat or string's + operator overloading (which does just call string.Concat under the hood). There's the "does that right/wrong" apply to other languages question? (The answer is far more complex than just "right" and "wrong".) There's the VM guarantees of .NET CLR's hard line "no string is mutable" setting a somewhat hard "right" versus "wrong" and other language's VMs/interpreters not needing to make such guarantees to themselves or to others. None of these are really ever "right" versus "wrong", almost all of them are trade-offs described as "best practices" and we take the word "best" too strongly especially when we don't know/examine/explore the trade-off context it originated from (and sometimes wrongly assuming that "best" means "universally the best").

I believe joining an array of strings is still faster in JavaScript, since the combined size can be known up front.

Reply on news.ycombinator.com