Сортировка векторов строк: plain C vs idiomatic С++ 11

В настоящее время я пытаюсь изучить С++ 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&)

Как я читал, кажется, что выделение не является единственной причиной.

Ответы

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

 real   0m0.167s
 user   0m0.164s
 sys    0m0.000s

a.reserve(num_lines);

#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;
}