Я хочу реализовать copy-on-write в моем настраиваемом классе С++ String, и мне интересно, как...
Я попытался реализовать некоторые параметры, но все они оказались очень неэффективными.
Спасибо, ребята: -)
Как реализовать Copy-on-Write?
Ответ 1
В многопоточной среде (в настоящее время это большая часть) CoW часто представляет собой огромный успех, а не выигрыш. И с осторожным использованием ссылок на const они не сильно выигрывают от производительности даже в однопоточной среде.
В этой старой статье DDJ объясняется насколько плохо CoW может быть в многопоточной среде, даже если есть только один поток.
Кроме того, как отмечали другие люди, строки CoW действительно сложны в реализации, и легко ошибиться. Это в сочетании с их низкой производительностью в ситуациях с резьбой заставляет меня действительно подвергать сомнению их полезность в целом. Это становится еще более актуальным, если вы начнете использовать конструкцию перемещения С++ 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 allocation functions on purpose.
// C++ 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_ - это тип, который у вас есть как атомарный инкремент, а также инструкцию о сокращении атома и теста.
Существует еще более совершенная методика оптимизации, в которой используется объединение для хранения коротких строк прямо в битах данных, которые вы использовали бы для описания более длинной строки. Но это еще сложнее, и я не думаю, что буду чувствовать себя склонным редактировать это, чтобы упростить пример здесь позже, но вы никогда не можете сказать.
Ответ 2
В этой серии статей о том, как именно это делается на странице Herb Sutter Больше исключительных С++. Если у вас нет доступа к нему, вы можете попробовать следующие статьи в Интернете: часть 1, часть 2 и часть 3.
Ответ 3
Там не так много для CoW. В основном, вы копируете, когда хотите изменить его, и пусть любой, кто не хочет его менять, сохраняет ссылку на старый экземпляр. Вам понадобится подсчет ссылок, чтобы отслеживать, кто еще ссылается на объект, а так как вы создаете новую копию, вам нужно уменьшить счетчик на "старом" экземпляре. Ярлык будет заключаться в том, чтобы не делать копию, когда этот счет один (вы единственная ссылка).
Кроме этого, не так много, что можно сказать, если нет конкретной проблемы, с которой вы сталкиваетесь.
Ответ 4
Я бы предположил, что если кто-то хочет эффективно реализовать copy-on-write (для строк или что-то еще), следует определить тип-оболочку, который будет вести себя как изменяемая строка и который будет содержать как нулевую ссылку на изменяемую string (никакая другая ссылка на этот элемент никогда не будет существовать) и нулевая ссылка на "неизменяемую" строку (ссылки на которые никогда не будут существовать вне вещей, которые не будут пытаться ее мутировать). Упаковщики всегда будут созданы, по крайней мере, с одной из этих ссылок, не нулевых; после того, как ссылка на изменяемый элемент когда-либо будет установлена на ненулевое значение (во время или после построения), оно навсегда будет ссылаться на одну и ту же цель. Каждый раз, когда обе ссылки не являются нулевыми, ссылка на неизменяемые позиции указывает на копию элемента, которая была сделана через некоторое время после последней завершенной мутации (во время мутации ссылка на неизменяемые позиции может содержать или не содержать ссылку до значения перед мутацией).
Чтобы прочитать объект, проверьте, не указана ли ссылка "mutable-item". Если да, используйте его. В противном случае проверьте, не указана ли ссылка "неизменяемый элемент" . Если да, используйте его. В противном случае используйте ссылку "изменяемый элемент" (которая теперь будет не нулевой).
Чтобы мутировать объект, проверьте, не имеет ли значение ссылка "mutable-item". Если нет, скопируйте цель ссылки "неизменяемый элемент" и CompareExchange ссылку на новый объект в ссылку "изменяемый элемент" . Затем измените цель ссылки "изменчивый элемент" и аннулируйте ссылку "неизменяемый элемент" .
Чтобы клонировать объект, если клон, как ожидается, будет клонирован снова, прежде чем он будет мутирован, извлеките значение ссылки "неизменяемый элемент" . Если он равен нулю, сделайте копию цели "изменчивого элемента" и CompareExchange ссылку на этот новый объект в ссылку на неизменяемые позиции. Затем создайте новую оболочку, чья ссылка "mutable-item" имеет значение null, а ссылка "неизменяемый элемент" - это либо полученное значение (если оно не было null), либо новый элемент (если он был).
Чтобы клонировать объект, если ожидается, что клон будет мутирован до его клонирования, извлеките значение ссылки "неизменяемый элемент" . Если значение null, выберите ссылку "mutable-item". Скопируйте цель любой из исходных данных и создайте новую оболочку, чья ссылка "изменяемый элемент" указывает на новую копию, а ссылка "неизменяемый элемент" равна нулю.
Два метода клонирования будут семантически идентичными, но выбор неправильного для данной ситуации приведет к дополнительной операции копирования. Если вы последовательно выбираете правильную операцию копирования, вы получите большую выгоду от "агрессивного" подхода к копированию на запись, но с гораздо меньшими затратами на потоки. Каждый объект хранения данных (например, строка) будет либо несовместимым, либо измененным, либо общим неизменным, и ни один объект не будет переключаться между этими состояниями. Следовательно, можно было бы при желании устранить все "потоки/потоки синхронизации" (заменяя операции CompareExchange с прямыми магазинами) при условии, что ни один объект-обертку не используется одновременно в нескольких потоках. Два объекта-обертки могут содержать ссылки на один и тот же неизменяемый держатель данных, но они могут не обращать внимания на существование других.
Обратите внимание, что при использовании этого подхода может потребоваться несколько операций копирования, чем при использовании "агрессивного" подхода. Например, если новая оболочка создается с новой строкой и эта оболочка мутируется и копируется шесть раз, исходная оболочка будет содержать ссылки на исходный держатель строки и неизменяемый, содержащий копию данных. Шесть скопированных оберток просто проведут ссылку на неизменяемую строку (всего две строки, хотя, если исходная строка никогда не была мутировалась после того, как была сделана копия, агрессивная реализация могла обойтись одним). Если исходная обертка была мутирована вместе с пятью из шести экземпляров, то все, кроме одной ссылки на неизменяемую строку, будут признаны недействительными. В этот момент, если шестая копия обертки была мутирована, агрессивная реализация copy-on-write может понять, что она содержала единственную ссылку на ее строку и, таким образом, решила, что копия не нужна. Однако реализация, которую я описываю, создала бы новую изменяемую копию и оставила бы неизменяемую. Однако, несмотря на то, что есть некоторые дополнительные операции копирования, сокращение накладных расходов на потоки должно в большинстве случаев более чем компенсировать затраты. Если большинство созданных логических копий никогда не мутируются, этот подход может быть более эффективным, чем всегда делать копии строк.
Ответ 5
Вы можете захотеть эмулировать "неизменяемую" строку, которую имеют другие языки (Python, С#, насколько мне известно).
Идея состоит в том, что каждая строка неизменна, поэтому любая работа над строкой создает новую неизменяемую... или что основная идея, чтобы избежать взрыва, вам не нужно было создавать другую, если есть аналогичная.
Ответ 6
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);
}
}