Как реализовать Copy-on-Write?
Я хочу реализовать функцию копирования при записи в моем собственном классе C++ String, и мне интересно, как...
Я пытался реализовать некоторые варианты, но все они оказались очень неэффективными.
Спасибо вам, ребята:-)
6 ответов
В многопоточном окружении (которое является большинством из них в настоящее время) 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_ это тип, для которого у вас есть как атомарный инкремент, так и атомарный декремент и инструкция тестирования.
Существует еще более продвинутый метод оптимизации, который включает использование объединения для хранения коротких строк прямо в битах данных, которые вы использовали бы для описания более длинной строки. Но это еще сложнее, и я не думаю, что я буду склонен отредактировать это, чтобы позже привести упрощенный пример, но вы никогда не сможете сказать.
Есть серия статей именно об этом в книге Херба Саттера " Больше исключений на С ++". Если у вас нет доступа к нему, вы можете попробовать следовать через статьи в Интернете: часть 1, часть 2 и часть 3.
Я хотел бы предложить, что если кто-то хочет эффективно реализовать копирование при записи (для строк или чего-либо еще), следует определить тип оболочки, который будет вести себя как изменяемая строка и который будет содержать как обнуляемую ссылку на изменяемую строку (нет другая ссылка на этот элемент когда-либо будет существовать) и пустая ссылка на "неизменяемую" строку (ссылки на которые никогда не будут существовать вне вещей, которые не будут пытаться изменить его). Обертки всегда будут создаваться с хотя бы одной из этих ссылок, отличных от 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 прямыми хранилищами) при условии, что ни один объект-оболочка не используется одновременно в нескольких потоках. Два объекта-обертки могут содержать ссылки на один и тот же неизменный держатель данных, но они могут не замечать существование друг друга.
Обратите внимание, что при использовании этого подхода может потребоваться еще несколько операций копирования, чем при использовании "агрессивного" подхода. Например, если новая оболочка создается с новой строкой, и эта оболочка видоизменяется и копируется шесть раз, исходная оболочка будет содержать ссылки на исходный держатель строки и неизменную, содержащую копию данных. Шесть скопированных оболочек будут содержать ссылку на неизменяемую строку (всего две строки, хотя, если исходная строка никогда не была видоизменена после того, как была сделана копия, агрессивная реализация могла бы обойтись одной). Если оригинальная оболочка была видоизменена вместе с пятью из шести копий, то все ссылки на неизменяемую строку, кроме одной, станут недействительными. В этот момент, если шестая копия оболочки была видоизменена, агрессивная реализация копирования при записи может понять, что она содержит единственную ссылку на свою строку, и, таким образом, решить, что копия не нужна. Реализация, которую я описываю, однако, создаст новую изменяемую копию и откажется от неизменной. Несмотря на то, что существуют некоторые дополнительные операции копирования, сокращение накладных расходов в большинстве случаев должно более чем компенсировать затраты. Если большинство создаваемых логических копий никогда не видоизменяются, этот подход может быть более эффективным, чем всегда делать копии строк.
Там не так много для CoW. По сути, вы копируете, когда хотите изменить его, и позволяете любому, кто не хочет его изменять, сохранять ссылку на старый экземпляр. Вам понадобится подсчет ссылок, чтобы отслеживать, кто все еще ссылается на объект, и, поскольку вы создаете новую копию, вам необходимо уменьшить количество "старых" экземпляров. Сочетание будет не делать копию, когда этот счет равен единице (вы единственная ссылка).
Кроме этого, мало что можно сказать, если только у вас нет конкретной проблемы.
Вы можете эмулировать "неизменяемую" строку, которую имеют другие языки (насколько я знаю, Python, C#).
Идея состоит в том, что каждая строка является неизменной, поэтому любая работа над строкой создает новую неизменяемую... или это основная идея, чтобы избежать взрыва, вам не нужно создавать другую, если есть подобная.
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);
}
}