В настоящее время я пытаюсь изучить С++ 11 и его причудливые функции. Чтобы быть конкретным, я ищу высокую эффективность. Поэтому я с радостью написал программу на С++ 11 для сортировки строк входного файла для проверки моих новых навыков. Из-за встроенных и приятных функций компиляторов С++ я ожидал высокой производительности на этом небольшом примере. Чтобы понять, насколько быстро была моя программа, я взломал точно такую же программу на C, используя функцию qsort
, так как она является исходной C. Для этой функции не выполняется инкрустация, и моя функция сравнения вызывается с косвенностью и должна выполняться две ссылки для доступа к указателям char *
, представляющим строки.
Факты
Тем не менее, я был очень удивлен результатами, C кажется в 4 раза быстрее, чем С++. В файле 8 Мб я получаю следующие результаты:
$ 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 вызывает malloc
почти один раз для каждой строки ввода, программа С++ имеет отношение 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-like, когда хочу высокой производительности? Почему программа С++ выделяет столько в куче, как я могу уменьшить это?
редактирует
По многочисленным просьбам я показываю результаты профилирования моей программы на С++. Вот забавный вывод профилировщика моей программы на С++ (первые две строки):
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&)
Как я читал, кажется, что выделение не является единственной причиной.