Why are strings so slow?

Question

Ever since my very first programming class in high school, I've been hearing that string operations are slower — i.e. more costly — than the mythical "average operation." Why makes them so slow? (This question left intentionally broad.)

Answer 1

"The average operation" takes place on primitives. But even in languages where strings are treated as primitives, they're still arrays under the hood, and doing anything involving the whole string takes O(N) time, where N is the length of the string.

For example, adding two numbers generally takes 2-4 ASM instructions. Concatenating ("adding") two strings requires a new memory allocation and either one or two string copies, involving the entire string.

Certain language factors can make it worse. In C, for example, a string is simply a pointer to a null-terminated array of characters. This means that you don't know how long it is, so there's no way to optimize a string-copying loop with fast move operations; you need to copy one character at a time so you can test each byte for the null terminator.

Answer 2

^{This is an old thread and I think that the other answers are great, but overlook something, so here's my (late) 2 cents.}

Syntactic Sugar-Coating Hides Complexity

The problem with strings is that they are second class citizens in most languages, and are in fact most of the time not really a part of the language specification itself: they are a library-implemented construct with some occasional syntactic sugar-coating on the top to make them less of a pain to use.

The direct consequence of this is that the language hides a very large part of their complexity away from your sight, and you pay for the sneaky side-effects because you grow into the habit of considering them like a low-level atomic entity, just like other primitive types (as explained by the top-voted answer and others).

Implementation Details

Good Ol' Array

One of the elements of this underlying "complexity" is that most string implementations would resort to using a simple data-structure with some contiguous memory space to represent the string: your good ol' array.

This makes good sense, mind you, as you want the access to the string as a whole to be fast. But that implies potentially dreadful costs when you want to manipulate this string. Accessing an element in the middle might is fast if you know what index you are after, but looking for an element based on a condition isn't.

Even returning the size of string might be costly, if your language doesn't cache the string's length and needs to run through it to count characters.

For similar reasons, adding elements to your string will prove costly as you'll most likely need to re-allocate some memory for this operation to occur.

So, different languages take different approaches to these issues. Java, for instance, took the liberty of making its strings immutable for some valid reasons (caching length, thread-safety) and for its mutable counterparts (StringBuffer and StringBuilder) will choose to allocate size using larger-sized chunks to not need to allocate every time, but rather hope for best case scenarios. It generally works well, but the down-side is to sometimes pay for memory impacts.

Unicode Support

Also, and again this is due to the fact that the syntactic sugar coating of your language hides this from you to play nice, you often don't think it terms of unicode support (especially for as long as you don't really need it and hit that wall). And some languages, being forward thinking, do not implement strings with underlying arrays of simple 8-bit char primitives. They baked in UTF-8 or UTF-16 or what-have-you support for you, and the consequence is a tremendously larger memory consumption, which is often times not needed, and a larger processing time to allocate memory, process the strings, and implement all the logic that goes hand in hand with manipulating code points.

---

The results of all this, is that when you do something equivalent in pseudo-code to:

hello = "hello,"
world = " world!"
str = hello + world

It may not be - despite all the best efforts the language developers put in to have them behave as you'd except - a simple as:

a = 1;
b = 2;
shouldBeThree = a + b

---

As a follow-up, you may want to read:

• Is it Inefficient to concatenate strings one at a time?

Answer 3

The phrase "average operation" is probably shorthand for a single operation of a theoretical Random-Access Stored-Program machine. This is the theoretical machine it's customary to use to analyse the running time of various algorithms.

The generic operations are normally taken to be load, add, subtract, store, branch. Maybe also read, print and halt.

But most string operations require several of these fundamental operations. For example, duplicating a string normally requires a copying operation, and hence a number of operations which is proportional to the length of a string (that is, it's "linear"). Finding a substring inside another string also has linear complexity.

Answer 4

It completely depends on the operation, how strings are represented, and what optimizations exist. If strings are 4 or 8 bytes in length (and aligned), they wouldn't necessarily be slower - many operations would be just as fast as primitives. Or, if all strings have a 32-bit or 64-bit hash, many operations would also be just as fast (though you pay the hashing cost up front).

It also depends on what you mean by "slow". Most programs will process strings plenty fast for what is needed. String comparisons might not be as fast as comparing two ints, but only profiling will reveal what "slow" means to your program.

Answer 5

Let me answer your question with a question. Why does saying a string of words take longer than saying a single word?