c++ - std::vector は、要素をシフトするときに追加の操作を行います

Question

ソートされた要素をメモリに連続して格納する必要があるため、std::vector と boost::flat_set について考えました。私は両方を試して、それらのパフォーマンスをチェックしましたが、std::vector を使用すると後方挿入が少し高速になりましたが、boost::flat_set を使用すると前方挿入がはるかに高速になりました。ここに私のテストコードがあります:

#include <iostream>
#include <vector>
#include <boost/container/flat_set.hpp>
#include <boost/chrono.hpp>
#include <windows.h>

// Just a basic movable object for my tests
class Component
{
public :
    Component( void ) :
        id( 0 ),
        name( "default" ),
        data( 100 )
    {
    }

    Component( uint32_t id ) :
        id( id ),
        name( "default" ),
        data( 100 )
    {
    }

    Component( Component&& component ) throw() :
        id( std::move( component.id ) ),
        name( std::move( component.name ) ),
        data( std::move( component.data ) )
    {
    }

    Component& operator=( Component&& component ) throw()
    {
        id = std::move( component.id );
        name = std::move( component.name );
        data = std::move( component.data );
        return ( *this );
    }

    uint32_t    get_id( void ) const
    {
        return ( id );
    }

private :
    uint32_t                id;
    std::string             name;
    std::vector< uint32_t > data;
};

// This object can be sorted
inline bool operator<( const Component& component1, const Component& component2 )
{
    return ( component1.get_id() < component2.get_id() );
}

#define COMP_NB 1000000

int main( void )
{
    /*******************************/
    /* Test vector insertion speed */
    /*******************************/
    std::vector< Component > vector;

    vector.reserve( COMP_NB + 1 );

    std::cout << "Push back components in the vector: ";
    auto startTime = boost::chrono::steady_clock::now();

    // Back insertion
    for ( uint32_t i = 0; i < COMP_NB; ++i )
    {
        vector.push_back( Component( i + 1 ) );
    }

    auto thisTime = boost::chrono::steady_clock::now();
    std::cout << boost::chrono::duration_cast< boost::chrono::milliseconds >( thisTime - startTime ).count() << "ms" << std::endl;

    std::cout << "Insert one component at the beginning of the vector: ";
    startTime = boost::chrono::steady_clock::now();

    // Front insertion (all components are shifted)
    vector.insert( vector.begin(), Component( 0 ) );

    thisTime = boost::chrono::steady_clock::now();
    std::cout << boost::chrono::duration_cast< boost::chrono::milliseconds >( thisTime - startTime ).count() << "ms" << std::endl;

    /*********************************/
    /* Test flat_set insertion speed */
    /*********************************/
    boost::container::flat_set< Component > flat_set;

    flat_set.reserve( COMP_NB + 1 );

    std::cout << "Push back components in the flat_set: ";
    startTime = boost::chrono::steady_clock::now();

    // Back insertion
    for ( uint32_t i = 0; i < COMP_NB; ++i )
    {
        flat_set.insert( Component( i + 1 ) );
    }

    thisTime = boost::chrono::steady_clock::now();
    std::cout << boost::chrono::duration_cast< boost::chrono::milliseconds >( thisTime - startTime ).count() << "ms" << std::endl;

    std::cout << "Insert one component at the beginning of the flat_set: ";
    startTime = boost::chrono::steady_clock::now();

    // Front insertion (all components are shifted)
    flat_set.insert( Component( 0 ) );

    thisTime = boost::chrono::steady_clock::now();
    std::cout << boost::chrono::duration_cast< boost::chrono::milliseconds >( thisTime - startTime ).count() << "ms" << std::endl;

    system( "PAUSE" );

    return ( 0 );
}

そして出力：

ベクトル内のコンポーネントをプッシュバックする
: 852ms ベクトルの先頭に 1 つのコンポーネントを挿入する
: 59ms flat_set 内のコンポーネントをプッシュバックする: 912ms flat_set
の先頭に 1 つのコンポーネントを挿入する: 16ms

flat_setでフロント挿入が3.6倍高速化！そこで、移動関数が使用されているかどうかを確認したかったので、別のテストを実行したところ、奇妙なことがわかりました。新しいコードは次のとおりです。

#include <iostream>
#include <vector>
#include <boost/container/flat_set.hpp>
#include <boost/chrono.hpp>
#include <windows.h>

// Just a basic movable object for my tests
class Component
{
public :
    Component( void ) :
        id( 0 ),
        name( "default" ),
        data( 100 )
    {
        std::cout << "Default constructor" << std::endl;
    }

    Component( uint32_t id ) :
        id( id ),
        name( "default" ),
        data( 100 )
    {
        std::cout << "Custom constructor" << std::endl;
    }

    Component( Component&& component ) throw() :
        id( std::move( component.id ) ),
        name( std::move( component.name ) ),
        data( std::move( component.data ) )
    {
        std::cout << "Move constructor" << std::endl;
    }

    Component& operator=( Component&& component ) throw()
    {
        std::cout << "Move assignment operator" << std::endl;
        id = std::move( component.id );
        name = std::move( component.name );
        data = std::move( component.data );
        return ( *this );
    }

    uint32_t    get_id( void ) const
    {
        return ( id );
    }

private :
    uint32_t                id;
    std::string             name;
    std::vector< uint32_t > data;
};

// This object can be sorted
inline bool operator<( const Component& component1, const Component& component2 )
{
    return ( component1.get_id() < component2.get_id() );
}

#define COMP_NB 1

int main( void )
{
    /*******************************/
    /* Test vector insertion speed */
    /*******************************/
    std::vector< Component > vector;

    vector.reserve( COMP_NB + 1 );

    std::cout << "-- Push back one component in the vector: " << std::endl;

    // Back insertion
    for ( uint32_t i = 0; i < COMP_NB; ++i )
    {
        vector.push_back( Component( i + 1 ) );
    }

    std::cout << "-- Insert one component at the beginning of the vector: " << std::endl;

    // Front insertion (the other component is shifted)
    vector.insert( vector.begin(), Component( 0 ) );

    std::cout << std::endl;

    /*********************************/
    /* Test flat_set insertion speed */
    /*********************************/
    boost::container::flat_set< Component > flat_set;

    flat_set.reserve( COMP_NB + 1 );

    std::cout << "-- Push back one component in the flat_set: " << std::endl;

    // Back insertion
    for ( uint32_t i = 0; i < COMP_NB; ++i )
    {
        flat_set.insert( Component( i + 1 ) );
    }

    std::cout << "-- Insert one component at the beginning of the flat_set: " << std::endl;

    // Front insertion (the other component is shifted)
    flat_set.insert( Component( 0 ) );

    system( "PAUSE" );

    return ( 0 );
}

新しい出力:

-- ベクター内の 1 つのコンポーネントをプッシュバック:
カスタムコンストラクター
移動コンストラクター
-- ベクターの先頭に 1 つのコンポーネントを挿入:
カスタムコンストラクター
移動コンストラクター
移動コンストラクター
移動代入演算子
移動代入演算子

-- flat_set 内の 1 つのコンポーネントをプッシュバック:
カスタムコンストラクター
移動コンストラクター
-- flat_set の先頭に 1 つのコンポーネントを挿入します。
カスタムコンストラクター
移動コンストラクター
移動代入演算子

ここで奇妙なことがあります。Flat_set の動作は正常なようです:

-- flat_set の先頭に 1 つのコンポーネントを挿入します:
カスタムコンストラクタ //わかりました、新しいコンポーネントの作成を要求しました
コンストラクタを移動します //わかりました、flat_set は前のコンポーネントを新しい位置にシフトする必要があります
代入演算子を移動します //OK 、新しいコンポーネントを flat_set の前に移動する必要があります

しかし、ベクトルはどうですか？

-- ベクターの先頭に 1 つのコンポーネントを挿入します。
カスタムコンストラクター //わかりました、新しいコンポーネントの作成を要求しました
移動コンストラクター //わかりました、ベクターは前のコンポーネントを新しい位置にシフトする必要があります
移動コンストラクター //待機。 .. 何？
代入演算子の移動 //OK、新しいコンポーネントをベクトルの前に移動する必要があります
代入演算子の移動 //Wtf?

より多くのコンポーネントを試してみましたが、ベクトルの動作は同じです。すべての移動操作を 2 回実行し続けます。なんで？回避できますか？そうでない場合は、flat_set を使用する必要がありますか (データをシフトする必要がある場合があります)。

[編集] : 10 個のコンポーネントが後ろに挿入され、1 個が前に挿入され、コンポーネントの ID が作成または移動された出力は次のとおりです: http://pastebin.com/SzT5M8yP

[編集 2] : boost::container::vector で同じテストを行ったところ、出力 (および速度!) は flag_set と同じです。ベクターの Microsoft 実装に問題がありますか? うーん

[編集 3]: Microsoft に提出された問題: https://connect.microsoft.com/VisualStudio/feedback/details/801205/std-vector-do-extra-operations-when-shifting-elements

score 2 · Accepted Answer

すべての移動操作を 2 回実行しているわけではありません。ベクトルに複数の要素が含まれている場合、一部の操作のみが 2 回発生することがわかります。

N 要素のベクトルの先頭に右辺値を挿入する (十分な容量がある) ための典型的なアプローチは次のとおりです。

インデックス N-1 の要素からインデックス N の構築新しい要素を移動する
new (_M_data+N) T(_M_data[N-1]);
_M_size += 1;
インデックス 0 から N-2 の割り当て要素をインデックス 1 から N-1 に移動します。
for (int i = N-1; i > 0; --i)
_M_data[i] = std::move(_M_data[i-1]);
コンストラクトを一時的に移動し、それをインデックス 0 に割り当てます
_M_data[0] = T(std::move(arg));

これは、1 つの move 構築が表示され、その後に (N-1) 回の move 割り当てが表示されることを意味します (この場合、ベクトルには 1 つの要素しかないため、ステップ 2 では何も表示されません)、次に move 構築と move 割り当てが表示されます。

emplaceステップ 3 では、同じ挿入ロジックがasに使用されるため、テンポラリが構築されますinsert。したがって、実際にはT(std::move(args)...)0 個以上の引数で行われます。タイプの引数が 1 つだけの場合は、単に実行して移動を回避することTが可能でした。_M_data[0] = std::move(arg);工事。

最後に追加の移動割り当てが表示される理由がわかりません.GCCの標準ライブラリの実装ではそれが行われず、なぜ必要なのかわかりません. コードを簡単に変更して、構築/割り当てられて移動されるオブジェクトの ID を出力し、どの要素が 2 回移動されているかを確認して、さらに光を当てることができます。

score 0 · Accepted Answer

3年後、これが私のメールボックスに届きます：

Microsoft Connect からこんにちは。

この通知は、フィードバック項目に対して生成されました: std::vector は、Microsoft Connect サイトで送信した要素をシフトするときに追加の操作を行います。

やあ、

このバグを報告していただきありがとうございます。正確性とパフォーマンスのために vector を徹底的に見直して修正しました。この修正は VS "15" RC で利用できるようになります。以前は、特定の状況で挿入/配置がrotate()を呼び出していました。これで、アクションをよりインテリジェントに順序付けし、要素を回転させる必要がなくなりました。

Stephan T. Lavavej プリンシパルソフトウェアエンジニア、Visual C++ ライブラリ stl@microsoft.com

Microsoft によってその他の変更が加えられた場合は、一般的な "フィードバック項目が更新されました" という通知も受け取ることがあります。

Microsoft Connect をご利用いただきありがとうございます。

よろしく、

Microsoft Connect チーム

このメッセージは監視されていない電子メールアカウントから生成されているため、このメッセージに直接返信しないでください。フィードバックに関連するコメントがある場合は、上記のリンクの [フィードバック] 項目に移動して、フィードバック項目の [コメント] セクション (Microsoft にコメントを投稿) に入力してください。

上記のフィードバックリンクへのアクセスに問題がある場合は、http://connect.microsoft.com/help/default.aspxページにアクセスして問題を報告してください。送信する際は、上記のリンクのコピーを必ず貼り付けてください。レポートに。

万歳！すぐに修正されます。:D 確かに少し遅いですが、それでも良いことです。

score -1 · Accepted Answer

私の推測ではstd::vector、新しいベクトルを割り当て、現在の特異値を新しいベクトルにコピーしてから、新しい値を挿入することで、ベクトルのサイズを大きくしています。の呼び出しを削除しreserveて、メモリ管理がstd::vector機能するようにしてください。

c++ - std::vector は、要素をシフトするときに追加の操作を行います

3 に答える 3

Related

Reference