4

TL/DRstd::vector<std::string> : Visual Studio 2012 RC でリリース設定を使用してコンパイルした場合、どのように大規模な高速割り当て解除を達成できますか?

基本的なコピーと移動のセマンティクスを実装して、演習としてstrungと同様に動作するクラスを作成しました。std::string

class strung
{
private:
    size_t length_;
    char* data_;

public:
    // -------- Constructors --------

    strung() : length_(0), data_(nullptr) {};

    strung(const char* c_str)
    {
        length_ = strlen(c_str);
        data_ = new char[length_];
        ::std::copy(c_str, c_str + length_, data_);
    };

    inline explicit strung(size_t length) : length_(length)
    {
        data_ = new char[length_];
    };

    strung(size_t length, char value) : length_(length)
    {
        data_ = new char[length_];
        ::std::fill(data_, data_ + length_, value);
    };

    // -------- Copy/move-constructors --------

    strung(const strung& old)
    {
        data_ = new char[old.length_];
        ::std::copy(old.data_, old.data_ + old.length_, data_);
        length_ = old.length_;
    };

    strung(strung&& old)
    {
        data_ = old.data_;
        length_ = old.length_;
        // Even though it is a rvalue, its destructor will still be called,
        // so we would like to prevent our data from being freed.
        old.data_ = nullptr;
    };

    // -------- Assignment operators --------

    inline strung & operator =(const strung& old)
    {
        if (this != &old)
        {
            delete[] data_;
            data_ = new char[old.length_];
            ::std::copy(old.data_, old.data_ + old.length_, data_);
            length_ = old.length_;
        }
        return *this;
    };

    strung & operator =(strung&& old)
    {
        if (this != &old)
        {
            delete[] data_;
            data_ = old.data_;
            length_ = old.length_;
            old.data_ = nullptr;
        }
        return *this;
    };

    // -------- Array operators (no bounds checking by design) --------

    inline char& operator[](size_t pos)
    {
        return data_[pos];
    };

    inline const char& operator[](size_t pos) const
    {
        return data_[pos];
    };

    // -------- Insertion operator for `ostream`s --------

    inline friend ::std::ostream &operator<<(::std::ostream &out, const strung& source)
    {
        out.write(source.data_, source.length_);
        return out;
    };

    // -------- Various functions --------

    inline const size_t length() const
    {
        return length_;
    }

    // -------- Poor man's iterators --------

    char* begin()
    {
        return data_;
    };

    char* end()
    {
        return data_ + length_;
    };

    // -------- Destructor --------

    inline ~strung()
    {
        delete[] data_;
    };
};

このコードのパフォーマンスstd::stringと使用を比較してみました:strung

double time(const std::function<void(void)> &func)
{
    using namespace std::chrono;
    auto t1 = high_resolution_clock::now(); 
    func();
    auto total = duration_cast<nanoseconds>(high_resolution_clock::now()-t1);
    return static_cast<double>(total.count()) / 1000000.;
}

template<typename T>
void test(const int num)
{
    double allocation_time, full_time;

    full_time = time([&] {
        std::vector<T> container;

        allocation_time = time([&] {
            container.reserve(num);

            for (int i=0; i < num; i++)
            {
                container.emplace_back(rand() % 10 + 1,'\0');

                for (char &chr : container.back())
                    chr = ('A' + rand() % ('Z' - 'A' + 1) );
            }
        });
    });

    std::cout << "Full time: " <<  full_time << " miliseconds" << std::endl 
        << "Allocation time: " << allocation_time << " miliseconds" << std::endl 
        << "Deallocation time: " << full_time - allocation_time << " miliseconds" << std::endl;
}

int main()
{
    std::cout << "-------- std::string --------" << std::endl;
    test<std::string>(500000);
    std::cout << "-------- strung --------" << std::endl;
    test<strung>(500000);
    return EXIT_SUCCESS;
}

そして、これらは結果でした：

デバッグ (x86-64)

-------- std::string --------
Full time: 51050.9 miliseconds
Allocation time: 1853.11 miliseconds
Deallocation time: 49197.8 miliseconds
-------- strung --------
Full time: 52404 miliseconds
Allocation time: 4886.28 miliseconds
Deallocation time: 47517.7 miliseconds

リリース (x86-64):

-------- std::string --------
Full time: 113.007 miliseconds
Allocation time: 107.006 miliseconds
Deallocation time: 6.0004 miliseconds
-------- strung --------
Full time: 47771.7 miliseconds
Allocation time: 356.02 miliseconds
Deallocation time: 47415.7 miliseconds

クラスに対してあまり最適化を行っていないので、割り当ての速度は理解できますが、解放の速度はもっと興味深いものです。

std::stringDebug 設定でのテストは、割り当て解除が と の両方で同様に複雑であることを示していますがstrung(それでも非常に遅い)、Release 設定でのテストでは、まったく同じままstd::stringで、非常に高速に割り当て解除が行われます。のデストラクタがほとんど自明であることを考えると、そのような高速な解放を達成するためにstrung何をしますか。std::stringstrung

最初は nop に最適化されていると思っていstd::stringたので、解放はまったく行われませんでしたが、strungのデストラクタを削除すると、後者の方がはるかに高速だったので、おそらくそうではありません。

割り当て解除を高速にしたいのですが、同様の割り当て解除速度を達成するにはどうすればよいですか?

4

1 に答える 1

12

Microsoftのstd::string実装では、「小さな文字列の最適化」と呼ばれるものを使用しています。これが意味するのは、std::string実際には15文字の文字列（a char[16]）が含まれているということです。16文字より短い文字列が指定された場合、その内部メモリに格納されます。したがって、これらの場合には動的メモリ割り当ては行われません。

常に動的に文字列を割り当てますstrung 。これは、そのデストラクタが常に割り当てを解除することを意味します。std::string、十分に小さい場合は、どちらも実行しません。

于 2012-08-26T15:06:51.543 に答える