Brendan (btrotter.delete@this.gmail.com) on July 4, 2022 4:54 pm wrote:
> Hi,
>
> 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.
>
> - Brendan
>


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.


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.

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.


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.


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.