[解決済み] std::stringの文脈における頭文字SSOの意味
質問
で
最適化とコードスタイルに関するC++の質問
のコピーを最適化するという文脈で、いくつかの回答が "SSO" に言及しました。
std::string
. その中で、SSOとはどのような意味ですか?
シングルサインオンではないことは明らかですが、共有文字列の最適化、でしょうか。
解決方法は?
背景・概要
自動変数の操作("from stack"、つまり
malloc
/
new
を使用して作成される変数は、一般的にフリーストア("ヒープ")に関わるものよりもはるかに高速です。
new
). ただし、自動配列のサイズはコンパイル時に固定されていますが、フリーストアからの配列のサイズは固定されていません。さらに、スタックのサイズは制限されています(通常は数MiB)。一方、フリーストアはシステムのメモリによってのみ制限されます。
SSOとは、Short / Small String Optimizationのことです。A
std::string
は通常、文字列をフリーストア ("the heap") へのポインタとして格納します。
new char [size]
. これにより、非常に大きな文字列に対するスタックのオーバーフローを防ぐことができますが、特にコピー操作の際に遅くなることがあります。最適化として、多くの
std::string
のような小さな自動配列を作成します。
char [20]
. 20文字以下の文字列があれば(この例では、実際のサイズは異なります)、その配列に直接格納されます。これによって
new
を全く使わないので、少しスピードアップしています。
EDIT
この回答がこれほど人気があるとは思っていませんでしたが、せっかくなので、私が実際にSSOの実装を読んだことがないという注意点を踏まえつつ、より現実的な実装を紹介させていただきます。
実装の詳細
最低でも
std::string
は、以下の情報を格納する必要がある。
- サイズ
- 容量
- データの保存場所
サイズを格納することができ
std::string::size_type
または末尾へのポインタとして使用します。唯一の違いは、ユーザが
size
を追加するか
size_type
を呼び出すと、ポインタに
end
. 容量はどちらの方法でも保存可能です。
使わないものにはお金を払わない。
まず、上で説明したことに基づいて、素朴な実装を考えてみましょう。
class string {
public:
// all 83 member functions
private:
std::unique_ptr<char[]> m_data;
size_type m_size;
size_type m_capacity;
std::array<char, 16> m_sso;
};
64ビットシステムの場合、一般的には
std::string
は、文字列ごとに24バイトの「オーバーヘッド」と、さらに16バイトのSSOバッファを持ちます(ここではパディングの必要性から20ではなく16が選ばれています)。単純化した例のように、これら3つのデータメンバーと文字のローカル配列を保存することは、実際には意味がありません。もし
m_size <= 16
ということであれば、すべてのデータを
m_sso
だから、私はすでに容量を知っているので、データへのポインタは必要ない。もし
m_size > 16
は必要ない。
m_sso
. 全部が必要なところは全く重ならない。スペースを無駄にしない、よりスマートな解決策は、もう少し以下のようなものでしょう(未検証、例示のみ)。
class string {
public:
// all 83 member functions
private:
size_type m_size;
union {
class {
// This is probably better designed as an array-like class
std::unique_ptr<char[]> m_data;
size_type m_capacity;
} m_large;
std::array<char, sizeof(m_large)> m_small;
};
};
ほとんどの実装は、このような感じだと思います。
関連
-
[解決済み】非静的メンバ関数への参照を呼び出す必要がある
-
[解決済み] error: 'if' の前に unqualified-id を期待した。
-
[解決済み] 文字列リテラルの前にある'b'文字は何を意味するのでしょうか?
-
[解決済み] C#のStringとstringの違いは何ですか?
-
[解決済み] 文字列の単語を反復処理するにはどうすればよいですか?
-
[解決済み] SQLiteのINSERT/per-secondのパフォーマンスを向上させる
-
[解決済み] 要素ごとの加算は、結合ループよりも分離ループの方がはるかに高速なのはなぜですか?
-
[解決済み] C++11では、標準化されたメモリモデルが導入されました。その意味するところは?そして、C++プログラミングにどのような影響を与えるのでしょうか?
-
[解決済み] なぜC++はPythonよりもstdinからの行の読み込みが遅いのですか?
-
[解決済み】なぜC++プログラマは'new'の使用を最小限に抑えなければならないのでしょうか?
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
[解決済み】非静的メンバ関数への参照を呼び出す必要がある
-
[解決済み】関数名の前に期待されるイニシャライザー
-
[解決済み] 既に.objで定義されている-二重包含はない
-
[解決済み】cc1plus:エラー:g++で認識されないコマンドラインオプション"-std=c++11"
-
[解決済み】「Expected '(' for function-style cast or type construction」エラーの意味とは?
-
[解決済み】Visual Studio 2013および2015でC++コンパイラーエラーC2280「削除された関数を参照しようとした」が発生する
-
[解決済み] gdbを使用してもデバッグシンボルが見つからない
-
[解決済み】変数やフィールドがvoid宣言されている
-
[解決済み] スタックアロケーションにより初期化されていない値が作成された
-
[解決済み] const std::string & をパラメータとして渡す時代は終わったのでしょうか?