c++ - 如何实现写时复制？

Question

我想在我的自定义 C++ String 类上实现写时复制，我想知道如何...

我尝试实现一些选项，但结果都非常低效。

感谢你们：-）

score 18 · 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_是一种同时具有原子增量和原子减量的类型和测试说明。

还有一种更高级的优化技术，它涉及使用联合将短字符串存储在您将用来描述较长字符串的数据位中。但这更复杂，我不认为我会倾向于编辑它以便稍后在此处放置一个简化的示例，但你永远无法判断。

score 5 · Accepted Answer

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

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

要改变对象，请检查“mutable-item”引用是否为非空。如果不是，则将“不可变项”引用的目标和 CompareExchange 对新对象的引用复制到“可变项”引用中。然后改变“可变项”引用的目标并使“不可变项”引用无效。

要克隆一个对象，如果希望克隆在它发生变异之前再次被克隆，则检索“immutable-item”引用的值。如果它为 null，则复制“可变项”目标并将 CompareExchange 对该新对象的引用复制到不可变项引用中。然后创建一个新包装器，其“可变项”引用为空，其“不可变项”引用是检索到的值（如果它不为空）或新项目（如果它是）。

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

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

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

score 3 · Accepted Answer

CoW没有太多东西。基本上，您在想要更改它时复制它，并让不想更改它的任何人保留对旧实例的引用。您需要引用计数来跟踪谁仍在引用该对象，并且由于您正在创建新副本，因此您需要减少“旧”实例的计数。一个捷径是在计数为 1 时不进行复制（您是唯一的参考）。

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

score 1 · Accepted Answer

您可能想要模拟其他语言具有的“不可变”字符串（据我所知，Python、C#）。

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

score 0 · Accepted Answer

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);
  }
}

c++ - 如何实现写时复制？

5 回答 5

Related

Reference