如何实现Copy-on-Write？

Question

我想在我的自定义C++ String类上实现copy-on-write,我想知道如何...

我试图实现一些选项,但结果都非常低效.

感谢你们 :-)

Answer 1

在一个多线程的环境中(现在大部分都是这样),CoW经常是一个巨大的性能打击而不是收益.仔细使用const引用,即使在单线程环境中也不会带来很大的性能提升.

这篇旧的DDJ文章解释了CoW在多线程环境中的糟糕程度,即使只有一个线程.

另外,正如其他人所指出的那样,CoW字符串实现起来非常棘手,并且很容易出错.再加上他们在线程情况下表现不佳,这让我真的质疑他们的用处.一旦开始使用C++ 11移动构造和移动分配,这就变得更加真实.

但是,回答你的问题....

以下是一些可能有助于提高性能的实现技术.

首先,将长度存储在字符串本身中.长度是经常访问的,消除指针取消引用可能会有所帮助.我只是为了保持一致,也把分配的长度放在那里.这将花费你的字符串对象有点大,但空间和复制时间的开销非常小,特别是因为这些值将变得更容易让编译器发挥有趣的优化技巧.

这将为您留下一个如下所示的字符串类:

class MyString {
   ...
 private:
   class Buf {
      ...
    private:
      ::std::size_t refct_;
      char *data_;
   };

   ::std::size_t len_;
   ::std::size_t alloclen_;
   Buf *data_;
};

现在,您可以执行进一步的优化.那里的Buf类看起来并不真正包含或做得太多,这是真的.另外,它需要分配一个Buf实例和一个缓冲区来保存字符.这似乎相当浪费.因此,我们将转向一种常见的C实现技术,即弹性缓冲区:

class MyString {
   ...
 private:
   struct Buf {
      ::std::size_t refct_;
      char data_[1];
   };

   void resizeBufTo(::std::size_t newsize);
   void dereferenceBuf();

   ::std::size_t len_;
   ::std::size_t alloclen_;
   Buf *data_;
};

void MyString::resizeBufTo(::std::size_t newsize)
{
   assert((data_ == 0) || (data_->refct_ == 1));
   if (newsize != 0) {
      // Yes, I'm using C's allocation functions on purpose.
      // C++'s new is a poor match for stretchy buffers.
      Buf *newbuf = ::std::realloc(data_, sizeof(*newbuf) + (newsize - 1));
      if (newbuf == 0) {
         throw ::std::bad_alloc();
      } else {
         data_ = newbuf_;
      }
   } else { // newsize is 0
      if (data_ != 0) {
         ::std::free(data_);
         data_ = 0;
      }
   }
   alloclen_ = newsize;
}

当您以这种方式执行操作时,您可以将其data_->data_视为包含alloclen_字节而不是1.

请记住,在所有这些情况下,您必须确保在多线程环境中永远不要使用它,或者确保这refct_是一种既有原子增量又有原子减量的类型和测试指令.

还有一种更高级的优化技术,它涉及使用union来将短字符串存储在用于描述较长字符串的数据位内.但这更复杂,我不认为我会倾向于编辑它以便稍后在这里放一个简化的例子,但你永远无法分辨.

Answer 2

我建议，如果要有效地实现写时复制（对于字符串等），则应该定义一个包装器类型，该类型将充当可变字符串，并同时包含对可变字符串的可空引用（否对该项目的其他引用将永远存在）和对“不可变”字符串的可为空的引用（在不会尝试对其进行突变的事物之外，对它的引用将永远不存在）。包装器将始终使用其中至少一个非空引用创建；一旦将可变项引用设置为非空值（在构造期间或构造之后），它将永远引用相同的目标。每当两个引用都不为空时，不可变项目引用将指向该项目的副本，该副本是在最近完成的突变（在突变，

要读取对象，请检查“可变项”引用是否为非空。如果是这样，请使用它。否则，请检查“ immutable-item”引用是否为非空。如果是这样，请使用它。否则，请使用“可变项”引用（目前将是非null）。

要更改对象，请检查“ mutable-item”引用是否为非null。如果不是，则将“不可变项目”引用的目标复制并将对新对象的引用CompareExchange转换为“可变项目”引用。然后，对“可变项”引用的目标进行突变，并使“不可变项”引用无效。

要克隆对象，如果希望在突变之前将其克隆，请获取“ immutable-item”引用的值。如果为null，请复制“可变项”目标，并将CompareExchange对该新对象的引用转换为不可变项引用。然后创建一个新的包装，其“ mutable-item”引用为空，并且其“ immutable-item”引用为检索值（如果不为null）或新项目（如果为null）。

要克隆对象，如果希望在克隆之前将其克隆，请检索“ immutable-item”引用的值。如果为null，则检索“可变项”引用。复制检索到的所有引用的目标，并创建一个新包装，其“ mutable-item”引用指向新副本，并且其“ immutable-item”引用为null。

两种克隆方法在语义上将是相同的，但是针对给定情况选择错误的一种方法将导致额外的复制操作。如果人们始终选择正确的复制操作，则将获得“积极的”写时复制方法的大部分好处，但线程开销却少得多。每个数据保存对象（例如字符串）将是不可共享的可变对象或共享的不可变对象，并且没有对象将在这些状态之间切换。因此，如果不希望在一个以上的线程中同时使用包装对象，则可以根据需要消除所有的“线程/同步开销”（用直线存储代替CompareExchange操作）。两个包装器对象可能持有对同一不可变数据持有者的引用，但它们可能忽略了彼此的存在。

请注意，与使用“积极”方法相比，使用此方法可能需要更多的复制操作。例如，如果使用新字符串创建了一个新包装器，并且该包装器被突变并复制了六次，则原始包装器将保留对原始字符串保存器的引用，而一个不可变的保存器将保留数据的副本。六个复制的包装器仅包含对不可变字符串的引用（总共两个字符串，尽管如果原始字符串在复制后从未被更改过，则积极的实现可以通过一个实现）。如果原始包装器连同六个副本中的五个一起被更改，则对不可变字符串的引用（除了其中之一）将全部失效。那时，如果第六个包装副本被突变，积极的写时复制实现可能会意识到，它仅保留对其字符串的引用，因此认为不需要复制。但是，我描述的实现将创建一个新的可变副本，并放弃不变的副本。尽管存在一些额外的复制操作，但是在大多数情况下线程开销的减少应该可以抵消成本。如果生成的大多数逻辑副本从未被突变，则此方法可能比始终制作字符串副本更为有效。在大多数情况下，线程开销的减少应足以抵消成本。如果生成的大多数逻辑副本从未被突变，则此方法可能比始终制作字符串副本更为有效。在大多数情况下，线程开销的减少应足以抵消成本。如果生成的大多数逻辑副本从未被突变，则此方法可能比始终制作字符串副本更为有效。