C++ Short String Optimization st

作者: 韬czt | 来源:发表于2017-07-16 16:47 被阅读0次

简单说明：
C++ Short String Optimization 指C++针对短字符串的优化。

默认情况下，C++的std::string都是存储在heap中，导致访问std::string需要经过一次寻址过程，速度较慢，并且这种实现的空间局部性不好，对cache的利用较低。
很多string的字符串长度很小，这个时候，我们可以把字符串存储到栈上，从而不需要进行内存分配，优化创建速度，并且访问栈上数据的局部性很好，速度比较快。

std::string需要存储如下变量：字符串所在地址，字符串大小size，字符串已经申请的内存capacity，加上短字符串
类似如下struct声明：

struct String {
    char* addr;
    size_t size;
    size_t capacity;
    char[16] short_string;
}

在现在的C++编译器中，因为当小于一定大小时，我们没有使用堆，所以不需要存储addr指针，并且此时的容量就是短字符串容量，也不需要存储，所以短字符串缓存可以和这两者复用，样例如下：

struct String {
    size_t size;
    union {
        struct {
            size_t capacity;
            char* addr;
        }
        char[16] short_string;
    }
}

这时，string没有使用额外的空间，并且能够针对端字符串进行优化，是一个很好的优化方式。

我自己的测试代码：

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <mutex>
#include <array>

using namespace std;

int main(int argc, char const* argv[])
{
  int i;
  vector<char> test_vector;
  mutex g_mutex;
  array<int, 10> test_array;
  deque<char> test_deque;
  string short4("test");
  string long19("test test test test");
  string long29("test test test test test test");

  cout << "stack address: " << &i << endl;
  cout << "vector sizeof: " << sizeof(test_vector) << " vector address: " << &test_vector << endl;
  cout << "g_mutex sizeof: " << sizeof(g_mutex) << " g_mutex address: " << &g_mutex << endl;
  cout << "test_deque sizeof: " << sizeof(test_deque) << " test_deque address: " << &test_deque << endl;
  cout << "test_array sizeof: " << sizeof(test_array) << " test_array address: " << &test_array << endl;
  cout << "sizeof short4: " << sizeof(short4) << " address: " << &short4 << " char address: " << (void*)(&(short4[0])) << endl;
  cout << "sizeof long19: " << sizeof(long19)  << " address: " << &long19 << " char address: " << (void*)(&(long19[0])) << endl;
  cout << "sizeof long29: " << sizeof(long29) << " address: " << &long29 << " char address: " << (void*)(&(long29[0])) << endl;
  return 0;
}

输出：

stack address: 0x7fff5d7eeca4
vector sizeof: 24 vector address: 0x7fff5d7eec88
g_mutex sizeof: 64 g_mutex address: 0x7fff5d7ef210
test_deque sizeof: 48 test_deque address: 0x7fff5d7eec30
test_array sizeof: 40 test_array address: 0x7fff5d7eec60
sizeof short4: 24 address: 0x7fff5d7eec08 char address: 0x7fff5d7eec09 —— 在栈上分配
sizeof long19: 24 address: 0x7fff5d7eebf0 char address: 0x7fff5d7eebf1 —— 栈上
sizeof long29: 24 address: 0x7fff5d7eebd8 char address: 0x7fdf27402710 —— 堆上

工具提示：
在线在 Visual C++里执行C++代码： http://webcompiler.cloudapp.net/
在线在gcc，clang里面执行C++代码： https://wandbox.org/

参考：

[什么是SSO？] (https://stackoverflow.com/questions/10315041/meaning-of-acronym-sso-in-the-context-of-stdstring/10319672#10319672)

回答翻译：

在automatic variables（『栈上』，指没有通过malloc/new常见的变量）上的操作通常要比在free store（『堆上』，通过malloc/new创建的变量）。但是，栈的大小是在编译期确定的，而堆的大小不是的。并且，栈有大小限制（一般是几M），而堆的大小只受限于你的系统内存大小。

SSO是 Short/Small String Optimization. 一个std::string通常是存储指向堆空间的指针，这和调用new char[size]的性能类似。这样做能够防止在非常大的string时不会出现栈溢出，不过它会比较慢，尤其是在复制操作时。作为一个优化，需要std::string的实现创建一个小的栈上的数组，例如:char[20]. 如果你的string长度小于等于20（这是一个例子，与实际大小不同), 它直接把数据保存到这个数组中。这去除了new调用，从而提高了一些速度。

EDIT：
我没有想到这个回答现在这么火，但是因为它确实很火，我在下面给出一个更加实际的实现，但是请注意我没有度过真实世界的SSO实现。

实现详情：
std::string最少需要下述信息：

大小 size
容量 capacity
数据的位置 the location of data

大小可以被存储为std::string::size_type 或者指向末尾的指针。唯一的区别是是在用户调用size时两个指针相减，还是在用户调用end时对开始指针加一个数。capacity也可以以这两种方式存储。

你不需要为你不会使用的东西付款

首先，考虑我在上面提到的最原始的实现方式：

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，我知道了capacity，并且我知道我不需要指向数据的指针。如果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;
    };
};

我认为大多数的实现和这个比较类似。

[Meaning of acronym SSO in the context of std::string 各个编译器实现使用的内存使用情况对比，包含在stack heap中分配的内存，以及可用的capacity Why does libc++'s implementation of std::string take up 3x memory as libstdc++?] (https://stackoverflow.com/questions/27631065/why-does-libcs-implementation-of-stdstring-take-up-3x-memory-as-libstdc/28003328#28003328)

回答翻译：
这辆车有一个简短的程序来帮助你探索std::string使用的不同类型的内存，包括stack和heap

#include <string>
#include <new>
#include <cstdio>
#include <cstdlib>

std::size_t allocated = 0;

void* operator new (size_t sz)
{
    void* p = std::malloc(sz);
    allocated += sz;
    return p;
}

void operator delete(void* p) noexcept
{
    return std::free(p);
}

int
main()
{
    allocated = 0;
    std::string s("hi");
    std::printf("stack space = %zu, heap space = %zu, capacity = %zu\n",
     sizeof(s), allocated, s.capacity());
}

使用 http://melpon.org/wandbox/ 可以很容易的得到不同编译器、库组合的结果，例如：

gcc 4.9.1

stack space = 8, heap space = 27, capacity = 2

gcc 5.0.0

stack space = 32, heap space = 0, capacity = 15

clang/libc++

stack space = 24, heap space = 0, capacity = 22

VS-2015: from( http://webcompiler.cloudapp.net)

stack space = 32, heap space = 0, capacity = 15

上述输出同样带有capacity，这表示度量string能够在堆中新分配一个更大的缓存前能够容纳多少个chars。在gcc5.0.0, libc++和VS2015的实现中，这表示的是短字符串缓存的大小。即：在栈上分配，用来存储短字符串缓存的大小，这时可以避免更代价高昂的堆内存分配。

这里发现libc++中的短字符串实现使用了最小的stack usage，并且包含了最大的短字符串缓存。并且如果你统计总共内存使用（stack + heap），在这四种2-character的string实现中，libC++使用了最小的总内存。

需要注意的是，这些测试都是在64位机器上运行的。在32位系统中，libc++的stack大小降到12，并且短字符串缓存大小降到10。我不知道其他实现在32位的表现，不过你可以使用上述代码来找到相应结果。

[What are the mechanics of short string optimization in libc++? Libc++ 实现] (https://stackoverflow.com/questions/21694302/what-are-the-mechanics-of-short-string-optimization-in-libc)
回答翻译：
libc++的basic_string在所有架构上被设计为sizeof大小为3个words，在这里sizeof(word) == sizeof(void*)。你已经正确分析出long/short标志，以及在short string类型时的size区域。

what value would __min_cap, the capacity of short strings, take for different architectures?

那么__min_cap，short string的容量，在各个架构上怎么计算的？

在short string的情况下，下面是string实现的3个words所做的工作

1一个bit用来表示short/long标志
7个bits表示字符串当前大小
在char的情况下，一个字节用来表示字符串末尾的null（libc++会在数据后面一致保存一个结束的null）

这种情况下，剩下3 * words - 2 bytes的数据来存储短字符串(也就是短字符串不进行内存分配时最大的capacity())
在32位模式下，短字符串可以放置10个chars，sizeof(string) = 12 (3 * 4).
在64位模式下，短字符串可以放置22个chars，sizeof(string) = 24 (3 * 8).

这里的一个主要设计目标是：在最小化sizeof(string)的同时，让内部的buffer尽可能大。其中的根本原因是加速move语义构造和move语义赋值。当sizeof越大时，就需要在move语义构造和move语义赋值时移动更多的字节。

在长字符串的情况，至少需要三个words来分别存储数据指针(pointer)、大小(size)、容量(capacity)，因此我(作者)把短字符串格式限制到这三个words中。曾经有人提出4个words大小的sizeof可能会有更好的性能。但是我(作者)没有测试过这种设计选择。

[更精致的实现 SSO23，还分析了相关各个实现的细节] (https://github.com/elliotgoodrich/SSO-23)

写作方式参考，从string可能会占据多少字符串开始讲起

C++ Short String Optimization st

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读