高性能std::string替代品fbstring

当在程序里面需要使用string时,一般大家会有这样几种实现:

  1. char[SIZE],栈上分配性能高,但大小有限制,不能动态增长。
  2. 一个简单的对象,里面持有一块堆上分配的内存空间,但拷贝时会分配新空间把这块东西拷贝过去。但如果string很大,则拷贝的性能开销也不小。
  3. 在2的基础上加入引用计数,然后copy on write,从而防止过多的拷贝性能开销,但引用计数本身会有一定的同步机制,从而对CPU的流水线造成一些影响。

std::string是以上第三种方案的实现。所以其实std::string在持有较小的string时并不十分有效,且在多线程环境下可能对CPU的流水线执行造成一定的影响。

Facebook的folly中的fbstring通过把以上三种方式揉在一起,提供了一种性能较高的string实现,在大部分string较小且处于多线程环境中时,fbstring会提供比std::string更好的表现。

简单来说,fbstring是这样实现的(摘自FBString.h中的注释,我简单翻译了一下):

  1. “小”string(长度0~23字节)保存在fbstring结构内部,不额外在堆上开空间
  2. “中”string(长度24~254字节)在堆上开空间,但拷贝时会复制整个string
  3. “大”string(长度大于254字节)在堆上开空间,引用计数

这样就综合了文章最开始提到的三种方案的优点。

那么它是如何把这三种结构融合到一起的呢?

重点在这里(fbstring的数据成员):

union {	
  mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
  mutable MediumLarge ml_;
};

其中MediumLarge的实现为:

struct MediumLarge {
  Char * data_;
  size_t size_;
  size_t capacity_;

  size_t capacity() const {
    return capacity_ & capacityExtractMask;
   }
};

MediumLarge的大小为24个字节,也就是说这样small_数组的长度也就是24字节,“小”string就是保存在small_数组中的。

而“中”和“大”的string则是保存在MediumLarge中。

那么还剩下三个问题:

  1. “小”string的长度放在哪里?
  2. string的类型(小中大)放在哪里?
  3. “大”string的引用计数对象指针放在哪里?

这里的实现很有意思,有点榨干每一分剩余空间的意思,回答依次如下:

  1. 长度存放在small_数组的最后一个元素上,因为small_数组只有24个字节,所以长度必然不可能超过一个字节
  2. 既然small_数组的最后一个元素不可能超过24,那么就利用这个元素的最高两位存type好了。那么MediumLarge结构体怎么办呢?回头看看,在小字端的情况下,这两个位正好对应capacity_的最高两位,size_t的最高两位怎么也不可能用到,那就成了~ (实际上fbstring也不支持大字端)
  3. 其实也很简单,因为已经可以根据2区分出type,那么data_的头上就可以存放引用计数对象啦。

里面还有一些比较细节的优化,感觉作者很有心,标准库也可以做的很精细,佩服。

5 thoughts on “高性能std::string替代品fbstring

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s