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.

On 03/09/2023 22:40, Scott Lurndal wrote:
> 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.

If I have a block of memory, and I want to change its size, it's
possible that the heap management routines can optimise to something
better than make new allocation then memcpy. Perhaps there's enough free
space just past my buffer for my expansion. Perhaps there's enough free
memory that it's not worth moving the data to a smaller block.

It's not something I've used often, but I have used it occasionally.

Andy

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

[ to realloc or malloc/copy/free ? ]

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

Now that I understand your perspective I think we are on the
same page (no pun intended). Stand-alone environments do
indeed promote a different mindset with respect to malloc()
and to memory allocation generally.