« 上一章：10.2. 小内存分配的额外开销 下一章：10.4. 字符串之外的优化应用 »
返回目录

10.3. 局部缓冲区优化原理

程序完成某项任务的最少工作量就是“什么都不做”，免费的东西总是好的。同样，分配和释放内存最快的方法就是：不要分配和释放。局部缓冲区优化就是一种“无中生有”的方法 —— 这种情况下，可以以零成本获得所需的内存。

10.3.1 核心思想

要理解局部缓冲区优化：内存分配并不是孤立发生的。通常，当需要少量内存时，这块分配的内存会作为某个数据结构的一部分使用。考虑一个非常简单的字符串：

// Example 04
class simple_string {
public:
  simple_string() = default;

  explicit simple_string(const char* s) : s_(strdup(s)) {}

  simple_string(const simple_string& s)
  : s_(strdup(s.s_)) {}
    simple_string& operator=(const char* s) {
    free(s_);
    s_ = strdup(s);
    return *this;
  }

  simple_string& operator=(const simple_string& s) {
    if (this == &s) return *this;
    free(s_);
    s_ = strdup(s.s_);
    return *this;
  }

  bool operator==(const simple_string& rhs) const {
    return strcmp(s_, rhs.s_) == 0;
  }

  ~simple_string() { free(s_); }
private:
  char* s_ = nullptr;
};

该字符串通过调用 strdup() 从 malloc() 分配内存，并通过调用 free() 释放内存。为了让这个字符串类具备实际用途，还需要许多其他成员函数，但目前这两个函数已足以用来探讨内存分配的开销。说到分配，每次构造、复制或赋值一个字符串时，都会发生一次内存分配。更准确地说，每次构造一个字符串时，都会发生一次分配；字符串对象本身必须分配在某处，对于局部变量而言可能在栈上，如果字符串是某个动态分配数据结构的一部分，则可能在堆上。除此之外，字符串数据本身也需要分配内存，而这些内存总是从 malloc() 获取。

这正是局部缓冲区优化的核心思想 —— 为何不将字符串对象设计得更大一些，使其能够容纳自身的数据呢？这确实是一种“无中生有”的方式；字符串对象的内存无论如何都必须分配，而用于存储字符串数据的内存则无需付出成本。当然，字符串的长度可以任意，无法预先知道需要将字符串对象扩大多少，才能存储程序中遇到的所有字符串。即使能确定这个大小，为每个字符串(包括非常短的)都分配如此大的对象也将会造成巨大的内存浪费。

可以观察到：字符串越长，处理所需的时间就越长(无论是复制、搜索、转换还是其他操作)。对于非常长的字符串，分配内存的开销与处理成本将微不足道。而对于短字符串，分配开销则可能相当显著。因此，最大的性能收益来自于将短字符串直接存储在对象内部，而那些过长、无法放入对象内的字符串，则仍像以前一样存储在动态分配的内存中。简而言之，这就是局部缓冲区优化(对于字符串而言，也称为短字符串优化)：对象(字符串)内部包含一个固定大小的局部缓冲区，能放入该缓冲区的字符串都将直接存储在对象内部：

// Example 04
class small_string {
public:
  small_string() = default;

  explicit small_string(const char* s) :
    s_((strlen(s) + 1 < sizeof(buf_)) ? strcpy(buf_, s)
                                      : strdup(s)) {}

  small_string(const small_string& s) :
    s_((s.s_ == s.buf_) ? strcpy(buf_, s.buf_)
                        : strdup(s.s_)) {}

  small_string& operator=(const char* s) {
    if (s_ != buf_) free(s_);
    s_ = (strlen(s) + 1 < sizeof(buf_)) ? strcpy(buf_, s)
                                        : strdup(s);
    return *this;
  }

  small_string& operator=(const small_string& s) {
    if (this == &s) return *this;
    if (s_ != buf_) free(s_);
    s_ = (s.s_ == s.buf_) ? strcpy(buf_, s.buf_)
                          : strdup(s.s_);
    return *this;
  }

  bool operator==(const small_string& rhs) const {
    return strcmp(s_, rhs.s_) == 0;
  }

  ~small_string() {
    if (s_ != buf_) free(s_);
  }

private:
  char* s_ = nullptr;
  char buf_[16];
};

缓冲区大小被静态地设置为 16 个字符，其中包括用于终止字符串的空字符。长度超过 16 的字符串都将从 malloc() 分配内存。在赋值或销毁字符串对象时，必须检查是进行了动态分配还是使用了内部缓冲区，以便正确释放字符串所使用的内存。

10.3.2 局部缓冲区优化的效果

small_string 相比 simple_string 能快多少？这当然取决于你对它的具体使用方式。先从简单的创建和删除字符串操作开始测试。为了避免重复编写相同的基准测试代码，可以使用模板化的基准测试：

// Example 04
template <typename T>
void BM_string_create_short(benchmark::State& state) {
  const char* s = "Simple string";
  for (auto _ : state) {
    REPEAT({
      T S(s);
      benchmark::DoNotOptimize(S);
    })
  }
  state.SetItemsProcessed(32*state.iterations());
}
BENCHMARK_TEMPLATE1(BM_string_create_short, simple_string);
BENCHMARK_TEMPLATE1(BM_string_create_short, small_string);

结果相当令人印象深刻：

Benchmark                                Time       Items per sec
BM_string_create_short<simple_string>     835 ns    38.34M/s
BM_string_create_short<small_string>     18.7 ns    1.71658G/s

尝试在多个线程上运行相同的测试时，效果甚至更好：

Benchmark                             Time       Items per sec
BM_create<simple_string>/threads:2     743 ns    21.5644M/s
BM_create<simple_string>/threads:4     435 ns    18.4288M/s
BM_create<small_string>/threads:2     9.34 ns    1.71508G/s
BM_create<small_string>/threads:4     4.77 ns    1.67998G/s

在两个线程上，普通字符串的创建速度略有提升，但短字符串的创建速度正好快了一倍(在四个线程上同样快了近一倍)。当然，这是短字符串优化的最佳情况 —— 首先，我们所做的仅仅是创建和删除字符串，而这正是优化的部分；其次，由于字符串是局部变量，其内存作为栈帧的一部分进行分配，因此没有分配开销。

然而，这种情况并非不合理。毕竟，局部变量非常常见；如果字符串是某个较大数据结构的一部分，该结构的分配成本无论如何都必须承担，同时分配其他内容相当于免费。

尽管如此，我们不太可能只分配字符串然后立即释放。因此，还应考虑其他操作的开销。可以预期，只要字符串保持较短，在复制或赋值操作上也会有类似的性能提升：

template <typename T>
void BM_string_copy_short(benchmark::State& state) {
  const T s("Simple string");
  for (auto _ : state) {
    REPEAT({
      T S(s);
      benchmark::DoNotOptimize(S);
    })
  }
  state.SetItemsProcessed(32*state.iterations());
}

template <typename T>
void BM_string_assign_short(benchmark::State& state) {
  const T s("Simple string");
  T S;
  for (auto _ : state) {
    REPEAT({ benchmark::DoNotOptimize(S = s); })
  }
  state.SetItemsProcessed(32*state.iterations());
}

BENCHMARK_TEMPLATE1(BM_string_copy_short, simple_string);
BENCHMARK_TEMPLATE1(BM_string_copy_short, small_string);
BENCHMARK_TEMPLATE1(BM_string_assign_short, simple_string);
BENCHMARK_TEMPLATE1(BM_string_assign_short, small_string);

确实，我们观察到了类似的显著性能提升：

Benchmark Time                          Items    per sec
BM_string_copy_short<simple_string>     786 ns   40.725M/s
BM_string_copy_short<small_string>      53.5 ns  598.847M/s
BM_string_assign_short<simple_string>   770 ns   41.5977M/s
BM_string_assign_short<small_string>    46.9 ns  683.182M/s

我们也很可能至少需要读取一次字符串中的数据，用于比较、搜索特定字符串或字符，或计算某些派生值。当然，对于这些操作，并不期望获得同等量级的性能提升，因其都不涉及内存的分配或释放。

既然如此，为何还期望有性能提升呢？确实，例如一个简单的字符串比较测试就显示，这两种字符串版本之间没有区别。要想看到优势，必须创建大量字符串对象并进行比较：

template <typename T>
void BM_string_compare_short(benchmark::State& state) {
  const size_t N = state.range(0);
  const T s("Simple string");
  std::vector<T> v1, v2;

  ... 用字符串填充vector ...

  for (auto _ : state) {
    for (size_t i = 0; i < N; ++i) {
      benchmark::DoNotOptimize(v1[i] == v2[i]);
    }
  }
  state.SetItemsProcessed(N*state.iterations());
}
BENCHMARK_TEMPLATE1(BM_string_compare_short,
                    simple_string)->Arg(1<<22);
BENCHMARK_TEMPLATE1(BM_string_compare_short,
                    small_string)->Arg(1<<22);

当 N 较小(字符串总数较少)时，这种优化不会带来显著的好处。当需要处理大量字符串时，使用短字符串优化的字符串比较速度大约可以提升一倍：

Benchmark                                Time       Items per sec
BM_compare<simple_string>/4194304    30230749 ns    138.855M/s
BM_compare<small_string>/4194304     15062582 ns    278.684M/s

如果根本没有涉及内存分配，为何会出现这种情况呢？这个实验揭示了局部缓冲区优化的第二个非常重要的优势 —— 改善了缓存局部性。在读取字符串数据之前，必须先访问字符串对象本身，包含了指向数据的指针。对于普通字符串，访问字符需要进行两次内存访问，而这两次访问的地址通常互不相关。如果数据总量较大，第二次访问(即访问字符串数据)很可能发生缓存未命中，需要等待数据从主内存加载。相反，经过优化的字符串将数据保存在字符串对象附近，当字符串对象载入缓存，其数据也随之进入缓存。

我们需要足够多的不同字符串，才能观察到这一优势的原因是：当字符串数量较少时，所有字符串对象及其数据可以一直驻留在缓存中。只有当字符串的总大小超过缓存容量时，这种性能优势才会显现出来。

现在，让我们深入探讨一些其他的优化方法。

10.3.3 其他优化方法

我们实现的 small_string 类存在一个明显的低效之处 —— 当字符串存储在局部缓冲区中时，实际上并不需要指向数据的指针，并确切地知道数据就在局部缓冲区中。也需要以某种方式知道数据，是在局部缓冲区还是在外部分配的内存中，但并不需要用8个字节(在64位机器上)仅来存储这个信息。当然，对于存储较长的字符串，仍然需要指针，但在字符串较短时，可以将指针的内存空间复用为缓冲区的一部分：

// Example 05
class small_string {
  ...
private:
  union {
    char* s_;
    struct {
      char buf[15];
      char tag;
    } b_;
  };
};

使用最后一个字节作为标签，用以指示字符串是存储在本地(tag == 0)，还是存储在独立分配的内存中(tag == 1)。注意，总缓冲区大小仍然是16个字符，其中15个用于字符串本身，1个用于标签；当字符串需要全部16个字节时，该标签也同时充当字符串末尾的空字符(这正是使用 tag == 0 表示本地存储的原因，否则会消耗一个字节)。指针在内存中与字符缓冲区的前8个字节重叠。在此示例中，我们选择优化字符串所占用的总内存；这个字符串仍然拥有16个字符的本地缓冲区，与之前的版本相同，但现在对象本身的大小仅为16字节，而不是24字节。如果保持对象大小不变，则可以使用更大的缓冲区，从而在本地存储更长的字符串。通常来说，随着字符串变长，短字符串优化带来的好处会逐渐减少。从本地存储切换到远程存储的最佳临界点，取决于具体应用。当然，需要通过基准测试来确定。

返回目录
« 上一章：10.2. 小内存分配的额外开销 下一章：10.4. 字符串之外的优化应用 »