注意
本文仅代表个人浅显观点. 尽量考虑很多可能的情况了, 但也可能还是有以偏概全的情况, 如果有错误, 欢迎指正.

之前主要学的C, 因为那个时候听说C比C++快. 现在我写代码几乎都是C风格的. (但不完全是, 虽然说没有用C++的太多特性, 但我的代码经过纯C编译时还是会出错, 因为有时变量没有在开头申明, 结构体在使用时也没有在前面加struct) 最近打acm了解了点C++和STL, 在看其他人代码的时候发现大多数人用的C++风格代码. 他们排序时用的是sort函数. 然后我就想测试一下qsort和std::sort哪个快. 翻文章和做逆向时学到了很多东西, 在此记录一下.

效率测试

直接放测试代码:

#include <stdlib.h>
#include <stdio.h>
#include <windows.h>

#include <vector>
#include <algorithm>

using namespace std;

int pause(int c){
    DWORD pid;
    HWND hWnd = GetConsoleWindow();
    GetWindowThreadProcessId(hWnd, &pid);
    if (pid == GetCurrentProcessId()){
        while (getchar() != '\n');
    }
    return c;
}

LONGLONG frequency = 0;

LONGLONG counter(){
    LARGE_INTEGER l;
    if (!QueryPerformanceCounter(&l)) return 0LL;
    return l.QuadPart;
}

int cmp(const void *p1, const void *p2){
    return *(int*)p1 - *(int*)p2;
}

int main(){
    LARGE_INTEGER l;
    if (QueryPerformanceFrequency(&l)){
        frequency = l.QuadPart;
        printf("Counter frequency: %lld\n", frequency);
    }
    srand(0x1234);
    int N = 0x400000;
    int *s = new int[N];
    for (int i = 0; i < N; i++) s[i] = rand();
    //for (int i = 0; i < N; i++) s[i] = i;
    //for (int i = 0; i < N; i++) s[i] = N - i;
    LONGLONG c;

    int *t = new int[N];
    memcpy(t, s, N * sizeof (int));
    c = counter();
    qsort(t, N, sizeof (int), &cmp);
    c = counter() - c;
    printf("qsort     %lld\n", c);
    delete t;

    vector<int> v;
    v.resize(N);
    memcpy(v.data(), s, N * sizeof (int));
    vector<int>::iterator _l = v.begin(), _r = v.end();
    c = counter();
    sort(_l, _r);
    c = counter() - c;
    printf("std::sort %lld\n", c);

    delete s;
    return pause(0);
}

简单解释一下吧. 代码用了Windows平台的一些特性. pause函数不用也行, 主要是在调试时你总不希望程序双击运行的时候窗口一闪而过吧. 这个函数会判断当前窗口是否是自身进程(在命令行下运行窗口就不是自身进程, 是宿主cmd的), 如果是就暂停. counter是一个高精度的计时器(硬件层计数器), 比GetTickCount精确. 两次计数的差值就是计数时代码的运行时间, 单位是tick每秒. tick保存在frequency变量里, 在我的电脑上它的值为10000000(所以说比较精确). 然后后面的就是测试程序了, 相信这个应该好看懂.

在我电脑上测试结果如下(N=0x400000):

数据	`qsort`用时	`std::sort`用时	不优化的`std::sort`用时
乱序	3,312,103	2,162,993	10,723,971
正序	1,698,487	636,871	6,639,209
逆序	1,755,068	499,027	5,116,859

编译参数:

1 2	gcc "%~1" -o "%~n1.exe" -O2 -g -lstdc++ %O2优化% gcc "%~1" -o "%~n1d.exe" -O0 -g -lstdc++ %无优化%

在acm比赛时, 一般开O2优化

由于qsort只是库中的一个函数, 所以开不开优化对时间影响不大; 而std::sort是模板库, 会参与编译过程, 于是把两种情况都列了出来. 上面的结果吓我一跳, 之前听说C++输入输出流如果处理好会比C的输入输出快, 没想到C++的std::sort处理好效率也会很高. 于是我打开IDA, 胡乱地分析一波.

简单分析

O2优化改变了什么

IDA打开后, 直接F5大法好, 得到下图:

其中代码少的那个是不优化的.
什么嘛, 明明不优化更简单一些, 怎么就慢了这么多?
这就是产生效率问题的华点, 解释下代码先.

左图中的counter函数被内联了, 简单来说就是把函数内部的代码直接”拿来”, 嵌到调用函数的地方, 这样可以减少堆栈的使用, 进而提升效率. 所以左图中第34行, 对应右图的45-46行. 下面出现的counter同理.
左图39-43行, 是初始化vector和从s搬移数组的代码, 对应右边54-57行. 也是发生了一定的内联.
47行调用了std::sort进行排序, 对应右边61-94行

右图看起来代码很多就是因为排序函数的内联展开, 但是, 这真的说明右边的代码多吗?
我们从左图的排序函数点进去, 图太多懒得截了, 总之里面调用了很多其他函数, 而且其他函数又调用了很多函数, 但这些有很多是重载运算符的函数, 它们实际上只是简单地返回一个值. 也就是说如果可以把它们内联, 代码量是可以大量减少的. 实际上, 开O2优化让代码的体积减少了50K. 虽然说调试符号占了大多数体积, 不输出调试符号只能减少大概10K. 但是如果你的代码用了更多STL的内容, 优化的效果就很显著了.
扯远了~~ 反正逆向后我找到的区别就这么些. 我修改了代码, 统计排序比较的次数, 结果在乱序的情况下, 二者的比较次数都是96906511次, 就是说优化并没有改变算法过程, 它只是内联了部分函数而已. 下面我们来看看不开优化的函数调用关系:

别看不优化也只调用这么几个函数, 其实是我把一些不重要的忽略了. 而且像这些末端函数内部也是有大量优化操作的, 这个图只是展示了main函数中我们看到的std::sort优化与否的区别. 不优化的时候, 我们从main函数上只看到了第一层, 即std::sort. 开O2优化时, 我们看到了第四层, 直接看到了图中的三个叶子结点, 它们对应61行, 66行和70-94行. 如果我们从优化后的std::__introsort_loop点进去, 会发现又是巨量的优化. 所以, 这个优化极大地减少了函数调用次数.

关于函数调用

为什么函数调用对效率的影响这么大呢?
函数调用的过程:

准备好所有参数, 将它们置入栈或者寄存器, 其中前者要比后者慢.
执行call指令(期间会将调用函数后的下一行代码的地址(EIP/RIP)入栈).
从寄存器中取得返回值.

测试使用的是x64的编译器, 前四个参数都是通过寄存器传递(32位的__thiscall有3个是栈传递), 然后返回地址通过栈传递. 如果我把函数内联了, 这些操作都不会有, 速度上就可以快一点. 如果一个函数被调用很多次, 对效率的影响就有些明显了.

可能有点绕, 下面是一个直观的例子(不开优化, 手动模拟内联操作):

#include <stdio.h>
#include <windows.h>

int pause(int c){
    DWORD pid;
    HWND hWnd = GetConsoleWindow();
    GetWindowThreadProcessId(hWnd, &pid);
    if (pid == GetCurrentProcessId()){
        while (getchar() != '\n');
    }
    return c;
}

LONGLONG frequency = 0;

LONGLONG counter(){
    LARGE_INTEGER l;
    if (!QueryPerformanceCounter(&l)) return 0LL;
    return l.QuadPart;
}

int one__(){return 1;}
int one_(){return one__();}
int one(){return one_();}

int main(){
    LARGE_INTEGER l;
    if (QueryPerformanceFrequency(&l)){
        frequency = l.QuadPart;
        printf("Counter frequency: %lld\n", frequency);
    }

    LONGLONG c, cc = 0;
    c = counter();
    for (int i = 0; i < 0x7FFFFFFF; i++){
        cc += 1;
    }
    c = counter() - c;
    printf("inline   %lld\n", c);

    cc = 0;
    c = counter();
    for (int i = 0; i < 0x7FFFFFFF; i++){
        cc += one();
    }
    c = counter() - c;
    printf("function %lld\n", c);

    return pause(0);
}

结果:

1
2
3

Counter frequency: 10000000
inline   39988174
function 81251130

可以看到, 如果原来调用嵌入函数需要8秒, 那内联以后就只需要4秒. 这是3层嵌套, 实际上刚才的std::sort内部的某些过程可能比这还多. 所以, 使用STL的话, 开优化还是很必要的.

结论

qsort内部使用快速排序, std::sort根据实际情况混合使用内省排序, 快速排序, 堆排序. 从原理上说后者是比前者快的, 但由于模板的存在, 后者的函数调用次数过多, 所以看起来后者更慢. 在编译器打开O2优化的情况下, 一些函数调用被内联了, 后者的优势显现出来. 所以, 如果打开优化, 只是让编译过程慢一点点, 等编译完成后速度会飞起. 在实际写代码时, 也不用纠结于一个函数要不要指定__inline(如果你的项目只有一个文件), 编译器会帮我们优化这个过程.

参考

内省排序_百度百科
 为什么g++能够优化到动态库里的STL-知乎
 为什么不要自己乱造轮子: std::sort方法的实现

C中的qsort真的比C++中的std::sort快吗?

效率测试

简单分析

O2优化改变了什么

关于函数调用

结论

参考