size_t or int for malloc-type functions?

[Chris Dollin]

Which operation do you mean by division ?

Integer division with remainder: "the usual" division, at
least in my head.

If you
mean for example the usual a/b where a,b are real
numbers then it's not an operation in the formal
sense of the word although informally it may be called
such.

Presumably it's not a formal operation because it's not
a total function.

 

[Chris Dollin]

Spiros Bousbouras wrote:

Integer division with remainder: "the usual" division, at
least in my head.

Grrr. /Without/ (discarding) remainder. (Otherwise the function is from
NxN -> NxN rather than -> N. Not that it matters if we're talking
totality, but staying in the spirit of algebra.)

(This is sufficiently offtopical to go to email, yes?)

 

[Charlie Gordon]

CBFalconer wrote: [...]

void *calloc(size_t n, size_t s) {
void *result;
size_t sz;

result = NULL;
if (SIZE_MAX / n < s) {

What if n == 0 ?

That should be

if (n == 0 || s == 0 || SIZE_MAX / n > s) {

or something like that.

The version I have just put in nmalloc.c (not yet published) is:

/* calloc included here to ensure that it handles the
same range of sizes (s * n) as does malloc. The
multiplication n*s can wrap, yielding a too small
value, so we must ensure calloc rejects this.
*/
void *ncalloc(size_t n, size_t s)
{
void *result;
size_t sz;

result = NULL;
if (!n || ((size_t)-1) / n > s) {
sz = n * s;
if ((result = nmalloc(sz))) memset(result, 0, sz);
}
return result;
} (* ncalloc *)

which makes the output of ncalloc be that of nmalloc(0) whenever
either n or s is 0. I think there is still a possible glitch when
((size_t)-1) / n) == s. The only thing that needs protection
agains n==0 is the division. s==0 will simply force sz==0.

As was pointed out later in this thread, >= is required to allow ncalloc(1,
SIZE_MAX). But IMHO it is more efficient to write this:

if (n <= 1 || SIZE_MAX / n >= s)

indeed, you should probably compare both arguments to 1 to avoid computing a
potentially costly division in the very common cases s==1 or n==1

if (n <= 1 || s <= 1 || SIZE_MAX / n >= s) ...

Whether it is more advisable to compute SIZE_MAX / n or SIZE_MAX / s is
debatable.

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.

Chqrlie.

 

[David R Tribble]

[...]
indeed, you should probably compare both arguments to 1 to avoid computing a
potentially costly division in the very common cases s==1 or n==1
if (n <= 1 || s <= 1 || SIZE_MAX / n >= s) ...
Whether it is more advisable to compute SIZE_MAX / n or SIZE_MAX / s is
debatable.

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.

Yes, that's what I've been trying to remember for the last two days!

Basically, the width of n*s must be less than SIZE_MAX, which is
true only if the combined width of the significant (non-zero) bits of
both is less than sqrt(SIZE_MAX). No need to use 'long long'
arithmetic (which might be relatively expensive).

There is also the problem (not mentioned so far) of allowing for
the extra space required in the allocated block for bookkeeping
(typically consisting of a size_t and maybe a pointer to the next
block in the allocation pool). In other words, I doubt that
malloc(SIZE_MAX)
will work on most systems.

-drt

 

[Wojtek Lerch]

[...]
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.

Basically, the width of n*s must be less than SIZE_MAX, which is
true only if the combined width of the significant (non-zero) bits of
both is less than sqrt(SIZE_MAX). No need to use 'long long'
arithmetic (which might be relatively expensive).

Yes, if by "combined" you mean added, and by sqrt(SIZE_MAX) you mean the
width of size_t. It's a simple consequence of the mathematical fact that
log(n*s) == log(n) + log(s).

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

 

[CBFalconer]

.... snip ...

There is also the problem (not mentioned so far) of allowing for
the extra space required in the allocated block for bookkeeping
(typically consisting of a size_t and maybe a pointer to the next
block in the allocation pool). In other words, I doubt that
malloc(SIZE_MAX)
will work on most systems.

No problem. If the system can't do it, it returns NULL.

--
Some informative links:
<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html>
<http://www.netmeister.org/news/learn2quote.html>
<http://cfaj.freeshell.org/google/> (taming google)
<http://members.fortunecity.com/nnqweb/> (newusers)

 

[David R Tribble]

Yes, if by "combined" you mean added, and by sqrt(SIZE_MAX) you mean the
width of size_t. It's a simple consequence of the mathematical fact that
log(n*s) == log(n) + log(s).

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

I think there may be a HAKMEM trick that sets all the bits below the
most significant 1 bit to zero, but I could not find it with a cursory
scan of
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
Something about or-ing an int with its two's-complement, or
something like that.

-drt

 

[Arthur J. O'Dwyer]

I think there may be a HAKMEM trick that sets all the bits below the
most significant 1 bit to zero, but I could not find it with a cursory
scan of
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
Something about or-ing an int with its two's-complement, or
something like that.

uintfoo_t x = (uintfoo_t)-1;
x ^= x>>1;

gets you the most significant bit of an unsigned type; that's easy.
But getting from "0x1000" to "16 bits" in constant time is tough
(in C; of course, some assembly languages give you that operation).
I think the answer to Wojtek's question is "No."

HTH,
-Arthur

 

[Ben Bacarisse]

uintfoo_t x = (uintfoo_t)-1;
x ^= x>>1;

gets you the most significant bit of an unsigned type; that's easy.
But getting from "0x1000" to "16 bits" in constant time is tough
(in C; of course, some assembly languages give you that operation).
I think the answer to Wojtek's question is "No."

Surely CHAR_BIT * sizeof unsigned int does it for unsigned integers?
There are problem with "non-value" bits (probably the wrong term) in
signed integer types, but the OP did not specify.

 

[Guest]

Surely CHAR_BIT * sizeof unsigned int does it for unsigned integers?
There are problem with "non-value" bits (probably the wrong term) in
signed integer types, but the OP did not specify.

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

 

[Ben Bacarisse]

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

Ah, yes. You are, of course, quite right. It is trap representations
that unsigned types don't have.

It is possible to tell if an unsigned type has padding in O(1) time,
but one can't tell how many there are.

 

[Wojtek Lerch]

Surely CHAR_BIT * sizeof unsigned int does it for unsigned integers?

I didn't mean the width of an integer type; when I said "width" (in quotes),
I was referring to what David Tribble described as the "width of the
significant (non-zero) bits" -- in other words, the minimum width (in the
normal sense) of a type capable of representing a given value. 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.

 

[Ben Bacarisse]

I didn't mean the width of an integer type; when I said "width" (in
quotes), I was referring to what David Tribble described as the "width
of the significant (non-zero) bits" -- in other words, the minimum
width (in the normal sense) of a type capable of representing a given
value. 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.

Sorry, I was not paying attention. I offer this in compensation,
although if you like bit-fiddling you will hate it:

For X != 0, ilogb((double)(unsigned int)X) + 1 does what you want, I
think. Those who know hardware can say how many thousand cycles
converting to double will cost. The ilogb is probably fast, though!

 

[CBFalconer]

I didn't mean the width of an integer type; when I said "width"
(in quotes), I was referring to what David Tribble described as
the "width of the significant (non-zero) bits" -- in other words,
the minimum width (in the normal sense) of a type capable of
representing a given value. 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.

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

"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

 

[Wojtek Lerch]

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?

 

[Keith Thompson]

Ah, yes. You are, of course, quite right. It is trap representations
that unsigned types don't have.

I'm fairly sure unsigned types (other than unsigned char) can have
trap representations.

 

[Ben Bacarisse]

I'm fairly sure unsigned types (other than unsigned char) can have
trap representations.

Sigh. Yes. I was mis-remembering the fact that trap representations
can't result from valid operations on valid unsigned values and it
came out as the erroneous statement above. I'll shut up now.

[BTW, your post presented un-surmountable obstacles to my news reader
(despite its similarity to yours) so I had to read in Google groups
and paste your message into this reply. I hope I have not
misrepresented anything in the process.]

 

[Keith Thompson]

[BTW, your post presented un-surmountable obstacles to my news reader
(despite its similarity to yours) so I had to read in Google groups
and paste your message into this reply. I hope I have not
misrepresented anything in the process.]

Yes, it showed up as a bunch of '?' characters in mine, but some
people apparently were able to read it anyway.

 

[Ian Collins]

[BTW, your post presented un-surmountable obstacles to my news reader
(despite its similarity to yours) so I had to read in Google groups
and paste your message into this reply. I hope I have not
misrepresented anything in the process.]

Yes, it showed up as a bunch of '?' characters in mine, but some
people apparently were able to read it anyway.

For some reason, you managed to post with charset=utf-16be!

 

[Richard Tobin]

Yes, it showed up as a bunch of '?' characters in mine, but some
people apparently were able to read it anyway.

[/QUOTE]

For some reason, you managed to post with charset=utf-16be!

The post was labelled that, but was in fact mostly in ascii, so
old-fashioned newsreaders that don't understand mime had no problem.

-- Richard