By: Adrian (a.delete@this.acm.org), July 3, 2022 10:04 pm
Room: Moderated Discussions
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.
Even when the "free" invocations happen in a random order compared with the corresponding "malloc" invocations, if the size of the allocation requests is the same (in practice it is enough for the size to belong to a certain range, for which the allocation requests are satisfied using free memory blocks of the same size), then the memory allocator can make the allocation and freeing actions for memory blocks in a last-in-first-out-manner, which allows the implementation of the heap as a stack (in practice as a set of stacks, corresponding to the set of size ranges).
The reason why this is possible is that when a new "malloc" invocation happens (for a given size range), it will be possible to satisfy the request by pulling the last freed memory block from the list of free memory block, because it has the same size.
It does not matter to which previous "malloc" the last "free" corresponded. The last freed block will always be good for the next "malloc", so it will be the first to be allocated again.
This contrasts with the standard heap implementation, where in order to satisfy a new "malloc" request, the heap must be searched to find a memory block whose size matches the new "malloc" and that will be a block who might have been freed a long time ago, and many other "malloc" and "free" invocations might have happened since that time. With this kind of heap, what you have written, i.e. "they cannot be done in a simple stack-like (i.e. LIFO) fashion", is definitely true.
With a heap implemented as a set of stacks, corresponding to size ranges, that phrase is false, because the memory blocks are always freed, then allocated, in a LIFO manner, more precisely in a last-freed-first-allocated manner.
This simplification of a heap into a stack is possible only for memory blocks of the same size, which makes them equivalent.
> 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.
Even when the "free" invocations happen in a random order compared with the corresponding "malloc" invocations, if the size of the allocation requests is the same (in practice it is enough for the size to belong to a certain range, for which the allocation requests are satisfied using free memory blocks of the same size), then the memory allocator can make the allocation and freeing actions for memory blocks in a last-in-first-out-manner, which allows the implementation of the heap as a stack (in practice as a set of stacks, corresponding to the set of size ranges).
The reason why this is possible is that when a new "malloc" invocation happens (for a given size range), it will be possible to satisfy the request by pulling the last freed memory block from the list of free memory block, because it has the same size.
It does not matter to which previous "malloc" the last "free" corresponded. The last freed block will always be good for the next "malloc", so it will be the first to be allocated again.
This contrasts with the standard heap implementation, where in order to satisfy a new "malloc" request, the heap must be searched to find a memory block whose size matches the new "malloc" and that will be a block who might have been freed a long time ago, and many other "malloc" and "free" invocations might have happened since that time. With this kind of heap, what you have written, i.e. "they cannot be done in a simple stack-like (i.e. LIFO) fashion", is definitely true.
With a heap implemented as a set of stacks, corresponding to size ranges, that phrase is false, because the memory blocks are always freed, then allocated, in a LIFO manner, more precisely in a last-freed-first-allocated manner.
This simplification of a heap into a stack is possible only for memory blocks of the same size, which makes them equivalent.
