Как реализовать Копию на записи?

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

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

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

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

В многопоточном окружении (а сейчас их большинство) 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_ - это тип, для которого у вас есть как атомарное приращение, так и атомарное декремент и тестовая инструкция.

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