size_t or int for malloc-type functions?

[Gennaro Prota]

Wojtek Lerch wrote:

But is there an inexpensive way to compute the "width" of a
given integer in C?
[...] In other words, I was looking for a
formula that takes a positive integer value X and produces W such
that X >> (W-1) == 1.

I think rounding up log2 covers it.

Is it likely to be less expensive than an integer division?

For some reason I had assumed that you wanted to do the computation at
compile time, which I don't know how to achieve in C (it's fairly easy
in C++ instead). But if you are happy with a run-time calculation you
might want to adapt this one:


<http://boost.cvs.sourceforge.net/boost/boost/boost/pending/integer_log2.hpp?view=log>

Genny.

 

[Charlie Gordon]

Wojtek Lerch wrote:
Wojtek Lerch wrote:

But is there an inexpensive way to compute the "width" of a
given integer in C?

[...] In other words, I was looking for a
formula that takes a positive integer value X and produces W such
that X >> (W-1) == 1.

I think rounding up log2 covers it.

Is it likely to be less expensive than an integer division?

For some reason I had assumed that you wanted to do the computation at
compile time, which I don't know how to achieve in C (it's fairly easy
in C++ instead). But if you are happy with a run-time calculation you
might want to adapt this one:


<http://boost.cvs.sourceforge.net/boost/boost/boost/pending/integer_log2.hpp?view=log>

Yak ! my keyboard is all slimey now ! Please keep this stuff out of
comp.std.c

Chqrlie.

 

[Charlie Gordon]

[...]
Another idea to avoid the division is to compare (n | s) to a value
known to
be less than square root of SIZE_MAX, such as
(((size_t)1 << (CHAR_BIT * sizeof(size_t) / 2)) - 1) but that might not
be
100% portable.

I don't think so. It'll make calloc( 256, 1 ) fail on a system with
SIZE_MAX=65535.

No, the test is not final: if it passes, we know the multiplication will not
overflow, if it fails, we must do the division to check for overflow.
For your example, 65535 / 256 will be larger than 1, therefore no overflow,
try to allocate malloc(256 * 1).
Also note that in my sample code, n is tested against 1 first, as it is a
very common case and cannot overflow.

Chqrlie.

 

[Charlie Gordon]

Almost all signed and unsigned integer types may have padding bits.

That's in theory. In practice, none of them do ;-)

Chqrlie.

 

[Douglas A. Gwyn]

That's in theory. In practice, none of them do ;-)

There is at least one C implementation that has padding bits
in some of its integer representations.

 

[Wojtek Lerch]

Charlie Gordon wrote:
[...]
Another idea to avoid the division is to compare (n | s) to a value
known to
be less than square root of SIZE_MAX, such as
(((size_t)1 << (CHAR_BIT * sizeof(size_t) / 2)) - 1) but that might not
be
100% portable.

I don't think so. It'll make calloc( 256, 1 ) fail on a system with
SIZE_MAX=65535.

No, the test is not final: if it passes, we know the multiplication will
not overflow, if it fails, we must do the division to check for overflow.

Ah, so your idea is to *sometimes* avoid the division, not always. That
makes sense -- when the amount of memory you're allocating is sufficiently
big, the cost of the division is negligible compared to the cost of the
memset(). I imagine that on a lot of systems, it's negligible no matter
what.

 

[Clark S. Cox III]

That's in theory. In practice, none of them do ;-)

Except for the ones that do.

 

[Charlie Gordon]

There is at least one C implementation that has padding bits
in some of its integer representations.

Which one is that ? Death Star 9k of sorts or some similar useless junk ?

Chqrlie

 

[Charlie Gordon]

Except for the ones that do.

Interestingly, nobody is willing to shed light on these weird systems that
plague the standard with useless complex counterintuitive and universally
misunderstood garbage.

I pretend that architectures that require padding bits or trap
representations are a thing of the past that belong in computer museums.
Time has come the simplify and remove all that from future versions of the
standard. Who cares if new compilers cannot target obsolete hardware any
more in C201x mode ? Older versions will continue to support older
hardware, and new programs most likely cannot be made to fit on obsolete
hardware anyway.

Chqrlie.

 

[Chris Dollin]

Which one is that ? Death Star 9k of sorts or some similar useless junk ?

I seem to recall it's a Cray.

 

[Christopher Layne]

I pretend that architectures that require padding bits or trap
representations are a thing of the past that belong in computer museums.
Time has come the simplify and remove all that from future versions of the
standard. Who cares if new compilers cannot target obsolete hardware any
more in C201x mode ? Older versions will continue to support older
hardware, and new programs most likely cannot be made to fit on obsolete
hardware anyway.

Chqrlie.

Amen. Although honestly I think some of the regulars enjoy some of the stupid
limitations expressed above.

 

[CBFalconer]

.... snip ...

Interestingly, nobody is willing to shed light on these weird
systems that plague the standard with useless complex
counterintuitive and universally misunderstood garbage.

I pretend that architectures that require padding bits or trap
representations are a thing of the past that belong in computer
museums. Time has come the simplify and remove all that from
future versions of the standard. Who cares if new compilers
cannot target obsolete hardware any more in C201x mode ? Older
versions will continue to support older hardware, and new
programs most likely cannot be made to fit on obsolete hardware
anyway.

I would be very happy to have hardware with trap values, which
could automatically detect any use of uninitialized variables,
distinguish between malloced pointers and others, etc. However the
penny pinchers have pretty well driven such designs out of the mass
market, similarly the generic use of ECC.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[Douglas A. Gwyn]

I pretend that architectures that require padding bits or trap
representations are a thing of the past that belong in computer museums.
Time has come the simplify and remove all that from future versions of the
standard. Who cares if new compilers cannot target obsolete hardware any
more in C201x mode ? Older versions will continue to support older
hardware, and new programs most likely cannot be made to fit on obsolete
hardware anyway.

It's not just older hardware, it's also modern hardware under
various real-world constraints. DSP comes to mind. Padding
bits are sometimes needed in the middle of a wide integer type,
in order to skip over the sign bit in the middle of a multiword
representation. If the sign bit had to be used as part of the
binary numeration system representation of the value, it could
force much slower run-time arithmetic, completely contrary to
the design goals of that hardware.

It is simply not necessary to pretend that all architectures
follow some simple-minded model. It is very rare that a C
programmer needs to worry about the existence of padding bits,
and in C99 we gave you a standard way to specify unpadded,
twos-complement integer types if you really have to have them.
(But if the implementation doesn't provide them, either your
program won't be usable on that platform, or you'll have to
provide an alternate algorithm anyway.)

 

[Douglas A. Gwyn]

I would be very happy to have hardware with trap values, which
could automatically detect any use of uninitialized variables,
distinguish between malloced pointers and others, etc. However the
penny pinchers have pretty well driven such designs out of the mass
market, similarly the generic use of ECC.

Largely it's a matter of maximizing computational speed.
Almost any kind of checking does not come "free", from
that perspective. Generally, customers tend to be more
concerned over speed than in detecting poor program
quality as a side effect of execution.

 

[CBFalconer]

Largely it's a matter of maximizing computational speed. Almost
any kind of checking does not come "free", from that perspective.
Generally, customers tend to be more concerned over speed than in
detecting poor program quality as a side effect of execution.

ECC can cause a (very) slight degradation in performance, but not a
trap mechanism. ECC has to correct in line, but trapping can be
done on or during instruction completion, by separate paths, etc.
It's purely a passive monitoring of data paths.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[Charlie Gordon]

It's not just older hardware, it's also modern hardware under
various real-world constraints. DSP comes to mind. Padding
bits are sometimes needed in the middle of a wide integer type,
in order to skip over the sign bit in the middle of a multiword
representation. If the sign bit had to be used as part of the
binary numeration system representation of the value, it could
force much slower run-time arithmetic, completely contrary to
the design goals of that hardware.

Real world DSPs don't do that, and such lack of symmetry is actually more
expensive to implement in hardware and more painful to support in software .

It is simply not necessary to pretend that all architectures
follow some simple-minded model. It is very rare that a C
programmer needs to worry about the existence of padding bits,
and in C99 we gave you a standard way to specify unpadded,
twos-complement integer types if you really have to have them.
(But if the implementation doesn't provide them, either your
program won't be usable on that platform, or you'll have to
provide an alternate algorithm anyway.)

Why even bother to standardize such oddities ?
Simple concepts are not necessarily simple-minded.
Useless complexity breeds broken and bloated software.

Chqrlie.

 

[¬a\\b]

Real world DSPs don't do that, and such lack of symmetry is actually more
expensive to implement in hardware and more painful to support in software .

if some variable has the need of pad-bits and there is not the problem
on memory size, it is possible to use 2 variables "contigui" one for
store and one for pading bits

 

[¬a\\/b]

Real world DSPs don't do that, and such lack of symmetry is actually more
expensive to implement in hardware and more painful to support in software .

if some variable has the need of pad-bits and there is not the problem
on memory size, it is possible to use 2 variables "contigui" one for
store and one for pading bits

 

[Douglas A. Gwyn]

Why even bother to standardize such oddities ?

I already explained that. Some architectures need the latitude
in order to conform to the standard and yet generate fast code.

Simple concepts are not necessarily simple-minded.

They are when you insist that they be applied where they don't fit.

Useless complexity breeds broken and bloated software.

Platitudes are no substitute for thought. If a C implementor
doesn't need to embed padding bits in a datatype, he certainly
won't be doing so -- no different from your simple model.
On the other hand, if he needs to reserve some padding bits
to fit the particular architectural properties, there would be
complexity added (and execution speed lost) if he had to force
the representation to fit the simple model (since e.g. the sign bit
in a signed-magnitude representation is hard to use as part of
a binary numeration for the magnitude) and there is a very real
danger that the implementor would opt to not conform on that
point, which would very likely lead to further nonconformance,
and which would be doing the programmer no good if the
standard guarantee of no padding were being trusted in some
essential way. *That* would be broken software. Nothing
is broken by allowing for the possibility of padding bits (which
normally doesn't even have to be thought about), whether or
not padding bits actually occur.