0/1 Knapsack problem, what am I doing wrong

[Nate Eldredge]

An example please for those of us with limited imaginations.

For the side against casting malloc:

[markg@cpa-re-test ~]1002$ cat t.c
int main(void)
{
return malloc(9);
}
[markg@cpa-re-test ~]1003$ gcc t.c


This is on a server running a still commercially supported version of
Linux. The server in question is the one we use to do our official
software builds.

You complain about a compiler not providing warnings when you don't ask
it to provide warnings? Even an ancient gcc will warn about this if
told to.

neldredg@zeno:/tmp$ gcc -v
Reading specs from /usr/local/gnu/pkg/gcc/lib/gcc-lib/sparc-sun-solaris2.8/2.95.3/specs
gcc version 2.95.3 20010315 (release)
neldredg@zeno:/tmp$ gcc -Wall t.c
t.c: In function `main':
t.c:3: warning: implicit declaration of function `malloc'

 

[Flash Gordon]

On Thu, 23 Apr 2009 03:10:00 -0600 (MDT), Han from China

James Kuyper wrote:
snip

There's a second reason that's specific to C90. If you try to call
malloc() without having a declaration of that function in scope
snip

In other words, the cast turns off the diagnostic, and it's a
diagnostic you should really want to recieve.
Not using a cast can also turn off a diagnostic in certain situations.
Those situations aren't any more contrived.
An example please for those of us with limited imaginations.

For the side against casting malloc:

[markg@cpa-re-test ~]1002$ cat t.c
int main(void)
{
return malloc(9);
}
[markg@cpa-re-test ~]1003$ gcc t.c


This is on a server running a still commercially supported version of
Linux. The server in question is the one we use to do our official
software builds.

You complain about a compiler not providing warnings when you don't ask
it to provide warnings?

No, but I comment that by default the compilers on some current systems
do not warn about it. So a simple statement that you should cast,
without also saying you should make sure your implementation is set to
diagnose the problem, is bad advice in my opinion.

Personally I would advice not casting and enabling the warning.

Even an ancient gcc will warn about this if
told to.

<snip>

I know that when requested it will, and I have set up our makefiles so
that this and many other warnings are enabled. I also know that current
gcc versions produce warning by default.

 

[Kaz Kylheku]

An example please for those of us with limited imaginations.

For the side against casting malloc:

[markg@cpa-re-test ~]1002$ cat t.c
int main(void)
{
return malloc(9);
}

So is it to be understood that are offering a program which contains no casts
whatsover as a counterexample against casting?

If we add the cast, then we catch an error:

int main(void)
{
return (void *) malloc(9);
}

gcc will now diagnose this even if given no warning options:

test.c: In function `main':
test.c:3: warning: return makes integer from pointer without a cast

So, in summary:

- no cast: the broken program compiles without a hitch.

- cast added: a diagnostic is produced.

Looks like you lose.

It so happens that an installation of gcc I have here also silently accepts
this program, in which there is no cast:

int main(void)
{
char *str = malloc(9);
return 0;
}

If I add the cast, it also silently accepts the program. Oops!

Maybe using gcc installations to prove your case is not such a hot idea.

It depends on what version of gcc you are using. The one which accepts the
program with or without a cast is 3.4.3.

Version 4.3.2 prints this:

test.c: In function main:
test.c:4: warning: incompatible implicit declaration of built-in function malloc

That's with, or without the cast, doesn't matter.

Two wrongs don't make a right. The ability to call functions without declaring
them is an unfortunate hole in the C type system. The ability to convert from
void * without a cast is also an unfortunate hole in the type system.

Yes, so there are situations in which there is a tradeoff between risk between
two holes: cast the return of a function and you cover up the bad function
call. Don't cast the return value, and you subvert the type system via void *,
without a cast. Which poison to choose?

Let's see, I can deal with the first hole by using a decent compiler with good
diagnostics, so that I never call an undeclared function. So I don't have to
worry about the cast covering up a bad function call.

Few C compilers provide a diagnostic against the second hole (warning for
a void * being converted to a pointer to object type).

So it's illogical to assert that when there is an unfortunate conflict between
two type system holes, the programmer should cater to the hole which is easily
fixable with widely available technology, and ignore the one which isn't.

[markg@cpa-re-test ~]1003$ gcc t.c

This is on a server running a still commercially supported version of
Linux. The server in question is the one we use to do our official
software builds.

And these offical builds of yours take the form of ``gcc file.c -c'' with no
arguments to the compiler? And do do you use a half-decade old gcc that
came with your Linux server, for your official builds? Then you deserve
whatever you get.

 

[Ben Bacarisse]

Hmm... I suppose it depends on what counts as a good reason, but it
is sometimes needed in old C when the malloc call is an argument to
non-prototyped function (it depends on that type as actually
expected). The other situation that springs to mind is initialising a
union (in C90) whose first member is not a pointer compatible with
void *. To my mind these are good reasons but they fall outside the
scope of "in general" since they are rare situations.

[...]

I don't understand the union case. For example, this:

union {
int *p;
double d;
} *obj = { malloc(sizeof obj->p) };

I did not explain it well, and now I am forced to give an example it
is rather contrived...

is valid as far as I can tell. (I presume the "(in C90)"
qualification is because in C90 you'd use a designated initializer
rather than depending on the first-member rule.)

Yes, but that is the problem with my imagined example! This is what I
was thinking of. If the union sometimes holds, say, plain ints (that
happen to be the same width as pointers) and sometimes int pointers:

union U { int num; int *vec; };
...
union U obj = { (int)(int *)malloc(42 * sizeof *obj.vec) };

the casts let you, just about, get away with the initialisation.
Without the cast, the code would fail if the void * to int *
conversion actually did something (e.g. on a word-addressed
machine).

The trouble is, an automatic variable can have a function call in the
initialiser only in C99, and in C99 you would just write:

union U obj = { .vec = malloc(42 * sizeof *obj.vec) };

and avoid the issue of being forced to initialise the first member.

It is a non-example. The fact that some C90 compilers extended the
initialiser rules to allow such things does not really rescue it.

 

[Ben Bacarisse]

Ben Bacarisse said:

I don't remember that - but I will cheerfully believe it.

For reference:

The way I see it, all code should either do something good or stop
something bad happening. The malloc cast fails both tests

That sounds like double counting for the sake of it. Here is a
required cast:

printf("%p\n", (void *)some_struct_ptr);

It is (by your count) doubly good because it does something good
(converts the pointer to the required type) and also prevents
something bad from happening (the wrong output on some systems).

Almost every required piece of code I can think of counts twice and
everything redundant fails twice (anything that does no good cannot
but fail to prevent something bad).

 

[Ben Bacarisse]

A good reason to use a cast when converting from void * is that this is a
potentially unsafe conversion. It constitutes a hole in the type system, which
allows the programmer to take on the responsibility for correct typing,
such that there is no easy way to identify the places where this is happening
in the program: there is no diagnosis for those places, nor are they flagged
with an explicit syntax that can be searched for.

The ideal way to resolve the situation is to a) add the diagnostic to the
compiler, so that implicit unsafe conversions are flagged, and then b) to add
the explicit conversion operator to all of the places that are consequently
flagged, once they have been reviewed and regarded as safe. Then the diagnostic
will catch future situations where the conversion is introduced, but not
denoted by explicit syntax.

The second best thing, if you can't do a), is to just do b) anyway: add the
casts.

I think the difference between doing the essential part of b)
(ensuring that the conversions are safe) and your version b) (adding
the casts as well) is not significant. You then end up with markers
(the casts) of danger in places you have checked for safety. I'd just
ensure the conversions are safe which is often trivial and mark those
where it is not obvious with good comments that explain why it is OK
and state the conditions that must continue to prevail for things to
remain safe.

For example:

int cmp_record(const void *a, const void *b)
{
/* Always ensure that cmp_record is called only from
* sort_basic_recs or sort_full_recs. Both sort arrays
* of structs that start with a rec_common member.
*/
const struct rec_common *rca = a;
const struct rec_common *rcb = b;
}

is better than the version with just the casts. The version with the
comment /and/ the casts is not in any way harmful, but the casts add
nothing once the comment is doing the important stuff.

One day, the C standard may close the hole, like C++ did, making the cast
required. Programs that already have the cast are ``future proofed''
against this situation.

Life is too short to worry about second guessing a future standard.
Look at the state of C99 implementation after 10 years and that did
not break oodles of existing code. (The things code it broke will (a)
usually compile as C99 but with diagnostics and (b) was widely
considered broken before C99 made it official -- e.g. implicit int.)

The diagnostic may be available in existing some
compilers as an option; by using the cast you are writing code that will
not raise false positives when it's used in a project whose maintainers
decide to turn this on.


Considering only what is strictly needed isn't always good engineering.

Correctly written assert expressions aren't needed; we add them anyway.

A function prototype declaration isn't needed. The number and types of
arguments can be deduced from the call to the function, so the prototype
is redundant. Just get the call right, and all is well.

Superfluous parentheses are not needed; just memorize the precedence table.

In writing software, we take lots of steps and measures that aren't strictly
needed.

The ``not needed'' argument is weak.

Yes, that was my point. I was asking if there any other (possibly
stronger) reasons. A strong argument either way will overcome a
simple "it's not needed" argument.

For example, I find the arguments for assert calls very strong indeed,
but I have not heard anything so persuasive either for or against the
cast of a plain malloc. Hence my "it's enough for me", but I am open
to being persuaded.

 

[Flash Gordon]

On Thu, 23 Apr 2009 03:10:00 -0600 (MDT), Han from China

James Kuyper wrote:
snip

There's a second reason that's specific to C90. If you try to call
malloc() without having a declaration of that function in scope
snip

In other words, the cast turns off the diagnostic, and it's a diagnostic
you should really want to recieve.
Not using a cast can also turn off a diagnostic in certain situations.
Those situations aren't any more contrived.
An example please for those of us with limited imaginations.

For the side against casting malloc:

[markg@cpa-re-test ~]1002$ cat t.c
int main(void)
{
return malloc(9);
}

So is it to be understood that are offering a program which contains no casts
whatsover as a counterexample against casting?

It shows that gcc does not by default generate the warnings that several
people claim that you get from compilers.

If we add the cast, then we catch an error:

int main(void)
{
return (void *) malloc(9);
}

gcc will now diagnose this even if given no warning options:

test.c: In function `main':
test.c:3: warning: return makes integer from pointer without a cast

So, in summary:

- no cast: the broken program compiles without a hitch.

- cast added: a diagnostic is produced.

Looks like you lose.

It so happens that an installation of gcc I have here also silently accepts
this program, in which there is no cast:

int main(void)
{
char *str = malloc(9);
return 0;
}

You have a strange version of gcc if it accepts that as is without
warning. Every version I've used for the past 8 years has issues a
warning by default for that code.

If I add the cast, it also silently accepts the program. Oops!

Actually, since the program has an error that DOES cause it to fail on
current real systems with gcc (64 bit pointer and 32 bit int) that shows
nicely the cast hiding the problem!

Maybe using gcc installations to prove your case is not such a hot idea.

It depends on what version of gcc you are using. The one which accepts the
program with or without a cast is 3.4.3.

I don't happen to have that version to see that myself. However, it was
a bug in that version. Are you sure you did not include stdlib.h out of
habit?

Version 4.3.2 prints this:

test.c: In function main:
test.c:4: warning: incompatible implicit declaration of built-in function malloc

That's with, or without the cast, doesn't matter.

I know recent version do.

Two wrongs don't make a right. The ability to call functions without declaring
them is an unfortunate hole in the C type system.

Fortunately it is a hole fixed in C99, but a lot of people are not using
C99 compilers.

The ability to convert from
void * without a cast is also an unfortunate hole in the type system.

That's debatable.

Yes, so there are situations in which there is a tradeoff between risk between
two holes: cast the return of a function and you cover up the bad function
call. Don't cast the return value, and you subvert the type system via void *,
without a cast. Which poison to choose?

Putting in the cast does not avoid the problem.

char *fred = "blogs"
void *oops = (void*)fred;
int *wrong = (int*)oops;

Let's see, I can deal with the first hole by using a decent compiler with good
diagnostics, so that I never call an undeclared function. So I don't have to
worry about the cast covering up a bad function call.

If when people advised casting they also advised making sure that
compiler options to enable the warnings for implicit function
declarations I would be less concerned about it.

Few C compilers provide a diagnostic against the second hole (warning for
a void * being converted to a pointer to object type).

I don't know of any, so there is nothing to ensure that you really have
put in the casts for all of those conversions.

So it's illogical to assert that when there is an unfortunate conflict between
two type system holes, the programmer should cater to the hole which is easily
fixable with widely available technology, and ignore the one which isn't.

I've not come across any real instances of bugs which the cast would
have prevented. I have, on the other hand, come across instances where
the cast was preventing the compiler from diagnosing a problem. I prefer
to write code (and advise people to write code) to avoid bugs I actually
find in code rather than trying to avoid bugs that I don't see in real
code anyway.

Also I find it is quicker nd easier to take in code without the casts.

[markg@cpa-re-test ~]1003$ gcc t.c

This is on a server running a still commercially supported version of
Linux. The server in question is the one we use to do our official
software builds.

And these offical builds of yours take the form of ``gcc file.c -c'' with no
arguments to the compiler?

No, because I know better. However, before I rewrote the makefiles and
did a lot of tidying up of the code base the makefiles did not enable
warnings for implicit declarations of functions.

And do do you use a half-decade old gcc that
came with your Linux server, for your official builds? Then you deserve
whatever you get.

I use an old version for official builds because it is a nice easy way
to ensure that it will run on old (but still officially supported by
RedHat) versions of Linux. I have come across instances where if you
compile with a newer version of gcc a program would not run on a system
without that newer version installed (although this was not on Linux, I
think it was on SCO).

A lot of the time we use newer versions of gcc because they have better
warnings.

 

[Keith Thompson]

Yes, but that is the problem with my imagined example! This is what I
was thinking of. If the union sometimes holds, say, plain ints (that
happen to be the same width as pointers) and sometimes int pointers:

union U { int num; int *vec; };
...
union U obj = { (int)(int *)malloc(42 * sizeof *obj.vec) };

the casts let you, just about, get away with the initialisation.
Without the cast, the code would fail if the void * to int *
conversion actually did something (e.g. on a word-addressed
machine).

A type-pun is the lowest form of wit. }

The trouble is, an automatic variable can have a function call in the
initialiser only in C99, and in C99 you would just write:

union U obj = { .vec = malloc(42 * sizeof *obj.vec) };

and avoid the issue of being forced to initialise the first member.

It is a non-example. The fact that some C90 compilers extended the
initialiser rules to allow such things does not really rescue it.

And of course you could always just write:
union U obj;
obj.vec = malloc(42 * sizeof *obj.vec);
(along with whatever else is necessary to remember that vec, not num,
is the currently active member.)

 

[Ben Bacarisse]

Ben Bacarisse said:


Perhaps my meaning isn't as clear as I thought. It's late here, but
I'll try to summarise, and please forgive me if I'm still not
expressing myself terribly well.

I think we have the same "here" so the lateness may be affecting my
understanding as much as your expression.

All code should either move the
spec forward or deal with some issue that isn't really related to
the spec but which we know is, or may be, going to be a problem if
we don't deal with it. I thus distinguish between, say, a call to
isdigit (which positively contributes to the overall high-level
goal for some given program, and thus Does Something Good) and the
cast of its argument to unsigned char (if it can conceivably be
negative and is known not to be EOF), which is really only there
because in C bad things could happen if it isn't. We can easily
imagine a language just like C in all respects save that it doesn't
oblige us to use this cast. In such a language, we wouldn't bother
to put the cast in - so it's really a Stop Something Bad Happening
aspect of the code, rather than a positive Do Something Good
aspect.

I think this is a slightly artificial distinction, but let me try to
run with it. If I follow you, then, the oft-seen cast on a malloc
call "fails both tests" because it neither helps advance the purpose
of the code nor does it stop any bad things from happening?

Taking your example... In your estimation the (unsigned char) cast in
the call to isdigit() fails one test (by not doing something good) and
the call itself fails the other test (by not preventing anything bad).
Only a lucky few constructs will manage to achieve both, with almost
everything else one writes in C (except for redundant stuff of course)
failing one or other test of purpose.

By this reckoning, the only things that can be justly criticised are
those that do fail both. To my mind, accusing the malloc cast of
failing both is then hyperbole.

 

[Keith Thompson]

Taking your example... In your estimation the (unsigned char) cast in
the call to isdigit() fails one test (by not doing something good) and
the call itself fails the other test (by not preventing anything bad).
Only a lucky few constructs will manage to achieve both, with almost
everything else one writes in C (except for redundant stuff of course)
failing one or other test of purpose.

But the cast does "do something good": it enables isdigit() to
correctly determine whether the argument is a digit, even if the
argument happens to be a char with a negative value.

 

[Ben Bacarisse]

But the cast does "do something good": it enables isdigit() to
correctly determine whether the argument is a digit, even if the
argument happens to be a char with a negative value.

That is my view, but is it Richard's? I think only he can say for
sure. If it is then I think my previous critique stands.

I was trying to follow though the consequences of his (in my view
rather artificial) distinction between "doing good" and "preventing
harm". I may have got his meaning wrong, of course.

 

[Bubba]

James Kuyper's log on stardate 23 tra 2009

/snip

OK, but the only real reason I used cast is VS2008 returned error on
malloc call without cast:

error C2440: 'initializing' : cannot convert from 'void *' to 'int **'
....

gcc had no issues connected to this matter, not even with -Wall -pedantic
-std=c99 options.

Any ideas about that one?

 

[Bubba]

Ben Bacarisse's log on stardate 23 tra 2009

The two tests are redundant since EOF is negative but, yes, that kind
of thing. Now that everything is integer-based, one function could
be written to prompt for and read a number. You'd use it all over
the place.

I see. Thx.

Note that almost everyone agrees that not casting malloc is the right
thing to do in C.

Please see my reply to James:
Message-ID: <[email protected]>

 

[Keith Thompson]

James Kuyper's log on stardate 23 tra 2009

/snip

OK, but the only real reason I used cast is VS2008 returned error on
malloc call without cast:

error C2440: 'initializing' : cannot convert from 'void *' to 'int **'
...

gcc had no issues connected to this matter, not even with -Wall -pedantic
-std=c99 options.

Any ideas about that one?

You're probably invoking it as a C++ compiler.

 

[Ben Bacarisse]

Ben Bacarisse said:

[...]
Taking your example... In your estimation the (unsigned char)
cast in the call to isdigit() fails one test (by not doing
something good) and the call itself fails the other test (by not
preventing anything bad). Only a lucky few constructs will
manage to achieve both, with almost everything else one writes
in C (except for redundant stuff of course) failing one or other
test of purpose.

But the cast does "do something good": it enables isdigit() to
correctly determine whether the argument is a digit, even if the
argument happens to be a char with a negative value.

That is my view, but is it Richard's? I think only he can say for
sure. If it is then I think my previous critique stands.

I was trying to follow though the consequences of his (in my view
rather artificial) distinction between "doing good" and
"preventing
harm". I may have got his meaning wrong, of course.

Okay, I'm awake I'm awake I'm awake I'm awake I'm awake. Let me try
again.

Imagine the current state of the program as being a point on a
plane.

Imagine the desired state of the program (perfect completion) as
being some other point, way over there somewhere.

On this plane, the perfect route from A to B lies on the straight
line that joins them. Unfortunately, there may be obstacles on the
path that prevent the perfect route from being practical.

The only important thing is to reach the destination (i.e. to
achieve the desired program specification) in one piece (i.e. to
budget, to quality, on time, within the law, etc). If an obstacle
cannot be removed within these constraints, we must navigate around
it.

By "do something good or stop something bad happening" I mean that
it should either move us closer to the goal or, at least,
re-position us on the plane so that the obstacle that prevents us
moving closer can be avoided (and it is by no means necessary to
leave this till the last moment - early avoidance can be a great
strategy for route minimisation).

Unless I have misunderstood again, you have re-explained something I
understood the first time. Did you understand my point?

Now expand to N dimensions and add grouchy co-workers, a nagging
boss, and an impossible deadline. Add salt and sulphur to taste.

That would let you amplify the hyperbole. You could then claim that
the malloc cast fails all N tests rather than just two.

 

[Barry Schwarz]

---------------------------------------------------------------------------
#include <stdlib.h>

int main(void)
{
int *p;

/* ... */

p = (int *) malloc(sizeof *p);

/* ... */

return 0;

You claimed that not using a cast could suppress a diagnostic. I
asked for an example. This example uses a cast. I still don't see
how removing the cast would suppress a diagnostic. Please enlighten
me.

 

[lawrence.jones]

One day, the C standard may close the hole, like C++ did, making the cast
required.

Almost assuredly not, since that's not what happened. C++ never closed
the hole, because it was never there: Stroustrup invented void * for C++
with the same semantics it has today. When C adopted void * from C++,
the sole reason was to *put* the hole in the type system; otherwise, we
could have continued to just use char * as we traditionally did.

 

[Ben Bacarisse]

Ben Bacarisse said:



Apparently not, since I would have thought that the difference
between "make something good happen" (move closer to the goal) and
"stop something bad happening" (take evasive action around an
obstacle) would now be obvious. Since it doesn't seem to be, we
must be thinking about this in very different ways.

If your purpose was to ensure that your views are properly understood
I think you can consider this thread a success.

 

[Barry Schwarz]

Here's the part of my post that you snipped for some reason:

Imagine an idiot coworker -- possibly the same idiot coworker who
often forgets to include stdlib.h when using the company's C90
compiler -- coming along and changing the `int *p' to `long *p'.
With the malloc() cast, you get your diagnostic.

Without the cast, there is no diagnostic, since the
(void *) --> (long *) is fine. With the cast, (int *) --> (long *)
should give a diagnostic.

If I hadn't missed this in the original, I probably wouldn't have
needed to ask the question in the first place. I'd apologize for the
wasted bandwidth but the thread was hijacked a long time ago.

That's a clear example of how not using a cast can suppress a
diagnostic.

I willingly concede the point that coding an improper cast (or leaving
a previously "harmless" cast that has become improper in the code)
will generate a diagnostic that would not appear without the cast.

Like I said in my original request, I suffer from a limited
imagination. When you (or anyone) come up with these esoteric
situations, I can never tell if you have hit on something that might
affect my code. I'm glad this one doesn't but thanks for the info.

 

[Richard Bos]

A good reason to use a cast when converting from void * is that this is a
potentially unsafe conversion.

Bollocks, and precisely the kind of bollocks why C++ is misguided. It is
not the conversion one way which is unsafe, and it is not the conversion
the other way which is unsafe. What is unsafe is a _wrongly matched_
combination of conversions, and you cannot make that combination safe by
adding a cast to either single conversion, nor even by adding a cast to
both.

Richard