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.
>
> 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.
>

I implemented something like this, only as linked lists, on a PDP-11 in 1975.
It worked fine.