By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
439,971 Members | 1,451 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 439,971 IT Pros & Developers. It's quick & easy.

C++ more efficient than C?

P: n/a
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:
===
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. 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;
buf = (double *)realloc(buf, sizeof(double) *res);
if (buf==0) quit();
}
buf[n++] = d;
mean = (n == 1) ? d : mean + (d - mean) / n;
}

qsort(buf, n, sizeof(double), compare);

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';
}
======================

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.

So C coders who care about efficiency should switch to C++?

Are their any counter-arguments against Stroustroups claim?

Apr 6 '08 #1
Share this Question
Share on Google+
74 Replies


P: n/a
copx wrote:
>
So C coders who care about efficiency should switch to C++?
Are you trying to start a flame war?

In some instances (typically where inlined function templates can
replace functions with void* parameters) C++ will be faster. Because
the C++ standard library incorporates the C standard library, C++ code
should never have to be slower.

--
Ian Collins.
Apr 6 '08 #2

P: n/a

"copx" <co**@gazeta.plschrieb im Newsbeitrag
news:ft**********@inews.gazeta.pl...
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:
[snip]

I copied the examples by hand, and two typos sneaked in: in the C example it
should be "stderr" instead of "stder", and the C++ example lacks a final
closing bracket.
Apr 6 '08 #3

P: n/a

"Ian Collins" <ia******@hotmail.comschrieb im Newsbeitrag
news:65*************@mid.individual.net...
copx wrote:
>>
So C coders who care about efficiency should switch to C++?
Are you trying to start a flame war?
No, if that were my intention, I would have crossposted this to
comp.lang.c++ for maximum effect! ;)
In some instances (typically where inlined function templates can
replace functions with void* parameters) C++ will be faster. Because
the C++ standard library incorporates the C standard library, C++ code
should never have to be slower.
Of course, but the interesting claim here is that you should NOT use C style
code but modern C++ abstractions, because they are not only more readable
and expressive, but also more efficient. The second part (they actually
being more efficient) was news to me.
Well, the inlined function templates superiour to void * functions thing
certainly makes sense. Maybe I should finally "move on" after all.
However, I compiled both examples with the current version of GCC (on
Win32-x86), and there is at least one area where C won: code size. The size
difference between the resoluting executables was grotesque: C code =5KB,
C++ code =over 400KB! (both binaries optimized for size and stripped!)


Apr 6 '08 #4

P: n/a
copx said:
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:
===
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. A conventional C-style solution would be:
<snip>

The C-style solution did not compile. When I fixed it minimally, it
segfaulted. So I wrote my own.
>
To compare, here is an idiomatic C++ solution:
<snip>

Results on my system:
C:
number of elements = 5000000, median = -9.10326e+08, mean = -1.40759e+10

real 0m29.955s
user 0m25.840s
sys 0m3.500s

C++:
number of elements = 5000000 , median = -9.10326e+08, mean = -1.40759e+10

real 0m22.701s
user 0m12.260s
sys 0m3.970s
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.
<shrugMy very, very simplistic C code doesn't quite manage to keep up
with the C++ code, but it certainly isn't four times slower. The
difference between my code and the C++ code is likely to be caused by
better memory management on the part of gcc's STL writer.
follow to
prove the superiority of C++ even in the realm of efficiency.
<shrugYou picked a rather artificial example. There is more to efficiency
than being able to store and sort five million numbers.
So C coders who care about efficiency should switch to C++?
C coders who care about efficiency enough to consider switching languages
should first ensure that the language switch really does give sufficient
efficiency gains to justify the switch. They should also bear in mind the
costs in terms of simplicity, readability, maintainability, and
portability.
Are their any counter-arguments against Stroustroups claim?
My favourite example is a 450-line C++ program I was shown, about eight
years ago, which had taken four man-years to write and took about 10
minutes to process a fairly trivial amount of data. I rewrote it from spec
(because I saw no point in rewriting it from the code) in a single day, in
C. My version took considerably less than a second to process the same
amount of data. There is more to efficiency than mere language choice.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Apr 6 '08 #5

P: n/a
copx wrote:
"Ian Collins" <ia******@hotmail.comschrieb im Newsbeitrag
news:65*************@mid.individual.net...
>copx wrote:
>>So C coders who care about efficiency should switch to C++?
Are you trying to start a flame war?

No, if that were my intention, I would have crossposted this to
comp.lang.c++ for maximum effect! ;)
Ho No! Please don't we've had another Java troll stirring things up
over there!
>In some instances (typically where inlined function templates can
replace functions with void* parameters) C++ will be faster. Because
the C++ standard library incorporates the C standard library, C++ code
should never have to be slower.

Of course, but the interesting claim here is that you should NOT use C style
code but modern C++ abstractions, because they are not only more readable
and expressive, but also more efficient. The second part (they actually
being more efficient) was news to me.
The only place C++ will win the performance race is where the *language*
offers an advantage, which is why sorting is often cited as an example.
A lot of C++ code (including libraries) is written either in the C
subset of C++ or using constructs that can be implemented equally well in C.
Well, the inlined function templates superiour to void * functions thing
certainly makes sense. Maybe I should finally "move on" after all.
However, I compiled both examples with the current version of GCC (on
Win32-x86), and there is at least one area where C won: code size. The size
difference between the resoluting executables was grotesque: C code =5KB,
C++ code =over 400KB! (both binaries optimized for size and stripped!)
That'll be all those inlined templates! Seriously, there is nearly
always a performance/size trade-off. Not always this big though.

--
Ian Collins.
Apr 6 '08 #6

P: n/a
copx said:

<snip>
However, I compiled both examples with the current version of GCC (on
Win32-x86), and there is at least one area where C won: code size. The
size difference between the resoluting executables was grotesque: C code
=5KB, C++ code =over 400KB! (both binaries optimized for size and
stripped!)
I didn't find the difference to be quite so remarkable. I didn't bother
with size optimisation, and I got these results:

Your C version: 37519
My C version: 60818
Your C++ version: 101287

Stripping yielded these figures:

Your C version: 4752
My C version: 9984
Your C++ version: 12172

Whilst the C++ version is significantly larger, it's not that big a deal
really, is it?

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Apr 6 '08 #7

P: n/a
On Sun, 06 Apr 2008 13:30:22 +0500, arnuld wrote:

:: Is C++ powerful ?

yes, a lot.
....[SNIP]....
I give the same advice to "copx" (the OP)
Oh.. no. I unintentionally f*cked-up the thread from other NG. Negligence
is on my part.

I apologize for the mistake & inconvenience I have caused.

--
http://lispmachine.wordpress.com/

Please remove capital 'V's when you reply
to me via e-mail.

Apr 6 '08 #8

P: n/a
On Sun, 06 Apr 2008 13:34:13 +0500, arnuld wrote:
Oh.. no. I unintentionally f*cked-up the thread from other NG. Negligence
is on my part.

I apologize for the mistake & inconvenience I have caused.

That apology was for comp.lang.c++. My PAN settings were wrong. I just
corrected them.

-- http://lispmachine.wordpress.com/

Please remove capital 'V's when you reply to me via e-mail.

Apr 6 '08 #9

P: n/a

My own stance on C versus C++ can be summed up in one word: compilers.

The only reason I program in C rather than C++ is that reliable C
compilers are far more ubiquitous than reliable C++ compilers. I don't
think this will change any time soon either; I mean who's actually
gonna sit down and write a C++ compiler for the PIC16F684
microcontroller when the C compiler is perfectly sufficient?

Both languages get compiled to machine code, and one language is for
the most part a superset of the other, so in my own eyes it stands to
reason that C++ could be better in every way (except when it comes to
finding a decent compiler for your platform).
Apr 6 '08 #10

P: n/a
"copx" <co**@gazeta.plwrote in message
>
So C coders who care about efficiency should switch to C++?

Are their any counter-arguments against Stroustroups claim?
Templates are faster than void *s and function pointers for generalising
code. It is a real argument for C++.
The main problem is the C++ template syntax. It's just a stretch too
difficult for a programmer to use comfortably.
--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Apr 6 '08 #11

P: n/a
Malcolm McLean said:
>
"Richard Heathfield" <rj*@see.sig.invalidwrote in message
>I think there are many more factors than you're allowing for here, and
language choice (between C and C++, at least) is a relatively
insignificant factor. As for programmers of equal skill, how would you
measure that?
Get the same programmer to write code in C and C++.
Finding a programmer who is precisely as skilled in C as he or she is in
C++ - no more, no less - will not be easy.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Apr 6 '08 #12

P: n/a
Malcolm McLean wrote:
"copx" <co**@gazeta.plwrote in message
>>
So C coders who care about efficiency should switch to C++?

Are their any counter-arguments against Stroustroups claim?
Templates are faster than void *s and function pointers for generalising
code. It is a real argument for C++.
The main problem is the C++ template syntax. It's just a stretch too
difficult for a programmer to use comfortably.
I don't think it's the syntax, templates fall well short of function
pointer declarations in the obscurity scale. I think it's more a case
of the conceptual next level of indirection that throws novices.

--
Ian Collins.
Apr 6 '08 #13

P: n/a
On Apr 5, 9:46*pm, "copx" <c...@gazeta.plwrote:
To compare, here is an idiomatic C++ solution:
You can also write some silly #define macros whose job it is to write
a type-specialized sort function.

#define GEN_SORT_FUNCTION(TYPE, FUNC_NAME, LESS, EQUAL) ...

GEN_SORT_FUNCTION(int, sort_int, left < right, left == right)

The idea is that would generate a function sort_int which sorts an
array of integers, using ``left < right'' and ``left == right'' to
compare elements. (The definition of GEN_SORT_FUNCTION is a reader
exercise).

This has some concrete advantages over C++, because it doesn't suffer
from the std::less braindamage.

Our sorting function doesn't have to deduce that the elements are
equal by comparing them for inequality both ways.

We could easily develop a variant of GEN_SORT_FUNCTION in which a
single comparison expression is specified---one whose job it is to
produce a negative integer, 0, or a positive integer for the left <
right, left == right and left right cases.

This has the advantage that if you are comparing strings, you only
have to make a single scan through them, from which you have all the
information you need.

(Look up the definition of strmp, and how it fits into qsort).

There is a reason that Stroustrup chose doubles, because if the data
consisted of strings---particularly long ones with lengthy common
prefixes---it's possible that the idiomatic C++ would actually lose to
the idiomatic C due to the impedance mismatch between std::less and
complex comparisons.

The cost of going through a function pointer to get to a comparison
function only matters if that comparison function does next to
nothing.

If the comparison function is nontrivial, you can bungle performance
by having to do that comparison two or more times over again.

If the comparison function is nontrivial, you can also bungle
performance by inappropriately inlining it, so that the combination of
sort function and inlined comparison code exceeds the available
instruction cache.
So C coders who care about efficiency should switch to C++?
Or maybe only those coders who can't figure out how to sort an array
of doubles without using function indirection, yet are comfortable
with templates. :)
Apr 7 '08 #14

P: n/a
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
static const double CLOCK_INV = 1.0 / CLOCKS_PER_SEC;
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(stderr, "memory exhausted\n");
exit(1);
}

int main(int argc, char *argv[])
{
int res = 100000;
char *file = argv[1];
double median = 0;
double mean = 0;
int n = 0;
double d;
clock_t start, end;
double *buf = (double *) malloc(sizeof(double) * res);
FILE *fin = fopen(file, "r");
if (buf == 0)
quit();
start = clock();
while (fscanf(fin, "%lg", &d) == 1) {
if (n == res) {
res += res;
buf = (double *) realloc(buf, sizeof(double) * res);
if (buf == 0)
quit();
}
buf[n++] = d;
mean = (n == 1) ? d : mean + (d - mean) / n;
}

qsort(buf, n, sizeof(double), compare);

if (n) {
int mid = n / 2;
median = (n % 2) ? buf[mid] : (buf[mid - 1] + buf[mid]) / 2;
}
end = clock();
printf("number of elements = %d, median = %g, mean = %g in %f
seconds\n", n, median, mean, (end - start)*CLOCK_INV);
free(buf);
return 0;
}
#include <vector>
#include <fstream>
#include <iostream>
#include <ctime>
#include <algorithm>

using namespace std;

static const double CLOCK_INV = 1.0 / CLOCKS_PER_SEC;

int main(int argc, char *argv[])
{
char *file = argv[1];
vector < double >buf;
clock_t start, end;
double median = 0;
double mean = 0;

fstream fin(file, ios::in);
double d;

start = clock();

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;
}
end = clock();
cout << "number of elements = " << buf.size()
<< " , median = " << median << ", mean = " << mean << " in " <<
(end - start)*CLOCK_INV << " seconds." << endl ;
}
/*
C:\tmp>cl /EHsc /W4 /Ox testcpp.cpp
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.762 for
80x86
Copyright (C) Microsoft Corporation. All rights reserved.

testcpp.cpp
testcpp.cpp(12) : warning C4100: 'argc' : unreferenced formal parameter
Microsoft (R) Incremental Linker Version 8.00.50727.762
Copyright (C) Microsoft Corporation. All rights reserved.

/out:testcpp.exe
testcpp.obj

C:\tmp>testcpp n.txt
number of elements = 5000000 , median = 1.00008, mean = 5.42094 in 10.344
seconds.

C:\tmp>testcpp n.txt
number of elements = 5000000 , median = 1.00008, mean = 5.42094 in 10.328
seconds.

C:\tmp>testcpp n.txt
number of elements = 5000000 , median = 1.00008, mean = 5.42094 in 10.344
seconds.

C:\tmp>cl /W4 /Ox testc.c
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.762 for
80x86
Copyright (C) Microsoft Corporation. All rights reserved.

testc.c
testc.c(32) : warning C4996: 'fopen': This function or variable may be
unsafe. Consider using fopen_s instead. To disable deprecation, use
_CRT_SECURE_NO_WARNINGS. See online help for d
etails.
C:\Program Files\Microsoft Visual Studio 8\VC\INCLUDE\stdio.h(234) :
see declaration of 'fopen'
testc.c(36) : warning C4996: 'fscanf': This function or variable may be
unsafe. Consider using fscanf_s instead. To disable deprecation, use
_CRT_SECURE_NO_WARNINGS. See online help for
details.
C:\Program Files\Microsoft Visual Studio 8\VC\INCLUDE\stdio.h(249) :
see declaration of 'fscanf'
testc.c(22) : warning C4100: 'argc' : unreferenced formal parameter
Microsoft (R) Incremental Linker Version 8.00.50727.762
Copyright (C) Microsoft Corporation. All rights reserved.

/out:testc.exe
testc.obj

C:\tmp>testc n.txt
number of elements = 5000000, median = 1.00008, mean = 5.42094 in 9.469000
seconds

C:\tmp>testc n.txt
number of elements = 5000000, median = 1.00008, mean = 5.42094 in 9.406000
seconds

C:\tmp>testc n.txt
number of elements = 5000000, median = 1.00008, mean = 5.42094 in 9.484000
seconds

C:\tmp>
*/
** Posted from http://www.teranews.com **
Apr 8 '08 #15

P: n/a
On Apr 8, 12:20*pm, Kelsey Bjarnason <kbjarna...@gmail.comwrote:
I happen to like both C and C++, but there _are_ cases where C++ makes
things a little less clear than they could be. *As a trivial example:

* int x = 3, y;

* y = func(x);

Quick: what's the value of x?
Maybe with a name better than "func" it would be less ambiguous.
In C the answer's easy: the value is 3. *In C++, there is absolutely no
way to know, at the point of calling, what will happen to the variable.
And in C, there's absolutely no way to know who's fiddling around with
your struct members because you can't restrict access to them.
Apr 8 '08 #16

P: n/a
lb*******@yahoo.com said:

<snip>
And in C, there's absolutely no way to know who's fiddling around with
your struct members because you can't restrict access to them.
Wrong. Maybe *you* can't restrict access to them, but I can, and so can
quite a few others in comp.lang.c. The technique is not difficult.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Apr 8 '08 #17

P: n/a
<OT>
Richard <de***@gmail.comwrites:
[...]
Heres another C++ snippet:

int x=0,y=0;

x=1;
x=x+y;

y=x+2;

Quick what is y?
3
Answer no idea. Because you don't know what "+" does half the time .....
Ah, but this is the other half. C++ doesn't allow "+" to be
overloaded for type int.
</OT>

[...]

--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Apr 8 '08 #18

P: n/a
On Apr 8, 12:20*pm, Kelsey Bjarnason <kbjarna...@gmail.comwrote:
* int x = 3, y;

* y = func(x);

Quick: what's the value of x?

In C the answer's easy: the value is 3. *In C++, there is absolutely no
way to know, at the point of calling, what will happen to the variable.

This makes the same code, in C, somewhat easier to read, as the
indicators of whether the value will be modified or not are right there,
in your face - or not. *In C++, there's no indication whatsoever, meaning
you have to hunt for the called function, check its interface, realize
that yes, it modifies the value and add this to the growing list of
pointless things to remember which shouldn't need remembering.
ITYM "... realize that yes, it /could modify/ the value ....". Unless
you look at func's definition, one cannot know for sure (just from
checking its interface) if it actually modifies 'x' or not.

- Anand
Apr 8 '08 #19

P: n/a
On Tue, 08 Apr 2008 11:35:10 -0700, Anand Hariharan wrote:
On Apr 8, 12:20*pm, Kelsey Bjarnason <kbjarna...@gmail.comwrote:
>* int x = 3, y;

* y = func(x);

Quick: what's the value of x?

In C the answer's easy: the value is 3. *In C++, there is absolutely no
way to know, at the point of calling, what will happen to the variable.

This makes the same code, in C, somewhat easier to read, as the
indicators of whether the value will be modified or not are right
there, in your face - or not. *In C++, there's no indication
whatsoever, meaning you have to hunt for the called function, check its
interface, realize that yes, it modifies the value and add this to the
growing list of pointless things to remember which shouldn't need
remembering.

ITYM "... realize that yes, it /could modify/ the value ....". Unless
you look at func's definition, one cannot know for sure (just from
checking its interface) if it actually modifies 'x' or not.
Indeed. However, the more important point is that you can be reasonably
certain that it will *not* be modifying values unless there's a pointer
involved somewhere, which is generally *visible* at the point of the call.

eg:

void func1(void)
{
int x = 3;

func2(x);
}
Anyone seeing this sort of thing wouldn't _need_ to examine "func2" to
see if x is modified. It's not. Simple as that. Unless you're using C+
+, in which case you have no way to tell either way.

Apr 8 '08 #20

P: n/a
In article <87************@bsb.me.uk>,
Ben Bacarisse <be********@bsb.me.ukwrote:
>Many C compilers have the ability to arbitrarily inline functions that are
small enough to inline.
>Yes, but very few (none?) can do it for the comparison function used
in qsort. I am sure it can be done, but I don't know of it being
done, which suggests it is tricky to get right.
It could work if qsort() itself was inlined as well as the comparison
function, because then the comparison function would be known at compile
time.

This would use more space, but in principle a compiler could generate
"curried" versions of qsort() for each (known-at-compile-time) comparison
function, to avoid replication of the code where the the same comparison
function is used in multiple calls to qsort().

(Currying is "partially evaluating" a function after fixing some of
its arguments.)

-- Richard
--
:wq
Apr 8 '08 #21

P: n/a
"Dann Corbit" <dc*****@connx.comwrote in message
news:a1******************@news.teranews.com...
[snip]
/*
if n is odd, then we use (n+1)/2
If n is even, we use [(n/2)th term + (n/2+1)th term] / 2
*/
if (n) {
int mid = n / 2;
median = (n % 2) ? RandomSelect(buf, 0, n - 1, mid) :
(RandomSelect(buf, 0, n - 1, mid-1) + RandomSelect(buf, 0, n - 1, mid))/2;
}
[snip]
>
/*
It would be a lot faster for odd numbered data sets:
C:\tmp>ksel n.txt
number of elements = 5000000, median = 1.00008, mean = 5.42094 in 8.000000
seconds

C:\tmp>ksel n.txt
number of elements = 5000000, median = 1.00008, mean = 5.42094 in 7.375000
seconds

C:\tmp>ksel n.txt
number of elements = 5000000, median = 1.00008, mean = 5.42094 in 7.437000
seconds
*/
I guessed wrong, the extra cost for a second call to RandomSelect is
negligible:
C:\tmp>ksel n.txt
number of elements = 5000001, median = 1.00008, mean = 5.42094 in 7.328000
seconds

C:\tmp>ksel n.txt
number of elements = 5000001, median = 1.00008, mean = 5.42094 in 7.375000
seconds

C:\tmp>ksel n.txt
number of elements = 5000001, median = 1.00008, mean = 5.42094 in 7.375000
seconds

I did not profile, but I guess that we are now limited by file I/O.
** Posted from http://www.teranews.com **

** Posted from http://www.teranews.com **
Apr 8 '08 #22

P: n/a
"Dann Corbit" <dc*****@connx.comwrites:
"Keith Thompson" <ks***@mib.orgwrote in message
news:87************@kvetch.smov.org...
[...]
>Inlining qsort's comparison function should be straightforward *if*
the compiler is able to inline (a call to) the qsort() function
itself. That would require either the ability to inline across
separately compiled translation units, or an implementation that in
effect delays compilation until link time.

Also, I would have used this comparison function:

#include <float.h>
#include <math.h>

int double_compare(void *pd1, void *pd2)
{
double d1 = *(double *) pd1;
double d2 = *(double *) pd2;
if (d1 d2)
if ((d1 - d2) < fabs(d1 * DBL_EPSILON))
return 0;
else
return 1;
if (d1 < d2)
if ((d2 - d1) < fabs(d2 * DBL_EPSILON))
return 0;
else
return -1;
return 0;
}
[...]

Bad idea. Treating two floating-point values as "equal" if they're
sufficiently close might be useful in some contexts, but not in a
qsort comparison function.

Suppose your array contains three elements X, Y, Z whose values are
very close to each other. Your comparison function could cause qsort
to treat them as if X==Y and Y==Z, but X < Z. Hilarity ensues.

What's wrong with just using the predefined "<" and "=="?

--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Apr 8 '08 #23

P: n/a
Keith Thompson wrote:
... Treating two floating-point values as "equal" if they're
sufficiently close might be useful in some contexts, but
not in a qsort comparison function.

Suppose your array contains three elements X, Y, Z
whose values are very close to each other. Your
comparison function could cause qsort to treat them
as if X==Y and Y==Z, but X < Z. Hilarity ensues.

What's wrong with just using the predefined "<" and "=="?
Just "<" will do...

int dbl_cmp(const void *lv, const void *rv)
{
const double *ld = lv;
const double *rd = rv;
return !(*ld < *rd) - (*ld < *rd);
}

Care still needs to be taken though with infinities and nans.

--
Peter
Apr 9 '08 #24

P: n/a
"Keith Thompson" <ks***@mib.orgwrote in message
news:87************@kvetch.smov.org...
"Dann Corbit" <dc*****@connx.comwrites:
>"Keith Thompson" <ks***@mib.orgwrote in message
news:87************@kvetch.smov.org...
[...]
>>Inlining qsort's comparison function should be straightforward *if*
the compiler is able to inline (a call to) the qsort() function
itself. That would require either the ability to inline across
separately compiled translation units, or an implementation that in
effect delays compilation until link time.

Also, I would have used this comparison function:

#include <float.h>
#include <math.h>

int double_compare(void *pd1, void *pd2)
{
double d1 = *(double *) pd1;
double d2 = *(double *) pd2;
if (d1 d2)
if ((d1 - d2) < fabs(d1 * DBL_EPSILON))
return 0;
else
return 1;
if (d1 < d2)
if ((d2 - d1) < fabs(d2 * DBL_EPSILON))
return 0;
else
return -1;
return 0;
}
[...]

Bad idea. Treating two floating-point values as "equal" if they're
sufficiently close might be useful in some contexts, but not in a
qsort comparison function.

Suppose your array contains three elements X, Y, Z whose values are
very close to each other. Your comparison function could cause qsort
to treat them as if X==Y and Y==Z, but X < Z. Hilarity ensues.
No it won't. Try it.
What's wrong with just using the predefined "<" and "=="?
The principle of least surprise.
** Posted from http://www.teranews.com **
Apr 9 '08 #25

P: n/a
In article <3f******************@news.teranews.com>,
Dann Corbit <dc*****@connx.comwrote:
>>int double_compare(void *pd1, void *pd2)
{
double d1 = *(double *) pd1;
double d2 = *(double *) pd2;
if (d1 d2)
if ((d1 - d2) < fabs(d1 * DBL_EPSILON))
return 0;
else
return 1;
if (d1 < d2)
if ((d2 - d1) < fabs(d2 * DBL_EPSILON))
return 0;
else
return -1;
return 0;
}
>Suppose your array contains three elements X, Y, Z whose values are
very close to each other. Your comparison function could cause qsort
to treat them as if X==Y and Y==Z, but X < Z. Hilarity ensues.
>No it won't.
What won't what? Hilarity won't ensue?

Are you saying you can't have X "equal" to Y, Y equal to Z, but X less
than Z? Or are you saying this doesn't matter?

If the input is Z, Y, X, what stops qsort() leaving it unchanged, even though
X < Z?
>Try it.
I did. The program is below. The output is

comparisons: 0 0 -1
before: 1.25000000000000044409 1.25000000000000022204 1.25000000000000000000
after: 1.25000000000000044409 1.25000000000000022204 1.25000000000000000000

X compares equal to Y. Y compares equal to Z. X compares as less than Z.
When I sort them, Z wrongly comes before X.

#include <float.h>
#include <stdio.h>
#include <math.h>

int double_compare(void *pd1, void *pd2)
{
double d1 = *(double *) pd1;
double d2 = *(double *) pd2;
if (d1 d2)
if ((d1 - d2) < fabs(d1 * DBL_EPSILON))
return 0;
else
return 1;
if (d1 < d2)
if ((d2 - d1) < fabs(d2 * DBL_EPSILON))
return 0;
else
return -1;
return 0;
}

int main(void)
{
double x = 1.25, y = x+DBL_EPSILON, z = y+DBL_EPSILON;
double a[3];

printf("comparisons: %d %d %d\n",
double_compare(&x, &y),
double_compare(&y, &z),
double_compare(&x, &z));

a[0] = z; a[1] = y; a[2] = x;
printf("before: %.20f %.20f %.20f\n", a[0], a[1], a[2]);
qsort(a, 3, sizeof(a[0]), double_compare);
printf("after: %.20f %.20f %.20f\n", a[0], a[1], a[2]);

return 0;
}

-- Richard

--
:wq
Apr 9 '08 #26

P: n/a
"Richard Tobin" <ri*****@cogsci.ed.ac.ukwrote in message
news:ft**********@pc-news.cogsci.ed.ac.uk...
In article <3f******************@news.teranews.com>,
Dann Corbit <dc*****@connx.comwrote:
>>>int double_compare(void *pd1, void *pd2)
{
double d1 = *(double *) pd1;
double d2 = *(double *) pd2;
if (d1 d2)
if ((d1 - d2) < fabs(d1 * DBL_EPSILON))
return 0;
else
return 1;
if (d1 < d2)
if ((d2 - d1) < fabs(d2 * DBL_EPSILON))
return 0;
else
return -1;
return 0;
}
>>Suppose your array contains three elements X, Y, Z whose values are
very close to each other. Your comparison function could cause qsort
to treat them as if X==Y and Y==Z, but X < Z. Hilarity ensues.
>>No it won't.

What won't what? Hilarity won't ensue?

Are you saying you can't have X "equal" to Y, Y equal to Z, but X less
than Z? Or are you saying this doesn't matter?

If the input is Z, Y, X, what stops qsort() leaving it unchanged, even
though
X < Z?
>>Try it.

I did. The program is below. The output is

comparisons: 0 0 -1
before: 1.25000000000000044409 1.25000000000000022204
1.25000000000000000000
after: 1.25000000000000044409 1.25000000000000022204
1.25000000000000000000
Ah, but those are all the same number.
** Posted from http://www.teranews.com **
Apr 9 '08 #27

P: n/a
Dann Corbit wrote:
"Richard Tobin" <ri*****@cogsci.ed.ac.ukwrote
.... snip ...
>
>after: 1.25000000000000044409
1.25000000000000022204
1.25000000000000000000

Ah, but those are all the same number.
No they're not. They are exactly:

125000000000000044409 / 100000000000000000000
125000000000000022204 / 100000000000000000000
and 5 / 4

However, they may have arisen differently :-)

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
** Posted from http://www.teranews.com **
Apr 9 '08 #28

P: n/a
Richard Heathfield wrote:
lb*******@yahoo.com said:

<snip>
>And in C, there's absolutely no way to know who's fiddling around with
your struct members because you can't restrict access to them.

Wrong. Maybe *you* can't restrict access to them, but I can, and so can
quite a few others in comp.lang.c. The technique is not difficult.
I have always detested this kind of argument. "Maybe you can't, but we
who are better than you can", "it's quite easy", and then don't even
show this "easy" solution at all (which usually involves ugly hacks and
jumping through completely unnecessary hoops).

Reminds me of the C-hackers who insist that it's "easy" and "feasible"
to use dynamically bound "member functions" in structs, as if that
somehow made C as good as C++ (yet the big problem with that hack is
that each "member function" of the struct increases the size of the
struct, which in many cases is a completely useless waste and makes that
struct larger and more inefficient).
Apr 9 '08 #29

P: n/a

"Juha Nieminen" <no****@thanks.invalidwrote in message
news:47***********************@news.tdc.fi...
Richard Heathfield wrote:
>lb*******@yahoo.com said:

<snip>
>>And in C, there's absolutely no way to know who's fiddling around with
your struct members because you can't restrict access to them.

Wrong. Maybe *you* can't restrict access to them, but I can, and so can
quite a few others in comp.lang.c. The technique is not difficult.

I have always detested this kind of argument. "Maybe you can't, but we
who are better than you can", "it's quite easy", and then don't even
show this "easy" solution at all (which usually involves ugly hacks and
jumping through completely unnecessary hoops).

Reminds me of the C-hackers who insist that it's "easy" and "feasible"
to use dynamically bound "member functions" in structs, as if that
somehow made C as good as C++ (yet the big problem with that hack is
that each "member function" of the struct increases the size of the
struct, which in many cases is a completely useless waste and makes that
struct larger and more inefficient).
Is this on topic:

http://groups.google.com/group/comp....b16567e49c42fc

?

Apr 9 '08 #30

P: n/a
On 8 Apr, 18:37, Richard <de...@gmail.comwrote:

<snip>
Heres another C++ snippet:

* * int x=0,y=0;

* * x=1;
* * x=x+y;

* * y=x+2;

Quick what is y?

Answer no idea. Because you don't know what "+" does half the time .....

The clc crowd who fix bugs from a printout would not fare too well
methinks ....
we'd have the printout for operator+()

:-)
--
Nick Keighley

Apr 9 '08 #31

P: n/a
ge*****@gmail.com said:
On Apr 5, 11:28 pm, Richard Heathfield <r...@see.sig.invalidwrote:
<snip>
>>
Are their any counter-arguments against Stroustroups claim?

My favourite example is a 450-line C++ program I was shown, about eight
years ago, which had taken four man-years to write and took about 10
minutes to process a fairly trivial amount of data. I rewrote it from
spec (because I saw no point in rewriting it from the code) in a single
day, in C. My version took considerably less than a second to process
the same amount of data. There is more to efficiency than mere language
choice.
Four man-years to write a 450-line C++ code? Jesus, were they high or
something?
Eight blokes * six months. (I don't know whether they were high. But in the
end, they were fired.) There was no excuse for it. The task was a very,
very slightly forgiving file-comparison routine, used for comparing
QARun-recorded data without worrying too much about dates and stuff.
Really, the only reason I took a day over it was to be sure that I didn't
hand back a lemon. To take four man-years was unforgivable (and was not in
fact forgiven, once it came to light).

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Apr 9 '08 #32

P: n/a
Keith Thompson <ks***@mib.orgwrote:
>
Inlining qsort's comparison function should be straightforward *if*
the compiler is able to inline (a call to) the qsort() function
itself. That would require either the ability to inline across
separately compiled translation units, or an implementation that in
effect delays compilation until link time.
Or an inline definition of qsort() in <stdlib.h>. A conforming
implementation can't do that directly, but it can define the inline
function with a reserved name and then define a qsort() macro that
invokes the inline function.

-Larry Jones

It works on the same principle as electroshock therapy. -- Calvin
Apr 9 '08 #33

P: n/a
On Apr 9, 6:28*pm, Richard Heathfield <r...@see.sig.invalidwrote:
<shrugActually, it doesn't make a lot of odds. Anyway, I'm not trying to
prove that opaque types are speed demons. I'm merely demonstrating that
they are *possible*!
And thank you, by the way, from the one who derailed this thread in
the first place. Glad I learned something...been way too long since I
programmed in C. I should probably keep my kisser shut about it.
Apr 9 '08 #34

P: n/a
Richard Heathfield <rj*@see.sig.invalidwrites:
Juha Nieminen said:
>Richard Heathfield wrote:
>>typedef struct point_ point;

point *point_make(int, int);

There are two problems with that:

1) It forces the user to write unsafe code even if he didn't want to (in
other words, even if in his case it would be enough to use a local,
stack-allocated object of type 'point').

I disagree that this is unsafe. Please explain why you think so. Please
also explain where I can find a definition for "stack-allocated object" in
the C Standard.
You know full well what he meant. Don't pollute a decent thread with
your typical arsey pedantic nit picking.
Apr 9 '08 #35

P: n/a
"Juha Nieminen" <no****@thanks.invalidwrote in message
news:47**********************@news.tdc.fi...
Richard Heathfield wrote:
>>1) It forces the user to write unsafe code even if he didn't want to (in
other words, even if in his case it would be enough to use a local,
stack-allocated object of type 'point').

I disagree that this is unsafe.

You are seriously claiming that allocating objects dynamically with
malloc is no more error-prone than using local instances of objects?
>Please explain why you think so.

I don't have to explain. Just look at the amount of memory-leaking C
programs out there.
[...]

Well, IMO, that's not the languages fault... Perhaps you should rethink your
comment; something like:
'Just look at the amount of programmers creating memory-leaking programs out
there.'
Would that be okay? Or, am I totally misrepresenting your thoughts?

Apr 10 '08 #36

P: n/a
Richard Heathfield <rj*@see.sig.invalidwrites:
Juha Nieminen said:
>Richard Heathfield wrote:
>>>1) It forces the user to write unsafe code even if he didn't want to
(in other words, even if in his case it would be enough to use a local,
stack-allocated object of type 'point').

I disagree that this is unsafe.

You are seriously claiming that allocating objects dynamically with
malloc is no more error-prone than using local instances of objects?

I am seriously claiming that allocating objects dynamically with malloc and
managing them properly is a skill that is not difficult to master.
Yet there are millions of systems out there leaking memory.

Hmmm.

Apr 10 '08 #37

P: n/a
Richard Heathfield wrote:
I am seriously claiming that allocating objects dynamically with malloc and
managing them properly is a skill that is not difficult to master.
It might not be excessively *difficult*. However, it's excessively
tedious and laborious, which is why so many people skip doing it.
> Also, given that with your scheme just *accessing* the objects is
slower, that's a minus too.

When it becomes a bottleneck, I'll weep. Until then, why worry?
I prefer having the modularity *and* the efficiency. I don't have to
choose between the two. And all this without having to resort to ugly hacks.
I'm not
saying performance isn't important - far from it - but correctness is
considerably *more* important, and opaque types can provide a substantial
amount of protection against accidental data misuse.
Which is exactly why I like having the best of both worlds:
Correctness *and* efficiency, not *or*.
Apr 10 '08 #38

P: n/a
Juha Nieminen said:
Richard Heathfield wrote:
>I am seriously claiming that allocating objects dynamically with malloc
and managing them properly is a skill that is not difficult to master.

It might not be excessively *difficult*. However, it's excessively
tedious and laborious, which is why so many people skip doing it.
I don't find it so.
>
>> Also, given that with your scheme just *accessing* the objects is
slower, that's a minus too.

When it becomes a bottleneck, I'll weep. Until then, why worry?

I prefer having the modularity *and* the efficiency.
So do I. But I don't sweat buckets over a microsecond here and a
microsecond there. I have found that the choice of good algorithms
normally makes code quick enough no matter how much data you chuck at it.
I say "normally" because it's easy to come up with exceptions! For
example, my bignum lib was recently criticised for being a little slow to
calculate 5 to the (4 to the (3 to the 2)) - but how often do I need to do
/that/?
I don't have to
choose between the two. And all this without having to resort to ugly
hacks.
Beauty is in the eye of the beholder. I see nothing terribly ugly or
hackish about opaque types.
>
>I'm not
saying performance isn't important - far from it - but correctness is
considerably *more* important, and opaque types can provide a
substantial amount of protection against accidental data misuse.

Which is exactly why I like having the best of both worlds:
Correctness *and* efficiency, not *or*.
I'm quite content with the efficiency of my code, thank you. :-)

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Apr 10 '08 #39

P: n/a
"Richard" <de***@gmail.comwrote in message
news:ft**********@registered.motzarella.org...
Richard Heathfield <rj*@see.sig.invalidwrites:
>Juha Nieminen said:
>>Richard Heathfield wrote:
1) It forces the user to write unsafe code even if he didn't want to
(in other words, even if in his case it would be enough to use a
local,
stack-allocated object of type 'point').

I disagree that this is unsafe.

You are seriously claiming that allocating objects dynamically with
malloc is no more error-prone than using local instances of objects?

I am seriously claiming that allocating objects dynamically with malloc
and
managing them properly is a skill that is not difficult to master.

Yet there are millions of systems out there leaking memory.
Only because the programmer screwed up. This is not C's fault at all.

Apr 10 '08 #40

P: n/a
"Juha Nieminen" <no****@thanks.invalidwrote in message
news:47***********************@news.tdc.fi...
Richard Heathfield wrote:
>I am seriously claiming that allocating objects dynamically with malloc
and
managing them properly is a skill that is not difficult to master.

It might not be excessively *difficult*. However, it's excessively
tedious and laborious, which is why so many people skip doing it.
[...]

It's not that bad. IMO, the fact that some programmers don't have the skills
and/or patience to program in C does not make it a bad language at all.

Apr 10 '08 #41

P: n/a
[snips]

On Wed, 09 Apr 2008 03:11:14 +0000, ozbear wrote:
There are a myriad of C functions
"myriad C functions".
(both that you/someone else wrote) as
well as ones in the stdio/stdlib/etc., that take pointers as parameters.
And calling any of them potentially risks having the data modified.
Sure, we know that. This does not excuse making the programmer's job
more difficult than it needs be by hiding still more cases where the
value may be modified.

Your counter-argument is, in effect, if it can't be perfect, who cares
how bad it is? To me, that's a bad argument. While perfection is not
attainable, this is not sufficient reason to not at least try to do
things well.

Apr 10 '08 #42

P: n/a
In article <39**********************************@u12g2000prd. googlegroups.com>,
christian.bau <ch***********@cbau.wanadoo.co.ukwrote:
>I must say I have never seen an x86 implementation of floating point
arithmetic where 80 bit floating point numbers gave inconsistent
results for comparisons
Was Dann's quoted text about x86s? It referred only to "Itanium".

-- Richard
--
:wq
Apr 10 '08 #43

P: n/a
Richard Heathfield <rj*@see.sig.invalidwrote in
news:Sf******************************@bt.com:
Make it possible to program in English, and you will find that
programmers can't write English. The fact that some people can't get a
simple thing right doesn't mean that it isn't simple. People are
people. If we want the average quality of computer programs to rise by
1000%, all we have to do is carefully to select 90% of the world's
programmers, and shoot them.
I agree with the sentiment, but that's a terrible waste of bullets. Sadly,
mgmt was sold a bill of goods and now these programmers are leaking
references and causing NullPointerExceptions, which ostensibly is much
"safer" than programming in C or C++.
Apr 10 '08 #44

P: n/a
pj*@informatimago.com (Pascal J. Bourguignon) wrote in
news:7c************@pbourguignon.anevia.com:
However, since it is known that the programmers make errors, and that
C allows these programmers errors to lead to catastrophical
consequences, there is still someone who is at fault for allowing (or
more often, to mandate) programmers to use C to develop software. I'm
pointing my finger at the managers who should forbid programmers to
use languages like C or C++ to develop any MIT software.
They have. Now they're leaking references and causing
NullPointerExceptions (and NullReferenceExceptions in C#). You can't
invent a language that will write good code for a bad programmer.
Apr 10 '08 #45

P: n/a
Kelsey Bjarnason <kb********@gmail.comwrote in news:r311d5-hbb.ln1
@spanky.localhost.net:
[snips]

On Wed, 09 Apr 2008 03:11:14 +0000, ozbear wrote:
>There are a myriad of C functions

"myriad C functions".
Myriad can be used as a noun or an adjective. And correcting grammar in
a technical discussion is bad form, especially when you're wrong.

http://dictionary.reference.com/browse/myriad

"Usage Note: Throughout most of its history in English myriad was used
as a noun, as in a myriad of men. In the 19th century it began to be
used in poetry as an adjective, as in myriad men. Both usages in English
are acceptable, as in Samuel Taylor Coleridge's "Myriad myriads of
lives.""

Apr 10 '08 #46

P: n/a
Lloyd Bonafide wrote:
You can't
invent a language that will write good code for a bad programmer.
But you can invent a language which doesn't leak memory.
Apr 10 '08 #47

P: n/a
Juha Nieminen wrote:
Lloyd Bonafide wrote:
>You can't
invent a language that will write good code for a bad programmer.

But you can invent a language which doesn't leak memory.
No, you can't

If you hold a reference to an unneeded object NO garbage
collector will collect it. You will have to find it.

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32
Apr 10 '08 #48

P: n/a
Lloyd Bonafide <no****@nicetry.orgwrites:
pj*@informatimago.com (Pascal J. Bourguignon) wrote in
news:7c************@pbourguignon.anevia.com:
>However, since it is known that the programmers make errors, and that
C allows these programmers errors to lead to catastrophical
consequences, there is still someone who is at fault for allowing (or
more often, to mandate) programmers to use C to develop software. I'm
pointing my finger at the managers who should forbid programmers to
use languages like C or C++ to develop any MIT software.

They have. Now they're leaking references and causing
NullPointerExceptions (and NullReferenceExceptions in C#). You can't
invent a language that will write good code for a bad programmer.
http://web.media.mit.edu/%7Ehugo/dem...der-simple.mov
(Metafor, Interactive Natural Language Programming)

--
__Pascal Bourguignon__
Apr 10 '08 #49

P: n/a
On Apr 10, 7:01*am, Juha Nieminen <nos...@thanks.invalidwrote:
Lloyd Bonafide wrote:
You can't
invent a language that will write good code for a bad programmer.

* But you can invent a language which doesn't leak memory.
Such as?
Apr 10 '08 #50

74 Replies

This discussion thread is closed

Replies have been disabled for this discussion.