mpu*_*mpu 22 c c++ sorting benchmarking c++11
我目前正在尝试学习C++ 11及其奇特的功能.具体而言,我正在寻找高效率的通用性.所以我很高兴在C++ 11中编写了一个程序来对输入文件的行进行排序以测试我的新技能.由于C++编译器的内联和良好功能,我期望在这个小例子上获得高性能.为了得到我的程序有多快的提示,我使用该qsort函数在C中攻击了完全相同的程序,因为它是原始C,没有对该函数执行内联,并且我的比较函数被调用间接并且需要做两个间接到访问char *表示字符串的指针.
然而,我对结果感到非常惊讶,C似乎比C++快4倍.在8Mb文件中,我得到以下结果:
$ g++ -O3 -std=c++11 -o sort sort.C
$ time ./sort < huge > /dev/null
real 0m0.415s
user 0m0.397s
sys 0m0.013s
$ cc -O3 -Wall -o sortc sort.c
$ time ./sortc < huge > /dev/null
real 0m0.104s
user 0m0.097s
sys 0m0.010s
$ wc -l huge
140190 huge
请注意,我试图尽可能公平,编译选项是相同的,我的C程序(稍后转储)的行为与C++程序相同:输入行的大小没有限制,输入数量没有限制线.
我还注意到,虽然我的C程序malloc几乎每个输入行调用一次,但C++程序的每个输入行的比例为10!
以下是我用来比较的两个程序.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <memory>
int main () {
typedef std::vector<std::string> svec;
svec a;
std::string s;
for (;;) {
getline(std::cin, s);
if (std::cin.eof()) {
if (s != "")
a.push_back(std::move(s));
break;
}
a.push_back(std::move(s));
}
std::sort(a.begin(), a.end());
for (std::string &s : a) {
std::cout << s << "\n";
}
}
而我的更详细的C版本.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define BUFSZ 100
size_t getl(char **line, size_t len) {
char buf[BUFSZ];
size_t i, n;
for (i=0; i<BUFSZ; i++) {
int c = getchar();
if (c == EOF || c == '\n') {
*line = malloc(len+i+1);
memcpy(&(*line)[len], buf, i);
(*line)[len+i] = 0;
return i;
}
buf[i] = c;
}
n = getl(line, len+i);
memcpy(&(*line)[len], buf, i);
return i+n;
}
#define ARRAYSZ 30
struct Array {
char **lv;
size_t li, lc;
};
void addline(struct Array *a, char *line) {
if (a->li == a->lc) {
a->lc *= 2;
a->lv = realloc(a->lv, a->lc * sizeof *a->lv);
}
a->lv[a->li++] = line;
}
int cmp(const void *a, const void *b) {
return strcmp(*(const char **)a, *(const char **)b);
}
int main(void) {
char *line;
struct Array a;
size_t i;
a.li = 0;
a.lc = ARRAYSZ;
a.lv = malloc(a.lc * sizeof *a.lv);
for (;;) {
getl(&line, 0);
if (feof(stdin)) {
if (line[0] != 0)
addline(&a, line);
else
free(line);
break;
}
addline(&a, line);
}
qsort(a.lv, a.li, sizeof *a.lv, cmp);
for (i=0; i<a.li; i++) {
printf("%s\n", a.lv[i]);
free(a.lv[i]);
}
free(a.lv);
return 0;
}
有人能告诉我哪些C++程序必须更改(不成为普通C)更快？我试图保持非常惯用,这是一个很好的方式来破解C++,还是我倾向于编写类似C的代码,当我想要高性能？为什么C++程序在堆上分配那么多,我该如何减少它？
根据大众的需求,我会显示我的C++程序的分析结果.这是我的C++程序的探查器的有趣输出(前两行):
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
40.03 0.02 0.02 1198484 0.00 0.00 __gnu_cxx::__normal_iterator<std::string*, std::vector<std::string, std::allocator<std::string> > >::operator--()
30.02 0.04 0.02 2206802 0.00 0.00 bool std::operator< <char, std::char_traits<char>, std::allocator<char> >(std::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::basic_string<char, std::char_traits<char>, std::allocator<char> > const&)
当我读到它时,似乎分配不是唯一的原因.
mir*_*irt 27
原因在于c ++ std io同步.以下代码:
int main () {
typedef std::vector<std::string> svec;
svec a;
std::string s;
// note
std::ios_base::sync_with_stdio(false);
for (;;) {
getline(std::cin, s);
if (std::cin.eof()) {
if (s != "")
a.push_back(std::move(s));
break;
}
a.push_back(std::move(s));
}
std::sort(a.begin(), a.end());
for (std::string &s : a) {
std::cout << s << "\n";
}
}
给
real 0m0.106s
user 0m0.104s
sys 0m0.004s
C版本给出了:
real 0m0.167s
user 0m0.164s
sys 0m0.000s
编辑:由于RiaD正确提到sync_with_stdio当然是静态函数,所以它足以为所有std io流调用一次函数.
Pup*_*ppy 11
您还使用了两个不同的I/O库.这将完全搞砸任何时序信息,因为C和C++ I/O库非常不同.IOstream并不是为速度而设计的.
此外,I/O完全不可估量.如果I/O数据源恰好一次变慢,那么无论排序时间如何,一个程序看起来都会变慢 - 例如,如果操作系统碰巧在一次运行的缓存中而不是另一个运行.
std::vector<std::string>比如说,你需要花时间对预先存在的时间进行排序.
哦,是的,你getl的内存泄漏.
我的猜测是你没有测量排序速度,而是测量内存重新分配.而不是一次做a.push_back一个元素,尝试像在C程序中一样预先分配向量内存
a.reserve(num_lines);
根据你的编译器是否使用重新分配与扩展因子1.5(VC++)或2(G ++),你必须29和17重新分配与140,190您的文件(即行log(total lines) / log(expansion factor)).
R. Martinho Fernandes的评论也很有说服力:利用两个项目中std::chrono::high_resolution_clock::now()的sort陈述来获得时间差异.这会将您与内存和IO差异隔离开来.
其他人已经注意到,您测量的大多数是I/O库的速度.但是,我认为值得注意的是,与此处所做的一些陈述相反,C++ iostream可以完全与使用C FILE *的I/O竞争.那么,你所测量的主要是"gcc的iostreams有多糟糕？",而不是"一般来说有多糟糕？"
例如,我首先将我在一个目录中的所有.txt文件连接在一起,以创建一个相当大的文本文件.然后我用VC++ 10编译你的C代码并用它来排序该文件(将输出写入另一个文件).那是在3.2秒内完成的.
我还写了一些我认为合理惯用的C++来完成同样的任务:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iterator>
class line {
std::string data;
public:
friend std::istream &operator>>(std::istream &is, line &l) {
return std::getline(is, l.data);
}
operator std::string() const { return data; }
};
int main() {
std::vector<std::string> vec(
(std::istream_iterator<line>(std::cin)),
std::istream_iterator<line>());
std::sort(vec.begin(), vec.end());
std::copy(vec.begin(), vec.end(),
std::ostream_iterator<std::string>(std::cout, "\n"));
return 0;
}
这与您的C++代码大致相同,但(我声称)比您的任何一个程序都简单.如果你真的在意,那么让它变得更短也很容易.它根本没有特别尝试进行优化.使用VC++ 10编译(具有与我在C代码中使用的相同的优化标志 - -O2b2 -GL),它运行2.8秒,比C代码快大约10%.
我希望如果你在Linux上运行它,你会发现它比你的C代码慢.添加这两个sync_with_stdio(false);调用可能会解决这个问题,就像他们使用C++代码一样.这些sync_with_stdio(false);调用在Linux上通常会产生很大的差异,但是我从来没有能够衡量在Windows上使用它们的任何改进(使用我尝试过的任何编译器 - 最近VC++和MinGW,以及更久以前的Intel,Comeau ,CygWin和Borland也是如此).