Richard Damon wrote:
> My understanding is that, in effect, the call to realloc(p,0), if it is
> using the second option of returning a suitable pointer, is effectively
> do a free(p), and then allocating a "0 byte" block of memory and
> returning the address of that.

Or it just returns p, as it might do whenever the requested new size is smaller
than the already-allocated size. No reason for 0 to be a special case.

Robert Latest <boblatest@yahoo.com> writes:

> Richard Damon wrote:
>
>> My understanding is that, in effect, the call to realloc(p,0), if
>> it is using the second option of returning a suitable pointer, is
>> effectively do a free(p), and then allocating a "0 byte" block of
>> memory and returning the address of that.
>
> Or it just returns p, as it might do whenever the requested new size
> is smaller than the already-allocated size. No reason for 0 to be a
> special case.

There are reasons for realloc() to zize 0 to be a special case.
Specifically, because the pointer value returned doesn't have to
be dereferencable, it can point to parts of the address space
that are otherwise unusable. The overhead for such "zero-byte
blocks" is very low, just a smidge over one bit. The usuable
memory previously allocated can be reclaimed and used in its
entirely for subsequent allocations. If running in a 64-bit
address space, vast amounts of otherwise unusable areas can
be used for these "special objects", having very little impact
on memory usable for actual objects.

On 31/08/2023 06:33, Tim Rentsch wrote:
> There are reasons for realloc() to zize 0 to be a special case.
> Specifically, because the pointer value returned doesn't have to
> be dereferencable, it can point to parts of the address space
> that are otherwise unusable. The overhead for such "zero-byte
> blocks" is very low, just a smidge over one bit. The usuable
> memory previously allocated can be reclaimed and used in its
> entirely for subsequent allocations. If running in a 64-bit
> address space, vast amounts of otherwise unusable areas can
> be used for these "special objects", having very little impact
> on memory usable for actual objects.

Tim, I'm confused by a little bit of that:

"just a smidge over one bit"

I can see how you might point them all to a single place that can't be
read or written, and have safety in case anyone tries to use them.

I can see that you might have a section of memory with a series of
bytes, each one reserved for these empty allocations. It might be
inaccessible, but will still use address space.

But how do you get anything smaller than a byte, but non-zero? I've only
ever used one CPU with addressing smaller than a byte.

Andy

Vir Campestris <vir.campestris@invalid.invalid> writes:

> On 31/08/2023 06:33, Tim Rentsch wrote:
>
>> There are reasons for realloc() to zize 0 to be a special case.
>> Specifically, because the pointer value returned doesn't have to
>> be dereferencable, it can point to parts of the address space
>> that are otherwise unusable. The overhead for such "zero-byte
>> blocks" is very low, just a smidge over one bit. The usuable
>> memory previously allocated can be reclaimed and used in its
>> entirely for subsequent allocations. If running in a 64-bit
>> address space, vast amounts of otherwise unusable areas can
>> be used for these "special objects", having very little impact
>> on memory usable for actual objects.
>
> Tim, I'm confused by a little bit of that:
>
> "just a smidge over one bit"
>
> I can see how you might point them all to a single place that can't be
> read or written, and have safety in case anyone tries to use them.
>
> I can see that you might have a section of memory with a series of
> bytes, each one reserved for these empty allocations. It might be
> inaccessible, but will still use address space.
>
> But how do you get anything smaller than a byte, but non-zero? I've
> only ever used one CPU with addressing smaller than a byte.

I was tempted to make a joke here, but I couldn't see how to turn
out something funny.

What I meant was just over one bit /per zero-byte block/. So if
there were 20,000 zero-byte blocks, they could be managed with
just a little more than 2500 bytes of allocated memory. Sorry
for the confusion.

On 01/09/2023 08:14, Tim Rentsch wrote:
> Vir Campestris <vir.campestris@invalid.invalid> writes:
>
>> On 31/08/2023 06:33, Tim Rentsch wrote:
>>
>>> There are reasons for realloc() to zize 0 to be a special case.
>>> Specifically, because the pointer value returned doesn't have to
>>> be dereferencable, it can point to parts of the address space
>>> that are otherwise unusable. The overhead for such "zero-byte
>>> blocks" is very low, just a smidge over one bit. The usuable
>>> memory previously allocated can be reclaimed and used in its
>>> entirely for subsequent allocations. If running in a 64-bit
>>> address space, vast amounts of otherwise unusable areas can
>>> be used for these "special objects", having very little impact
>>> on memory usable for actual objects.
>>
>> Tim, I'm confused by a little bit of that:
>>
>> "just a smidge over one bit"
>>
>> I can see how you might point them all to a single place that can't be
>> read or written, and have safety in case anyone tries to use them.
>>
>> I can see that you might have a section of memory with a series of
>> bytes, each one reserved for these empty allocations. It might be
>> inaccessible, but will still use address space.
>>
>> But how do you get anything smaller than a byte, but non-zero? I've
>> only ever used one CPU with addressing smaller than a byte.
>
> I was tempted to make a joke here, but I couldn't see how to turn
> out something funny.
>
> What I meant was just over one bit /per zero-byte block/. So if
> there were 20,000 zero-byte blocks, they could be managed with
> just a little more than 2500 bytes of allocated memory. Sorry
> for the confusion.

I still don't follow you.

If I realloc to size 0 I get an address back. That can be a unique
address, in which case each one uses an address, and therefore a byte.

It can be a shared address, in which case the overhead per allocation is 0.

When I call free it would look at the shared address, and do nothing; if
it's a non-shared address it moves it to a free pool.

What does your bit do?

Andy

On 2023-09-01, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> What I meant was just over one bit /per zero-byte block/. So if
> there were 20,000 zero-byte blocks, they could be managed with
> just a little more than 2500 bytes of allocated memory. Sorry
> for the confusion.

The following is a much better requirement for malloc and realloc:

In the zero size case, return a non-null pointer to a single
program-wide object (always the same one), which can be passed
to the free function any number of times.

Since a zero sized object doesn't store any information, there
is no need to have more than one.

We satisfy these requirements:

- realloc(x, 0) is effectively free(x), except that it also
returns that object.

- the non-null object can be passed to library functions whose
behavior is not defined for null pointers, provided the
functions are not instructed to dereference it, or perform
pointer arithmetic.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

On 2023-09-01, Vir Campestris <vir.campestris@invalid.invalid> wrote:
> It can be a shared address, in which case the overhead per allocation is 0.
>
> When I call free it would look at the shared address, and do nothing; if
> it's a non-shared address it moves it to a free pool.
>
> What does your bit do?

The address returned has to be a unique byte, but it doesn't have to
point to valid virtual or physical memory. On, say, 64 bit systems,
there is a lot of pointer space to play with that will never be used
for storage.

But you have to track, "did we allocate that pointer or not",
which is a Boolean property. That can be packed into a bit array
somewhere, whose elements correspond to a consecutive range of
some pointers. Just like a free sector map in MS-DOS FAT or whatever.

It's a decent implementation of the (possible) protocol that we have in
the standard of allocating unique objects for zero-sized requests.

The protocol itself is a silly idea, though.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

On Fri, 01 Sep 2023 17:03:06 +0000, Kaz Kylheku wrote:

> On 2023-09-01, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>> What I meant was just over one bit /per zero-byte block/. So if there
>> were 20,000 zero-byte blocks, they could be managed with just a little
>> more than 2500 bytes of allocated memory. Sorry for the confusion.
>
> The following is a much better requirement for malloc and realloc:
>
> In the zero size case, return a non-null pointer to a single
> program-wide object (always the same one), which can be passed to the
> free function any number of times.
>
> Since a zero sized object doesn't store any information, there is no
> need to have more than one.
>
> We satisfy these requirements:
>
> - realloc(x, 0) is effectively free(x), except that it also
> returns that object.
>
> - the non-null object can be passed to library functions whose
> behavior is not defined for null pointers, provided the functions are
> not instructed to dereference it, or perform pointer arithmetic.

This last point implies that there must be some way for code to
distinguish this non-null object (that cannot be dereferenced)
from other non-null objects that /can/ be dereferenced.

Given that you specify that the non-null pointer returned from
realloc(x,0)
would be "a single program-wide object" and "always the same one",
would you consider providing a unique name (like we do for the
null pointer constant NULL) for such an object? If so, what name
would you suggest, and what would the definition look like?

Just curious,
--
Lew Pitcher
"In Skills We Trust"

Vir Campestris <vir.campestris@invalid.invalid> writes:

> On 01/09/2023 08:14, Tim Rentsch wrote:
>
>> Vir Campestris <vir.campestris@invalid.invalid> writes:
>>
>>> On 31/08/2023 06:33, Tim Rentsch wrote:
>>>
>>>> There are reasons for realloc() to zize 0 to be a special case.
>>>> Specifically, because the pointer value returned doesn't have to
>>>> be dereferencable, it can point to parts of the address space
>>>> that are otherwise unusable. The overhead for such "zero-byte
>>>> blocks" is very low, just a smidge over one bit. The usuable
>>>> memory previously allocated can be reclaimed and used in its
>>>> entirely for subsequent allocations. If running in a 64-bit
>>>> address space, vast amounts of otherwise unusable areas can
>>>> be used for these "special objects", having very little impact
>>>> on memory usable for actual objects.
>>>
>>> Tim, I'm confused by a little bit of that:
>>>
>>> "just a smidge over one bit"
>>>
>>> I can see how you might point them all to a single place that can't be
>>> read or written, and have safety in case anyone tries to use them.
>>>
>>> I can see that you might have a section of memory with a series of
>>> bytes, each one reserved for these empty allocations. It might be
>>> inaccessible, but will still use address space.
>>>
>>> But how do you get anything smaller than a byte, but non-zero? I've
>>> only ever used one CPU with addressing smaller than a byte.
>>
>> I was tempted to make a joke here, but I couldn't see how to turn
>> out something funny.
>>
>> What I meant was just over one bit /per zero-byte block/. So if
>> there were 20,000 zero-byte blocks, they could be managed with
>> just a little more than 2500 bytes of allocated memory. Sorry
>> for the confusion.
>
> I still don't follow you.
>
> If I realloc to size 0 I get an address back. That can be a unique
> address, in which case each one uses an address, and therefore a byte.
> [...]

In fact it must be a unique address, distinct from any other
address that has been allocated but not yet freed.

The key point is that, when the size is zero, the allocation
routine allocates /address space/ but does not allocate /memory/.
The address is not mapped to any memory, either physical or
virtual.

In a 64-bit address space, there are a lot more addresses than
there are bytes of memory, even virtual bytes of memory. All but
a very small fraction of 64-bit addresses cannot map to actual
memory, because there is no room on the address bus (figuratively
speaking).

For example, suppose our zero byte block reside at addresses
in the range

0x800000000000 to
0x802000000000

and "objects" are aligned to 32-byte boundaries. That means
there are 4294967296 zero-byte "objects" available. For each of
those objects, we need to know if it has been allocated by not
yet freed, that is, one bit per object. Add in a few extra
pointers and counts to manage the space to hold the bitmap
(so we don't have to use much more space for the bitmap than
is necessary), and we get a little over one bit /of actual
memory/ that is used to manage the zero-byte objects, which
take no actual memory.

Does that make more sense now?

On 2023-09-01, Lew Pitcher <lew.pitcher@digitalfreehold.ca> wrote:
> On Fri, 01 Sep 2023 17:03:06 +0000, Kaz Kylheku wrote:
>
>> On 2023-09-01, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>> What I meant was just over one bit /per zero-byte block/. So if there
>>> were 20,000 zero-byte blocks, they could be managed with just a little
>>> more than 2500 bytes of allocated memory. Sorry for the confusion.
>>
>> The following is a much better requirement for malloc and realloc:
>>
>> In the zero size case, return a non-null pointer to a single
>> program-wide object (always the same one), which can be passed to the
>> free function any number of times.
>>
>> Since a zero sized object doesn't store any information, there is no
>> need to have more than one.
>>
>> We satisfy these requirements:
>>
>> - realloc(x, 0) is effectively free(x), except that it also
>> returns that object.
>>
>> - the non-null object can be passed to library functions whose
>> behavior is not defined for null pointers, provided the functions are
>> not instructed to dereference it, or perform pointer arithmetic.
>
> This last point implies that there must be some way for code to
> distinguish this non-null object (that cannot be dereferenced)
> from other non-null objects that /can/ be dereferenced.

No, it doesn't.

Say we make this pointer:

char x[4], *p = x + 4;

f(p);

p effectively points to the base of a zero length array: one
byte past its last element.

Does f need "some what to distinguish this p value from one that
can bedereferenced"?
>
> Given that you specify that the non-null pointer returned from
> realloc(x,0)
> would be "a single program-wide object" and "always the same one",
> would you consider providing a unique name (like we do for the
> null pointer constant NULL) for such an object?

Tentatively yes. POSIX systems could use the same value as MAP_FAILED
which is typically

#define MAP_FAILED ((void *) -1)

It is sometimes useful to have an additional pointer value that is
not the same as any object, and invalid.

One example is in this source file:

https://www.kylheku.com/cgit/txr/tree/regex.c

Look for casts like coerce(cset_L2_t *, -1). I didn't define
a constant for this.

This code implements a multi-level radix tree structure for
representing Unicode character sets.

A null pointer at any level in the tree indicates that that
section of the space is all zero bits: those code points
under that tree are not in the set. We don't have to allocate
the underying directories and pages just to fill them wit zeros.

I also wanted an efficient way to say that an entire subtree
contains nothing but 1 bits. For that, I used a -1 converted
to the pointer type.

> If so, what name
> would you suggest, and what would the definition look like?

The definition cannot be dictated at the ISO C level;
only its properties can be described.

In some implementation ((void *) -1) might be indistinguishable
from the null pointer; you know the deal.

I'm not conviced that the constant would have to be published just for
the purpose of its connection with malloc(0); it would have to be
considered separately useful.

And even then, it would ahve to be decided whether that constant should
actually be that malloc(0) value, or should that still use its own
value.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

Kaz Kylheku <864-117-4973@kylheku.com> writes:

> On 2023-09-01, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> What I meant was just over one bit /per zero-byte block/. So if
>> there were 20,000 zero-byte blocks, they could be managed with
>> just a little more than 2500 bytes of allocated memory. Sorry
>> for the confusion.
>
> The following is a much better requirement for malloc and realloc:
>
> In the zero size case, return a non-null pointer to a single
> program-wide object (always the same one), which can be passed
> to the free function any number of times. [...]

This idea is worse in one important respect: it doesn't satisfy
the specification in the C standard.

Incidentally, it also doesn't satisfy the requirements of the
people who proposed the idea to begin with.

Lew Pitcher <lew.pitcher@digitalfreehold.ca> writes:

> On Fri, 01 Sep 2023 17:03:06 +0000, Kaz Kylheku wrote:
>
>> On 2023-09-01, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>
>>> What I meant was just over one bit /per zero-byte block/. So if there
>>> were 20,000 zero-byte blocks, they could be managed with just a little
>>> more than 2500 bytes of allocated memory. Sorry for the confusion.
>>
>> The following is a much better requirement for malloc and realloc:
>>
>> In the zero size case, return a non-null pointer to a single
>> program-wide object (always the same one), which can be passed to the
>> free function any number of times.
>>
>> Since a zero sized object doesn't store any information, there is no
>> need to have more than one.
>>
>> We satisfy these requirements:
>>
>> - realloc(x, 0) is effectively free(x), except that it also
>> returns that object.
>>
>> - the non-null object can be passed to library functions whose
>> behavior is not defined for null pointers, provided the functions are
>> not instructed to dereference it, or perform pointer arithmetic.
>
> This last point implies that there must be some way for code to
> distinguish this non-null object (that cannot be dereferenced)
> from other non-null objects that /can/ be dereferenced.

The idea that zero-byte objects can all be the same doesn't
satisfy the specifications in the C standard.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>Vir Campestris <vir.campestris@invalid.invalid> writes:
>
>
>In a 64-bit address space, there are a lot more addresses than
>there are bytes of memory, even virtual bytes of memory. All but
>a very small fraction of 64-bit addresses cannot map to actual
>memory, because there is no room on the address bus (figuratively
>speaking).

Current processors support between 44 and 52 bits of physical
address, and for the most part, the same on the virtual address
space as well. ARMv8 allows the VA space to be anywhere
from 16 bits to 52 bits on a per-translation-context) basis;
where smaller VA sizes can significantly decrease translation
table walk cost (i.e. by skipping levels).

With DDR5 and HBM we're seeing terabytes of DRAM on the bus.

With CXL (and Intel's PUMA chip) the physical address bus
will be fully utilized (all 64 bits) in the not so distant
future, if perhaps sparsely by using higher order bits to
identify nodes on the fabric.

On 2023-09-01, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> The idea that zero-byte objects can all be the same doesn't
> satisfy the specifications in the C standard.

yes; we all know are talking about an alternative requiremnt
that is not one of the current two implementation-defined choices.

However, anyone can implement the idea (or others) in an allocator
wrapper.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

On Fri, 01 Sep 2023 18:44:55 +0000, Kaz Kylheku wrote:

> On 2023-09-01, Lew Pitcher <lew.pitcher@digitalfreehold.ca> wrote:
>> On Fri, 01 Sep 2023 17:03:06 +0000, Kaz Kylheku wrote:
>>
>>> On 2023-09-01, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>>> What I meant was just over one bit /per zero-byte block/. So if
>>>> there were 20,000 zero-byte blocks, they could be managed with just a
>>>> little more than 2500 bytes of allocated memory. Sorry for the
>>>> confusion.
>>>
>>> The following is a much better requirement for malloc and realloc:
>>>
>>> In the zero size case, return a non-null pointer to a single
>>> program-wide object (always the same one), which can be passed to the
>>> free function any number of times.
>>>
>>> Since a zero sized object doesn't store any information, there is no
>>> need to have more than one.
>>>
>>> We satisfy these requirements:
>>>
>>> - realloc(x, 0) is effectively free(x), except that it also
>>> returns that object.
>>>
>>> - the non-null object can be passed to library functions whose
>>> behavior is not defined for null pointers, provided the functions
>>> are not instructed to dereference it, or perform pointer arithmetic.
>>
>> This last point implies that there must be some way for code to
>> distinguish this non-null object (that cannot be dereferenced) from
>> other non-null objects that /can/ be dereferenced.
>
> No, it doesn't.
>
> Say we make this pointer:
>
> char x[4], *p = x + 4;
>
> f(p);
>
> p effectively points to the base of a zero length array: one byte past
> its last element.
>
> Does f need "some what to distinguish this p value from one that can
> be dereferenced"?

OK, I get that. I took your statement that "the non-null object can be
passed to library functions whose behavior is not defined for null
pointers, provided the functions are not instructed to dereference it,
or perform pointer arithmetic" as implying that, for instance
strcpy(realloc(x,0),"abc"); /* unrealistic, but... */
would need some way to determine that the function would need to check
the given destination pointer for it's zero-length not-nullness before
performing the requested copy operation. If it does not, then the
standard function would violate your "cannot be dereferenced or be the
subject of pointer arithmetic" rule.

So, I guess that strcpy() will just have to "take it on faith" that
the given pointer points to something of more than zero size.

ISTM that strcpy() can easily test it's arguments for NULLness and
cleanly abort the copy operation if either equals NULL, although it is
under no obligation to do so by the C standard. I wondered how the
function could ensure that neither of it's arguments were of the
not-null zero-length variety.

Thanks for the clarification.
--
Lew Pitcher
"In Skills We Trust"

On 01/09/2023 19:42, Tim Rentsch wrote:
> In fact it must be a unique address, distinct from any other
> address that has been allocated but not yet freed.
>
> The key point is that, when the size is zero, the allocation
> routine allocates/address space/ but does not allocate/memory/.
> The address is not mapped to any memory, either physical or
> virtual.
>
> In a 64-bit address space, there are a lot more addresses than
> there are bytes of memory, even virtual bytes of memory. All but
> a very small fraction of 64-bit addresses cannot map to actual
> memory, because there is no room on the address bus (figuratively
> speaking).
>
> For example, suppose our zero byte block reside at addresses
> in the range
>
> 0x800000000000 to
> 0x802000000000
>
> and "objects" are aligned to 32-byte boundaries. That means
> there are 4294967296 zero-byte "objects" available. For each of
> those objects, we need to know if it has been allocated by not
> yet freed, that is, one bit per object. Add in a few extra
> pointers and counts to manage the space to hold the bitmap
> (so we don't have to use much more space for the bitmap than
> is necessary), and we get a little over one bit /of actual
> memory/ that is used to manage the zero-byte objects, which
> take no actual memory.
>
> Does that make more sense now?

Yes, it does. Thank you (and Kaz).

Andy

scott@slp53.sl.home (Scott Lurndal) writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Vir Campestris <vir.campestris@invalid.invalid> writes:
>>
>>
>> In a 64-bit address space, there are a lot more addresses than
>> there are bytes of memory, even virtual bytes of memory. All but
>> a very small fraction of 64-bit addresses cannot map to actual
>> memory, because there is no room on the address bus (figuratively
>> speaking).
>
> Current processors support between 44 and 52 bits of physical
> address, and for the most part, the same on the virtual address
> space as well. ARMv8 allows the VA space to be anywhere
> from 16 bits to 52 bits on a per-translation-context) basis;
> where smaller VA sizes can significantly decrease translation
> table walk cost (i.e. by skipping levels).
>
> With DDR5 and HBM we're seeing terabytes of DRAM on the bus.

Still plenty of address space left over.

> With CXL (and Intel's PUMA chip) the physical address bus
> will be fully utilized (all 64 bits) in the not so distant
> future, if perhaps sparsely by using higher order bits to
> identify nodes on the fabric.

I think the key word there is sparsely. A very small
fraction of a 64-bit address space suffices, and that
needn't be all contiguous either - it's easy to handle
a modest number of distinct areas, without too much
burden either in space or time.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>scott@slp53.sl.home (Scott Lurndal) writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> Vir Campestris <vir.campestris@invalid.invalid> writes:
>>>
>>>
>>> In a 64-bit address space, there are a lot more addresses than
>>> there are bytes of memory, even virtual bytes of memory. All but
>>> a very small fraction of 64-bit addresses cannot map to actual
>>> memory, because there is no room on the address bus (figuratively
>>> speaking).
>>
>> Current processors support between 44 and 52 bits of physical
>> address, and for the most part, the same on the virtual address
>> space as well. ARMv8 allows the VA space to be anywhere
>> from 16 bits to 52 bits on a per-translation-context) basis;
>> where smaller VA sizes can significantly decrease translation
>> table walk cost (i.e. by skipping levels).
>>
>> With DDR5 and HBM we're seeing terabytes of DRAM on the bus.
>
>Still plenty of address space left over.
>
>> With CXL (and Intel's PUMA chip) the physical address bus
>> will be fully utilized (all 64 bits) in the not so distant
>> future, if perhaps sparsely by using higher order bits to
>> identify nodes on the fabric.
>
>I think the key word there is sparsely. A very small
>fraction of a 64-bit address space suffices, and that
>needn't be all contiguous either - it's easy to handle
>a modest number of distinct areas, without too much
>burden either in space or time.

Perhaps, but vis-a-vis realloc(p,0), I'd say just don't
do that rather than adding an arcane 'zero-byte object'
concept. Deprecate the feature completely.

In fact, I'd suggest using malloc(), memcpy()/and free() if
necessary to reallocate something.

scott@slp53.sl.home (Scott Lurndal) writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

[use of address space for zero-byte allocated objects]

>> I think the key word there is sparsely. A very small
>> fraction of a 64-bit address space suffices, and that
>> needn't be all contiguous either - it's easy to handle
>> a modest number of distinct areas, without too much
>> burden either in space or time.
>
> Perhaps, but vis-a-vis realloc(p,0), I'd say just don't
> do that rather than adding an arcane 'zero-byte object'
> concept. Deprecate the feature completely.

Probably a lot of other people agree with you, but the problem
is not just realloc(). A call of malloc(0) has the same problem.
And that problem is not going away - the C standard gives an
implementation-defined choice as to whether malloc(0) returns
NULL or a pointer to "a zero-sized object" (my phrasing).

> In fact, I'd suggest using malloc(), memcpy()/and free() if
> necessary to reallocate something.

I think that idea is nutty. The realloc() function serves a
useful purpose, including better utilization of memory. If
someone wants to avoid the weird possibilities of zero-sized
objects, it's easy enough to program around that without
having to completely give up on realloc().

Kaz Kylheku <864-117-4973@kylheku.com> writes:

> On 2023-09-01, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> The idea that zero-byte objects can all be the same doesn't
>> satisfy the specifications in the C standard.
>
> yes; we all know are talking about an alternative requiremnt
> that is not one of the current two implementation-defined choices.
>
> However, anyone can implement the idea (or others) in an allocator
> wrapper.

Yes, anyone can, but no one does, because it's a lame idea.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>scott@slp53.sl.home (Scott Lurndal) writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>[use of address space for zero-byte allocated objects]
>
>>> I think the key word there is sparsely. A very small
>>> fraction of a 64-bit address space suffices, and that
>>> needn't be all contiguous either - it's easy to handle
>>> a modest number of distinct areas, without too much
>>> burden either in space or time.
>>
>> Perhaps, but vis-a-vis realloc(p,0), I'd say just don't
>> do that rather than adding an arcane 'zero-byte object'
>> concept. Deprecate the feature completely.
>
>Probably a lot of other people agree with you, but the problem
>is not just realloc(). A call of malloc(0) has the same problem.
>And that problem is not going away - the C standard gives an
>implementation-defined choice as to whether malloc(0) returns
>NULL or a pointer to "a zero-sized object" (my phrasing).
>
>> In fact, I'd suggest using malloc(), memcpy()/and free() if
>> necessary to reallocate something.
>
>I think that idea is nutty. The realloc() function serves a
>useful purpose, including better utilization of memory. If
>someone wants to avoid the weird possibilities of zero-sized
>objects, it's easy enough to program around that without
>having to completely give up on realloc().

I've never used it (realloc) in forty-plus years of C programming.

As for better utilization of memory, there may be cases where
a growth request can be fulfilled by expanding the existing
allocation (e.g. glibc _int_realloc). I'd think that would be
less likely in modern threaded environments, although I'd like
to see some real workload data, perhaps by instrumenting
_int_realloc to keep statistics on the frequency of cases
where the memcpy is not required.

On Sun, 03 Sep 2023 21:40:44 GMT
scott@slp53.sl.home (Scott Lurndal) wrote:
> I've never used it (realloc) in forty-plus years of C programming.

I use it all the time.

On Monday, 4 September 2023 at 00:08:47 UTC+1, Spiros Bousbouras wrote:
> On Sun, 03 Sep 2023 21:40:44 GMT
> sc...@slp53.sl.home (Scott Lurndal) wrote:
> > I've never used it (realloc) in forty-plus years of C programming.
> I use it all the time.
>
It's used heavily for data input where the data comes in a stream with a sentinel
indicating end of data. Particularly if the stream cannot be guaranteed seekable.

It's seldom needed for core algorithms, because normally there's a fairly tight upper
bound on the memory space required.

scott@slp53.sl.home (Scott Lurndal) writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> scott@slp53.sl.home (Scott Lurndal) writes:
>>
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>> [use of address space for zero-byte allocated objects]
>>
>>>> I think the key word there is sparsely. A very small
>>>> fraction of a 64-bit address space suffices, and that
>>>> needn't be all contiguous either - it's easy to handle
>>>> a modest number of distinct areas, without too much
>>>> burden either in space or time.
>>>
>>> Perhaps, but vis-a-vis realloc(p,0), I'd say just don't
>>> do that rather than adding an arcane 'zero-byte object'
>>> concept. Deprecate the feature completely.
>>
>> Probably a lot of other people agree with you, but the problem
>> is not just realloc(). A call of malloc(0) has the same problem.
>> And that problem is not going away - the C standard gives an
>> implementation-defined choice as to whether malloc(0) returns
>> NULL or a pointer to "a zero-sized object" (my phrasing).
>>
>>> In fact, I'd suggest using malloc(), memcpy()/and free() if
>>> necessary to reallocate something.
>>
>> I think that idea is nutty. The realloc() function serves a
>> useful purpose, including better utilization of memory. If
>> someone wants to avoid the weird possibilities of zero-sized
>> objects, it's easy enough to program around that without
>> having to completely give up on realloc().
>
> I've never used it (realloc) in forty-plus years of C programming.
>
> As for better utilization of memory, there may be cases where
> a growth request can be fulfilled by expanding the existing
> allocation (e.g. glibc _int_realloc). I'd think that would be
> less likely in modern threaded environments, although I'd like
> to see some real workload data, perhaps by instrumenting
> _int_realloc to keep statistics on the frequency of cases
> where the memcpy is not required.

Obviously it depends on how much memory is available, and how
close to the memory limits the program is running. If we have an
environment with only, say, 1.5 G available, and we want to grow
a 0.8 G block to 1 G, the malloc/copy/free approach will fail,
but using realloc may very well succeed. Even shrinking a memory
block can fail under the malloc/copy/free approach, but will
almost certainly succeed when using realloc. Clearly there are
some potential upsides to using realloc, and I don't see any
downsides. So I still don't understand your position, unless
you're saying this is what you've always done and you don't see
any reason to change it, even if it might be suboptimal.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>scott@slp53.sl.home (Scott Lurndal) writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> scott@slp53.sl.home (Scott Lurndal) writes:
>>>
>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>
>>> [use of address space for zero-byte allocated objects]
>>>
>>>>> I think the key word there is sparsely. A very small
>>>>> fraction of a 64-bit address space suffices, and that
>>>>> needn't be all contiguous either - it's easy to handle
>>>>> a modest number of distinct areas, without too much
>>>>> burden either in space or time.
>>>>
>>>> Perhaps, but vis-a-vis realloc(p,0), I'd say just don't
>>>> do that rather than adding an arcane 'zero-byte object'
>>>> concept. Deprecate the feature completely.
>>>
>>> Probably a lot of other people agree with you, but the problem
>>> is not just realloc(). A call of malloc(0) has the same problem.
>>> And that problem is not going away - the C standard gives an
>>> implementation-defined choice as to whether malloc(0) returns
>>> NULL or a pointer to "a zero-sized object" (my phrasing).
>>>
>>>> In fact, I'd suggest using malloc(), memcpy()/and free() if
>>>> necessary to reallocate something.
>>>
>>> I think that idea is nutty. The realloc() function serves a
>>> useful purpose, including better utilization of memory. If
>>> someone wants to avoid the weird possibilities of zero-sized
>>> objects, it's easy enough to program around that without
>>> having to completely give up on realloc().
>>
>> I've never used it (realloc) in forty-plus years of C programming.
>>
>> As for better utilization of memory, there may be cases where
>> a growth request can be fulfilled by expanding the existing
>> allocation (e.g. glibc _int_realloc). I'd think that would be
>> less likely in modern threaded environments, although I'd like
>> to see some real workload data, perhaps by instrumenting
>> _int_realloc to keep statistics on the frequency of cases
>> where the memcpy is not required.
>
>Obviously it depends on how much memory is available, and how
>close to the memory limits the program is running. If we have an
>environment with only, say, 1.5 G available, and we want to grow
>a 0.8 G block to 1 G, the malloc/copy/free approach will fail,
>but using realloc may very well succeed. Even shrinking a memory
>block can fail under the malloc/copy/free approach, but will
>almost certainly succeed when using realloc. Clearly there are
>some potential upsides to using realloc, and I don't see any
>downsides. So I still don't understand your position, unless
>you're saying this is what you've always done and you don't see
>any reason to change it, even if it might be suboptimal.

Most of the code I've worked on has been bare metal (operating systems,
hypervisors, run-time firmware) where dynamic allocation is
either discouraged or managed with fixed size pool allocators or
slab allocators, et cetera. I suppose that's influenced my thinking about
the desirability of realloc() and run-time heap management.

Clearly others have found it useful.