如何实现写时复制？

Question

如何实现写时复制？

c++stringcopy-on-write

21

我希望在我的自定义C++字符串类中实现写时复制(copy-on-write)，不知道该怎么做。

我尝试了一些选项，但它们都非常低效。

- fiveOthersWaiting

你的内存分配策略是什么？你可能想依靠池分配来获得更好的性能。 - Matthieu M.

2

希望这只是为了学习目的。在所有情况下，让它正确运作有很多陷阱。 - Martin York

仅用于学习目的，各位： - fiveOthersWaiting

5个回答

5

我建议，如果想要高效地实现写时复制（针对字符串或其他内容），应该定义一个包装类型，它将表现为可变字符串，并且将持有对可变字符串（不会存在对该项的其他引用）和对“不可变”字符串（在不尝试对其进行更改的事物之外，不会存在对其的引用）的可空引用。包装器始终至少使用其中一个引用非空创建；一旦在构造期间或之后将可变项引用设置为非空值，它将永远指向相同的目标。任何时候，当两个引用都非空时，“不可变项”引用将指向在最近完成的突变之后某个时间制作的该项的副本（在突变期间，“不可变项”引用可能或可能不持有对预突变值的引用）。

要读取对象，请检查“可变项”引用是否非空。如果是，则使用它。否则，请检查“不可变项”引用是否非空。如果是，则使用它。否则，使用“可变项”引用（此时将为非空）。

要突变对象，请检查“可变项”引用是否非空。如果不是，请复制“不可变项”引用的目标并CompareExchange一个对新对象的引用到“可变项”引用中。然后突变“可变项”引用的目标并使“不可变项”引用失效。

要克隆对象，如果预计克隆的副本将在突变之前再次被克隆，请检索“不可变项”引用的值。如果它为空，则复制“可变项”目标并CompareExchange一个对该新对象的引用到“不可变项”引用中。然后创建一个新的包装器，其“可变项”引用为空，而其“不可变项”引用是检索到的值（如果它不为空）或新项（如果它为空）。

要克隆对象，如果预计克隆的副本将在突变之前进行突变，请检索“不可变项”引用的值。如果为空，则检索“可变项”引用。复制检索到的任一引用的目标并创建一个新的包装器，其“可变项”引用指向新的副本，而其“不可变项”引用为空。

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

请注意，使用这种方法可能需要更多的复制操作，而不是使用“激进”方法。例如，如果使用新字符串创建了一个新的包装器，并且该包装器被改变并复制了六次，那么原始包装器将保存对原始字符串持有者和一个保存数据副本的不可变字符串的引用。六个复制的包装器只会保存对不可变字符串的引用（总共两个字符串，但如果在复制后从未改变原始字符串，则激进实现可以只使用一个）。如果原始包装器以及其中五个副本都被改变，则除了一个之外的所有不可变字符串的引用都将失效。此时，如果第六个包装器副本被改变，激进的写时复制实现可能会意识到它持有其字符串的唯一引用，因此决定不需要进行复制。然而，我描述的实现将创建一个新的可变副本并放弃不可变副本。尽管存在一些额外的复制操作，但大多数情况下，线程开销的减少应该超过成本。如果产生的大部分逻辑副本永远不会改变，则此方法可能比始终复制字符串更有效率。

- supercat

3

CoW并不复杂。基本上，当你想要更改它时，你就进行复制，并让任何不想更改它的人保留对旧实例的引用。你需要使用引用计数来跟踪仍在引用对象的人，并且由于你正在创建一个新副本，所以需要减少“旧”实例的计数。一种快捷方式是在该计数为1（即只有你自己的引用）时不进行复制。

除此之外，除非你面临特定的问题，否则没有什么可以说的了。

- falstro

3

细节决定成败：你如何处理运算符[]？你返回char&并总是复制，假设它会改变吗？你返回char并且从不复制，禁止修改单独的字符吗？你返回代理对象并在赋值时进行复制？有这么多问题，却没有一个正确答案 :) - sbk

@sbk：简单的答案？不要使用它。 :) 例如，您可以为单个字符操作编写get/set方法。 - falstro

@roe：但那将是一个残缺不全的字符串类...我记得当我看到Java中的字符串charAt方法时感到非常厌恶。呸！ - sbk

@sbk：也许是这样，但是将内部引用/指针提供给他人无论如何都会对你造成伤害。即使你现在复制了，以后可能会有其他人对你的对象进行读取引用。任何人都不允许与除字符串对象之外的任何东西进行交互。不过，你可以通过实现一个字符指针对象（由[]运算符返回），在赋值运算符中进行复制来解决这个问题。这实际上是一个非常有趣的想法，谢谢！ - falstro

@roe：我很高兴在这次讨论中有所收获 :) 无论如何，我认为 CoW 并不值得额外的复杂性。我宁愿选择不可变字符串 + 字符串构建器的组合，就像 .Net/Java/Python 和几乎所有其他“现代”语言一样。 - sbk

1

你可能想要模仿其他语言（如Python、C#）中具有的“不可变”字符串。

这个想法是每个字符串都是不可变的，因此对字符串的任何操作都会创建一个新的不可变字符串...或者这是基本的想法，为了避免爆炸，如果存在相似的字符串，则不需要创建另一个。

- Matthieu M.

0

template <class T> struct cow {
  typedef boost::shared_ptr<T> ptr_t;
  ptr_t _data;

  ptr_t get()
  {
    return boost::atomic_load(&_data);
  }

  void set(ptr_t const& data)
  {
    boost::atomic_store(&_data, data);
  }
}

- bobah

@daramarak cow::set() 会释放对旧数据的引用，而不会触及它。如果没有其他人通过调用cow::get()来引用旧数据，则该数据将被删除。想想cow<std :: string const>如何工作。 - bobah

通常情况下，使用 cow 时，您希望有一个单独的 cow 对象，该对象是未共享的，可以重复修改，以避免创建新对象或进行分配。 - Yakk - Adam Nevraumont

@Yakk - 这是一种不同的模式，称为“复制读取”或简称为“合并”。 - bobah

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Omnifarious · Accepted Answer

在多线程环境中（现在大多数都是），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_是一种类型，您拥有原子增量、原子减量和测试指令。

甚至还有一种更高级的优化技术，涉及使用联合来存储短字符串，直接存储在用于描述较长字符串的数据位中。但那更加复杂，我不认为我会倾向于编辑这里以后放一个简化的例子，但你永远无法确定。