Sorting string vectors: plain C vs idiomatic C++11

Question

I am currently trying to learn C++11 and its fancy features. To be specific I am searching for high efficiency genericity. So I happily wrote a program in C++11 to sort lines of an input file to test my fresh skills. Because of inlining and nice features of C++ compilers I expected high performance on this small example. To get a hint at how fast was my program I hacked exactly the same program in C using the qsort function, since it is raw C no inlining is performed on this function and my comparison function is called with an indirection and needs to do two indirections to access char * pointers representing strings.

The facts

Yet, I was very surprised by the results, C seems 4 times faster than C++. On a 8Mb file, I get the following results:

$ 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 

Note that I tried to be as fair as possible, compilation options are the same and my C program (dumped later) behave the same way as the C++ one: no limit on the size of the input lines and no limit on the number of input lines.

I also noticed that while my C program calls malloc almost once for each input line, the C++ program has a ratio of 10 allocations per input line!

The code

Here are the two programs I used to make my comparison.

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

And my much more verbose C version.

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

Question

Could someone tell me where my C++ program must be changed (without becoming plain C) to be faster? I tried to stay very idiomatic, is it a good way to hack in C++ or should I tend to write C-like code when I want high performance? Why is the C++ program allocating that much on the heap, how can I reduce this?

Edits

By popular demand I display the results of the profiling of my C++ program. Here is the funny output of the profiler for my C++ program (first two lines):

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&) 

As I read it, it seems that allocation is not the only reason.

Answer 1

The cause is in c++ std io synchronization. The following code:

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

gives

 real   0m0.106s  user   0m0.104s  sys    0m0.004s 

The C-version gives this:

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

Edit: As RiaD correct mentioned sync_with_stdio of course is static function, so it enough to call the function once for all std io streams.

Answer 2

You're also using two different I/O libraries. This will completely screw up any timing information, as the C and C++ I/O libs are very different. IOstreams are plain not designed for speed.

In addition, I/O is completely untimable. If the source of I/O data simply happened to be coming in slower one time, one program would appear to be slower regardless of the sort time- for example, if the OS happened to have it in cache for one run but not for another.

You need to time purely the time taken to sort a pre-existing std::vector<std::string>, say.

Oh yeah, and your getl is full of memory leak.