在std::string的上下文中，SSO缩写的意思是什么？

Question

在std::string的上下文中，SSO缩写的意思是什么？

c++stringoptimization

196

在有关优化和代码风格的C++问题中，有几个答案提到了在优化std::string的拷贝时上下文中的“SSO”。那么在这个上下文中，SSO是什么意思呢？

显然不是“单点登录”。也许是“共享字符串优化”？

- Raedwald

72

这只是一种类似于“2+2等于几”的问题，与“200/50的结果是多少”相同。答案是相同的，但问题完全不同。“标记为重复”意在用于多人提出同样的问题。当一个人问“如何实现'std::string'”，而另一个人问“什么是SSO”的含义时，你必须非常疯狂才能认为它们是相同的问题。 - jalf

3

如果已经有一个现有的问答涵盖了这个问题的范围，我会认为这是一个重复的问题（我并不是说提问者应该自己搜索，只是任何在这里回答的内容都将涵盖已经被讨论过的领域）。 - Oliver Charlesworth

55

你实际上在告诉提问者：“你的问题是错误的。但是你需要知道答案才能知道你应该问什么。”这样说很容易让人对 SO 失去兴趣。这也使得查找所需信息变得不必要地困难。如果人们不问问题（关闭实际上意味着“这个问题不应该被问到”），那么那些不已经知道答案的人想要得到这个问题的答案将没有可能。 - jalf

12

@jalf: 完全不是这样。在我看来，“投票关闭”并不意味着“问题很差”。我用downvotes来表示这点。我认为这是一个重复的问题，因为所有无数个问题（如i=i++等），它们的答案都是“未定义行为”，彼此之间都是重复的。另外，如果这不是重复问题，为什么没有人回答这个问题呢？ - Oliver Charlesworth

10

@jalf: 我同意Oli的观点，这个问题不是重复的，但答案可能会是，因此将其重定向到另一个已经有答案的问题似乎是合适的。作为重复关闭的问题并没有消失，而是充当指向答案所在的另一个问题的指针。下一个寻找SSO的人将会来到这里，跟随重定向，并找到她的答案。 - Matthieu M.

3个回答

34

正如其他答案已经解释的那样，SSO表示"Small/Short String Optimization"（小字符串/短字符串优化）。这种优化的动机是不可否认的证据表明，应用程序通常处理的字符串要比长字符串短得多。

正如David Stone在他上面的回答中所解释的那样，std::string类使用一个内部缓冲区来存储内容，直到给定长度为止，这消除了动态分配内存的需要。这使代码更高效和更快。

这个相关的答案清楚地显示，内部缓冲区的大小取决于std::string的实现，这因平台而异（请参见下面的基准测试结果）。

基准测试

下面是一个小程序，对具有相同长度的大量字符串进行复制操作的基准测试。它开始打印复制1千万个长度为1的字符串所需的时间。然后，它会重复使用长度为2的字符串。一直进行下去，直到长度达到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;
}

如果您想运行此程序，应该像这样执行：./a.out > /dev/null，这样打印字符串的时间就不会被计算。

重要的数字将被打印到stderr中，因此它们将显示在控制台中。

我已经使用我的MacBook和Ubuntu机器的输出创建了图表。请注意，当长度达到一定点时，复制字符串所需的时间会大幅增加。那是字符串不再适合内部缓冲区并且必须使用内存分配的时刻。

还要注意，在Linux机器上，跳变发生在字符串长度达到16时。在Macbook上，跳变发生在长度达到23时。这证实了SSO取决于平台实现。

Ubuntu

Macbook Pro

- HugoTeixeira

1

我通过删除不必要的设计选择，将时间从将近4分钟缩短到将近1分钟。https://ideone.com/KJCh2H - user10063119

34

SSO是“Small String Optimization”的缩写，这是一种技术，在该技术中，小字符串被嵌入到字符串类的主体中，而不是使用单独分配的缓冲区。

- Mark Ransom

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Stone · Accepted Answer

背景/概述

自动变量（从栈中创建的变量，即不调用malloc/new创建的变量）的操作通常比涉及自由存储区（使用new创建的变量）的操作要快得多。但是，自动数组的大小在编译时固定，而来自自由存储区的数组的大小则不固定。此外，堆栈大小受限（通常为几个 MiB），而自由存储区仅受系统内存限制。

SSO 是短字符串优化。一个std::string通常将字符串存储为指向自由存储区（"堆"）的指针，这给出了类似于调用new char [size]的性能特征。这可以防止非常大的字符串导致堆栈溢出，但对于复制操作可能会更慢。作为一种优化，许多std::string实现会创建一个小的自动数组，例如char [20]。如果您有一个长度小于等于20个字符的字符串（根据此示例，实际大小会有所变化），它会直接存储在该数组中。这避免了完全调用new的需要，从而加快了速度。

编辑：

我没有预料到这个答案会如此受欢迎，但既然如此，让我给出一个更现实的实现，但要注意我从未真正阅读过 SSO 的任何实现。

实现细节

std::string至少需要存储以下信息：

大小
容量
数据位置

大小可以存储为std::string::size_type 或指向末尾的指针。唯一的区别在于您是想在用户调用size时必须减去两个指针还是在用户调用end时必须将size_type加到指针上。容量也可以以这两种方式之一存储。

你所不使用的部分不需要付出代价。

首先，考虑基于我上面概述的 Naive 实现：

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;
};

对于一个64位系统，这通常意味着每个字符串的std::string有24字节的“开销”，再加上SSO缓冲区的16字节（由于填充要求，这里选择16而不是20）。在我的简化示例中，将那三个数据成员和本地字符数组存储起来并不是很明智。如果m_size <= 16，那么我会将所有数据存储在m_sso中，因此我已经知道容量，不需要指向数据的指针。如果m_size > 16，则我不需要m_sso。绝对没有重叠的情况下我需要它们全部。一个更聪明、不浪费空间的解决方案看起来会像这样（未经测试，仅供示例）：

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;
    };
};

我会认为大多数实现看起来更像这样。