Le 21/11/2021 à 00:52, Keith Thompson a écrit :
> David Brown <david.brown@hesbynett.no> writes:
>> On 19/11/2021 21:52, Keith Thompson wrote:
> [...]
>>> Perhaps -- but typically that information is not stored in the pointer
>>> itself. If it were, all void* values would have to store that extra
>>> information.
>>>
>>> (I think it's easier to store bookkeeping data before the allocated
>>> space. If you store it after the space, it's hard to know where it is.)
>>
>> That's the most common way for a simple malloc/free system.
>>
>> It has always struck me as a mistake that C did things that way - in my
>> opinion, "free" should have taken an additional parameter of the size
>> for the deallocation.
>
> Meh. That would have introduced another rich source of programming
> errors (passing the wrong size).

Yes absolutely. Besides, the extra data allocated for each malloc() is a
bunch of stuff to identify the chain of allocated blocks, so this extra
data is needed anyway.

On 21/11/2021 00:34, Guillaume wrote:
> Le 21/11/2021 à 00:52, Keith Thompson a écrit :
>> David Brown <david.brown@hesbynett.no> writes:
>>> On 19/11/2021 21:52, Keith Thompson wrote:
>> [...]
>>>> Perhaps -- but typically that information is not stored in the pointer
>>>> itself.  If it were, all void* values would have to store that extra
>>>> information.
>>>>
>>>> (I think it's easier to store bookkeeping data before the allocated
>>>> space.  If you store it after the space, it's hard to know where it
>>>> is.)
>>>
>>> That's the most common way for a simple malloc/free system.
>>>
>>> It has always struck me as a mistake that C did things that way - in my
>>> opinion, "free" should have taken an additional parameter of the size
>>> for the deallocation.
>>
>> Meh.  That would have introduced another rich source of programming
>> errors (passing the wrong size).
>
> Yes absolutely. Besides, the extra data allocated for each malloc() is a
> bunch of stuff to identify the chain of allocated blocks, so this extra
> data is needed anyway.
>

Why for allocated blocks? The chain of freed blocks would be more
relevant, and there you can just use the freed data space.

On 11/20/2021 4:34 PM, Guillaume wrote:
> Le 21/11/2021 à 00:52, Keith Thompson a écrit :
>> David Brown <david.brown@hesbynett.no> writes:
>>> On 19/11/2021 21:52, Keith Thompson wrote:
>> [...]
>>>> Perhaps -- but typically that information is not stored in the pointer
>>>> itself.  If it were, all void* values would have to store that extra
>>>> information.
>>>>
>>>> (I think it's easier to store bookkeeping data before the allocated
>>>> space.  If you store it after the space, it's hard to know where it
>>>> is.)
>>>
>>> That's the most common way for a simple malloc/free system.
>>>
>>> It has always struck me as a mistake that C did things that way - in my
>>> opinion, "free" should have taken an additional parameter of the size
>>> for the deallocation.
>>
>> Meh.  That would have introduced another rich source of programming
>> errors (passing the wrong size).
>
> Yes absolutely. Besides, the extra data allocated for each malloc() is a
> bunch of stuff to identify the chain of allocated blocks, so this extra
> data is needed anyway.
>

It is not needed in some allocators. I have coded them with basically
zero overhead. Actually, only allocations less than sizeof(void*) are
padded up to the size of a pointer...

On 11/20/21 7:19 PM, Bart wrote:
> On 20/11/2021 23:52, Keith Thompson wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>> On 19/11/2021 21:52, Keith Thompson wrote:
>> [...]
>>>> Perhaps -- but typically that information is not stored in the pointer
>>>> itself.  If it were, all void* values would have to store that extra
>>>> information.
>>>>
>>>> (I think it's easier to store bookkeeping data before the allocated
>>>> space.  If you store it after the space, it's hard to know where it
>>>> is.)
>>>
>>> That's the most common way for a simple malloc/free system.
>>>
>>> It has always struck me as a mistake that C did things that way - in my
>>> opinion, "free" should have taken an additional parameter of the size
>>> for the deallocation.
>>
>> Meh.  That would have introduced another rich source of programming
>> errors (passing the wrong size).
>
> You could also pass the wrong size to malloc, or the wrong pointer to free.
>
>> Probably most implementations would
>> have kept track of the size anyway, so they could detect errors.
>
> I doubt that, unless it's for debugging mode.
>
> If an application needs to allocate 100 million 32-byte nodes, which
> would occupy 3.2GB by themselves, how much extra would be needed for the
> size, 'just for checking'?
>
> On my machine that seems to be 16 bytes per node, so 50% more. 1.6GB
> extra just so someone can write:
>
>    free(p);
>
> instead of:
>
>    free(p, sizeof(treenode));
>
> possibly in just one place in the program.
>
> It doesn't make sense.
>

Maybe not to you, but I would sure hate to have to keep track of all
that data, and would likely just wrap this dumb malloc with something
smarter.

If you need a lot of a fixed sized blocks, there are lots of algorithms
that work well for that with much less or zero overhead (if the blocks
are big enough for a pointer)

On 11/20/21 7:19 PM, Bart wrote:
> On 20/11/2021 23:52, Keith Thompson wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>> On 19/11/2021 21:52, Keith Thompson wrote:
>> [...]
>>>> Perhaps -- but typically that information is not stored in the pointer
>>>> itself.  If it were, all void* values would have to store that extra
>>>> information.
>>>>
>>>> (I think it's easier to store bookkeeping data before the allocated
>>>> space.  If you store it after the space, it's hard to know where it
>>>> is.)
>>>
>>> That's the most common way for a simple malloc/free system.
>>>
>>> It has always struck me as a mistake that C did things that way - in my
>>> opinion, "free" should have taken an additional parameter of the size
>>> for the deallocation.
>>
>> Meh.  That would have introduced another rich source of programming
>> errors (passing the wrong size).
>
> You could also pass the wrong size to malloc, or the wrong pointer to free.
>
>> Probably most implementations would
>> have kept track of the size anyway, so they could detect errors.
>
> I doubt that, unless it's for debugging mode.
>
> If an application needs to allocate 100 million 32-byte nodes, which
> would occupy 3.2GB by themselves, how much extra would be needed for the
> size, 'just for checking'?
>
> On my machine that seems to be 16 bytes per node, so 50% more. 1.6GB
> extra just so someone can write:
>
>    free(p);
>
> instead of:
>
>    free(p, sizeof(treenode));
>
> possibly in just one place in the program.
>
> It doesn't make sense.
>

Maybe not to you, but I would sure hate to have to keep track of all
that data, and would likely just wrap this dumb malloc with something
smarter.

If you need a lot of a fixed sized blocks, there are lots of algorithms
that work well for that with much less or zero overhead (if the blocks
are big enough for a pointer)

Bart <bc@freeuk.com> writes:

> On 20/11/2021 23:52, Keith Thompson wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>> On 19/11/2021 21:52, Keith Thompson wrote:
>> [...]
>>>> Perhaps -- but typically that information is not stored in the pointer
>>>> itself. If it were, all void* values would have to store that extra
>>>> information.
>>>>
>>>> (I think it's easier to store bookkeeping data before the allocated
>>>> space. If you store it after the space, it's hard to know where it is.)
>>>
>>> That's the most common way for a simple malloc/free system.
>>>
>>> It has always struck me as a mistake that C did things that way - in my
>>> opinion, "free" should have taken an additional parameter of the size
>>> for the deallocation.
>> Meh. That would have introduced another rich source of programming
>> errors (passing the wrong size).
>
> You could also pass the wrong size to malloc, or the wrong pointer to free.
>
>> Probably most implementations would
>> have kept track of the size anyway, so they could detect errors.
>
> I doubt that, unless it's for debugging mode.
>
> If an application needs to allocate 100 million 32-byte nodes, which
> would occupy 3.2GB by themselves, how much extra would be needed for
> the size, 'just for checking'?

If that's what you're doing, you shouldn't be using malloc() for the
individual nodes.

> On my machine that seems to be 16 bytes per node, so 50% more. 1.6GB
> extra just so someone can write:
>
> free(p);
>
> instead of:
>
> free(p, sizeof(treenode));
>
> possibly in just one place in the program.
>
> It doesn't make sense.

Remember, you have to have all the data structures to keep track of the
allocated space so malloc() will work. I expect that requirement will
eat up close to that much space anyway.

On 21/11/2021 01:44, Richard Damon wrote:
> On 11/20/21 7:19 PM, Bart wrote:
>> On 20/11/2021 23:52, Keith Thompson wrote:
>>> David Brown <david.brown@hesbynett.no> writes:
>>>> On 19/11/2021 21:52, Keith Thompson wrote:
>>> [...]
>>>>> Perhaps -- but typically that information is not stored in the pointer
>>>>> itself.  If it were, all void* values would have to store that extra
>>>>> information.
>>>>>
>>>>> (I think it's easier to store bookkeeping data before the allocated
>>>>> space.  If you store it after the space, it's hard to know where it
>>>>> is.)
>>>>
>>>> That's the most common way for a simple malloc/free system.
>>>>
>>>> It has always struck me as a mistake that C did things that way - in my
>>>> opinion, "free" should have taken an additional parameter of the size
>>>> for the deallocation.
>>>
>>> Meh.  That would have introduced another rich source of programming
>>> errors (passing the wrong size).
>>
>> You could also pass the wrong size to malloc, or the wrong pointer to
>> free.
>>
>>> Probably most implementations would
>>> have kept track of the size anyway, so they could detect errors.
>>
>> I doubt that, unless it's for debugging mode.
>>
>> If an application needs to allocate 100 million 32-byte nodes, which
>> would occupy 3.2GB by themselves, how much extra would be needed for
>> the size, 'just for checking'?
>>
>> On my machine that seems to be 16 bytes per node, so 50% more. 1.6GB
>> extra just so someone can write:
>>
>>     free(p);
>>
>> instead of:
>>
>>     free(p, sizeof(treenode));
>>
>> possibly in just one place in the program.
>>
>> It doesn't make sense.
>>
>
> Maybe not to you, but I would sure hate to have to keep track of all
> that data, and would likely just wrap this dumb malloc with something
> smarter.

I still don't understand why you have to keep track of /allocated/
blocks. Once allocated, they belong to the application; why does the
allocator need to care about them?

Once deallocated, or before they are allocated, then the allocator can
do what it likes with them. But it can use data within the blocks: it
doesn't need any extra space. (Unless the block is tiny, like one byte,
then it will have to impose a minimum size.)

> If you need a lot of a fixed sized blocks, there are lots of algorithms
> that work well for that with much less or zero overhead (if the blocks
> are big enough for a pointer)

Lots of same-sized blocks you mean? Then sure, there are all sorts of
custom allocators that could be used. Including the case where you know
that you will never free memory so there is no point wasting time and
space with housekeeping information.

But this is about the general purpose allocator provided by with malloc
and free. You can always add a 'better' allocator on top that uses extra
overheads; it's harder the other way around.

On 21/11/2021 03:13, Joe Pfeiffer wrote:
> Bart <bc@freeuk.com> writes:
>
>> On 20/11/2021 23:52, Keith Thompson wrote:
>>> David Brown <david.brown@hesbynett.no> writes:
>>>> On 19/11/2021 21:52, Keith Thompson wrote:
>>> [...]
>>>>> Perhaps -- but typically that information is not stored in the pointer
>>>>> itself. If it were, all void* values would have to store that extra
>>>>> information.
>>>>>
>>>>> (I think it's easier to store bookkeeping data before the allocated
>>>>> space. If you store it after the space, it's hard to know where it is.)
>>>>
>>>> That's the most common way for a simple malloc/free system.
>>>>
>>>> It has always struck me as a mistake that C did things that way - in my
>>>> opinion, "free" should have taken an additional parameter of the size
>>>> for the deallocation.
>>> Meh. That would have introduced another rich source of programming
>>> errors (passing the wrong size).
>>
>> You could also pass the wrong size to malloc, or the wrong pointer to free.
>>
>>> Probably most implementations would
>>> have kept track of the size anyway, so they could detect errors.
>>
>> I doubt that, unless it's for debugging mode.
>>
>> If an application needs to allocate 100 million 32-byte nodes, which
>> would occupy 3.2GB by themselves, how much extra would be needed for
>> the size, 'just for checking'?
>
> If that's what you're doing, you shouldn't be using malloc() for the
> individual nodes.

Why not; isn't that exactly what it's for?

And what is the alternative, to create a custom allocator?

>> On my machine that seems to be 16 bytes per node, so 50% more. 1.6GB
>> extra just so someone can write:
>>
>> free(p);
>>
>> instead of:
>>
>> free(p, sizeof(treenode));
>>
>> possibly in just one place in the program.
>>
>> It doesn't make sense.
>
> Remember, you have to have all the data structures to keep track of the
> allocated space so malloc() will work.

Everyone is saying this; no one is explaining exactly why it needs to!

Are you saying that, unless an allocated block is tagged with a size,
malloc has no idea which pool memory has been allocated and which hasn't?

I've written a few allocators over the years, they have never needed to
record the size of a block.

On 21/11/2021 00:52, Keith Thompson wrote:
> David Brown <david.brown@hesbynett.no> writes:
>> On 19/11/2021 21:52, Keith Thompson wrote:
> [...]
>>> Perhaps -- but typically that information is not stored in the pointer
>>> itself. If it were, all void* values would have to store that extra
>>> information.
>>>
>>> (I think it's easier to store bookkeeping data before the allocated
>>> space. If you store it after the space, it's hard to know where it is.)
>>
>> That's the most common way for a simple malloc/free system.
>>
>> It has always struck me as a mistake that C did things that way - in my
>> opinion, "free" should have taken an additional parameter of the size
>> for the deallocation.
>
> Meh. That would have introduced another rich source of programming
> errors (passing the wrong size). Probably most implementations would
> have kept track of the size anyway, so they could detect errors. As
> long as they're keeping track, why make the user do so as well?

It would have lead to some different programming errors, perhaps, but I
don't think it would have lead to more. If you are at the point in your
code where you can correctly call "free(p);", it seems highly unlikely
that you don't also have the size of the allocation there too. (To be
clear, I expect you to have the size used when calling malloc - if the
heap implementation rounds that up to a block size in some way, then it
would do the same for sized free.)

You know the size used in your malloc() call. Either you are getting
space for a single object (such as a large struct), or an array - and
you know the size when you are using the object or array later.

There may be some occasions when a little extra effort is needed on the
part of the programmer to keep track of the size before calling free(),
but I believe that would be a minority of cases.

>
> Perhaps a lower-level allocator might be more efficient if user code is
> required to keep track, but I don't think it would be all that useful
> for most applications.
>

It can easily make a big difference when you consider caches and pages.
A cache line might be 32 bytes long, or more - either your data is
badly aligned, or that's a lot of wasted space just to hold a size that
the client code already knows. If you've got a tree structure where the
node data (including pointers to branches) all fit within a 32 byte
block, half the space in your cache is wasted holding the sizes for
"free". For bigger cache lines, either you waste even more space per
allocation or your sizes (within their 16 or 32 byte alignment block)
are mixed with the data that you actually /want/ in your cache. However
you do it, it can be a serious waste of cache space.

The alternative is to have more advanced heap management algorithms
which keep the size information independently, meaning they have to
support a mapping between allocated addresses and the size allocated.
This is complex, slow and inefficient compared to a structure where the
client code has the size - all you need then might be a plain bitmap
with a single bit per used block (with pools to deal efficiently with
different sizes of allocation).

Storing the size of an allocation as an extra item before the block was
a simple and efficient mechanism in earlier computers - but not now.
There are, of course, many ways to implement a heap with different
balances of complexity, speed, efficiency, etc. Storing the size
somewhere does not make them simpler, faster or more efficient.

C++14 introduced sized deletion so that you can make allocators that
don't need to track sizes.

On 21/11/2021 02:44, Richard Damon wrote:
> On 11/20/21 7:19 PM, Bart wrote:

>> It doesn't make sense.

I don't want to make a habit of it, but I agree with Bart here :-)

>
> Maybe not to you, but I would sure hate to have to keep track of all
> that data, and would likely just wrap this dumb malloc with something
> smarter.

And that is /fine/. For those few cases where it might be inconvenient
to know the size at deallocation time, make a wrapper so that the size
is tracked. If you need that functionality, write the code and pay the
price - others that don't need the heap to record their allocation sizes
shouldn't have to pay for your needs. It is no different from malloc
and calloc - if you want the convenience of zeroing the memory, you can
use calloc, but if you don't want it you can use malloc and not pay for
the extra effort.

Of course it is too late to make such untracked-size heap functions the
standard for C - I see it as an unlucky choice made long ago. After
all, if you had "malloc_untracked" and "free_untracked" then it would be
a simple matter to implement traditional C "malloc" and "free" on top of it.

>
> If you need a lot of a fixed sized blocks, there are lots of algorithms
> that work well for that with much less or zero overhead (if the blocks
> are big enough for a pointer)

Yes, of course there are many ways of efficiently handling fixed size
blocks. But it would be more convenient if the common heap system
didn't have this particular inefficiency.

On 21/11/2021 00:19, Bart wrote:
> On 20/11/2021 23:52, Keith Thompson wrote:

>> Probably most implementations would
>> have kept track of the size anyway, so they could detect errors.
>
> I doubt that, unless it's for debugging mode.
>
> If an application needs to allocate 100 million 32-byte nodes, which
> would occupy 3.2GB by themselves, how much extra would be needed for the
> size, 'just for checking'?
>
> On my machine that seems to be 16 bytes per node, so 50% more. 1.6GB
> extra just so someone can write:
>
>    free(p);
>
> instead of:
>
>    free(p, sizeof(treenode));
>
> possibly in just one place in the program.

That last example (which would have been a Binary Trees benchmark) could
also be written as:

free(p, sizeof(*p));

If p has type T* and you know the allocation is for exactly one such
object (eg. as AST node in a compiler), then you don't need the
allocator to keep track of the size.

I usually go to some trouble to craft my struct sizes to be
powers-of-to, and it would be annoying for an allocator to just add its
own garbage on top.

(Here are the two lines from Binary Trees in my language (not using C as
I don't have my pcm library there) that handle memory:

t := malloc(treenode.bytes)
free(tree)

that's when I use C routines directly. If I switch to a different
allocator that I normally use within my interpreters, it looks like this:

t := pcm_alloc(treenode.bytes)
pcm_free(tree, treenode.bytes) # or tree^.bytes

Either work. Except that malloc/free [**] take 11 seconds for one run.

My pcm_alloc/pcm_free take 3.7 seconds, nearly 3 times as fast.

Although the reason for that is probably not the extra memory, as the
node size of 24 bytes is allocated 32 bytes in both cases: with malloc
because of the size overhead; in mine because it's rounded up to a
power-of-two.

My allocator is probably just simpler...

---------------

** Using malloc/free from msvcrt.dll.

C version using malloc/free and gcc-O3 takes 10.3 seconds, likely using
same library.

C version on WSL and with gcc-O3 takes 4.8 seconds.

However, if I port my language using those pcm calls to C, then I get
timings of 2.7 seconds on Windows, and 2.1 seconds on WSL, using gcc-O3.)

)

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>scott@slp53.sl.home (Scott Lurndal) writes:
>> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>>>Guillaume <message@bottle.org> writes:
>>>> Le 18/11/2021 à 22:58, David Brown a écrit :
>>
>>>> Now there are kind of exceptions to that, but that are purely
>>>> "hand-implemented" and have nothing to do with the language itself:
>>>> for instance, the typical malloc() behavior. Behind the scenes,
>>>> pointers returned by malloc() are "fat pointers", and you can also
>>>> implement your own fat pointers if you so wish. But the language
>>>> doesn't care. It has no provision for that, except you can do pointer
>>>> arithmetics to your heart's content.
>>>
>>>I'm not sure what you mean about malloc() returning "fat pointers".
>>>malloc() returns a void* with no information about the size or type of
>>>what it points to. Some implementations might provide a way to query
>>>the size of the allocated space, but that's not standard.
>>
>> Many malloc implementations reserve additional space, either before
>> or after the allocated space for bookkeeping and alignment purposes.
>>
>> Perhaps that is the source of Guillaume's "fat pointer" reference.
>
>Perhaps -- but typically that information is not stored in the pointer
>itself. If it were, all void* values would have to store that extra
>information.

True. The only modern fat pointers I'm aware of (at least that I can talk
about publically) are the Burroughs B6500 family processors (capabilities)
and the CHERI project.

>
>(I think it's easier to store bookkeeping data before the allocated
>space. If you store it after the space, it's hard to know where it is.)

Point.

Bart <bc@freeuk.com> writes:
> On 21/11/2021 03:13, Joe Pfeiffer wrote:
>> Bart <bc@freeuk.com> writes:
>>>
>>> If an application needs to allocate 100 million 32-byte nodes, which
>>> would occupy 3.2GB by themselves, how much extra would be needed for
>>> the size, 'just for checking'?
>> If that's what you're doing, you shouldn't be using malloc() for the
>> individual nodes.
>
> Why not; isn't that exactly what it's for?

Because it isn't optimized for a use case like that. It's a general
purpose allocator, and you're using it for a situation that's 'way out
on the fringes.

> And what is the alternative, to create a custom allocator?

Yes. When I've had similar situations I've allocated large blocks with
malloc() and then allocated my little blocks from the big ones.

>>> On my machine that seems to be 16 bytes per node, so 50% more. 1.6GB
>>> extra just so someone can write:
>>>
>>> free(p);
>>>
>>> instead of:
>>>
>>> free(p, sizeof(treenode));
>>>
>>> possibly in just one place in the program.
>>>
>>> It doesn't make sense.
>> Remember, you have to have all the data structures to keep track of
>> the
>> allocated space so malloc() will work.
>
> Everyone is saying this; no one is explaining exactly why it needs to!
>
> Are you saying that, unless an allocated block is tagged with a size,
> malloc has no idea which pool memory has been allocated and which
> hasn't?
>
> I've written a few allocators over the years, they have never needed
> to record the size of a block.

On 11/21/2021 2:51 PM, David Brown wrote:
> On 21/11/2021 02:44, Richard Damon wrote:
>> On 11/20/21 7:19 PM, Bart wrote:
>
>>> It doesn't make sense.
>
> I don't want to make a habit of it, but I agree with Bart here :-)
>
>>
>> Maybe not to you, but I would sure hate to have to keep track of all
>> that data, and would likely just wrap this dumb malloc with something
>> smarter.
>
> And that is /fine/. For those few cases where it might be inconvenient
> to know the size at deallocation time, make a wrapper so that the size
> is tracked. If you need that functionality, write the code and pay the
> price - others that don't need the heap to record their allocation sizes
> shouldn't have to pay for your needs. It is no different from malloc
> and calloc - if you want the convenience of zeroing the memory, you can
> use calloc, but if you don't want it you can use malloc and not pay for
> the extra effort.
>
> Of course it is too late to make such untracked-size heap functions the
> standard for C - I see it as an unlucky choice made long ago. After
> all, if you had "malloc_untracked" and "free_untracked" then it would be
> a simple matter to implement traditional C "malloc" and "free" on top of it.

The problem I see with this is that it assumes one and only type of
metadata information to be associated to the pointer, specifically the
block size.
I believe there are countless implementations of malloc out there, and I
guess this might not be the case, or it may be the case today but not
tomorrow.
The point is that if you set the interface to be pointer+size you also
put constraints on the implementation, on top of the extra burden for
the programmer.

>
>>
>> If you need a lot of a fixed sized blocks, there are lots of algorithms
>> that work well for that with much less or zero overhead (if the blocks
>> are big enough for a pointer)
>
> Yes, of course there are many ways of efficiently handling fixed size
> blocks. But it would be more convenient if the common heap system
> didn't have this particular inefficiency.
>

On 21/11/2021 17:53, Joe Pfeiffer wrote:
> Bart <bc@freeuk.com> writes:
>> On 21/11/2021 03:13, Joe Pfeiffer wrote:
>>> Bart <bc@freeuk.com> writes:
>>>>
>>>> If an application needs to allocate 100 million 32-byte nodes, which
>>>> would occupy 3.2GB by themselves, how much extra would be needed for
>>>> the size, 'just for checking'?
>>> If that's what you're doing, you shouldn't be using malloc() for the
>>> individual nodes.
>>
>> Why not; isn't that exactly what it's for?
>
> Because it isn't optimized for a use case like that. It's a general
> purpose allocator, and you're using it for a situation that's 'way out
> on the fringes.
>
>> And what is the alternative, to create a custom allocator?
>
> Yes. When I've had similar situations I've allocated large blocks with
> malloc() and then allocated my little blocks from the big ones.

I would expect the majority of allocs in an application (not total
memory used) are going to be small:

* Numbers of instances of identical struct types, across many types

* Allocation of short strings

Yet all these common uses, where overheads are likely to more
significant, are considered to be 'on the fringes'?

With strings in particular, the allocator holds info about the string
length (or its allocated size), then would be useful to an application,
yet there is no way to make use of that information in the application.

Which leads to the situation that for a C++-style expandable string or
vector, the necessary descriptor needs to maintain its own duplicate of
the 'allocated' size.

(Actually there will be the current length, the requested capacity,
which are known, and the space actually allocated by malloc, which is
unknown; plus the metadata it needs.)

It all seems rather wasteful.

On 21/11/2021 19:32, Manfred wrote:
> On 11/21/2021 2:51 PM, David Brown wrote:
>> On 21/11/2021 02:44, Richard Damon wrote:
>>> On 11/20/21 7:19 PM, Bart wrote:
>>
>>>> It doesn't make sense.
>>
>> I don't want to make a habit of it, but I agree with Bart here :-)
>>
>>>
>>> Maybe not to you, but I would sure hate to have to keep track of all
>>> that data, and would likely just wrap this dumb malloc with something
>>> smarter.
>>
>> And that is /fine/.  For those few cases where it might be inconvenient
>> to know the size at deallocation time, make a wrapper so that the size
>> is tracked.  If you need that functionality, write the code and pay the
>> price - others that don't need the heap to record their allocation sizes
>> shouldn't have to pay for your needs.  It is no different from malloc
>> and calloc - if you want the convenience of zeroing the memory, you can
>> use calloc, but if you don't want it you can use malloc and not pay for
>> the extra effort.
>>
>> Of course it is too late to make such untracked-size heap functions the
>> standard for C - I see it as an unlucky choice made long ago.  After
>> all, if you had "malloc_untracked" and "free_untracked" then it would be
>> a simple matter to implement traditional C "malloc" and "free" on top
>> of it.
>
> The problem I see with this is that it assumes one and only type of
> metadata information to be associated to the pointer, specifically the
> block size.

No. It merely relieves the heap implementation from having to store the
size of the allocation. Any other metadata (such as for tracking free
space lists, or handling efficient multi-threaded access) will still be
needed.

> I believe there are countless implementations of malloc out there, and I
> guess this might not be the case, or it may be the case today but not
> tomorrow.
> The point is that if you set the interface to be pointer+size you also
> put constraints on the implementation, on top of the extra burden for
> the programmer.
>
How could this suggestion impose any constraints on the implementation?
The interface for getting the memory is the same (albeit with a
different name, in order to keep compatibility with existing code), and
the interface for freeing memory gives the implementation more
information. It would be perfectly possible (though a little unhelpful)
for an implementation of the "_untracked" functions to be :

#define malloc_untracked(size) malloc(size)
#define free_untracked(ptr, size) free(ptr)

An implementation can do better, given this new information, but there
are no new limitations or restrictions.

On 11/21/2021 5:40 AM, David Brown wrote:
> On 21/11/2021 00:52, Keith Thompson wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>> On 19/11/2021 21:52, Keith Thompson wrote:
>> [...]
>>>> Perhaps -- but typically that information is not stored in the pointer
>>>> itself. If it were, all void* values would have to store that extra
>>>> information.
>>>>
>>>> (I think it's easier to store bookkeeping data before the allocated
>>>> space. If you store it after the space, it's hard to know where it is.)
>>>
>>> That's the most common way for a simple malloc/free system.
>>>
>>> It has always struck me as a mistake that C did things that way - in my
>>> opinion, "free" should have taken an additional parameter of the size
>>> for the deallocation.
>>
>> Meh. That would have introduced another rich source of programming
>> errors (passing the wrong size). Probably most implementations would
>> have kept track of the size anyway, so they could detect errors. As
>> long as they're keeping track, why make the user do so as well?
>
> It would have lead to some different programming errors, perhaps, but I
> don't think it would have lead to more. If you are at the point in your
> code where you can correctly call "free(p);", it seems highly unlikely
> that you don't also have the size of the allocation there too. (To be
> clear, I expect you to have the size used when calling malloc - if the
> heap implementation rounds that up to a block size in some way, then it
> would do the same for sized free.)
>
> You know the size used in your malloc() call. Either you are getting
> space for a single object (such as a large struct), or an array - and
> you know the size when you are using the object or array later.

[...]

Fwiw, I am quite fond of creating a big chunk of memory, and aligning it
on a "large" boundary. Say 4096*4 bytes... Now, every address in the
memory can be rounded down to get at the boundary. There is a structure
sitting right before this boundary, a header:

[header][aligned_memory]

Every memory allocation less than the size of a pointer, is rounded up
to the size of a pointer. So, on a 32-bit system, 0...3 are rounded up
to 4. That's it. Now, wrt freeing something, we take the address, round
down to boundary, subtract the header, then we are at the header that
can contain a free list to link the pointer in. It's quite nice, and can
be on a per-thread basis. headers per-thread...

;^)

On 11/21/2021 4:35 AM, Bart wrote:
> On 21/11/2021 03:13, Joe Pfeiffer wrote:
>> Bart <bc@freeuk.com> writes:
>>
>>> On 20/11/2021 23:52, Keith Thompson wrote:
>>>> David Brown <david.brown@hesbynett.no> writes:
>>>>> On 19/11/2021 21:52, Keith Thompson wrote:
>>>> [...]
>>>>>> Perhaps -- but typically that information is not stored in the
>>>>>> pointer
>>>>>> itself.  If it were, all void* values would have to store that extra
>>>>>> information.
>>>>>>
>>>>>> (I think it's easier to store bookkeeping data before the allocated
>>>>>> space.  If you store it after the space, it's hard to know where
>>>>>> it is.)
>>>>>
>>>>> That's the most common way for a simple malloc/free system.
>>>>>
>>>>> It has always struck me as a mistake that C did things that way -
>>>>> in my
>>>>> opinion, "free" should have taken an additional parameter of the size
>>>>> for the deallocation.
>>>> Meh.  That would have introduced another rich source of programming
>>>> errors (passing the wrong size).
>>>
>>> You could also pass the wrong size to malloc, or the wrong pointer to
>>> free.
>>>
>>>> Probably most implementations would
>>>> have kept track of the size anyway, so they could detect errors.
>>>
>>> I doubt that, unless it's for debugging mode.
>>>
>>> If an application needs to allocate 100 million 32-byte nodes, which
>>> would occupy 3.2GB by themselves, how much extra would be needed for
>>> the size, 'just for checking'?
>>
>> If that's what you're doing, you shouldn't be using malloc() for the
>> individual nodes.
>
> Why not; isn't that exactly what it's for?
>
> And what is the alternative, to create a custom allocator?
>
>>> On my machine that seems to be 16 bytes per node, so 50% more. 1.6GB
>>> extra just so someone can write:
>>>
>>>     free(p);
>>>
>>> instead of:
>>>
>>>     free(p, sizeof(treenode));
>>>
>>> possibly in just one place in the program.
>>>
>>> It doesn't make sense.
>>
>> Remember, you have to have all the data structures to keep track of the
>> allocated space so malloc() will work.
>
> Everyone is saying this; no one is explaining exactly why it needs to!
>
> Are you saying that, unless an allocated block is tagged with a size,
> malloc has no idea which pool memory has been allocated and which hasn't?

free can round its address down to a boundary, and get at a header from
there. Therefore it can find its freelist, or pool, or whatever...

>
> I've written a few allocators over the years, they have never needed to
> record the size of a block.
>

On 11/21/2021 5:51 AM, David Brown wrote:
> On 21/11/2021 02:44, Richard Damon wrote:
>> On 11/20/21 7:19 PM, Bart wrote:
>
>>> It doesn't make sense.
>
> I don't want to make a habit of it, but I agree with Bart here :-)
>
>>
>> Maybe not to you, but I would sure hate to have to keep track of all
>> that data, and would likely just wrap this dumb malloc with something
>> smarter.
>
> And that is /fine/. For those few cases where it might be inconvenient
> to know the size at deallocation time, make a wrapper so that the size
> is tracked. If you need that functionality, write the code and pay the
> price - others that don't need the heap to record their allocation sizes
> shouldn't have to pay for your needs. It is no different from malloc
> and calloc - if you want the convenience of zeroing the memory, you can
> use calloc, but if you don't want it you can use malloc and not pay for
> the extra effort.

For some reason this is making me think of a bug I found in MSVC:

https://groups.google.com/g/comp.lang.c++/c/48Tm8j8ag-0/m/VYI8rvB9vIwJ

>
> Of course it is too late to make such untracked-size heap functions the
> standard for C - I see it as an unlucky choice made long ago. After
> all, if you had "malloc_untracked" and "free_untracked" then it would be
> a simple matter to implement traditional C "malloc" and "free" on top of it.
>
>>
>> If you need a lot of a fixed sized blocks, there are lots of algorithms
>> that work well for that with much less or zero overhead (if the blocks
>> are big enough for a pointer)
>
> Yes, of course there are many ways of efficiently handling fixed size
> blocks. But it would be more convenient if the common heap system
> didn't have this particular inefficiency.
>

On 11/21/2021 9:51 PM, David Brown wrote:
> On 21/11/2021 19:32, Manfred wrote:
>> On 11/21/2021 2:51 PM, David Brown wrote:
>>> On 21/11/2021 02:44, Richard Damon wrote:
>>>> On 11/20/21 7:19 PM, Bart wrote:
>>>
>>>>> It doesn't make sense.
>>>
>>> I don't want to make a habit of it, but I agree with Bart here :-)
>>>
>>>>
>>>> Maybe not to you, but I would sure hate to have to keep track of all
>>>> that data, and would likely just wrap this dumb malloc with something
>>>> smarter.
>>>
>>> And that is /fine/.  For those few cases where it might be inconvenient
>>> to know the size at deallocation time, make a wrapper so that the size
>>> is tracked.  If you need that functionality, write the code and pay the
>>> price - others that don't need the heap to record their allocation sizes
>>> shouldn't have to pay for your needs.  It is no different from malloc
>>> and calloc - if you want the convenience of zeroing the memory, you can
>>> use calloc, but if you don't want it you can use malloc and not pay for
>>> the extra effort.
>>>
>>> Of course it is too late to make such untracked-size heap functions the
>>> standard for C - I see it as an unlucky choice made long ago.  After
>>> all, if you had "malloc_untracked" and "free_untracked" then it would be
>>> a simple matter to implement traditional C "malloc" and "free" on top
>>> of it.
>>
>> The problem I see with this is that it assumes one and only type of
>> metadata information to be associated to the pointer, specifically the
>> block size.
>
> No. It merely relieves the heap implementation from having to store the
> size of the allocation. Any other metadata (such as for tracking free
> space lists, or handling efficient multi-threaded access) will still be
> needed.

But it means that the implementation has to manage memory blocks based
on size instead of something else - if it had to store anything else
with the pointer, delegating the size to the programmer would be pointless
One alternative that pops to mind is a pointer to the next block,
however this might work, or nothing at all and a lookup table, or
anything else I couldn't think of right now, since I am not designing
the allocator, which the committee does not design either.
I think it makes sense that the language defines the interface strictly
to fulfill the requirements, and keep as much as possible of the design
internal to the implementation.

Moreover, the requested size (used by the user) may be different from
the actual size (used by the allocator), which poses some consistency
issues - but that's a side note.

>
>> I believe there are countless implementations of malloc out there, and I
>> guess this might not be the case, or it may be the case today but not
>> tomorrow.
>> The point is that if you set the interface to be pointer+size you also
>> put constraints on the implementation, on top of the extra burden for
>> the programmer.
>>
> How could this suggestion impose any constraints on the implementation?
> The interface for getting the memory is the same (albeit with a
> different name, in order to keep compatibility with existing code), and
> the interface for freeing memory gives the implementation more
> information. It would be perfectly possible (though a little unhelpful)
> for an implementation of the "_untracked" functions to be :
>
> #define malloc_untracked(size) malloc(size)
> #define free_untracked(ptr, size) free(ptr)
>
> An implementation can do better, given this new information, but there
> are no new limitations or restrictions.
>

Well, requiring the programmer to keep track of the block size is a
significant programming overhead - if it is unused, it's a significant
waste I'd rather not pay for.

Le 21/11/2021 à 21:51, David Brown a écrit :
> No. It merely relieves the heap implementation from having to store the
> size of the allocation. Any other metadata (such as for tracking free
> space lists, or handling efficient multi-threaded access) will still be
> needed.
>
>> I believe there are countless implementations of malloc out there, and I
>> guess this might not be the case, or it may be the case today but not
>> tomorrow.

Of all the typical implementations of malloc() and similar
general-purpose allocators, I've always seen the same approach of
storing metadata either right before (with then the appropriate padding
if required), or right after the actual usable block of memory. In a
number of cases, the metadata is even duplicated both before and after
the block - for data locality reasons. This can be more efficient
cache-wise.

On 22/11/2021 03:17, Manfred wrote:
> On 11/21/2021 9:51 PM, David Brown wrote:
>> On 21/11/2021 19:32, Manfred wrote:
>>> On 11/21/2021 2:51 PM, David Brown wrote:
>>>> On 21/11/2021 02:44, Richard Damon wrote:
>>>>> On 11/20/21 7:19 PM, Bart wrote:
>>>>
>>>>>> It doesn't make sense.
>>>>
>>>> I don't want to make a habit of it, but I agree with Bart here :-)
>>>>
>>>>>
>>>>> Maybe not to you, but I would sure hate to have to keep track of all
>>>>> that data, and would likely just wrap this dumb malloc with something
>>>>> smarter.
>>>>
>>>> And that is /fine/.  For those few cases where it might be inconvenient
>>>> to know the size at deallocation time, make a wrapper so that the size
>>>> is tracked.  If you need that functionality, write the code and pay the
>>>> price - others that don't need the heap to record their allocation
>>>> sizes
>>>> shouldn't have to pay for your needs.  It is no different from malloc
>>>> and calloc - if you want the convenience of zeroing the memory, you can
>>>> use calloc, but if you don't want it you can use malloc and not pay for
>>>> the extra effort.
>>>>
>>>> Of course it is too late to make such untracked-size heap functions the
>>>> standard for C - I see it as an unlucky choice made long ago.  After
>>>> all, if you had "malloc_untracked" and "free_untracked" then it
>>>> would be
>>>> a simple matter to implement traditional C "malloc" and "free" on top
>>>> of it.
>>>
>>> The problem I see with this is that it assumes one and only type of
>>> metadata information to be associated to the pointer, specifically the
>>> block size.
>>
>> No.  It merely relieves the heap implementation from having to store the
>> size of the allocation.  Any other metadata (such as for tracking free
>> space lists, or handling efficient multi-threaded access) will still be
>> needed.
>
> But it means that the implementation has to manage memory blocks based
> on size instead of something else - if it had to store anything else
> with the pointer, delegating the size to the programmer would be pointless

No, it does /not/ mean the implementation has to use the size. It means
it /can/ use the size - not that it has to!

And as I have said several times, and no one has (yet) given a
convincing counter-argument, the user code almost always knows the size
of the allocation already when it calls free. After all, it knows the
size when it allocates the memory, and it knows the size when it /uses/
the memory, so it's a tiny or non-existent cost to know the size when it
frees the memory.

>
> Moreover, the requested size (used by the user) may be different from
> the actual size (used by the allocator), which poses some consistency
> issues - but that's a side note.

The "free_untracked" implementation would match the "malloc_untracked"
algorithm - any changes made to the requested size (such as rounding up
to an allocation unit size) would be known to the "free" routine.

>
>>
>>> I believe there are countless implementations of malloc out there, and I
>>> guess this might not be the case, or it may be the case today but not
>>> tomorrow.
>>> The point is that if you set the interface to be pointer+size you also
>>> put constraints on the implementation, on top of the extra burden for
>>> the programmer.
>>>
>> How could this suggestion impose any constraints on the implementation?
>>   The interface for getting the memory is the same (albeit with a
>> different name, in order to keep compatibility with existing code), and
>> the interface for freeing memory gives the implementation more
>> information.  It would be perfectly possible (though a little unhelpful)
>> for an implementation of the "_untracked" functions to be :
>>
>>     #define malloc_untracked(size) malloc(size)
>>     #define free_untracked(ptr, size) free(ptr)
>>
>> An implementation can do better, given this new information, but there
>> are no new limitations or restrictions.
>>
>
> Well, requiring the programmer to keep track of the block size is a
> significant programming overhead - if it is unused, it's a significant
> waste I'd rather not pay for.

Does this mean you understand why this idea does not impose any
constraints on how the heap is implemented?

And can you give examples of where you have a pointer to a block of
memory but do not know the size of the memory?

On 22/11/2021 03:06, Guillaume wrote:
> Le 21/11/2021 à 21:51, David Brown a écrit :
>> No.  It merely relieves the heap implementation from having to store the
>> size of the allocation.  Any other metadata (such as for tracking free
>> space lists, or handling efficient multi-threaded access) will still be
>> needed.
>>
>>> I believe there are countless implementations of malloc out there, and I
>>> guess this might not be the case, or it may be the case today but not
>>> tomorrow.
>
>
> Of all the typical implementations of malloc() and similar
> general-purpose allocators, I've always seen the same approach of
> storing metadata either right before (with then the appropriate padding
> if required), or right after the actual usable block of memory. In a
> number of cases, the metadata is even duplicated both before and after
> the block - for data locality reasons. This can be more efficient
> cache-wise.

Have you considered the reason why such implementations need to store
such metadata at all?

Namely, because the specification says that malloc must record the size
simply so that free() will know what it is!

On 22/11/2021 02:17, Manfred wrote:
> On 11/21/2021 9:51 PM, David Brown wrote:

>> An implementation can do better, given this new information, but there
>> are no new limitations or restrictions.
>>
>
> Well, requiring the programmer to keep track of the block size is a
> significant programming overhead
Why is it a significant overhead for user-code, but not for the malloc
implementation?!

In any case, I've already mentioned some situations where there is
pretty much zero extra overhead for the programmer:

* When allocating a fixed sized struct or other fixed size type

* When allocating a block where the programmers needs to record the size
anyway

Or the programmer can determine the size:

* When allocating a zero-terminated string (they can use strlen if not
recording the size)

> - if it is unused, it's a significant waste I'd rather not pay for.

Exactly - it is an overhead of malloc that I'd rather not pay for either!

Just so programmers can do this:

p[i] = malloc(rand()); // or some varying size

....

free(p[i]);

I see that as a luxury in a lower-level language.

And also, goes against the 'spirit' of C where you are supposed to have
precise control over such things.

Potentially doubling (or sometimes quadrupling) heap memory usage for no
good reason sort of goes against that.

Bart <bc@freeuk.com> writes:
> On 22/11/2021 03:06, Guillaume wrote:
>> Le 21/11/2021 à 21:51, David Brown a écrit :
>>> No.  It merely relieves the heap implementation from having to store the
>>> size of the allocation.  Any other metadata (such as for tracking free
>>> space lists, or handling efficient multi-threaded access) will still be
>>> needed.
>>>
>>>> I believe there are countless implementations of malloc out there, and I
>>>> guess this might not be the case, or it may be the case today but not
>>>> tomorrow.
>>
>> Of all the typical implementations of malloc() and similar
>> general-purpose allocators, I've always seen the same approach of
>> storing metadata either right before (with then the appropriate
>> padding if required), or right after the actual usable block of
>> memory. In a number of cases, the metadata is even duplicated both
>> before and after the block - for data locality reasons. This can be
>> more efficient cache-wise.
>
> Have you considered the reason why such implementations need to store
> such metadata at all?
>
> Namely, because the specification says that malloc must record the
> size simply so that free() will know what it is!

There's no explicit requirement for free() to know the size of the
record being deallocated. It likely will in most implementations,
but I can imagine an implementation where deallocation doesn't
require knowing the size.

One example: malloc() may allocate more size than was asked for, and
remember only the actual allocated size, not the requested size.
Or the allocated size might change after allocation if a following
block is freed. (But realloc() does make it convenient to have some
idea of what was requested.)

Or malloc() and free() might be implemented on top of some lower
level interface that doesn't expose that information.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */