11

I recall back from my days of programming in C that when two strings are joined, the OS must allocate memory for the joined string, then the program can copy all the string text over to the new area in memory, then the old memory must manually be released. So if this is done multiple times as in the case of joining a list, the OS has to constantly allocate more and more memory, just to have it released after the next concatenation. A much better way to do this in C would be to determine the total size of the combined strings and allocate the necessary memory for the entire joined list of strings.

Now in modern programming languages (C# for instance), I commonly see the contents of collections being joined together by iterating through the collection and adding all the strings, one at a time, to a single string reference. Is this not inefficient, even with modern computing power?

JSideris
  • 591
  • 1
  • 5
  • 15
  • leave it to compiler and profiler, they will care about it, your time much more expensive than time to strings concatenation. – OZ_ Apr 25 '12 at 21:55
  • 7
    Depends on the implementation -- you should really check the documentation for your particular string library. It is possible to implement strings that concatenate by reference, in O(1) time. In any case, if you need to concatenate an arbitrarily-long list of strings, you should use classes or functions that are designed for this kind of thing. – comingstorm Apr 25 '12 at 22:19
  • Note that things like string concatenation are generally handled by a library function, not the operating system. The OS might get involved in memory allocation, but probably not for relatively small objects like strings. – Caleb Apr 26 '12 at 15:03
  • @Caleb The OS is involved in ALL memory allocation. Failing to follow this rule is a type of memory leak. The exception is when you have hard-coded strings in the application; those get written as binary data within the generated assembly. But as soon as you manipulate (or perhaps even assign) a string it needs to be stored in memory (that is, memory must be allocated). – JSideris Apr 27 '12 at 13:50
  • 4
    @Bizorke In a typical scenario, a memory allocator like malloc() (which is part of the C standard library, not the OS) is used to allocate various chunks of memory from the memory that's already been allocated to the process by the OS. The OS doesn't need to get involved unless the process runs low on memory and needs to request more. It may also take part at a lower level if an allocation causes a page fault. So yes, the OS ultimately provides the memory, but it's not necessarily involved in piecemeal allocation of strings and other objects inside the process. – Caleb Apr 27 '12 at 14:10
  • @Caleb Oh yea I always thought malloc was doing some type of OS memory request behind the scenes, but that makes a lot more sense as I also recall that the OS pages a bunch of memory for each application which can be used up and re-sized. – JSideris Apr 27 '12 at 15:08
  • This question relates to this other question posted recently: [Why are strings so slow?](http://programmers.stackexchange.com/questions/10672/why-are-strings-so-slow/174965#174965). – haylem Nov 09 '12 at 01:07

6 Answers6

21

Your explanation why it is inefficient is accurate, in at least the languages I am familiar with (C, Java, C#), though I would disagree that it is universally common to perform massive amounts of string concatenation. In the C# code I work on, there is copious usage of StringBuilder, String.Format, etc. which are all memory saving techiniques to avoid over-reallocation.

So to get to the answer for your question, we must ask another question: if it's never really an issue to concatenate strings, why would classes like StringBuilder and StringBuffer exist? Why is the use of such classes included in even semi-beginner programming books and classes? Why would seemingly pre-mature optimization advice be so prominent?

If most string-concatenating developers were to base their answer purely on experience, most would say it never makes a difference and would shun the use of such tools in favor of the "more readable" for (int i=0; i<1000; i++) { strA += strB; }. But they never measured it.

The real answer to this question could be found in this SO answer, which reveals that in one instance, when concatenating 50,000 strings (which depending on your application, may be a common occurence), even small ones, resulted in a 1000x performance hit.

If performance literally doesn't mean anything at all, by all means concatenate away. But I would disagree that using alternatives (StringBuilder) is difficult or less readable, and therefore would be a reasonable programming practice that shouldn't invoke the "premature optimization" defense.

UPDATE:

I think what this comes down to, is know your platform and follow its best practices, which are sadly not universal. Two examples from two different "modern languages":

  1. In another SO answer, the exact opposite performance characteristics (array.join vs +=) were found to be sometimes true in JavaScript. In some browsers, string concatenation appears to be optimized automatically, and in other cases it isn't. So the recommendation (at least in that SO question), is to just concatenate and not worry about it.
  2. In another case, a Java compiler can automatically replace concatenation with a more efficient construct such as StringBuilder. However, as others have pointed out, this is indeterministic, not guaranteed, and using StringBuilder doesn't hurt readability. In this particular case, I would tend to recommend against the use of concatenation for large collections or relying on an indeterministic Java compiler behavior. Similarly, in .NET, no optimization of the sort is performed, ever.

It's not exactly a cardinal sin to not know every nuance of every platform right away, but ignoring important platform issues like this would almost be like moving from Java to C++ and not caring about deallocating memory.

Community
  • 1
Kevin McCormick
  • 4,064
  • 1
  • 18
  • 28
  • -1: contains major BS. `strA + strB` is _exactly_ the same as using a StringBuilder. It has a 1x performance hit. Or 0x, depending on how you're measuring. For more detail, http://www.codinghorror.com/blog/2009/01/the-sad-tragedy-of-micro-optimization-theater.html – amara Apr 26 '12 at 04:21
  • 5
    @sparkleshy: My guess is that SO answer uses Java and your linked article uses C#. I agree with those who say "depends on implementation" and "measure it for your particular environment". – Kai Chan Apr 26 '12 at 05:56
  • 1
    @KaiChan: string concatenation is basically the same in java and c# – amara Apr 26 '12 at 13:38
  • 3
    @sparkleshy - Point taken, but using StringBuilder, String.Join, etc. to concatenate exactly two strings is rarely a recommendation, ever. Further, the OP's question is specifically in regards to "the contents of *collections* being joined together", which is not the case (where StringBuilder, etc. is very applicable). Regardless, I'll update my example to be more to the point. – Kevin McCormick Apr 26 '12 at 14:15
  • Most if not all `StringBuilder/StringBuffer` type implementations allow for you to provide the initial buffer size, which if set correctly does **not** occur any performance penalties regardless of the number of `.append()` calls as long as the final string size fits inside the initial size; it produces no reallocations or garbage. In Java, the initial size is so small that on large resulting strings with lots of small `.append()` it doesn't do anything positive for performance over just using `+` on all the parts, since a `StringBuilder` with the default size is used under the covers. –  Apr 26 '12 at 14:42
  • @Jarrod Roberson: you're very wrong on that last point - the Java classes will *double* the capacity when it is exceeded, which means that the number of reallocations is log(n), and most of them happen when the buffer is still small, so overall the performance penalty over preallocating the entire buffer beforehand is usually very small, and definitely insignifcant compared to using `+` – Michael Borgwardt Apr 26 '12 at 15:09
  • @sparkleshy: Unless it is written in the language spec, it is up to the implementation, hence the need to experiment. Don't know about C#, but Java 7 SE spec, section 15.18.1 states that a Java compiler "may" use StringBuffer or "a similar technique" to handle concatenation operator "+". The same section also says the result of + is a String, which "is newly created" unless the expression is "compile-time constant". So even if the compiler optimizes, it must convert the String(Buffer|Builder) to String at each "a = b + c". Interestingly, StringBuilder does not appear anywhere in the spec. – Kai Chan Apr 26 '12 at 15:28
  • @MichaelBorgwardt my point is using `StringBuilder` with the default size and doing `.append().append().append()` is the same as using `+` `+` `+` and results in same re-allocation behavior. Yes, doubling the size is the current Oracle JDK behavior, it is implementation specific, either way the behavior is the same. As mentioned in other comments, this behavior is **implemenation specific** so, using best practices and pre-allocating the initial size of a `StringBuilder/StringBuffer` is still the only way to guarantee deterministic behavior across JVM implementations and the best way to go. –  Apr 26 '12 at 16:00
  • 3
    I don't care about language for the purpose of this question. The use of stringbuilder behind the scenes in _some_ languages explains why it may not be inefficient to concatenate an entire list of strings, which answers my question. This answer did however explain that joining a list could potentially be hazardous, and recommended stringbuilder as an alternative. I recommend adding the compiler's use of stringbuilder behind the scenes to your answer, in order to avoid possible reputation loss or misinterpretation. – JSideris Apr 27 '12 at 15:54
  • @Bizorke I edited my answer to be a bit more all-encompassing. I hope that helps. – Kevin McCormick Apr 27 '12 at 16:45
2

It is not efficient, roughly for the reasons you described. Strings in C# and Java are immutable. Operations on strings return a separate instance instead of modifying the original one, unlike it was in C. When concatenating multiple strings, a separate instance is created at each step. Allocating and later garbage collecting those unused instances can cause a performance hit. Only this time memory management is handled for you by the garbage collector.

Both C# and Java introduce a StringBuilder class as a mutable string specifically for this type of tasks. An equivalent in C would be using a linked list of concatenated strings instead of joining them in an array. C# also offers a convenient Join method on strings for joining a collection of strings.

scrwtp
  • 4,532
  • 1
  • 24
  • 29
1

Strictly speaking it is less efficient use of CPU cycles, so you are correct. But what about developer time, maintenance costs etc. If you add the cost of time to the equation, it is almost always more efficient to do whats easiest, then if needed, profile and optimize the slow bits.
"The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet."

mattnz
  • 21,315
  • 5
  • 54
  • 83
  • 3
    not very effective rules, I think. – OZ_ Apr 25 '12 at 21:54
  • @OZ_ : This is a widely used quote (Michael A. Jackson) and other by the likes of Donald Knuth... Then there is this one, which I usually refrain from using "More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason — including blind stupidity." – mattnz Apr 25 '12 at 22:43
  • 2
    I should point out that [Michael A. Jackson](http://en.wikipedia.org/wiki/Michael_A._Jackson) was a brit, so it's *Optimisation* not *Optimization*. At some point I really should correct the [wikipedia page](http://en.wikipedia.org/wiki/Program_optimization#Quotes). *8') – Mark Booth Apr 26 '12 at 14:59
  • I totally agree, you should correct those spelling errors. Although my native language is Queens English, I find it easier to speak US on the intra-web....... – mattnz Apr 26 '12 at 22:12
  • won't somebody think of the users. You may make it slightly faster for the developer to create, but then every single one of your customers suffers for it. Write your code for them, not for you. – gbjbaanb Apr 27 '12 at 18:36
  • @gbjbaanb: Depends. I work for pay so I can feed my family, my pay comes from profits made by the company I work for. No profit, no company, no job, no pay, hungrey family, no family. Stuff the end users, I love my family, I do what it takes for the company to make a profit. Not some idealised idea of perfection at all costs, but the reality of capitalist world I live in. – mattnz Apr 29 '12 at 20:13
1

It's very hard to say anything about performance without a practical test. Recently I was very surprised to find out that in JavaScript a naïve string concatenation was usually faster than the recommended "make list and join" solution (test here, compare t1 with t4). I'm still puzzled about why that happens.

A few questions you might ask when reasoning about performance (especially concerning memory usage) are: 1) how big is my input? 2) how smart is my compiler? 3) how does my runtime manage memory? This is not exhaustive, but it's a starting point.

  1. How big is my input?

    A complex solution will often have a fixed overhead, maybe in the form of extra operations to be performed, or maybe in extra memory needed. Since those solutions are designed to handle big cases, the implementors will usually have no problem introducing that extra cost, since the net gain is more important that micro-optimizing the code. So, if your input is sufficiently small, a naïve solution may well have a better performance than the complex one, if only for avoiding this overhead. (determining what is "sufficiently small" is the hard part though)

  2. How smart is my compiler?

    Many compilers are smart enough to "optimize away" variables that are written to, but never read. Likewise, a good compiler might also be able to convert a naïve string concatenation to a (core) library use and, if many of them are made without any reads, there's no need to convert it back to a string between those operations (even if your source code seems to do just that). I can't tell whether or not any compilers out there do that, or to what extent that is done (AFAIK Java at least replace several concats in the same expression to a sequence of StringBuffer operations), but it's a possibility.

  3. How does my runtime manage memory?

    In modern CPUs the bottleneck is usually not the processor, but the cache; if your code accesses many "distant" memory addresses in a short time, the time it takes to move all that memory between the cache levels outweights most optimizations in the instructions used. That's of particular importance in runtimes with generational garbage collectors, since the most recently created variables (inside the same function scope, for instance) will usually be in contiguous memory addresses. Those runtimes also routinely move memory back and forth between method calls.

    One way it can affect string concatenation (disclaimer: this is a wild guess, I'm not knowledgeable enough to say for sure) would be if the memory for the naïve one were allocated close to the rest of the code that uses it (even if it allocates and releases it multiple times), while the memory for the library object were allocated far from it (so the many context changes while your code computes, the library consumes, your code computes more, etc would generate many cache misses). Of course for big inputs OTOH the cache misses will happen anyway, so the problem of multiple allocations becomes more pronounced.

That said, I'm not advocating the use of this or that method, only that testing and profiling and benchmarking should precede any theoretical analysis about performance, since most systems nowadays are just too complex to fully understand without a deep expertise in the subject.

mgibsonbr
  • 504
  • 3
  • 11
  • Yea I agree that this is definitely an area where a compiler could theoretically realize that you're trying to add a bunch of strings together and then optimize as though you were using a string builder. However this is hardly a trivial thing to do, and I do not think it's implemented in any modern compilers. You just gave me a great idea for an undergraduate research project :D. – JSideris Apr 26 '12 at 02:59
  • Check [this answer](http://stackoverflow.com/a/47628/520779), the Java compiler already uses `StringBuilder` under the hood, all it would need to do is not call `toString` until the variable is actually needed. If I recall correctly, it **does** that for a single expression, my only doubt is whether or not it applies to multiple statements in the same method. I know nothing about .NET internals, but I believe a similar strategy might be employed by the C# compiler as well. – mgibsonbr Apr 26 '12 at 04:03
0

Joel wrote a great article on this subject a while back. As some others have pointed, it is heavily dependent on the language. Because of the way strings are implemented in C (zero terminated, with no length field), the standard strcat library routine is very inefficient. Joel presents an alternative with just a minor change that is much more efficient.

tcrosley
  • 9,541
  • 1
  • 25
  • 41
-1

Is it inefficient to concatenate strings one at a time?

No.

Have you read 'The Sad Tragedy of Micro-Optimization Theater'?

Jim G.
  • 8,006
  • 3
  • 35
  • 66