首页 c++

今天研究 folly 的字符串的实现 ——FBString。

# 1. 字符串实现方式

要实现字符串，关键的是两个数据：

  1. 对应字符串数据的地址
  2. 字符串的长度

对于这些数据的维护方式，主要的有以下几种方式：

# i.eager copy：

eager copy 是最简单也是最暴力的字符串数据维护方式。当一个字符串进行拷贝操作时，直接将数据拷贝一份，将数据指针指向拷贝的对象。

这种实现虽然很简单，不用考虑各种复杂的情况，但是当字符串的长度很长时，在空间和时间上都会浪费很多效率。

# ii.COW(copy-on-write)

COW 的含义是当对目标字符串需要修改时再进行拷贝，因此拷贝的字符串未进行修改时，和被拷贝字符串使用的是同一片共享的数据。这种实现需要对每个字符串对应的数据计数，当一块数据没有字符串使用以后就将它回收，和 c++ 中的智能指针很类似。

这种方式处理较长的字符串时，可以避免不需要的拷贝，节省效率，但是由于需要维护一个 refcount，这个操作是一个原子操作，频繁进行拷贝的话，会比较消耗效率。

关于 COW，我看到了个比较有意思的情况：

std::string s("str");
const char* p = s.data();
{
    std::string s2(s);
    (void) s[0];
}
std::cout << *p << '\n';

下面这段代码在不使用 COW 时可以正常运行，但是用使用 COW 的 gcc 版本去执行会发现 p 变成了一个野指针。这是因为 s2 构造时，与 s 共享了同一片数据，但使用非 const 的 [] 操作符取出的对象，编译器会认为你要对其进行修改，所以会重新拷贝一份 “str” 的数据并让 s 指向新的数据，然后当代码走出中间一个代码段后，s2 的生命周期到了，而它指向的字符串数据没有被共享，因此 p 所指向的数据被析构了，p 也变成了野指针。

不过我用 4.8.5 版本的 gcc 试了以后貌似不会野指针，不过 s 确实重新拷贝了数据：

std::string s("str");
const char* p = s.data();
{
  std::string s2 = s;
  cout << (s.c_str() == s2.c_str()) << '\n';
  (void)s[0];
  cout << (s.c_str() == s2.c_str()) << '\n';
}
cout << (p == s.c_str()) << endl;
std::cout << *p << '\n';

输出结果：

> ./test
1
0
0
s

不过值得注意的一点是：COW 只在拷贝的时候触发：

std::string s1 = "4444";
std::string s2 = s1;
cout << ((unsigned long)s1.c_str() == (unsigned long)s2.c_str()) << endl;

这样结果输出的是 1，但是仅仅数据一样的话：

std::string s1 = "4444";
std::string s2 = "4444";
cout << ((unsigned long)s1.c_str() == (unsigned long)s2.c_str()) << endl;

输出的就是 0 了。

在 Lua 对 string 的处理中，将 string 计算 hash 存入一个 hashtable 中，所以相同数据的字符串对应数据只会是同一份。

# iii.SSO

由于大多数字符串比较短，所以使用 eager copy 的成本较低，所以为了效率考虑，出现了 SSO（Small String Optimization）这种优化方式。

SSO 的优化方式主要是对于较短的字符串的直接存在 string 类的内部，对于较长的字符串则使用 COW 的共享数据的方式。

据网上说，gcc5 开始禁止了 COW，开始使用 SSO。

# 2.FBString

FBString 就功能上来说和 string 是一致的，但是在效率方面有一定的优化。std 的 string 对于不同长度的 string 使用了两层分级策略，而 FBString 使用了三层分级策略：

  1. length≤23 字节：使用 SSO 中对短字符串的处理方式，直接存在 string 类内部；
  2. 23 字节＜length≤255 字节：使用 eager copy 的方式，直接拷贝 string 的数据；
  3. length>255 字节：使用 COW 的方式，进行懒拷贝，当数据发生变化的时候再进行实际的数据拷贝。

根据官方文档，FBString 有以下特性：

  1. 与 std::string 100% 兼容。
  2. 在对大字符串使用 COW 方式存储时，对于引用计数线程安全。
  3. 使用 malloc 代替 allocators。
  4. 对 Jemalloc 友好。如果检测到使用 jemalloc，那么将使用 jemalloc 的一些非标准扩展接口来提高性能。
  5. find() 使用简化版的 **Boyer-Moore algorithm**。在查找成功的情况下，相对于 string::find() 大致有 30 倍的性能提升。在查找失败的情况下也有 1.5 倍的性能提升。
  6. 可以与 std::string 互相转换。

# 3. 实现细节

# i. 字符串数据

FBString 的核心成员变量大致有这几个：

struct MediumLarge {
    Char* data_;
    size_t size_;
    size_t capacity_;
  };
union {
  uint8_t bytes_[sizeof(MediumLarge)]; // 为了能获取最后一个字节的数据
  Char small_[sizeof(MediumLarge) / sizeof(Char)];
  MediumLarge ml_;
};
FBString 使用了一个 union 去存储短字符串的数据或是中长字符串的指针、长度、容量，这 3 者在 64 位系统中正好占用 24 字节，因此短字符串的长度最长就是 23 字节。可以看到这个 union 里数组的大小都是通过 sizeof 表达式去计算出来的，这样就保证了不同环境下的稳定性。
包括一些常数数据，如大中小字符串长度的分割长度节点，FBString 中也是使用表达式去计算出来的，计算结果使用 constexpr 常量，即编译期的常量去保存，这样也避免了代码中出现魔法数字的问题：
constexpr static size_t lastChar = sizeof(MediumLarge) - 1;
  constexpr static size_t maxSmallSize = lastChar / sizeof(Char);
  constexpr static size_t maxMediumSize = 254 / sizeof(Char);
  constexpr static uint8_t categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3;
  constexpr static size_t kCategoryShift = (sizeof(size_t) - 1) * 8;
  constexpr static size_t capacityExtractMask = kIsLittleEndian
      ? ~(size_t(categoryExtractMask) << kCategoryShift)
      : 0x0 /* unused */;
然后根据上面计算的节点，FBString 在创建时会根据长度进行分类：
fbstring_core(
      const Char* const data,
      const size_t size,
      bool disableSSO = FBSTRING_DISABLE_SSO) {
    if (!disableSSO && size <= maxSmallSize) {
      initSmall(data, size);
    } else if (size <= maxMediumSize) {
      initMedium(data, size);
    } else {
      initLarge(data, size);
    }
    assert(this->size() == size);
    assert(size == 0 || memcmp(this->data(), data, size * sizeof(Char)) == 0);
  }
最终类型会被保存在最后一个字节中：
typedef uint8_t category_type;
  enum class Category : category_type {
    isSmall = 0,
    isMedium = kIsLittleEndian ? 0x80 : 0x2,
    isLarge = kIsLittleEndian ? 0x40 : 0x1,
  };
  Category category() const {
    return static_cast<Category>(bytes_[lastChar] & categoryExtractMask);
  }
Category 定义 isSmall = 0 其实利用了字符串数据的最后都是 0 的特性，而对于中大字符串也是在 capacity_ 中利用大小去判断，也算是巧妙地节省了保存类型的空间。
# ii. 引用计数线程安全
这个线程安全的实现依赖的是 atomic ：
struct RefCounted {
    std::atomic<size_t> refCount_;
    Char data_[1];
  };
# iii.jemalloc 友好
folly 整个库很多地方会使用 jemalloc 的非标准扩展接口，因此使用时需要特殊处理。
在 Malloc.h 中有很复杂的对是否使用 jemalloc 的判断。
p
/**
 * Determine if we are using jemalloc or not.
 */
#if defined(FOLLY_ASSUME_NO_JEMALLOC) || FOLLY_SANITIZE
  inline bool usingJEMalloc() noexcept {
    return false;
  }
#elif defined(USE_JEMALLOC) && !FOLLY_SANITIZE
  inline bool usingJEMalloc() noexcept {
    return true;
  }
#else
FOLLY_NOINLINE inline bool usingJEMalloc() noexcept {
  ...
}
首先会通过 FOLLY_ASSUME_NO_JEMALLOC 和 USE_JEMALLOC 两个选项直接指定是否使用 jemalloc。假如这两个选项都没有指定的话，则会经过通过一些检测去判断是否能使用 jemalloc。
FOLLY_NOINLINE inline bool usingJEMalloc() noexcept {
  static const bool result = []() noexcept {
    // Some platforms (*cough* OSX *cough*) require weak symbol checks to be
    // in the form if (mallctl != nullptr). Not if (mallctl) or if (!mallctl)
    // (!!). http://goo.gl/xpmctm
    if (mallocx == nullptr || rallocx == nullptr || xallocx == nullptr ||
        sallocx == nullptr || dallocx == nullptr || sdallocx == nullptr ||
        nallocx == nullptr || mallctl == nullptr ||
        mallctlnametomib == nullptr || mallctlbymib == nullptr) {
      return false;
    }
    ...
  }();
  return result;
}
if 条件语句中的变量都是函数指针，这些函数是 jemalloc 的函数，可以看到这个函数主要是判断一系列函数指针是否有值。这些函数都是 jemalloc 中的函数，为了防止未引用时报错，folly 在不使用 jemalloc 时将这些函数定义为空：
#if (!defined(USE_JEMALLOC) && !defined(FOLLY_USE_JEMALLOC)) || FOLLY_SANITIZE
void* (*mallocx)(size_t, int) = nullptr;
void* (*rallocx)(void*, size_t, int) = nullptr;
size_t (*xallocx)(void*, size_t, size_t, int) = nullptr;
size_t (*sallocx)(const void*, int) = nullptr;
void (*dallocx)(void*, int) = nullptr;
void (*sdallocx)(void*, size_t, int) = nullptr;
size_t (*nallocx)(size_t, int) = nullptr;
int (*mallctl)(const char*, void*, size_t*, void*, size_t) = nullptr;
int (*mallctlnametomib)(const char*, size_t*, size_t*) = nullptr;
int (*mallctlbymib)(const size_t*, size_t, void*, size_t*, void*, size_t) =
    nullptr;
而这些函数指针在检测到引用了 jemalloc 的情况下是非空的。folly 使用 CMake 的 CHECK_INCLUDE_FILE_CXX 去判断是否引用了 jemalloc：
if (CMAKE_SYSTEM_NAME STREQUAL "FreeBSD")
  CHECK_INCLUDE_FILE_CXX(malloc_np.h FOLLY_USE_JEMALLOC)
else()
  CHECK_INCLUDE_FILE_CXX(jemalloc/jemalloc.h FOLLY_USE_JEMALLOC)
endif(
当 FOLLY_USE_JEMALLOC 为 0 时，会将之前的函数指针都置为空。
剩下的看起来应该是一些特殊情况的处理。
# iv.find 函数的优化
FBString 对 find 函数的优化主要是使用了 Boyer-Moore 算法的思路（字符串匹配的 Boyer-Moore 算法）。不过原版比较复杂，适合去搜索长字符串，常用于网页、文本的搜索，对于目标字符串较短的情况反而有点得不偿失，因此 FBString 的 find 是它的简化版：
template <typename E, class T, class A, class S>
inline typename basic_fbstring<E, T, A, S>::size_type
basic_fbstring<E, T, A, S>::find(
    const value_type* needle,
    const size_type pos,
    const size_type nsize) const {
    ...
    // 前面逐位对比，直至 i 位置开始的字符串最后一位和 needle 最后一位相同
    for (size_t j = 0;;) {
      assert(j < nsize);
      if (i[j] != needle[j]) {
        // 然后这里会计算需要跳过的位数，不过没有 Boyer-Moore 那样对好后缀进行判断，仅是对最后一位字符找 needle 中相同的一位对齐
        if (skip == 0) {
          skip = 1;
          while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
            ++skip;
          }
        }
        i += skip;
        break;
      }
      if (++j == nsize) {
        // 找到目标
        return i - haystack;
      }
    }
}
# v. 与 std::string 的兼容
c++ 中的 std::string 其实是 basic_string<char> 的别名，FBString 为了兼容它，实现了一系列重载函数：
//std::string 转 FBString
  template <typename A2>
  basic_fbstring& operator=(const std::basic_string<E, T, A2>& rhs) {
    return assign(rhs.data(), rhs.size());
  }
  // FBString 转 std::string
  std::basic_string<E, T, A> toStdString() const {
    return std::basic_string<E, T, A>(data(), size());
  }
  // 比较函数 
  template <typename E, class T, class A, class S, class A2>
  inline bool operator==(
      const basic_fbstring<E, T, A, S>& lhs,
      const std::basic_string<E, T, A2>& rhs) {
    return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
  }
  ......
而且 std::string 的常用函数在 FBString 基本是以一样的形式去定义的，如 size() 、 capacity() 、 empty() 、 begin() 、 end() 等。而且看注释和记录，FBString 在 string 的函数更新后也会相应地更新去兼容。
这些函数保证了和原有的标准库的 std::string 的兼容性，在使用时完全可以当成 std::string 去用，甚至很多时候直接可以把旧代码的一个 std::string 替换成 fbstring，它们之间的比较和相互转换都是一个表达式就能完成的。当要研发一个旧系统的新版本时，兼容性是一个很重要但也很难完美满足的一个方面，FBString 的兼容性真的做的很好（不过工作量也确实挺大的）。
# 4. 总结
FBString 这么整体看下来，可以看得出来还是有很多细节的。感觉看下来这个库的代码风格整体很严谨，大致有这些特点：
  1. 几乎所有复杂接口都加上了 assert 验证正确性，保证可靠性。
  2. 很多地方也对大小端进行了区分，常量尽可能用系统变量计算，长度均使用 size_type，尽可能的保证了库的可移植性。
  3. 代码对内存的使用十分严格，能用一个 uint8 解决的问题绝对不会不用 uint32。
  4. 使用了非常多模板定义的类和函数，提高可复用性。（不过感觉有点过多了，不知道是不是真的都需要抽出来，可能有点过度设计，用的多的话也可能导致编译过慢，个人理解）
folly 确实有很多可以借鉴的地方，接下来继续研究ヾ (◍°∇°◍)ﾉﾞ！
# 参考资料
  • facebook/folly
  • C++ folly 库解读
  • GNU C++ 标准库中 string 实现简介
  • Legality of COW std::string implementation in C++11
  • c++ 再探 string 之 eager-copy、COW 和 SSO 方案
  • 一篇文章搞懂 STL 中的空间配置器 allocator
  • 分配器 ——allocators
 
 更新于   阅读次数  次
请我喝[茶]~(￣▽￣)~*
Nirvana 支付宝
支付宝