c++ - 元组上的推力排序非常慢

Question

我需要对元组数组进行排序，因此我为元组定义一个运算符并使用 thrust::sort 进行排序。

所以我发现对元组数组进行排序比对数字数组进行排序要慢得多。这是我的代码:

#include <thrust/device_vector.h>
#include <thrust/host_vector.h>
#include <thrust/set_operations.h>
#include <thrust/reduce.h>
#include <thrust/unique.h>
#include <thrust/binary_search.h>
#include <thrust/gather.h>
#include <thrust/transform.h>
#include <thrust/functional.h>
#include <thrust/sort.h>
#include <thrust/execution_policy.h>
#include <iostream>

static const int size = 100000;

#define mzi(x) thrust::make_zip_iterator(x)

#define mt(...) thrust::make_tuple(__VA_ARGS__)

typedef thrust::tuple<int, int> IntTuple;
typedef thrust::device_vector<IntTuple>::iterator TupleIterator;
typedef thrust::device_vector<int>::iterator IntIterator;
typedef thrust::tuple<IntIterator, IntIterator> IteratorTuple;
typedef thrust::zip_iterator<IteratorTuple> ZipIterator;

struct TupleComp
{
    __host__ __device__
    bool operator()(const IntTuple& t1, const IntTuple& t2)
    {
        return t1.get<0>() != t2.get<0>() ? t1.get<0>() < t2.get<0>() : t1.get<1>() > t2.get<1>();
    }
};

int main()
{
    timespec start;
    clock_gettime(0, &start);
    thrust::device_vector<int> dataA1(size);
    thrust::device_vector<int> dataA2(size);
    thrust::device_vector<int> dataB1(size);
    thrust::device_vector<int> dataB2(size);

    srand(time(NULL));
    for (int i = 0; i < size; i++)
    {
        //dataA[i] = dataA[i - 1] + (rand() % 100);
        dataA1[i] = (rand() % 100);
        dataA2[i] = (rand() % 100);
        dataB1[i] = (rand() % 100);
        dataB2[i] = (rand() % 100);
        std::cout << dataA1[i] << "\t" << dataA2[i] << "\t" << dataB1[i] << "\t" << dataB2[i];
        std::cout << std::endl;
    }
    timespec end;
    clock_gettime(0, &end);
    std::cout << "gendb took: " << end.tv_sec - start.tv_sec << "s" << end.tv_nsec - start.tv_nsec << "ns" << std::endl;
    ZipIterator beginA = mzi(mt(dataA1.begin(), dataA2.begin()));
    ZipIterator beginB = mzi(mt(dataB1.begin(), dataB2.begin()));
    ZipIterator endA = mzi(mt(dataA1.end(), dataA2.end()));
    ZipIterator endB = mzi(mt(dataB1.end(), dataB2.end()));
    thrust::device_vector<IntTuple> A(size);
    thrust::device_vector<IntTuple> B(size);

    clock_gettime(0, &start);
    thrust::copy(beginA, endA, A.begin());
    thrust::copy(beginB, endB, B.begin());
    clock_gettime(0, &end);
    std::cout << "thrust::copy took: " << end.tv_sec - start.tv_sec << "s" << end.tv_nsec - start.tv_nsec << "ns" << std::endl;

    clock_gettime(0, &start);
    thrust::sort(A.begin(), A.end());
    clock_gettime(0, &end);
    std::cout << "A thrust::sort took: " << end.tv_sec - start.tv_sec << "s" << end.tv_nsec - start.tv_nsec << "ns" << std::endl;
    clock_gettime(0, &start);
    thrust::sort(B.begin(), B.end(), TupleComp());
    clock_gettime(0, &end);
    std::cout << "B thrust::sort took: " << end.tv_sec - start.tv_sec << "s" << end.tv_nsec - start.tv_nsec << "ns" << std::endl;

    clock_gettime(0, &start);
    thrust::sort(dataA1.begin(), dataA1.end());
    clock_gettime(0, &end);
    std::cout << "regular thrust::sort took: " << end.tv_sec - start.tv_sec << "s" << end.tv_nsec - start.tv_nsec << "ns" << std::endl;
    clock_gettime(0, &start);
    thrust::sort(beginA, endA, TupleComp());
    thrust::sort(beginB, endB, TupleComp());
    clock_gettime(0, &end);
    std::cout << "thrust::sort took: " << end.tv_sec - start.tv_sec << "s" << end.tv_nsec - start.tv_nsec << "ns" << std::endl;
}

我发现元组排序比常规排序慢~10X倍。

我不明白为什么。推力中排序的复杂度是否直接受操作符影响？尽管如此，我的运算符并不比常规比较器慢 10 倍。

注意: 它不只是慢了 10 倍: 对于 100000 来说，速度慢了约 10 倍 对于 1000000 来说，速度慢了约 20 倍

我还发现，将两个数组复制到元组数组中并对该数组进行排序大约快 150%，而 Thrust::copy 几乎不需要任何操作(1M 需要 0.3)。

注2:

我将运算符更改为:

struct TupleComp
{
    __host__ __device__
    bool operator()(const IntTuple& t1, const IntTuple& t2)
    {
        if(t1.get<0>() < t2.get<0>())
            return true;
        if(t1.get<0>() > t2.get<0>())
            return false;
        return t1.get<1>() > t2.get<1>();
    }
};

现在排序速度快了大约 112.5%，这可能是因为第一个值上的 equals 很少发生，这样就需要检查更少的 if一般在运算符中。

Answer 1

抱歉，Nsight 完全让我困惑，一直以来我都相信自己处于 Release模式，但它本身的运行配置被设置为运行 Debug模式。

现在我已经确保一切都准备好发布，而且效果好多了。

整型排序和元组排序之间的差异仅约 150%，这更有意义。不确定我还能做些什么来提高性能，但它已经足够好了。

结论是:要小心 Eclipse 首选项，尤其是在 Linux 上。