Как реализовать Copy-on-Write?

Question

Я хочу реализовать функцию копирования при записи в моем пользовательском классе C ++ String, и мне интересно, как ...

Я пытался реализовать некоторые варианты, но все они оказались очень неэффективными.

Спасибо, ребята: -)

Answer 1

В многопоточном окружении (а это большинство из них в настоящее время) CoW часто является огромным ударом по производительности, а не выигрышем. А при аккуратном использовании константных ссылок это не сильно повышает производительность даже в однопоточной среде.

Эта старая статья о 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_ является типом, который у вас есть как атомарный инкремент, и атомарный декремент и инструкция по тестированию для.

Существует еще более продвинутый метод оптимизации, который включает использование объединения для хранения коротких строк прямо внутри битов данных, которые вы использовали бы для описания более длинной строки. Но это еще сложнее, и я не думаю, что буду склонен отредактировать это, чтобы позже привести здесь упрощенный пример, но вы никогда не сможете сказать.

Answer 2

Я хотел бы предложить, что если кто-то хочет эффективно реализовать копирование при записи (для строк или чего-либо еще), следует определить тип оболочки, который будет вести себя как изменяемая строка и который будет содержать как обнуляемую ссылку на изменяемый строка (никакой другой ссылки на этот элемент никогда не будет) и пустая ссылка на «неизменяемую» строку (ссылки на которые никогда не будут существовать вне вещей, которые не будут пытаться изменить его). Обертки всегда будут создаваться с хотя бы одной из этих ссылок, отличных от NULL; как только для ссылки на изменяемый элемент будет установлено ненулевое значение (во время или после создания), он всегда будет ссылаться на одну и ту же цель. Каждый раз, когда обе ссылки не равны NULL, ссылка на неизменяемый элемент будет указывать на копию элемента, которая была сделана через некоторое время после самой последней завершенной мутации (во время мутации ссылка на неизменяемый элемент может содержать или не содержать ссылку). до значения перед мутацией).

Чтобы прочитать объект, проверьте, не является ли ссылка "mutable-item" ненулевой. Если так, используйте это. В противном случае проверьте, не является ли ссылка «immutable-item» ненулевой. Если так, используйте это. В противном случае используйте ссылку «изменяемый элемент» (которая к настоящему времени будет не нулевой).

Чтобы изменить объект, проверьте, не является ли ссылка "mutable-item" ненулевой. Если нет, скопируйте цель ссылки «неизменяемый элемент» и CompareExchange ссылку на новый объект в ссылку «изменяемый элемент». Затем измените цель ссылки «изменяемый элемент» и аннулируйте ссылку «неизменяемый элемент».

Чтобы клонировать объект, если ожидается, что клон будет снова клонирован до его мутации, извлеките значение ссылки "immutable-item". Если это значение равно null, сделайте копию цели «изменяемый элемент» и CompareExchange ссылкой на этот новый объект в ссылку на неизменяемый элемент. Затем создайте новую оболочку, чья ссылка «mutable-item» равна нулю, а чья ссылка «immutable-item» является либо полученным значением (если оно не было нулевым), либо новым элементом (если он был).

Чтобы клонировать объект, если ожидается, что клон будет мутирован до его клонирования, извлеките значение ссылки "immutable-item". Если ноль, получить ссылку "mutable-item". Скопируйте цель для любой ссылки, которая была получена, и создайте новую оболочку, чья ссылка "mutable-item" указывает на новую копию, а чья ссылка "immutable-item" равна нулю.

Два метода клонирования будут семантически идентичны, но выбор неправильного метода для данной ситуации приведет к дополнительной операции копирования. Если кто-то последовательно выбирает правильную операцию копирования, он получит большую часть преимуществ «агрессивного» подхода «копирование при записи», но с гораздо меньшими накладными расходами. Каждый объект хранения данных (например, строка) будет либо непостоянным изменяемым, либо общим неизменяемым, и ни один объект никогда не будет переключаться между этими состояниями. Следовательно, при желании можно было бы устранить все «издержки на многопоточность / синхронизацию» (заменив операции CompareExchange прямыми хранилищами) при условии, что ни один объект-оболочка не используется более чем в одном потоке одновременно. Два объекта-обертки могут содержать ссылки на один и тот же неизменный держатель данных, но они могут не замечать существование друг друга.

Обратите внимание, что при использовании этого подхода может потребоваться еще несколько операций копирования, чем при использовании "агрессивного" подхода. Например, если новая оболочка создается с новой строкой, и эта оболочка видоизменяется и копируется шесть раз, исходная оболочка будет содержать ссылки на исходный держатель строки и неизменную, содержащую копию данных. Шесть скопированных оболочек будут содержать ссылку на неизменяемую строку (всего две строки, хотя, если исходная строка никогда не была видоизменена после того, как была сделана копия, агрессивная реализация могла бы обойтись одной). Если оригинальная оболочка была видоизменена вместе с пятью из шести копий, то все ссылки на неизменяемую строку, кроме одной, станут недействительными. В этот момент, если шестая копия оболочки была видоизменена, агрессивная реализация копирования при записи может понять, что она содержит единственную ссылку на свою строку, и, таким образом, решить, что копия не нужна. Реализация, которую я описываю, однако, создаст новую изменяемую копию и откажется от неизменной. Несмотря на то, что существуют некоторые дополнительные операции копирования, сокращение накладных расходов в большинстве случаев должно более чем компенсировать затраты. Если большинство создаваемых логических копий никогда не видоизменяются, этот подход может быть более эффективным, чем всегда делать копии строк.

Answer 3

Не так много для CoW. По сути, вы копируете, когда хотите изменить его, и позволяете любому, кто не хочет его изменять, сохранять ссылку на старый экземпляр. Вам понадобится подсчет ссылок, чтобы отслеживать, кто все еще ссылается на объект, и, поскольку вы создаете новую копию, вам нужно уменьшить количество «старых» экземпляров. Сочетание клавиш - не делать копию, если этот счет равен единице (вы - единственная ссылка).

Кроме этого, мало что можно сказать, если только у вас нет конкретной проблемы.

Answer 4

Вы можете эмулировать «неизменяемую» строку, которую имеют другие языки (насколько я знаю, Python, C #).

Идея состоит в том, что каждая строка является неизменной, поэтому любая работа над строкой создает новую неизменяемую ... или это основная идея, чтобы избежать взрыва, вам не нужно создавать другую, если есть подобная.

Answer 5

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