Re: C++ more efficient than C?
- From: Paul Hsieh <websnarf@xxxxxxxxx>
- Date: Wed, 9 Apr 2008 11:23:15 -0700 (PDT)
On Apr 5, 9:46 pm, "copx" <c...@xxxxxxxxx> wrote:
In "Learning Standard C++ as a New Language" Bjarne Stroustrup claims that
properly written C++ outperforms C code. I will just copy his first example
here, which is supposed to demonstrate how C++ abstractions do not only make
code easier to understand but also make it more efficient:
Do you consider Bjarne Stroustrup to be unbiased in his choosing of
how to code up the C solution? Not surprisingly he poisoned the C
solution, and is arguing a case for which *BOTH* solutions are
suboptimal by design.
If you want to do language comparisons, you should use "The Great
Computer Language Shootout". They accept solutions to each problem
from anyone who cares to submit them for each language, and they use
the fastest code for each language. The results clearly show C and C+
+ to be pretty much dead even. (Mostly because C++ compilers are
being used to compile C, and C++ the language itself has no additional
performance features whatsoever.)
===
The simplest specific example I can think of is a program to find the mean
and median of a sequence of double precision floating-point numbers read
from input.
The mean should be limited by input speed (it can be calculated
incrementally) and the median should be implemented using the "select"
algorithm, which offers no advantage for either side (its a fairly
complicated algorithm, though).
[...] A conventional C-style solution would be:
#include <stdlib.h>
#include <stdio.h>
int compare(const void *p, const void *q)
{
register double p0 = * (double *)p;
register double q0 = * (double *)q;
if (p0 > q0) return 1;
if (p0 < q0) return -1;
return 0;
}
void quit()
{
fprintf(stder, "memory exhausted\n");
exit(1);
}
int main(int argc, char *argv[])
{
int res = 1000;
char * file = argv[2];
double *buf = (double *) malloc(sizeof (double) *res);
if (buf==0) quit();
double median = 0;
double mean = 0;
int n = 0;
FILE *fin = fopen(file, "r");
double d;
while (fscanf(fin, "%lg", &d) == 1) {
if (n==res) {
res += res;
Integer overflow is not being tested for.
buf = (double *)realloc(buf, sizeof(double) *res);
if (buf==0) quit();
This is some pretty bad error handling.
}
buf[n++] = d;
mean = (n == 1) ? d : mean + (d - mean) / n;
}
qsort(buf, n, sizeof(double), compare);
C programmers who use qsort, are programmers who have absolutely no
interest in performance. The overhead of qsort immediately makes it
slower than a well implemented heapsort almost always (and certainly
in this case of floating point sorting). The algorithmic complexity
problems of quick sort makes it slower than even badly written
heapsorts some of the time.
But as I described above, using sort is not the right way to solve
this (Its O(N*ln(N)). Use the Select algorithm; its O(N).
if (n) {
int mid = n/2;
median = (n%2) ? buf[mid] : (buf[mid - 1] + buf[mid]) / 2;
}
printf("number of elements = %d, median = %g, mean = %g\n", n, median,
mean);
free(buf);
}
To compare, here is an idiomatic C++ solution:
#include<vector>
#include<fstream>
#include<algorithm>
using namespace std;
int main(int argc, char * argv[])
{
char *file = argv[2];
vector<double>buf;
double median = 0;
double mean = 0;
fstream fin(file, ios::in);
double d;
while (fin >> d) {
buf.push_back(d);
mean = (buf.size() == 1) ? d : mean + (d - mean) / buf.size();
}
sort(buf.begin(), buf.end());
if (buf.size()) {
int mid = buf.size() / 2;
median = (buf.size() %2) ? buf[mid] : (buf[mid - 1] + buf[mid]) / 2;
}
cout << "number of elements = " << buf.size()
<< " , median = " << median << ", mean = " << mean << '\n';}
The main thing Bjarne Stroustrup is trying to prove with all this is
that template code inlining is faster than eating indirect function
call overhead.
However, a completely macro-based heap sort can be implemented in C in
about 20 lines of code.
So its apples versus oranges, and specifically noting that the oranges
have been implemented in C++'s standard template library, while it has
not been in C's standard library.
======================
He goes on to claim that, using a sample set of 5,000,000 elements, the C++
code is more than 4 times faster than the C code. Further examples follow to
prove the superiority of C++ even in the realm of efficiency.
The larger he makes the sample set, the more of a fool he looks like.
If you have large N, and you do *NOT* use the select algorithm, then
you are very *demonstratively* doing a clearly very wrong thing.
So C coders who care about efficiency should switch to C++?
No. Coder who care about efficiency should first learn standard
algorithms, then understand how to recognize unnecessary performance
bottlenecks (which are always introduced when using qsort.)
Are their any counter-arguments against Stroustroups claim?
In this case, its not a question of counter-argument, its a question
of debunking. If this is *truly* an example cited by Bjarne
Stroustrup, he deserves to be tarred and feathered on at least 3
grounds: 1) ignoring the Great Computer Language Shootout, 2) being
unaware of standard algorithms, and 3) intentionally misrepresenting
the kind of performance you can get from good C code.
--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
.
- Follow-Ups:
- Re: C++ more efficient than C?
- From: bjarne
- Re: C++ more efficient than C?
- References:
- C++ more efficient than C?
- From: copx
- C++ more efficient than C?
- Prev by Date: Re: K&R2, exercise 5.4
- Next by Date: print output
- Previous by thread: Re: C++ more efficient than C?
- Next by thread: Re: C++ more efficient than C?
- Index(es):
Relevant Pages
|
Loading
