1 简介

本文主要介绍string在拷贝时, 对字符串的处理用了那些技术.

目前的STL中, gcc版(libstdc++)的string使用了COW技术, 而visual c++和clang c++使用了SSO(small object optimization). 还有一些用了eager copy.

COW

当两个 string 发生赋值, 拷贝构造时, 不会复制char *字符串, 而是增加一个引用计数, 然后指针指向同一个原始字符串. 只有当需要修改其中一个字符串时, 才复制.

COW可能会带来性能损失: 例如两个string共享了一个char *, 两个线程各自对两个string修改, 都发现该string的引用计数为2, 所以都分配一块新内存并复制, 此时就出现了两次复制, 而不用COW的话只有一次复制.

另外某些明明是只读的操作, 例如str.at(0), 但是由于并不知道拿到这个字符要干嘛, 所以也会复制一遍.

g++的string使用了COW, 但是引用计数并不在对象中, 实际上, 对象中只包含一个指针, 其他数据都在指向的地址中, 这样共享同一个字符串的string对象才能知道有多少引用计数.

cpp_string_20160405_210703.png

COW还有一个问题, 例如以下代码:

string s1 = "hehe";
char *p = &s1[0];
string s2 = s1;
*p = 'H';

这段代码会导致s2的第0个字符也被改变. 解决方法是新加一个flag, 当执行第二行语句时, flag=false, 第三句时发现flag为false, 就不增加引用计数而是新建一个字符串.

SSO

string的一般实现中, 会包含三个成员变量:

class string
{
  char*  _begin;                // 字符串指针
  size_t _size;                 // 字符串长度
  size_t _capacity;             // buffer的容量
  // ...
};

通常来说一个程序里用到的字符串大部分都很短小, 而在64位机器上, 一个char*指针就占用了8个字节. 因此出现了SSO, 核心思想就是, 反正发生拷贝时要复制一个char *指针, 对小字符串来说干嘛不直接复制整个字符串呢, 说不定还没有复制一个指针的代价大. 于是出现了这样的string

class string
{
  union Buffer
  {
    char*    _begin;
    char[16] _local;
  };

  Buffer _buffer;
  size_t _size;
  size_t _capacity;
  // ...
};

当字符串很小时, _buffer直接存放整个字符串. 当字符串很大时, _buffer才存放字符串指针.

这样做的好处还在于, 新分配一个字符串所需的空间需要通过new从heap中分配, 这部操作比较耗时, 而直接在string内部存放的话就跳过了这步.

实际的SSO是这样的: cpp_string_20160405_210400.png

eager copy

就是每次拷贝都深拷贝, 完全复制一遍.

最佳策略

例如facebook的folly库中, fbstring根据不同长度使用不同的拷贝策略, 最终每个fbstring对象都是24字节.

  1. 很短的用SSO(0-22), 23字节表示字符串(包括’\0′), 1字节表示长度.
  2. 中等长度的(23-255)用eager copy, 8字节字符串指针, 8字节size, 8字节capacity.
  3. 很长的(>255)用COW. 8字节指针(指向的内存包括字符串和引用计数), 8字节size, 8字节capacity.

2 线程安全性

两个线程同时对同一个字符串进行操作的话, 是不可能线程安全的, 出于性能考虑, C++并没有为string实现线程安全, 毕竟不是所有程序都要用到多线程.

但是两个线程同时对独立的两个string操作时, 必须是安全的. COW技术实现这一点是通过原子的对引用计数进行+1或-1操作.

CPU的原子操作虽然比mutex锁好多了, 但是仍然会带来性能损失, 原因如下:

  1. 阻止了CPU的乱性执行.
  2. 两个CPU对同一个地址进行原子操作, 会导致cache失效, 从而重新从内存中读数据.
  3. 系统通常会lock住比目标地址更大的一片区域,影响逻辑上不相关的地址访问
  1. 文章写的很不错,原理讲的非常清晰。难得看到这么清晰的文章,忍不住就回复一下。
    两个问题,一个是COW的代码有个地方写错了, char *p = s1[0]; 应该是 char *p = &s1[0];
    另一个是g++虽然是用COW,但是并不存在文章中代码所写的问题,stl为了保证cow的正确性,string统统认定operator[]和at()具有修改的“语义”,所以在char *p = &s1[0]的时候就已经深拷贝了。
    不过cow确实存在一些问题,原理跟博主说的差不多,详细就不在回复里提了。
    博主的文章写的很清晰,赞一个:D

    • 谢谢指正!

      关于第二个问题, 例子中char *p=s1[0]是在string s2=s1之前的, 所以在执行s1[0]的时候s1引用计数还是1, 也就不会有深拷贝发生了. 不过我后来在ubuntu上实验了一下, 确实并不会出现例子中问题, 应该是执行char *p=s1[0]的时候设置了某个flag, 这样到string s2=s1这一步的时候就不再COW, 而是直接复制整个字符串了.

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>