在 std: : string 上下文中缩写词 SSO 的含义

小开

SSO 是“小字符串优化”的缩写，这种技术将小字符串嵌入到字符串类的主体中，而不是使用单独分配的缓冲区。

小开

最佳答案

背景/概述

对自动变量的操作(“从堆栈”，这是您在不调用 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。容量也可以以任何一种方式存储。

不用的东西不用付钱。

首先，考虑一下基于我上面概述的初步实施情况:

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个字节的“开销”，另外还有16个 SSO 缓冲区(由于填充要求，这里选择了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;
};
};

我假设大多数实现看起来更像这样。

小开

正如其他答案已经解释的那样，SSO 意味着 小/短字符串优化。这种优化背后的动机是不可否认的证据，即应用程序通常处理比长字符串更短的字符串。

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

另一个相关的答案清楚地表明，内部缓冲区的大小取决于 std::string实现，这种实现因平台而异(参见下面的基准测试结果)。

基准

下面是一个小程序，它对大量具有相同长度的字符串的复制操作进行基准测试。它开始输出复制1000万个长度为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