1. ホーム
  2. c++

[解決済み] std::stringの文脈における頭文字SSOの意味

2022-04-21 02:50:47

質問

最適化とコードスタイルに関する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;
    };
};

ほとんどの実装は、このような感じだと思います。