通过引用传递比较器函数(C++11)

Question

我正在尝试加速我的代码(下面是最小的，可重现的例子)，我被告知，对于我的比较器函数，通过引用传递将是一种更有效的方法。这是我第一次听说这个短语，所以我查了查，找到了一些有例子的网站，但我不知道什么时候和如何使用它。在这种情况下，我该如何使用它？

#include <array>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <ctime>
#include <random>

using namespace std;

class arrMember {
public:
    int var;
    arrMember(int var) :
        var(var) {}
    arrMember() {};
};

array<int, 1000000> arraySource;

array<arrMember, 1000000> arrayObjects;

bool compare(arrMember(x), arrMember(y)) {
    return (x.var < y.var);
}

void arrayPrint() {
    ofstream output("arrayPrint.txt");
    for (int k = 0; k != arrayObjects.size(); k++) {
        output << arrayObjects[k].var << endl;
    }

    output.close();
}

void sort() {
    int j = 0;
    for (auto i = arraySource.begin(); i != arraySource.end(); i++, j++) {
        arrayObjects[j] = arrMember(arraySource[j]);
    }

    sort(arrayObjects.begin(), arrayObjects.end(), compare);
}

int main(){
    random_device rd{};
    mt19937 engine{ rd() };
    uniform_int_distribution<int> dist{ 0, 9999 };
    for (int x = 0; x < arraySource.size(); ++x){
        arraySource[x] = dist(engine);
    }

    cout << "Executing sort...\n";
    clock_t t1 = clock();
    sort();
    clock_t t2 = clock();
    double timeDiff = ((double)(t2 - t1)) / CLOCKS_PER_SEC;

    cout << "Sort finished. CPU time was " << timeDiff << " seconds.\n";

    arrayPrint();

    return 0;
}

谢谢你的帮助。

Answer 1

对于很小的类型，通过引用传递没有帮助；复制构造由单个int组成的类的成本基本上与获取现有实例的地址相同，并且复制构造意味着比较器不需要解引用指针来查找值，它已经在本地堆栈上了。

对于具有昂贵复制构造的较大类型，您可以更改(原始代码减去不必要的括号)：

bool compare(arrMember x, arrMember y) {
    return x.var < y.var;
}

至：

bool compare(const arrMember& x, const arrMember& y) {
    return x.var < y.var;
}

并获得有意义的加速，但是对于一个简单的int包装器类，您什么也得不到。

不管所讨论的class的大小如何，重要的是用函数器(或lambda，这是函数器的语法糖)替换原始函数。std::sort将模板专用于比较器的类型，而函数本身不是类型；它们实际上是共享同一原型的一组函数的实例。因此，如果您同时实现了这两个功能：

bool compare(const arrMember& x, const arrMember& y) {
    return x.var < y.var;
}
bool compareReverse(const arrMember& x, const arrMember& y) {
    return x.var > y.var;
}

在程序中的不同位置使用compare和compareReverse调用std::sort，它只对bool (*)(const arrMember&, const arrMember&)的std::sort进行了一次特殊化，而且这种特殊化实际上必须传递并通过指针调用所提供的函数；调用函数的成本远远高于执行比较本身的微不足道的成本，而且通过指针调用通常更昂贵。

相比之下，函数器(和std::sort )是独特的类型，因此std::sort可以完全专门化它们，包括内联比较，因此不会发生对比较器函数的调用；比较器逻辑直接内联到lambda的独特专门化中。因此，不是：

bool compare(const arrMember& x, const arrMember& y) {
    return x.var < y.var;
}
std::sort(..., compare);

你可以这样做：

struct compare {
    bool operator()(const arrMember& x, const arrMember& y) const {
        return x.var < y.var;
    }
};
std::sort(..., compare());

或者将整个代码内联为C++11 lambda：

std::sort(..., [](const arrMember& x, const arrMember& y) { return x.var < y.var; });

无论采用哪种方法，代码都会运行得更快；Godbolt shows认为，这两种函数指针方法几乎相同，而使用函数式方法，您可以将运行时间相对于函数指针方法减少大约三分之一(在这种情况下，通过值传递节省了一点时间，但大多数时间几乎不值得考虑；我默认使用const引用传递，并且仅当分析表明它很慢，并且类型足够简单，通过值传递可能会有所帮助时，才考虑切换)。

模板和函数器的这个好处就是为什么C++的std::sort在使用得当时可靠地击败了C的qsort；C没有模板，所以它根本不能专门化qsort，必须总是通过函数指针调用比较器。如果将std::sort与函数一起使用，它对qsort并没有真正的改进，但与函数器/λ一起使用时，它会生成更快的代码，但代价是生成更多的代码(每个函数器/λ对std::sort的唯一专门化)。在C语言中，你可以通过复制粘贴实现qsort的代码，去掉比较器并自己内联比较，来获得同样的好处，但这是大量的维护开销；C++模板为你做了99%的工作，你只需要记住使用函数器/lambda进行回调，而不是原始函数。

Answer 2

在代码中，将比较器函数定义为

bool compare(arrMember(x), arrMember(y)) {
    return (x.var < y.var);
}

该函数有两个通过值传递的arrMember类型的参数。这意味着x和y是传递给函数的参数的副本。因此，当您对数组进行排序时，每次调用比较器( O(n * logn)次)时，都会创建、比较和销毁两个临时对象。您可以修改您的函数以通过引用获取参数：

bool compare(arrMember const& x, arrMember const& y) {
    return x.var < y.var;
}

这样，函数就不会使用引用原始值的副本.它是一个不能修改的常量引用。

现在的想法是，这会将临时对象保存为副本，从而节省运行时间。然而，最好的建议是测量而不是争论。我对您的代码进行了一些修改，以运行这两个版本。

#include <array>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <ctime>
#include <random>

using namespace std;

constexpr size_t N=1000000;

class arrMember {
public:
    int var;
    arrMember(int var) :
        var(var) {}
    arrMember() {};
};

bool compare_by_value(arrMember x, arrMember y) {
    return (x.var < y.var);
}

bool compare_by_reference(arrMember const& x, arrMember const& y) {
    return (x.var < y.var);
}


template<typename C>
void sort(array<arrMember, N>& a, C comp) {
    sort(a.begin(), a.end(), comp);
}

int main(){
    random_device rd{};
    mt19937 engine{ rd() };
    uniform_int_distribution<int> dist{ 0, 9999 };

    array<arrMember, N> a;
    std::generate(a.begin(), a.end(), [&]() {return arrMember{dist(engine)};});

    int tmp=0;
    cout << "Executing sort...\n";
    {
        array<arrMember, N> x = a;
        clock_t t1 = clock();
        sort(x, compare_by_value);
        clock_t t2 = clock();
        double timeDiff = ((double)(t2 - t1)) / CLOCKS_PER_SEC;
        cout << "Sort finished. CPU time was " << timeDiff << " seconds.\n";
        tmp += x.front().var;
    }

    {
        array<arrMember, N> x = a;
        clock_t t1 = clock();
        sort(x, compare_by_reference);
        clock_t t2 = clock();
        double timeDiff = ((double)(t2 - t1)) / CLOCKS_PER_SEC;
        cout << "Sort finished. CPU time was " << timeDiff << " seconds.\n";
        tmp += x.front().var;
    }



    return tmp;
}

Here是输出的一个示例：

启动

正在执行排序...排序完成。CPU时间为0.105382秒。排序完成。CPU时间为0.108179秒。

0

完成

这两个版本似乎没有区别，那么发生了什么呢？优化编译器将比较器内联到排序算法代码中。为此，排序路由中的调用将替换为函数体，并且由于函数不修改参数，因此不必创建副本来防止“传递”的值被修改。