Hi,

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.

To bring this back into context (replacing linear address spaces with object stores); object stores do have fragmentation of free physical memory and it can not be avoided; and the consequences of this fragmentation are that you need to be able to defragment physical memory by moving/copying/relocating objects from one physical address to another. This (relocating objects) translates directly into unavoidable extra overhead.

- Brendan