c++ - 如何使用 Boost.Sort string_sort 函数使 C++ 结构快速运行

Question

与成对的指针+长度和 std::string 相比，我发现对 std::string 对象进行排序时性能差异非常大

我在我的应用程序中进行了大量排序，我发现性能瓶颈在于对大型字符串数组进行排序。我知道进行此类排序的两种好方法 - 使用 std::sort 和 Boost.sort 函数。我正在使用指针和字符串长度信息对大文件的各个部分进行排序

我尝试将我的性能与对 std::string 对象进行排序进行比较，而我的简单指针+长度结构要慢得多。 我无法想象 - 为什么？sizeof(std::string) 是 32，而 sizeof(my_struct) 是 16 字节。两者都是在内部使用::memcmp函数进行比较

为了描述这个问题，我制作了一个小应用程序，可以显示排序 std::string 和我的结构对象之间的性能差异:

#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <boost/sort/sort.hpp>

using namespace std;

#define LEN   4
#define COUNT 1000000
#define USE_BOOST_SORT

// simple structure that i think to be identical to std::string
struct test
{
    inline bool operator<(const test& a) const  noexcept
    {
        size_t minsize = len < a.len ? len : a.len;
        int res = ::memcmp(ptr, a.ptr, minsize);
        return res < 0 || (res == 0 && len < a.len);
    }
    inline size_t size() const noexcept
    {return len;}
    inline const char* data() const noexcept
    {return ptr;}
    inline const char& operator[](size_t index) const noexcept
    {return ptr[index];}

    const char* ptr = nullptr;
    size_t len = 0;
};


int main(int,char**)
{
    // stage 1.a - initialize string sorting data with randoms
    vector<string> strings;
    strings.resize(COUNT);
    int counter = 0;
    for (string& s : strings)
    {
        s.resize(LEN);
        for (char& c : s)
            c = (counter++) % 256;
    }
    // stage 1.b - make the copy of data to get deterministic results and initialize tests array
    vector<string> strings_copy = strings;
    vector<test> tests;
    tests.resize(strings_copy.size());
    for (size_t i = 0; i < tests.size(); ++i)
    {
        tests[i].ptr = strings_copy[i].data();
        tests[i].len = strings_copy[i].size();
    }

    //  stage 2. sorting
    for (size_t i = 0; i < 10; ++i)
    {
        // make the copy of data to keep order unchanged
        vector<string> to_be_sorted = strings;
        chrono::high_resolution_clock::time_point t1 = chrono::high_resolution_clock::now();
#ifdef USE_BOOST_SORT
        boost::sort::spreadsort::string_sort(to_be_sorted.begin(), to_be_sorted.end());
#else
        sort(to_be_sorted.begin(), to_be_sorted.end());
#endif
        chrono::high_resolution_clock::time_point t2 = chrono::high_resolution_clock::now();
        to_be_sorted.clear();
        // make the copy of tests for sorting
        vector<test> tests_for_sort = tests;
        chrono::high_resolution_clock::time_point t3 = chrono::high_resolution_clock::now();
#ifdef USE_BOOST_SORT
        boost::sort::spreadsort::string_sort(tests_for_sort.begin(), tests_for_sort.end());
#else
        sort(tests_for_sort.begin(), tests_for_sort.end());
#endif
        chrono::high_resolution_clock::time_point t4 = chrono::high_resolution_clock::now();

        cout << "String sort time: " << chrono::duration_cast<chrono::milliseconds>(t2-t1).count()
             << " msec" << endl;
        cout << "Test sort time: " << chrono::duration_cast<chrono::milliseconds>(t4-t3).count()
             << " msec" << endl;
    }
}

Here is same code at IDE One

程序输出为

String sort time: 57 msec
Test sort time: 134 msec
String sort time: 51 msec
Test sort time: 130 msec
String sort time: 49 msec
Test sort time: 131 msec
String sort time: 51 msec
Test sort time: 130 msec
String sort time: 49 msec
Test sort time: 129 msec
String sort time: 51 msec
Test sort time: 130 msec
String sort time: 49 msec
Test sort time: 130 msec
String sort time: 51 msec
Test sort time: 132 msec
String sort time: 50 msec
Test sort time: 130 msec
String sort time: 50 msec
Test sort time: 131 msec

如果我使用 std::sort 而不是 Boost.Sort，问题仍然存在。

但是如果我尝试将 LEN 参数更改为 16 或更大，我的结构将以相同的速度 开始排序。

那么我的问题 - 我如何改进我的代码以使其在使用小字符串时像 std::string 对象一样快速排序？

我的主要编译器是 MSVC 2015 update 3/Win64。 IDE one内部使用的是GCC，所以这可能不是编译器的问题

使用 Boost.Sort 时的另一种选择是创建一个“Functor”对象来包装我的结构并实现所需的接口(interface)。但是这样它的工作速度比现在还要慢

使用 unsigned char 数据类型而不是 char 不会改变任何东西

Answer 1

检查您的库是否使用 SSO(小字符串优化)来实现字符串。

如果是这样，增加的引用位置可以很容易地解释差异。它还解释了当字符串变得太大而无法从 SSO 中受益时，差异就会消失

概念证明:killSSO

使用 killSSO 行运行此基准测试，注释掉输出: Live On Coliru

String std::sort time:  193.334 msec
View std::sort time:    419.458 msec
String boost sort time: 63.2888 msec
View boost sort time:   154.191 msec
...

取消注释行 std::for_each(c.begin(), c.end(), kill_SSO{}); 打印: Live On Coliru

String std::sort time:  548.243 msec
View std::sort time:    422.26 msec
String boost sort time: 156.891 msec
View boost sort time:   154.163 msec

Nonius 基准测试

使用 Nonius micro-benchmark framework我们得到:

#include <algorithm>
#include <boost/sort/sort.hpp>
#include <boost/utility/string_view.hpp>
#include <vector>
#define NONIUS_RUNNER
#include <nonius/benchmark.h++>
#include <nonius/main.h++>

extern std::vector<std::string> const testdata;

struct kill_SSO {
    void operator()(std::string& s) const { s.reserve(20); }
    template <typename Other> void operator()(Other&&) const   {} // not needed
};

struct std_sort          { template <typename It> static void run(It b, It e) { std::sort(b,                            e); } };
struct boost_spread_sort { template <typename It> static void run(It b, It e) { boost::sort::spreadsort::string_sort(b, e); } };

template <typename C, typename Sort, bool Kill = false> void bench(nonius::chronometer& cm) {
    C c {testdata.begin(), testdata.end()};
    if (Kill) std::for_each(c.begin(), c.end(), kill_SSO{});

    cm.measure([&]{ Sort::run(c.begin(), c.end()); });
}

using view = boost::string_view; // std::string_view, boost::string_ref, gsl::span etc.
NONIUS_BENCHMARK("SSO std::sort time:  ",    [](nonius::chronometer cm) { bench<std::vector<std::string>, std_sort, false>(cm); })
NONIUS_BENCHMARK("SSO boost sort time: ",    [](nonius::chronometer cm) { bench<std::vector<std::string>, boost_spread_sort, false>(cm); })
NONIUS_BENCHMARK("String std::sort time:  ", [](nonius::chronometer cm) { bench<std::vector<std::string>, std_sort, true>(cm); })
NONIUS_BENCHMARK("String boost sort time: ", [](nonius::chronometer cm) { bench<std::vector<std::string>, boost_spread_sort, true>(cm); })
NONIUS_BENCHMARK("View std::sort time:    ", [](nonius::chronometer cm) { bench<std::vector<view>       , std_sort>(cm); })
NONIUS_BENCHMARK("View boost sort time:   ", [](nonius::chronometer cm) { bench<std::vector<view>       , boost_spread_sort>(cm); })

std::vector<std::string> const testdata = [] {
    std::vector<std::string> generated(1000000);
    auto genchar = [count=0]() mutable { return static_cast<char>(static_cast<uint8_t>(count++ % 256)); };
    std::generate(generated.begin(), generated.end(), [&] { return std::string {genchar(), genchar(), genchar(), genchar()}; });
    return generated;
}();

结果 Interactive On Plot.ly