FBString分析与使用FBString简介

  • 跟上一篇隔得时间有点久啊,得加强自律性了......
  • FBString这货基本上用到了所有常见的实现String的方法,有一定的学习和参考价值
  • 大家猜猜这个FBString的作者是谁,答案在篇尾

FBString简介

fbstring is a drop-in replacement for std::string. The main benefit of fbstring is significantly increased performance on virtually all important primitives. This is achieved by using a three-tiered storage strategy and by cooperating with the memory allocator. In particular, fbstring is designed to detect use of jemalloc and cooperate with it to achieve significant improvements in speed and memory usage.

简单来说,使用了三层存储策略+内存分配策略+大小端支持,特别是配合使用 jemalloc, 减少磁盘碎片,加快并发下的分配速度和性能。

存储策略

  • SSO技术,使用栈上缓冲区,存储字符不超过23个,存储在类的数组类型的成员变量中;
  • Eager Copy技术,存储字符不超过254个,总是存储在malloc分配的堆上内存空间;
  • Copy-On-Write技术,存储字符超过254, 使用COW技术,引入引用计数,避免不必要的copy操作。

核心实现

fbstring_core

  • 是FBString的实现核心,提供了全部的操作接口,实现了三层存储策略+内存分配策略+大小端支持;
  • 用户可根据需要实现自己的fbstring_core_model(即fbstring_core的mockup接口定义)接口,即实现了自己的String类;
  • 可以用状态机的思路来理解fbstring_core, 按存储策略的不同其当前可能处于三种不同的状态:small, medium, large, 当构造,赋值,扩容,收缩等操作发生时,会在这三种状态间转换,即其存储策略也会相应主调整,大部分函数都按这个思路来阅读吧;
  • category() 可获取当前的状态:small, medium, large,下面我们会经常提到这三种状态;
  • 数据成员
struct MediumLarge {
    Char * data_;
    size_t size_;
    size_t capacity_;
    size_t capacity() const {
      return kIsLittleEndian
        ? capacity_ & capacityExtractMask
        : capacity_ >> 2;
    }
    void setCapacity(size_t cap, Category cat) {
        capacity_ = kIsLittleEndian
          ? cap | static_cast<category_type>(cat)
          : (cap << 2) | static_cast<category_type>(cat);
    }
  };

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

使用了union,其中small_用于small状态时的字符串存储,MediumLarge用于mediumlarge状态时的字符串存储; 使用small_时,其最后一格存储 maxSmallSize - 当前字符串实现大小 这个看起来还是一目了然,很清楚的。

  • RefCounted
struct RefCounted {
    std::atomic<size_t> refCount_;
    Char data_[1];

    static RefCounted * fromData(Char * p) {
      return static_cast<RefCounted*>(
        static_cast<void*>(
          static_cast<unsigned char*>(static_cast<void*>(p))
          - sizeof(refCount_)));
    }

    static size_t refs(Char * p) {
      return fromData(p)->refCount_.load(std::memory_order_acquire);
    }

    static void incrementRefs(Char * p) {
      fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
    }

    static void decrementRefs(Char * p) {
      auto const dis = fromData(p);
      size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
      assert(oldcnt > 0);
      if (oldcnt == 1) {
        free(dis);
      }
    }

    static RefCounted * create(size_t * size) {
      // Don't forget to allocate one extra Char for the terminating
      // null. In this case, however, one Char is already part of the
      // struct.
      const size_t allocSize = goodMallocSize(
        sizeof(RefCounted) + *size * sizeof(Char));
      auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
      result->refCount_.store(1, std::memory_order_release);
      *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
      return result;
    }

    static RefCounted * create(const Char * data, size_t * size) {
      const size_t effectiveSize = *size;
      auto result = create(size);
      fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
      return result;
    }

    static RefCounted * reallocate(Char *const data,
                                   const size_t currentSize,
                                   const size_t currentCapacity,
                                   const size_t newCapacity) {
      assert(newCapacity > 0 && newCapacity > currentSize);
      auto const dis = fromData(data);
      assert(dis->refCount_.load(std::memory_order_acquire) == 1);
      // Don't forget to allocate one extra Char for the terminating
      // null. In this case, however, one Char is already part of the
      // struct.
      auto result = static_cast<RefCounted*>(
             smartRealloc(dis,
                          sizeof(RefCounted) + currentSize * sizeof(Char),
                          sizeof(RefCounted) + currentCapacity * sizeof(Char),
                          sizeof(RefCounted) + newCapacity * sizeof(Char)));
      assert(result->refCount_.load(std::memory_order_acquire) == 1);
      return result;
    }
  };

看着代码多,其实很简单。 在large状态使用COW技术就需要引用计数的存在,这个RefCounted就实现了这个,利用了std::atomic作计数,data_指向需要作计数的实体。fromData(Char p)*函数从需作计数的实体指针得到其对应的RefCounted实体的指针。

构造函数

fbstring_core(fbstring_core&& goner) noexcept {
    // Take goner's guts
    ml_ = goner.ml_;
    // Clean goner's carcass
    goner.reset();
  }

交换函数

  • void swap(fbstring_core & rhs)

auto const t = ml_; ml_ = rhs.ml_; rhs.ml_ = t;

实现简单,用处多多

### 访问函数
- const Char * data() const
- const Char * c_str()
- Char * mutable_data()
large状态的,要作拷贝啦~~~COW

### 回缩函数
- void shrink(const size_t delta)
size减少delta. "得儿塔" 让我想起了中学的数学课~~~还有我同桌

### Reserve函数
- void reserve(size_t minCapacity, bool disableSSO)
让这个string的capacity至少有minCapacity这么大,这个函数完美诠释了三种状态的转换。

## basic_fbstring
- 这个其实没什么说的,用fbstring_core的接口把std::string的所有接口都实现了一遍。
- 最后还附赠了一个 **typedef basic_fbstring<char> fbstring** 外加一个**FOLLY_FBSTRING_HASH**

# FBString作者:[Andrei Alexandrescu](https://zh.wikipedia.org/wiki/%E5%AE%89%E5%BE%B7%E7%83%88%C2%B7%E4%BA%9E%E6%AD%B7%E5%B1%B1%E5%BE%B7%E9%9B%B7%E6%96%AF%E5%BA%AB) C++和D語言專家

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开源优测

AutoLine源码分析之数据库模型

AutoLine开源平台是一个开源自动化测试解决方案,基于RobotFramework进行二次开发,支持RobotFramework几乎所有的库。

901
来自专栏黑泽君的专栏

day44_Oracle学习笔记_03

先去Oracle官网去下载最新版本的sqldeveloper,下载地址:https://www.oracle.com/technetwork/developer...

952
来自专栏张善友的专栏

LINQ to SQL集成到应用程序中需考虑的一些问题

1、LINQ to SQL集成到应用程序中需考虑的一个问题, 到底应该返回IQueryable<T>还是IQueryable? 或许这个列表还应该继续扩展为T,...

2036
来自专栏雪胖纸的玩蛇日常

django orm 重点大全

2554
来自专栏Java学习之路

Hibernate学习---关联关系映射

关联关系是用到的最多的一种关系,非常重要,在内存中反映为实体关系,映射到DB中主键外键关系,实体间的关联,即对外键的维护,关联关系的发生,即对外键数据的改变。 ...

2986
来自专栏西安-晁州

mysql随笔

Mysql学习笔记 1、操作数据库 use dataBaseName  //使用数据库 show databases   //显示所有数据库 show tabl...

1980
来自专栏Python爬虫实战

设计模式:单例模式

想想一下这个场景,一个系统中可以存在多个打印任务,但是只有一个正在工作的任务。我们怎样才能保证一个类只有一个实例并且这个实例易于被访问呢?一个全局变量可以使得一...

792
来自专栏Python

Django---ORM操作大全

前言 Django框架功能齐全自带数据库操作功能,本文主要介绍Django的ORM框架 到目前为止,当我们的程序涉及到数据库相关操作时,我们一般都会这么搞:...

83510
来自专栏更流畅、简洁的软件开发方式

分页控件之分页算法 —— for SQL Server 版。

上两篇随笔: 我的分页控件(未完,待续)——控件件介绍及思路 我自己写的一个分页控件(源码和演示代码)PostBack分页版 for vs2003、SQL ...

2179
来自专栏Java帮帮-微信公众号-技术文章全总结

Oracle应用实战八(完结)——存储过程、函数+对象曹组

游标 在写java程序中有结果集的概念,那么在pl/sql中也会用到多条记录,这时候我们就要用到游标,游标可以存储查询返回的多条数据。 游标可以理解为是PL/S...

3506

扫码关注云+社区