libc ++中短字符串优化的机制是什么？ [英] What are the mechanics of short string optimization in libc++?

问题描述

此回答提供了简短字符串优化（SSO）的高级概述。但是，我想更详细地了解它在实践中是如何工作的，特别是在libc ++实现中：

• 字符串必须是为了符合SSO资格吗？



• 在访问字符串数据时，实现如何区分短和长
  字符串？是简单的 m_size< =
16 还是它是一个标志，是一些其他成员变量的一部分？ （I
  设想 m_size 或其一部分也可用于存储
  字符串数据）。

我问这个问题专门为libc ++，因为我知道它使用SSO，这甚至提到在 libc ++主页。

这是观察源代码：

libc ++可以用两个稍微不同的字符串类的内存布局进行编译，这由 _LIBCPP_ALTERNATE_STRING_LAYOUT 标志管理。这两种布局还区分了小端和大端的机器，这使我们总共有4个不同的变体。

进一步假设 size_type 是4，我将在下面假设正常布局和小端。字节，并且 value_type 是1个字节，这是字符串的前4个字节在内存中的样子：

  // short string：（s）ize和3个字节的char（d）ata 
 sssssss0; dddddddd; dddddddd; dddddddd 
 ^  -  is_long = 0 
 
 // long string：（c）apacity 
 ccccccc1; cccccccc; cccccccc; cccccccc 
 ^  -  is_long = 1 
  

由于短字符串的大小位于高7位，因此访问时需要移动：

  size_type __get_short_size（）const {
 return __r_.first（）.__ s .__ size_>> 1; 
} 
  

类似地，长字符串容量的getter和setter使用 __ long_mask 以解决 is_long 位。

寻找对我的第一个问题的答案，即，什么值 __ min_cap ，短字符串的容量，为不同的架构？

其他标准库实现

这个回答在其他标准库实现中给出了 std :: string 内存布局的很好的概述。

解决方案

libc ++ basic_string 设计为在所有的 sizeof 架构，其中 sizeof（word）== sizeof（void *）。您已正确解析了长/短标记和缩写形式的大小字段。

__min_cap的值，short

在简短的形式中，有3个单词可以使用：

• 1位表示长/短标记。


• 大小为7位。


• 假设 char ，1个字节到尾部空值（libc ++将总是在数据后面存储一个尾随空值）。






这将留下3个字减去2个字节来存储一个短字符串（即最大的 capacity（），无需分配） / p>



在32位机器上，10个字符将适合短字符串。 sizeof（string）为12。





在64位机器上，22个字符将适合短字符串。 sizeof（string）为24。





主要设计目标是最小化 sizeof（string）内部缓冲区尽可能大。理由是加快移动建设和移动任务。 sizeof 越大，您在移动建筑或移动作业期间必须移动的字词越多。





形式需要至少3个字来存储数据指针，大小和容量。因此，我把短格式限制在那些相同的3个词。有人建议，一个4字的sizeof可能有更好的性能。我没有测试这个设计选择。




This answer gives a nice high-level overview of short string optimization (SSO). However, I would like to know in more detail how it works in practice, specifically in the libc++ implementation:

• How short does the string have to be in order to qualify for SSO? Does this depend on the target architecture?

• How does the implementation distinguish between short and long strings when accessing the string data? Is it as simple as m_size <= 16 or is it a flag that is part of some other member variable? (I imagine that m_size or part of it might also be used to store string data).

I asked this question specifically for libc++ because I know that it uses SSO, this is even mentioned on the libc++ home page.

Here are some observations after looking at the source:

libc++ can be compiled with two slightly different memory layouts for the string class, this is governed by the _LIBCPP_ALTERNATE_STRING_LAYOUT flag. Both of the layouts also distinguish between little-endian and big-endian machines which leaves us with a total of 4 different variants. I will assume the "normal" layout and little-endian in what follows.

Assuming further that size_type is 4 bytes and that value_type is 1 byte, this is what the first 4 bytes of a string would look like in memory:

// short string: (s)ize and 3 bytes of char (d)ata
sssssss0;dddddddd;dddddddd;dddddddd
       ^- is_long = 0

// long string: (c)apacity
ccccccc1;cccccccc;cccccccc;cccccccc
       ^- is_long = 1

Since the size of the short string is in the upper 7 bits, it needs to be shifted when accessing it:

size_type __get_short_size() const {
    return __r_.first().__s.__size_ >> 1;
}

Similarly, the getter and setter for the capacity of a long string uses __long_mask to work around the is_long bit.

I am still looking for an answer to my first question, i.e. what value would __min_cap, the capacity of short strings, take for different architectures?

Other standard library implementations

This answer gives a nice overview of std::string memory layouts in other standard library implementations.

解决方案

The libc++ basic_string is designed to have a sizeof 3 words on all architectures, where sizeof(word) == sizeof(void*). You have correctly dissected the long/short flag, and the size field in the short form.

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

In the short form, there are 3 words to work with:

• 1 bit goes to the long/short flag.
• 7 bits goes to the size.
• Assuming char, 1 byte goes to the trailing null (libc++ will always store a trailing null behind the data).

This leaves 3 words minus 2 bytes to store a short string (i.e. largest capacity() without an allocation).

On a 32 bit machine, 10 chars will fit in the short string. sizeof(string) is 12.

On a 64 bit machine, 22 chars will fit in the short string. sizeof(string) is 24.

A major design goal was to minimize sizeof(string), while making the internal buffer as large as possible. The rationale is to speed move construction and move assignment. The larger the sizeof, the more words you have to move during a move construction or move assignment.

The long form needs a minimum of 3 words to store the data pointer, size and capacity. Therefore I restricted the short form to those same 3 words. It has been suggested that a 4 word sizeof might have better performance. I have not tested that design choice.

这篇关于libc ++中短字符串优化的机制是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！