文档章节

C++的高效从何而来

abing_hu
 abing_hu
发布于 2013/08/22 16:54
字数 1834
阅读 143
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

前一段时间,实验室的一哥们突然跑过来跟我说,“我自己写了个C的快速排序,排了一个10000000个int的数组,貌似比C库中是qsort算法要快,咋回事?C++的STL中快排(quick sort)算法的效率如何?”。

听他这么一说,我就立即做了个实验,写了如下代码:

<!-- lang: cpp -->
#include <iostream>
#include <algorithm>
#include <time.h>

using namespace std;

#define MAX_LEN 10000000

int arri[MAX_LEN];

int compare(const void* i, const void* j)
{
    return (*(int*)i - *(int*)j);
}

int main()
{
    for (int i = 0; i < MAX_LEN; i++) 
    {
        arri[i] = rand() % MAX_LEN;
    }

    ::clock_t start, finish;

    //STL sort
    start = ::clock();
    sort(arri, arri + MAX_LEN);
    finish = ::clock();

    cout << "STL sort:\t" << finish - start << "ms" << endl;

    for (int i = 0; i < MAX_LEN; i++) 
    {
        arri[i] = rand() % MAX_LEN;
    }

    //C qsort
    start = ::clock();
    qsort(arri, MAX_LEN, sizeof(arri[0]), compare);
    finish = ::clock();

    cout << "C qsort:\t\t" << finish - start << "ms" << endl;

    return 0;
}

我机器上装的是CodeBlocks(10.05)+MinGW(4.7.2)的环境。

首先,在debug模式下,CodeBlocks显示出当前的编译器命令:

<!-- lang: shell -->
mingw32-g++.exe -Wall -fexceptions  -g  -std=c++0x  -c D:\Workspaces\CodeBlocks\TestSortQ\main.cpp -o obj\Debug\main.o
mingw32-g++.exe  -o bin\Debug\TestSortQ.exe obj\Debug\main.o

运行结果:

在此输入图片描述

运行结果让我大吃一惊,STL不可能这么慢啊!后来仔细一想,这是debug模式,没有加任何优化,加上优化看看什么结果:

<!-- lang: shell -->
mingw32-g++.exe -Wall -fexceptions  -O2  -std=c++0x    -c D:\Workspaces\CodeBlocks\TestSortQ\main.cpp -o obj\Release\main.o
mingw32-g++.exe  -o bin\Release\TestSortQ.exe obj\Release\main.o   -s

运行结果:

在此输入图片描述

果然,O2选项一加上,STL sort瞬间完成了逆袭,运行时间优化了75%,而C qsort优化前后变化不是很明显,大概减少了10%。

问题来了,为什么C++标准库的快排的优化效果如此明显,而C库的快排优化不是很明显呢?

答案是inline。

我们知道,STL是泛型编程的杰出成果,里面的容器、迭代器、算法几乎都是通过泛型实现的,使得STL的通用性很强。泛型编程的一个负面效果就是破坏了接口与实现的分离,即头文件中声明,源文件中实现,源文件单独编译成库,用户只需要拿到头文件和库就可以使用了,看不到具体实现,这就是所谓的ABI,也是C的传统做法。有人会问,为什么不能做到接口与实现的分离,因为泛型编程中的函数和类,在没有接受一个模版参数之前,是没办法实例化的,只有当用户给定了模版参数的时候,编译器才会去实例化一个具体的类或函数。

如,C++ STL中的快速排序算法定义:

<!-- lang: cpp -->
template< class RandomIt >
void sort( RandomIt first, RandomIt last );

只有RandomIt这个类型真正确定了,编译器才会去实例化这个方法。在上面的代码中,我这么写:

<!-- lang: cpp -->
sort(arri, arri + MAX_LEN);

编译器通过自动类型推导,知道了RandomIt其实是一个int*,于是产生这个函数:

<!-- lang: cpp -->
sort(int*, int*);

具体实现中的RandomIt已经都替换成相应的int*,一个完整的函数就产生了。

关键的问题出现了!编译器在实例化一个函数(类也一样)的时候,它必须知道具体的实现代码,才能够产生完整的函数。这也是为什么如果大家自己写模版的时候,.h文件和.cpp文件的关系变得十分奇怪的原因,一般做饭是在.h文件末尾,#include xx.cpp,其中xx.cpp中实现了.h文件中的函数声明,或者干脆直接在.h文件中写实现。否则,如果按照一般的.h和.cpp的关系,编译器会报错,说找不到函数的实现。写过模版的程序猿应该都知道这个。

事实上,C++标准委员会为了解决这个问题,曾经引入了export关键字,来试图解决这个问题,但很少有编译器实现了(估计是实现难度较大,且增加了复杂度,得不偿失),所以这个关键字后来基本上费了。

大家或许会问,你是不是走题了,刚开始不是讨论C++的效率问题吗?怎么说了半天泛型和模版的事情了?

答案是,真是由于泛型的这个“副作用”,使得编译器可以做更多的优化!

既然编译器知道具体的实现,那么inline是编译器可以在优化上大显身手的一个手段,sort函数中需要一个compare函数(在C++中还可以通过函数对象或者操作符重载实现)来知道如何比较两个元素的大小,sort函数每次比较的时候,都会调用这个函数。对于一个10000000个元素的数组,一共会调用多少次这个compare函数是可想而知的(具体数目可以算出来),而一次函数调用的开销比较大,如栈的分配等等,这就很大程度上限制了C库中的qsort的威力,因为qsort的实现是在编译在库中的,它所调用的函数就没法inline到qsort函数里面去。但是STL是可以做到的,所以它的优化效果非常明显。

另外一个STL sort效率高的原因,在于算法的实现,不仅仅是快速排序算法,估计这也是为什么名字叫sort而不叫qsort的原因吧。在SGI STL(GNU所使用的STL)的实现中,sort函数一共采用了三种排序算法,分别是quick sort,heap sort和insert sort。使用策略如下:

1、函数主体为quick sort,但是在递归调用的时候,加上了一个参数记录迭代层数,如果迭代次数超过一定数目,转而采用heap sort。原因是如果迭代次数过多,很可能意味着quick sort落入了最坏情况(O(n2)),而heap sort的最坏情况依然是O(nlogn)。

2、当数组划分到很小的一段时,采用insert sort。原因是对于小数据量采用quick sort有些不划算(quick sort适合处理大量数据),因为quick sort本身是递归的,递归就是一次函数调用,开销较大。而insert sort在较小数据量的情况下,表现很好。

具体算法可参考SGI STL和侯捷的《STL源码剖析》。

说了这么一大堆,其实想表达的一点就是,C++为了提高效率,可以说无所不用其极,无论是STL算法实现,还是编译器的优化(语言本身为了编译器能做优化也下了很多功夫),都体现了C++的三大设计思想(或者叫做约束,可参考孟岩《关于C++复杂性的零碎思考》)之一:最高性能。

回到那位哥们的问题,为什么他的快排效率比C库的要高?我不否认他的水平,但是我感觉最大的原因还是,自己写的函数,编译器可以将compare的功能内敛到函数里面去,所以效率比C库的qsort效率要高。

关于C++的高效,我还想继续写一些文章,这篇博客且当作一个开始吧。

本文转载自:http://www.cnblogs.com/codemood/archive/2012/11/25/2787691.html

abing_hu
粉丝 11
博文 29
码字总数 7098
作品 0
杭州
后端工程师
私信 提问
关于软件开发所需要学的内容

厚颜无耻请教诸位大大几个问题 本人在校生,比较了解c/c++,对于Java,Cisco(ccna),SQL,HTML,Javascript也有点接触 经常用vs2012;;;windows以外的系统都没接触过(苦逼的电脑性能不高,磁盘存储量...

劉ルーベン
2012/11/18
325
3
cxxJava -- 像Java一样开发C++

cxxJava -- 像Java一样开发C++ 当你同时有过java和c++两个语言的开发经历后,你会喜欢上java语言开发效率的高效但又深深的被c++语言运行效率的高效所吸引。 java类库的丰富性、通用性、易用性...

cxxjava
2016/12/12
186
0
Java程序员如何高效而优雅地入门C++

Java程序员如何高效而优雅地入门Cpp,由于工作需要,需要用C++写一些模块。关于C++ 的知识结构,虽说我有过快速学习很多新语言的经验,但对于C++ 我也算是老手,但也还需要心生敬畏,本文会从...

小欣妹妹
2018/04/23
110
1
C++ 并行任务编程库 - cpp-taskflow

cpp-taskflow 是一个开源的 C++ 并行任务编程库,cpp-tastflow 非常快,只包含头文件,可以帮你快速编写包含复杂任务依赖的并行程序。 与现有的并行任务编程库(如OpenMP Tasking和Intel TBB...

匿名
07/27
6.3K
6
C语言/C++程序员编程学习代码训练—精讲

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/03/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如何管stderr,而不是stdout?

我有一个要写入信息的程序stdout和stderr ,我需要grep通过什么是未来标准错误 ,而忽视标准输出 。 我当然可以分2步完成: command > /dev/null 2> temp.filegrep 'something' temp.file...

技术盛宴
25分钟前
5
0
centos7.5上通过docker安装并运行mysql5.7

1. docker pull mysql:5.7 2. docker run --name mysql5.7 -p 3306:3306 -e MYSQL_ROOT_PASSWORD=123456 -d mysql:5.7...

Ryub
29分钟前
6
0
什么是比赛条件?

在编写多线程应用程序时,遇到的最常见问题之一是竞争条件。 我对社区的问题是: 什么是比赛条件? 您如何检测到它们? 您如何处理它们? 最后,如何防止它们发生? #1楼 当设备或系统试图同...

javail
40分钟前
6
0
SpringMVC源码分析-DispatcherServlet-init方法分析

上一篇:SpringMVC源码分析-DispatcherServlet实例化干了些什么 先吐槽一下。。。写了两小时的博客突然被俺家小屁孩按了刷新,东西不见了,建议OSCHINA能够自动定时保存啊。让我先安静一下。...

特拉仔
48分钟前
7
0
python协程 生成器

协程,又称微线程,纤程。英文名Coroutine。 线程是系统级别的它们由操作系统调度,而协程则是程序级别的由程序根据需要自己调度。在一个线程中会有很多函数,我们把这些函数称为子程序,在子...

沙门行道
58分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部