C++ std::string 上下文中首字母缩略词 SSO 的含义
声明:本页面是StackOverFlow热门问题的中英对照翻译,遵循CC BY-SA 4.0协议,如果您需要使用它,必须同样遵循CC BY-SA许可,注明原文地址和作者信息,同时你必须将它归于原作者(不是我):StackOverFlow
原文地址: http://stackoverflow.com/questions/10315041/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Meaning of acronym SSO in the context of std::string
提问by Raedwald
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?
在有关优化和代码样式的 C++ 问题中,有几个答案在优化std::string
. 在这种情况下,SSO 是什么意思?
Clearly not "single sign on". "Shared string optimization", perhaps?
显然不是“单点登录”。“共享字符串优化”,也许?
回答by David Stone
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.
对自动变量(“来自堆栈”,即无需调用malloc
/即可创建的变量new
)的操作通常比涉及自由存储(“堆”,即使用 创建的变量)快得多new
。但是,自动数组的大小在编译时是固定的,而自由存储中的数组大小则不是。此外,堆栈大小是有限的(通常为几 MiB),而空闲存储仅受系统内存的限制。
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.
SSO 是短/小字符串优化。Astd::string
通常将字符串存储为指向空闲存储(“堆”)的指针,这提供了与调用new char [size]
. 这可以防止非常大的字符串的堆栈溢出,但它可能会更慢,尤其是对于复制操作。作为优化,许多实现std::string
创建了一个小的自动数组,比如char [20]
. 如果您有一个小于等于 20 个字符的字符串(在本示例中,实际大小会有所不同),它会将其直接存储在该数组中。这完全避免了调用的需要new
,从而加快了速度。
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".
我没想到这个答案会如此受欢迎,但既然如此,让我给出一个更现实的实现,但需要注意的是,我从未真正阅读过任何“野外”SSO 实现。
Implementation details
实施细则
At the minimum, a std::string
needs to store the following information:
至少,astd::string
需要存储以下信息:
- 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.
大小可以存储为std::string::size_type
指向末尾的指针或指针。唯一的区别是您是否希望在用户调用时减去两个指针size
或在用户调用时添加size_type
一个指针end
。容量也可以以任何一种方式存储。
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):
对于 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;
};
};
I'd assume that most implementations look more like this.
我认为大多数实现看起来更像这样。
回答by Mark Ransom
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.
SSO 是“Small String Optimization”的缩写,这是一种将小字符串嵌入到字符串类的主体中而不是使用单独分配的缓冲区的技术。
回答by HugoTeixeira
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.
正如其他答案已经解释的那样,SSO 意味着Small / Short String Optimization。这种优化背后的动机是不可否认的证据,即应用程序通常比长字符串处理更多的短字符串。
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 efficientand faster.
正如 David Stone在上面的回答中所解释的那样,std::string
该类使用内部缓冲区来存储最多给定长度的内容,这消除了动态分配内存的需要。这使得代码更加高效和快速。
This other related answerclearly shows that the size of the internal buffer depends on the std::string
implementation, which varies from platform to platform (see benchmark results below).
这个其他相关的答案清楚地表明内部缓冲区的大小取决于std::string
实现,这因平台而异(请参阅下面的基准测试结果)。
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.
这是一个小程序,用于对大量相同长度的字符串的复制操作进行基准测试。它开始打印复制 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;
}
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.
如果你想运行这个程序,你应该这样做,这样./a.out > /dev/null
打印字符串的时间就不会被计算在内。重要的数字被打印到stderr
,因此它们将显示在控制台中。
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.
我已经使用 MacBook 和 Ubuntu 机器的输出创建了图表。请注意,当长度达到给定点时,复制字符串的时间会有很大的跳跃。那是字符串不再适合内部缓冲区并且必须使用内存分配的时刻。
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.
还要注意,在linux机器上,当字符串的长度达到16时发生跳转。在macbook上,当长度达到23时发生跳转。这证实了SSO依赖于平台实现。