Hi,

Adrian (a.delete@this.acm.org) on July 5, 2022 2:18 am wrote:
> Brendan (btrotter.delete@this.gmail.com) on July 4, 2022 4:54 pm wrote:
> > Adrian (a.delete@this.acm.org) on July 3, 2022 10:04 pm wrote:
> > > Foo_ (foo.delete@this.nomail.com) on July 3, 2022 2:45 am wrote:
> > > > Adrian (a.delete@this.acm.org) on July 1, 2022 9:58 pm wrote:
> > > > > Foo_ (foo.delete@this.nomail.com) on July 1, 2022 3:21 am wrote:
> > > > > > Adrian (a.delete@this.acm.org) on June 30, 2022 9:43 am wrote:
> > > > > > >
> > > > > > > When all the allocation and free requests are done from stacks, each stack corresponding
> > > > > > > to a certain size class, nothing ever changes from the point of view of fragmentation.
> > > > > >
> > > > > > This is delusional. Allocation may be done "from stacks", but given that deallocations
> > > > > > happen in random order (random from the POV of the allocator, of course), they
> > > > > > cannot be done in a simple stack-like (i.e. LIFO) fashion.
> > > > >
> > > > >
> > > > > When the size is variable, you are right.
> > > > >
> > > > > But when the size of a memory block is fixed (being used to satisfy any allocation
> > > > > requests between 2 thresholds), the allocations and deallocations are really
> > > > > done as LIFO from the stack containing the free memory blocks.
> > > >
> > > > You don't read what you reply to, do you?
> > > >
> > >
> > >
> > > Actually I have read carefully, but maybe I have not explained clearly enough.
> >
> > As far as I can tell, all of the confusion is caused by different definitions of "fragmentation".
> >
> > Specifically, you don't seem to distinguish between "fragmentation"
> > and "negative consequences of fragmentation".
> >
> > For example, your previous "Due to paging, which remaps the addresses, all pages become equivalent,
> > it does not matter which are allocated at a request. This reduces the memory allocation problem for
> > the OS to the simple case of allocations of fixed size, when there is no danger of memory fragmentation"
> > could/should be rephrased as "paging allows both allocated physical memory and free physical memory
> > to become extremely fragmented; but hides most of the negative consequences of fragmentation".
> >
> > Of course paging doesn't avoid all negative consequences of fragmentation - e.g. if you want to transfer
> > a larger amount of data to a device you have to split it into page sized pieces due to the fragmentation
> > of allocated physical memory; and if you want to support "hot-remove" RAM or merge many free smaller pages
> > back into a large free page then you end up needing a way to defragment part of physical memory.
> >
> > In the same way; you think that a stack of fixed sized objects avoids fragmentation of the underlying
> > (virtual) memory when it does not (and merely hides most of the negative consequences of fragmentation).
> > E.g. with a stack of fixed sized objects; if you allocate 1 million objects (asking OS for more virtual
> > memory when you run out) and then free every second object, you will be unable to return the unused
> > underlying (virtual) memory back to the OS because it has become extremely fragmented.
> >
> > In other words; from other people's perspective (mine), it seems like you're
> > wrong, and it seems like you don't know what "fragmented" means.
>
> I have already explained in the reply to someone else that I agree that the difficulty in
> returning unused heap memory to the operating system is also a kind of fragmentation.
>
> Nevertheless, this kind of fragmentation specific to stack-based heap implementation has
> a completely different behavior in comparison with the fragmentation of standard heaps.
>
> There should be 2 completely different words for them, as both the conditions that
> make them happen and the consequences of fragmentation are very different.
>
>
> What causes "fragmentation" to appear:
>
> For standard heaps: normal use of "malloc" and "free" with random sizes.
>
> For stack-based heaps: an extremely large number of allocations for small
> objects, much smaller than a memory page, followed by freeing most of them
> and followed by never requesting allocations in that size range again.

The standard heap has both causes. In other words, fragmentation is exactly the same (regardless of "stack vs. standard heap") in all possible cases (where "all possible cases" excludes the lone impossible case of allocating random sizes from a stack).


> What happens after "fragmentation" has occurred:
>
> For standard heaps: "malloc" requests for the same sizes that have succeeded before are
> no longer successful, unless the heap is extended with new memory pages from the OS.
> The heap memory previously used is definitively lost, unless for some reason the process
> begins to need a much larger number of small objects than it has needed before.
>
>
> For stack-based heaps: usually nothing happens for the process itself. However the process
> keeps occupied more memory than it needs, which can cause problems when new processes
> are started and they request memory from the OS, requests that may fail now.

For standard heap; the only case where you can free an area then fail to allocate a an area of the same size is if a different size (smaller) allocation allocated the memory you freed. For stack, in the same scenario it's the same - to satisfy the smaller allocation you allocate the previously freed area then waste RAM by padding the smaller size up to the stack's fixed size, and then the next allocation (the "next for the same size") fails.

However, if you free a large area, then try to allocate many tiny areas, there will be a difference - the stack will waste all the RAM for padding for the first tiny allocation and then fail to have RAM that wasn't wasted left over for the subsequent allocations.

In other words, its exactly the same (regardless of "stack vs. standard heap") in almost all possible cases (where "all possible cases" excludes the lone impossible case of allocating random "larger than stack's fixed size" sizes from a stack); except that stack can be much worse for "tiny allocations padded up to fixed block size".

> This condition can be easily detected in a server, by looking at the memory usage of the processes, where the
> processes holding too much memory are easily seen. The internal heap fragmentation causing memory unavailability
> in standard heaps is invisible, unless some diagnostic logging is incorporated in the offending program.

The only meaningful difference (which has nothing to do with fragmentation but relates to memory consumption) is that standard heap needs a little extra meta-data to keep track of allocated block sizes and determine how many bytes to free. Due to minimum alignment requirements this typically means 16 bytes extra memory consumed per allocation.

> So in my opinion it is very wrong to use the same name for these 2 states,
> even if I do not know which would be the best alternative words for them.

In my opinion; there's no need for alternative words when something is exactly the same in all possible cases (where "all possible cases" excludes the lone impossible case of allocating random "larger than stack's fixed size" sizes from a stack).

> My initial comment, which started this subthread, was meant to say that the second kind of "fragmentation",
> if you want to call it so, is both far less likely to occur in any application, and even if it
> occurs it is easily detected and corrected by restarting the daemon/service.
>
> That is why stack-based heap implementations are much better for daemons/services, i.e.
> processes that must have a long lifetime, sometimes even up to several years (I have, like
> many others, servers where the time between successive reboots is usually much longer than
> a year), even if such heap implementations may be non-optimal for other purposes.

There's a strong argument for having special case allocators for special cases (instead of a generic allocator that can't be optimize for any specific special case). The problem is that it becomes too inflexible unless you're willing to have multiple/many special case allocators.

Note: My project uses something part way between - a "pool_number = create_pool(pool_name, type, max_objects, object_size);" and then a "pointer = alloc_from_pool(pool_number, name, size);", with 3 different types of pools (raw memory, stack and heap). The original intent was to improve locality (data that's used at the same time in the same general area, not intermingled with all other data), limit memory leaks (prevent one bug from gobbling all memory for other things), allow debugging (e.g. get a list of "123 KiB used for 456 blocks of 'foo'" entries from a pool), allow the pool to be destroyed (instead of having to free each individual scrap), and allow "thread local pools" that are auto-destroyed when a thread terminates. It's nice, except for the added burden of keeping track of which pool things were allocated from.

- Brendan