Meaning of acronym SSO in the context of std::string

Question

In a C++ question about optimization and code style, several answers referred to "SSO" in the context of optimizing copies of std::string. What does SSO mean in that context?

Clearly not "single sign on". "Shared string optimization", perhaps?

Solution 1

Background / Overview

Operations on automatic variables ("from the stack", which are variables that you create without calling malloc / new) are generally much faster than those involving the free store ("the heap", which are variables that are created using new). However, the size of automatic arrays is fixed at compile time, but the size of arrays from the free store is not. Moreover, the stack size is limited (typically a few MiB), whereas the free store is only limited by your system's memory.

SSO is the Short / Small String Optimization. A std::string typically stores the string as a pointer to the free store ("the heap"), which gives similar performance characteristics as if you were to call new char [size]. This prevents a stack overflow for very large strings, but it can be slower, especially with copy operations. As an optimization, many implementations of std::string create a small automatic array, something like char [20]. If you have a string that is 20 characters or smaller (given this example, the actual size varies), it stores it directly in that array. This avoids the need to call new at all, which speeds things up a bit.

EDIT:

I wasn't expecting this answer to be quite so popular, but since it is, let me give a more realistic implementation, with the caveat that I've never actually read any implementation of SSO "in the wild".

Implementation details

At the minimum, a std::string needs to store the following information:

• The size
• The capacity
• The location of the data

The size could be stored as a std::string::size_type or as a pointer to the end. The only difference is whether you want to have to subtract two pointers when the user calls size or add a size_type to a pointer when the user calls end. The capacity can be stored either way as well.

You don't pay for what you don't use.

First, consider the naive implementation based on what I outlined above:

class string {
public:
    // all 83 member functions
private:
    std::unique_ptr<char[]> m_data;
    size_type m_size;
    size_type m_capacity;
    std::array<char, 16> m_sso;
};

For a 64-bit system, that generally means that std::string has 24 bytes of 'overhead' per string, plus another 16 for the SSO buffer (16 chosen here instead of 20 due to padding requirements). It wouldn't really make sense to store those three data members plus a local array of characters, as in my simplified example. If m_size <= 16, then I will put all of the data in m_sso, so I already know the capacity and I don't need the pointer to the data. If m_size > 16, then I don't need m_sso. There is absolutely no overlap where I need all of them. A smarter solution that wastes no space would look something a little more like this (untested, example purposes only):

class string {
public:
    // all 83 member functions
private:
    size_type m_size;
    union {
        class {
            // This is probably better designed as an array-like class
            std::unique_ptr<char[]> m_data;
            size_type m_capacity;
        } m_large;
        std::array<char, sizeof(m_large)> m_small;
    };
};

I'd assume that most implementations look more like this.

Solution 2

SSO is the abbreviation for "Small String Optimization", a technique where small strings are embedded in the body of the string class rather than using a separately allocated buffer.

Solution 3

As already explained by the other answers, SSO means Small / Short String Optimization. The motivation behind this optimization is the undeniable evidence that applications in general handle much more shorter strings than longer strings.

As explained by David Stone in his answer above, the std::string class uses an internal buffer to store contents up to a given length, and this eliminates the need to dynamically allocate memory. This makes the code more efficient and faster.

This other related answer clearly shows that the size of the internal buffer depends on the std::string implementation, which varies from platform to platform (see benchmark results below).

Benchmarks

Here is a small program that benchmarks the copy operation of lots of strings with the same length. It starts printing the time to copy 10 million strings with length = 1. Then it repeats with strings of length = 2. It keeps going until the length is 50.

#include <string>
#include <iostream>
#include <vector>
#include <chrono>

static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
static const int ARRAY_SIZE = sizeof(CHARS) - 1;

static const int BENCHMARK_SIZE = 10000000;
static const int MAX_STRING_LENGTH = 50;

using time_point = std::chrono::high_resolution_clock::time_point;

void benchmark(std::vector<std::string>& list) {
    std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();

    // force a copy of each string in the loop iteration
    for (const auto s : list) {
        std::cout << s;
    }

    std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
    const auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
    std::cerr << list[0].length() << ',' << duration << '\n';
}

void addRandomString(std::vector<std::string>& list, const int length) {
    std::string s(length, 0);
    for (int i = 0; i < length; ++i) {
        s[i] = CHARS[rand() % ARRAY_SIZE];
    }
    list.push_back(s);
}

int main() {
    std::cerr << "length,time\n";

    for (int length = 1; length <= MAX_STRING_LENGTH; length++) {
        std::vector<std::string> list;
        for (int i = 0; i < BENCHMARK_SIZE; i++) {
            addRandomString(list, length);
        }
        benchmark(list);
    }

    return 0;
}

If you want to run this program, you should do it like ./a.out > /dev/null so that the time to print the strings isn't counted. The numbers that matter are printed to stderr, so they will show up in the console.

I have created charts with the output from my MacBook and Ubuntu machines. Note that there is a huge jump in the time to copy the strings when the length reaches a given point. That's the moment when strings don't fit in the internal buffer anymore and memory allocation has to be used.

Note also that on the linux machine, the jump happens when the length of the string reaches 16. On the macbook, the jump happens when the length reaches 23. This confirms that SSO depends on the platform implementation.

Ubuntu

Macbook Pro

Comments

[josesuero]

That is only a duplicate in the same way that "what is 2+2" is a duplicate of "what is the result of 200 / 50". The answer is the same. The question is completely different. "Close as duplicate" is intended to be used when multiple people ask the same* question. When one person asks "how is std::string implemented", and another asks "what does SSO mean", you have to be absolutely insane to consider them to be the same question

[Oliver Charlesworth]

@jalf: If there's an existing Q+A that exactly encompasses the scope of this question, I'd consider it a duplicate (I'm not saying the OP should have searched for this himself, merely that any answer here will cover ground that's already been covered.)

[josesuero]

You're effectively telling the OP that "your question is wrong. But you needed to know the answer in order to know what you should have asked". Nice way to turn people off SO. It also makes it needlessly hard to find the information you needed. If people don't ask questions (and closing is effectively saying "this question should not have been asked"), then there would be no possible way for people who don't already know the answer, to get the answer to this question

[Oliver Charlesworth]

@jalf: Not at all. IMO, "vote to close" doesn't imply "bad question". I use downvotes for that. I consider it a duplicate in the sense that all the myriad questions (i=i++, etc.) whose answer is "undefined behaviour" are duplicates of each other. On a different note, why has no-one answered the question if it's not a duplicate?

[Matthieu M.]

@jalf: I agree with Oli, the question is not a duplicate, but the answer would be, therefore redirecting to another question where the answers already lay seem appropriate. Questions closed as duplicates do not disappear, instead they act as pointers toward another question where the answer lays. The next person looking for SSO will end up here, follow the redirection, and find her answer.

[BillT]

Here's a good explanation of some actual implementations: stackoverflow.com/a/28003328/203044

[TonySalimi]

Is SSO really practical when most developers pass std::string using const references?

[David Stone]

SSO has two benefits beyond making copying cheaper. The first is that if your string size fits in the small buffer size, you do not need to allocate on the initial construction. The second is that when a function accepts a std::string const &, getting at the data is a single memory indirection, because the data is stored at the location of the reference. If there were no small string optimization, accessing the data would require two memory indirections (first to load the reference to the string and read its contents, then the second to read the contents of the data pointer in the string).

[Admin]

I cut the time down from nearly 4 minutes to nearly 1 minute by removing less than necessary design choices. ideone.com/KJCh2H