Memory Layout of Strings

Imagine you are writing a string class yourself. Your first version will probably work correctly, but it will often lose to the standard library's string on convenience and speed. One of the main reasons is a design choice the standard implementation makes for you: every time a value is stored, it decides whether the text should live inside the string object or somewhere outside it.

This technique is called short-string optimization. In this article you will follow it through a small example so you can see exactly where each piece of text ends up. By the end you should be able to look at a string value and reason about where its characters are kept, and why that matters for performance.

The core rule is simple to state. A short string value is kept in the string object itself. Only a longer string value is placed on the free store. This means the string object is not always the same kind of thing. For a short value, the object holds the characters directly. For a long value, the object works with storage that lives elsewhere. The layout of the object depends on which of these two situations applies.

Read the diagram as a sketch of structure, not a precise picture. The source gives the layout only in general terms, so it does not show exact sizes or byte counts. What it does show is the key distinction: one object keeps its short text inline, while the other object refers to text stored on the free store.

The source example uses two values: Annemarie, which is shorter, and Annemarie Stroustrup, which is longer. The code below is an original illustration that declares one string object for each value, so you can trace them with the rule from the previous section.

A string does not keep one layout forever. When a string's value changes from short to long, its representation adjusts to match. When the value changes from long back to short, the representation adjusts again. The storage decision follows the current value, not the value the string had when it was first created.

Follow the diagram from left to right. A string that starts with a short value keeps its text inside the object. When its value grows into the long range, the text moves to the free store. If the value later shrinks back to a short length, the representation adjusts again, and the text is kept inside the object once more. The same object can therefore pass through both layouts over its life.

The source makes an important point: the real speed of string operations depends heavily on where the program runs. Short-string optimization is a design answer to that environment, and it is a large part of why it is used so widely. Two environment factors are named in the source as able to change real performance: multi-threaded allocation cost and memory fragmentation from strings of differing lengths.

Multi-threaded allocation cost is about the work needed when storage is requested on the free store while more than one thread of the program is running. Whenever a long value needs free-store storage, that request is an allocation, so the cost of allocating matters more in an environment where several threads make such requests. Keeping short values inside the object avoids that request entirely for those values.

Memory fragmentation is the second factor. The source ties it to strings of differing lengths. When storage of varying sizes is repeatedly requested and released, the free store can end up with gaps between the pieces still in use. Those gaps can make later allocations less efficient, so the same string operation can cost more in a program that has been running a long time than it did at the start.