カスタム C++ 文字列クラスにコピー オン ライトを実装したいのですが、どうすれば...
いくつかのオプションを実装しようとしましたが、どれも非常に非効率的でした。
君たちありがとう ：-）
23402 次
5 に答える
18
マルチスレッド環境 (最近ではほとんどの環境) では、CoW は多くの場合、パフォーマンスを向上させるのではなく、パフォーマンスを大幅に低下させます。また、const 参照を慎重に使用すると、シングル スレッド環境でもパフォーマンスが大幅に向上することはありません。
この古い DDJ の記事では、スレッドが 1 つしかない場合でも、マルチスレッド環境で 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;
}
このようにすると、1 ではなくバイトがdata_->data_含まれているかのように扱うことができます。alloclen_
これらすべての場合において、これをマルチスレッド環境で決して使用しないようにするかrefct_、アトミック インクリメントとアトミック デクリメントの両方を持つタイプであることを確認する必要があることに注意してください。とテスト命令。
ユニオンを使用して、長い文字列を記述するために使用するデータのビット内に短い文字列を格納する、さらに高度な最適化手法があります。しかし、それはさらに複雑であり、後で簡単な例をここに置くためにこれを編集する気はないと思いますが、決してわかりません.
于 2009-10-30T10:34:09.963 に答える
5
コピーオンライトを効率的に実装したい場合 (文字列など)、変更可能な文字列として動作し、変更可能な文字列への null 許容参照 (noそのアイテムへの他の参照は常に存在します)、および「不変」文字列への nullable 参照 (それを変更しようとしないものの外部には決して存在しない参照)。ラッパーは常に、これらの参照の少なくとも 1 つが非 null で作成されます。mutable-item 参照が null 以外の値に設定されると (構築中または構築後に)、永久に同じターゲットを参照します。両方の参照が null でないときはいつでも、immutable-item 参照は、最後に完了したミューテーションの後に作成されたアイテムのコピーを指します (ミューテーション中、
オブジェクトを読み取るには、「mutable-item」参照が null でないかどうかを確認します。もしそうなら、それを使用してください。それ以外の場合は、「immutable-item」参照が null でないかどうかを確認してください。もしそうなら、それを使用してください。それ以外の場合は、「mutable item」参照を使用します (これは今では非 null になります)。
オブジェクトを変更するには、"mutable-item" 参照が null でないかどうかを確認します。そうでない場合は、「不変アイテム」参照のターゲットをコピーし、CompareExchange 新しいオブジェクトへの参照を「可変アイテム」参照にコピーします。次に、「可変アイテム」参照のターゲットを変更し、「不変アイテム」参照を無効にします。
オブジェクトを複製するには、複製が変更される前に再度複製されることが予想される場合は、「immutable-item」参照の値を取得します。null の場合は、「可変アイテム」ターゲットのコピーを作成し、CompareExchange をその新しいオブジェクトへの参照として不変アイテム参照に作成します。次に、「mutable-item」参照が null で、「immutable-item」参照が取得された値 (null でない場合) または新しい項目 (null の場合) である新しいラッパーを作成します。
オブジェクトを複製するには、複製が複製される前に変更されることが予想される場合は、「immutable-item」参照の値を取得します。null の場合は、「mutable-item」参照を取得します。取得された参照のターゲットをコピーし、「mutable-item」参照が新しいコピーを指し、「immutable-item」参照が null である新しいラッパーを作成します。
2 つの複製方法は意味的には同じですが、特定の状況で間違った方法を選択すると、余分なコピー操作が発生します。一貫して正しいコピー操作を選択すると、「アグレッシブな」コピー オン ライト アプローチの利点を最大限に活用できますが、スレッド化のオーバーヘッドははるかに少なくなります。すべてのデータ保持オブジェクト (文字列など) は、非共有可変または共有不変のいずれかになり、これらの状態の間でオブジェクトが切り替わることはありません。したがって、ラッパー オブジェクトが複数のスレッドで同時に使用されていない場合は、必要に応じてすべての「スレッド化/同期化オーバーヘッド」を排除できます (CompareExchange 操作をストレート ストアに置き換えます)。2 つのラッパー オブジェクトが同じ不変データ ホルダーへの参照を保持している可能性がありますが、互いの存在を認識していない可能性があります。
このアプローチを使用する場合は、「積極的な」アプローチを使用する場合よりもいくつかのコピー操作が必要になる場合があることに注意してください。たとえば、新しいラッパーが新しい文字列で作成され、そのラッパーが変更され、6 回コピーされた場合、元のラッパーは元の文字列ホルダーへの参照を保持し、不変のものはデータのコピーを保持します。コピーされた 6 つのラッパーは、不変文字列への参照を保持するだけです (合計 2 つの文字列ですが、コピーが作成された後に元の文字列が決して変更されていない場合、積極的な実装は 1 つだけで済む可能性があります)。元のラッパーが 6 つのコピーのうちの 5 つとともに変更された場合、不変文字列への参照は 1 つを除いてすべて無効になります。その時点で、6 番目のラッパー コピーが変異した場合、積極的なコピー オン ライトの実装では、文字列への唯一の参照を保持していることに気づき、コピーが不要であると判断する可能性があります。ただし、私が説明する実装は、新しい可変コピーを作成し、不変コピーを破棄します。ただし、余分なコピー操作がいくつかあるという事実にもかかわらず、ほとんどの場合、スレッド化のオーバーヘッドの削減はコストを相殺する以上のものになるはずです。生成される論理コピーの大部分が決して変更されない場合、このアプローチは常に文字列のコピーを作成するよりも効率的である可能性があります。ほとんどの場合、スレッド化のオーバーヘッドの削減は、コストを相殺する以上のものになるはずです。生成される論理コピーの大部分が決して変更されない場合、このアプローチは常に文字列のコピーを作成するよりも効率的である可能性があります。ほとんどの場合、スレッド化のオーバーヘッドの削減は、コストを相殺する以上のものになるはずです。生成される論理コピーの大部分が決して変更されない場合、このアプローチは常に文字列のコピーを作成するよりも効率的である可能性があります。
于 2012-06-05T19:45:54.550 に答える
0
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);
}
}
于 2012-02-28T17:25:15.453 に答える