24

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

7
  • 14
    If you know that these "average operations" are mythical, can you at least tell us what some of them are? Given that you're asking such a vague question, it's hard to trust your assertion that these unspecified operations truly are mythical.
    – seh
    Oct 9, 2010 at 14:49
  • 1
    @seh, unfortunately, I actually can't answer that. The few times I've actually asked people what strings are slower than, they just kind of shrug and say "they're just slow." Besides, if I had more specific information, this would be a question for SO, not Programmers; it's already kinda borderline.
    – Pops
    Oct 9, 2010 at 22:37
  • 1
    What is the point ? If told strings are actually slow, will you stop using them ? Nov 7, 2012 at 16:40
  • 3
    Forget it. If someone tells you such nonsense, the counterquestion is: "Really? Are they? Should we use an int-array then?"
    – Ingo
    Nov 7, 2012 at 23:10
  • 1
    @gnasher729 OK, what compiler that you know of will resolve this issue?
    – JimmyJames
    Dec 11, 2023 at 19:34

9 Answers 9

59

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

12
  • 6
    And certain languages make it much better: Delphi's encoding of the string length at the beginning of the array makes string concatenation very fast. Oct 9, 2010 at 5:53
  • 4
    @gablin: It also helps by making the string copying itself a lot faster. When you know the size up front, you don't have to copy one byte at a time and check each byte for a null terminator, so you can use the full size of any register, including the SIMD ones, for data movement, making it up to 16 times faster. Oct 9, 2010 at 12:54
  • 4
    @mathepic: Yeah, and that's fine for as far as it will take you, but when you start interacting with libc or other external code, it expects a char*, not a strbuf, and you're back to square 1. There's only so much you can do when a bad design is baked into the language. Oct 9, 2010 at 15:26
  • 7
    @mathepic: Of course the buf pointer's there. I never meant to imply that it's not available; rather, that it's necessary. Any code that doesn't know about your optimized-but-nonstandard string type, including things as fundamental as the standard library, still has to fall back on the slow, unsafe char*. You can call that FUD if you want to, but that doesn't make it not true. Oct 9, 2010 at 19:07
  • 7
    People, there's a Joel Spolsky column about Frank Shearer's point: Back to Basics
    – user16764
    Feb 29, 2012 at 4:06
17

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:

4
  • 1
    Good addition to the current discussion.
    – Abel
    Nov 7, 2012 at 15:33
  • 1
    I just realized this is the best answer because the mythical statement can be applied to anything like RSA encryption is slow. The only reason for string being put in this embarrassing spot is because the plus operator provided for strings in most languages, which makes newbies not aware of the cost behind the operation.
    – Codism
    Nov 7, 2012 at 15:45
  • @Abel: thanks, seemed to me the was room for more generic details.
    – haylem
    Nov 7, 2012 at 17:03
  • @Codism: thanks, glad you liked it. I do indeed think this can be applied to many cases where it's just a matter of complexity being hidden (and of us not paying that much attention to lower-level details anymore until we finally need to because we hit a bottleneck or brickwall of some sort).
    – haylem
    Nov 7, 2012 at 17:04
4

Strings are often no more expensive than other data types of similar complexity. Indeed they may be cheaper, because the creators of programming environments often put a lot of effort into optimising them.

So why do we tell students that strings are slow. I think there are a few reasons.

  1. Strings are often one of the first data types beginners are introduced to. Compared to primitive data types like fixed-size integers, strings are expensive.
  2. Historic languages did not have the rich selection of types that modern programming languages do. Strings were probably the most complex and expensive data type in many dialects of BASIC.
  3. Strings are often used as a crutch where another data type (such as an enum) would be more appropriate and efficient.
  4. What operations are cheap verses expensive on strings can be non-obvious, and can vary from one language to another, from one implemenation of a language to another and even from one invocation to another. You can learn what operations are cheap in one language, but that won't always carry over to another language.
  5. Since the performance of operations on strings often depends on their length, it's easy to create O(n2) algorithms without really thinking about it. This dovetails with the previous point, code that is O(n) in one programming environment may be O(n2) in another.

So what is the performance cost of strings? to discuss that we need to consider what we mean by a string! details will vary between languages, but I think a definition that captures most common ones is.

"a sequence of values representing characters stored in a contiguous region of memory"

In most modern languages the length of said sequence is arbitrary and not determined until run-time. This generally means that the values can't always be be stored directly in the variable. At least some strings must be stored somewhere else and referenced by the variable.

There are various strategies for managing the memory.

  • Reference to immutable data. Copying the string simply copies the reference. Writing directly to the string is not possible, if someone wants a string-like object they can write to they must use a different type. This approach is the norm in languages that use tracing garbage collectors. Some reference-counted implementations also use it.
  • Copy-on-write. Similar to above copying the string copies the reference. Writing to the string behaves differently depending on the reference count. If the reference count is 1 the string is simply written directly. If the reference count is greater than 1 then the string data is copied, the reference is updated to point to the new copy and then the string is written.
  • Unique owning reference, there is exactly one owning reference to each string. If the string is copied the actual data is copied. There may be a way to create non-owning references.
  • Short string optimisation, short strings are stored directly in the variable, longer strings are stored as a reference (potentially using any of the strategies mentioned above but most commonly using a unique reference).

Now lets look at some operations.

Depending on your language and possibly implementation, copying a string may mean just copying a reference, or it may mean copying all of the data in the string. For short strings copying all the data may actually be cheaper than copying a shared reference (thread-safe reference counting is expensive), however for long strings copying all the data can get very expensive. In some cases, you may want to go out of your way to create a non-owning reference to avoid this copy, but will you always remember to do so? and how will you manage the lifetime of that non-owning reference to ensure that the owning reference outlives it?

Comparing a string is another thorny one. In the general case, means working through the strings until a difference is found. In the worst case that potentially means looking at every character of both strings.

However there are often shortcuts. An implementation may bail out as soon as it finds a difference. An implementation that uses shared references may check for reference equality before comparing actual string data. An implementation that stores the length of the strings explicitly may compare the lengths before it starts comparing the data.

So the time to compare two strings can vary wildly, even within the same context.

Now lets consider concatenation. In some programming environments it may be possible to make += or a similar operator re-use the buffer of one of the strings, but much of the time concatenating two strings is likely to result in copying both of them.

Now lets consider searching, when you think about it, it's pretty obvious this must have a cost that depends on the size of the string but you don't always think about it.

Now lets consider slicing, in some languages this may return a special slice type which avoids copying the actual data, but in others it means creating a new string and copying all the data requested by the slice operation.

Now lets consider insertion and removal. At best, inserting into or removing from a string means at re-writing all the data beyond the point of insertion or removal. In practice either due to the structure of the language, or due to the inability of the memory manager to extend the allocation in place it will often involve copying all the data in the string.

1

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.

1

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.

1

Strings are not slow as a general rule, but certain operations on strings will depend on the length of the string, so will be slower the longer the string.

For example, searching for a particular character in a string will (in the worst case) take one "average operation" per character. So searching for a given character in a 1000-character string will take 1000 average operations.

Saying "strings are slow" is probably intended as a warning to look out for such cases where the cost of an operation will depend on the length of the string. For example the operation

a + b

would cost one "average operation" if a and b are integers, but if a and b are strings (assuming a language like Java), the operation is a string concatenation and the cost will be one average operation pr character in both strings. If you are doing lots of concatenation, e.g. adding to a string in a loop, it can easily get slow.

On the other hand, an assignment like:

a = b

would cost a single average operation whether the types are integers or strings, since it is just a reference being copied. So it is not always immediately obvious which operations will be slow and which will be fast, and it will depend on the programming language.

An operation like comparing two strings will in the worst case cost an average operation per character, but in a language like Java there are many optimizations which means in many (maybe most) cases it will only cost a single operation (e.g. if the strings have different length we know up front they can't be equal).

Java also have an optimization called string interning, where string literals are compared already at compile time to remove duplicates. This means two string literals will never need to be compared character-by-character at runtime. So for example using strings as an alternative to enum values will probably be just as fast as using integers, despite the intuition that strings would be slower.

Keep in mind that if you have short strings the cost of per-character operations would probably be practically negligible anyway. But if you want an intuition for what code could be a performance bottleneck, it is worth keeping the worst-case scenario of character-by-character operations in mind.

Finally, "slow" should always be met with "compared to what?". Sure concatenating two strings is slower than adding two numbers, but it is not really a relevant comparison since there isn't a realistic scenario where your choice would be between these two operations.

1

Despite obviously being essential, strings are an extremely complicated data type. They are mostly used to represent the text of natural language, using a binary computer which is fundamentally numeric in its representation.

The char type is (usually) an ordinary byte, but tagged as representing a non-numeric symbol according to an encoding scheme (like ASCII).

A string is typically a variable-length array of chars.

Variable-length arrays are inherently slow to process because of the nature of computer hardware, where hardware is typically tailored to accelerating certain fixed-length operations.

Fixed-length operations are usually so much faster, that it's usually desirable to waste space or risk overflow and crash, in order to represent something in a fixed-length form, than resort to a variable-length representation.

It is found in practice however that this shoehorning into fixed-length representations does not pay off with strings.

This is because the total length of a string is usually several bytes at minimum, to an almost unlimited maximum. The minimum is already too high for most hardware to treat efficiently as a single fixed-length unit, and the maximum is far too large to afford the waste.

Strings are also often quite large compared to any other data type, so the typical string is slower to process because it is inherently carrying a lot of weight in terms of data volume. For example, an Int-32 which is capable of representing a number to a fairly massive 10 places long (when written out as decimal), uses the same space as a string only 4 characters long (which is far shorter than the average string, not even enough for a single average word in English).

But unlike variable-length arrays in general, there are many frequently-used array operations that are fairly specific to strings, as well as handling patterns that resemble the way scalars are handled much more than they resemble how other kinds of array are commonly operated upon and handled.

This means that in most programming languages, strings are designed to seem to be on an equal footing with other "primitives" or scalar values.

But when you actually understand how they work, and how much data is actually in an average string compared to how much data is in (say) the average integer, you realise that they are conceptually quite complicated and they are relatively complicated for the hardware to handle.

That's why strings might be regarded as "slower than average", if we compare with the handling of other types which tend to be intrinsically smaller in the volume of data they carry, and have fixed-length, hardware-accelerated representations to make processing them blazingly fast.

-1

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

5
  • 3
    It doesn't necessarily.
    – user16764
    Feb 29, 2012 at 7:11
  • 3
    Supercalifragilisticexpialidocious
    – Spoike
    Apr 30, 2012 at 14:04
  • s/word/syllable/g
    – Caleb
    Nov 7, 2012 at 18:48
  • Let me answer your question-answer with a question: why don’t you say what your answer is meant to mean? It is, after all, far from clear how it can be interpreted as applying to some run-time system.
    – PJTraill
    Feb 15, 2016 at 11:58
  • @Spoike. Look at the Unicode standard. There’s an emoji (a single character) for a family with 2 children. With separate gender and skin colour for each. πŸ‘¨β€πŸ‘¨β€πŸ‘¦β€πŸ‘¦πŸ‘¨β€πŸ‘¨β€πŸ‘¦β€πŸ‘¦πŸ‘©β€πŸ‘©β€πŸ‘¦β€πŸ‘¦πŸ‘¨β€πŸ‘©β€πŸ‘¦β€πŸ‘¦
    – gnasher729
    Sep 29, 2023 at 19:33
-1

Your question is maybe 200 characters. It is stored in one string. It could have been stored in an array of 200 bytes.

A string will be slow compared to a byte. It is not slow compared to 200 bytes.

1

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