Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
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). –  Bizorke Apr 27 '12 at 13:50
3  
@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

6 Answers 6

up vote 21 down vote accepted

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.

share|improve this answer
    
-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, codinghorror.com/blog/2009/01/… –  naiad Apr 26 '12 at 4: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 5:56
1  
@KaiChan: string concatenation is basically the same in java and c# –  naiad 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
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. –  Bizorke Apr 27 '12 at 15:54

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."

share|improve this answer
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
1  
I should point out that Michael A. Jackson was a brit, so it's Optimisation not Optimization. At some point I really should correct the wikipedia page. *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

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.

share|improve this answer

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.

share|improve this answer
    
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. –  Bizorke Apr 26 '12 at 2:59
    
Check this answer, 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 4:03

Is it inefficient to concatenate strings one at a time?

No.

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

share|improve this answer
4  
"Premature optimization is the root of all evil." -- Knuth –  Scott Wilson Apr 26 '12 at 1:41
4  
Root of all evil in optimization is taking this phrase without context. –  OZ_ Apr 26 '12 at 10:26
    
Just saying something is true without providing some supporting reasons isn't useful on a forum like this. –  Crazy Eddie May 9 '12 at 22:38
    
@Crazy Eddie: Did you read why Jeff Atwood had to say? –  Jim G. May 10 '12 at 0:29

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.