178

最適化とコードスタイルに関するC++の質問では、のコピーを最適化するという文脈で「SSO」に言及した回答がいくつかありましたstd::string。その文脈でSSOはどういう意味ですか？

明らかに「シングルサインオン」ではありません。「共有文字列の最適化」、おそらく？

4

3 に答える 3

252

背景/概要

自動変数（malloc/を呼び出さずに作成する変数である「スタックから」 new）の操作は、通常、フリーストア（を使用して作成される変数である「ヒープ」）を含む操作よりもはるかに高速ですnew。ただし、自動配列のサイズはコンパイル時に固定されていますが、フリーストアからの配列のサイズは固定されていません。さらに、スタックサイズは制限されていますが（通常は数MiB）、フリーストアはシステムのメモリによってのみ制限されます。

SSOは、短い/小さい文字列の最適化です。通常std::string、文字列はフリーストア（「ヒープ」）へのポインタとして格納されます。これにより、を呼び出す場合と同様のパフォーマンス特性が得られますnew char [size]。これにより、非常に大きな文字列のスタックオーバーフローが防止されますが、特にコピー操作では遅くなる可能性があります。最適化として、の多くの実装は、のstd::stringような小さな自動配列を作成しますchar [20]。20文字以下の文字列がある場合（この例では、実際のサイズは異なります）、その配列に直接格納されます。これにより、電話をかける必要がまったくなくなり、処理がnew少しスピードアップします。

編集：

この回答がそれほど人気が​​あるとは思っていませんでしたが、人気があるので、実際にSSOの実装を「実際に」読んだことがないことに注意して、より現実的な実装を示しましょう。

実装の詳細

少なくとも、std::string次の情報を保存する必要があります。

  • サイズ
  • 容量
  • データの場所

std::string::size_typeサイズは、または最後へのポインタとして保存できます。唯一の違いは、ユーザーが呼び出したときに2つのポインターを減算するか、ユーザーが呼び出したときにポインターにをsize追加する必要があるかどうかです。容量はどちらの方法でも保存できます。size_typeend

使わないものにお金を払う必要はありません。

まず、上記で概説したことに基づいて、単純な実装を検討します。

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バイトの「オーバーヘッド」があり、さらにSSOバッファ用に16バイトあることを意味します（パディング要件のため、ここでは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;
    };
};

ほとんどの実装はこのように見えると思います。

于 2012-04-25T16:18:06.147 に答える
33

SSOは、「Small String Optimization」の略語です。これは、個別に割り当てられたバッファを使用するのではなく、文字列クラスの本体に小さな文字列を埋め込む手法です。

于 2012-04-25T16:15:57.390 に答える
28

他の回答ですでに説明されているように、SSOはSmall / ShortStringOptimizationを意味します。この最適化の背後にある動機は、アプリケーションが一般に長い文字列よりもはるかに短い文字列を処理するという否定できない証拠です。

上記の回答でDavidStoneが説明したように、std::stringクラスは内部バッファーを使用してコンテンツを指定された長さまで格納します。これにより、メモリを動的に割り当てる必要がなくなります。これにより、コードがより効率的かつ高速になります。

この他の関連する回答は、内部バッファーのサイズが実装に依存し、std::stringプラットフォームごとに異なることを明確に示しています（以下のベンチマーク結果を参照）。

ベンチマーク

これは、同じ長さの多数の文字列のコピー操作をベンチマークする小さなプログラムです。長さ=1の1,000万個の文字列をコピーする時間の印刷を開始し、次に長さ=2の文字列で繰り返します。長さが50になるまで続行します。

#include <string>
#include <iostream>
#include <vector>
#include <chrono>

static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
static const int ARRAY_SIZE = sizeof(CHARS) - 1;

static const int BENCHMARK_SIZE = 10000000;
static const int MAX_STRING_LENGTH = 50;

using time_point = std::chrono::high_resolution_clock::time_point;

void benchmark(std::vector<std::string>& list) {
    std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();

    // force a copy of each string in the loop iteration
    for (const auto s : list) {
        std::cout << s;
    }

    std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
    const auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
    std::cerr << list[0].length() << ',' << duration << '\n';
}

void addRandomString(std::vector<std::string>& list, const int length) {
    std::string s(length, 0);
    for (int i = 0; i < length; ++i) {
        s[i] = CHARS[rand() % ARRAY_SIZE];
    }
    list.push_back(s);
}

int main() {
    std::cerr << "length,time\n";

    for (int length = 1; length <= MAX_STRING_LENGTH; length++) {
        std::vector<std::string> list;
        for (int i = 0; i < BENCHMARK_SIZE; i++) {
            addRandomString(list, length);
        }
        benchmark(list);
    }

    return 0;
}

このプログラムを実行したい場合は./a.out > /dev/null、文字列を印刷する時間がカウントされないようにする必要があります。重要な番号はに印刷されるstderrため、コンソールに表示されます。

MacBookとUbuntuマシンからの出力でチャートを作成しました。長さが特定のポイントに達すると、文字列をコピーする時間が大幅に短縮されることに注意してください。これは、文字列が内部バッファに収まらなくなり、メモリ割り当てを使用する必要がある瞬間です。

Linuxマシンでは、文字列の長さが16に達するとジャンプが発生することにも注意してください。MacBookでは、長さが23に達するとジャンプが発生します。これは、SSOがプラットフォームの実装に依存することを確認します。

Ubuntu UbuntuのSSOベンチマーク

Macbook Pro MacbookProのSSOベンチマーク

于 2018-08-11T04:44:17.333 に答える