Brendan (btrotter.delete@this.gmail.com) on June 30, 2022 4:08 pm wrote:
> Hi,
>
> ⚛ (0xe2.0x9a.0x9b.delete@this.gmail.com) on June 30, 2022 10:09 am wrote:
> > Mark Roulo (nothanks.delete@this.xxx.com) on June 30, 2022 8:25 am wrote:
> > > Foo_ (foo.delete@this.nomail.com) on June 30, 2022 7:43 am wrote:
> > > > Adrian (a.delete@this.acm.org) on June 30, 2022 5:36 am wrote:
> > > > >
> > > > > In the memory allocators used by individual processes it is possible to completely avoid
> > > > > memory fragmentation, e.g. by using separate memory pools for different object sizes.
> > > >
> > > > That doesn't make sense. Memory fragmentation is typically caused by differing
> > > > *lifetimes* of heap allocations, not by differing object sizes.
> > > >
> > >
> > > It is both.
> > >
> > > All the allocations the same size (e.g. 1KB) mean there is no
> > > fragmentation because if you have enough memory for all your
> > > objects then there will be a slot. You won't have a situation
> > > where you need 1KB, have 5KB, but the 5KB is unusable because it
> > > is in 100 discontiguous 50B pieces.
> > >
> > > Alternately, if one wants to allocate a large number of randomly
> > > sized objects and then free them all at once (and you know this ...)
> > > then you can avoid fragmentation by simply allocating "from the end"
> > > and freeing by "resetting the 'next'" pointer.
> > >
> > > The intersection of different sizes and different lifetimes (and
> > > not knowing them up front ...) creates the fragmentation.
> >
> > Ok ... so, in my not-so-humble-this-time opinion, both mentioned explanations about the "alleged" primary
> > cause of memory fragmentation are actually invalid. The real/actual reason for memory fragmentation is
> > the impossibility of computing the time-order of deallocations
> > _before_ those deallocations are actually/physically
> > executed. In cases in which it is possible - at the _allocation_ point - to compute the _deallocation_
> > order, memory fragmentation either does not occur or does
> > not need to occur (unless, of course, the programmer
> > decides for fragmentation to occur on purpose because of some strange reason).
> >
> > The viewpoint that "memory fragmentation is caused by differences
> > in sizes of objects" and the viewpoint that
> > "memory fragmentation is caused by differing lifetimes of
> > objects" are both limited/restricted viewpoints. The
> > latter viewpoint is in my opinion slightly more accurate,
> > but only slightly. The viewpoint that "there is some
> > 'fundamental link' between [memory fragmentation] and [having multiple allocation pools instead of a single
> > pool, or in reverse, having a single pool instead of multiple pools]" is a limited viewpoint as well.
> >
> > In summary: If the _deallocation_ order was computable in advance in all cases, then it would be
> > possible to always _allocate_ memory in a way that is optimized in respect to the ordering.
>
> It doesn't solve fragmentation and just shifts the problem to a different time.
>
> If I allocate 3 things one at a time then free the middle one; it must be either
> fragmented after I free the middle one ("1st 2nd 3rd" becomes "1st gap 3rd"), or
> fragmented before I allocate the third one ("1st gap 2nd" becomes "1st 3rd 2nd").

You haven't computed the complete deallocation order of those 3 things (100%) - you computed the deallocation order of 1 of those 3 things (33%).

> ... or fragmented before I allocate the third one ("1st gap 2nd" becomes "1st 3rd 2nd").

"1st gap 2nd" is an impossible/unreachable state. From the viewpoint of the memory allocator, the next state after "1st gap gap" is "1st 3rd 2nd" because it has already computed that if the program reaches "1st gap gap" then the program will _inevitably_ call malloc(2nd), then malloc(3rd), then free(2nd), then free(3rd), and then free(1st).

The sequence "malloc(2nd); malloc(3rd)" is uninterruptible (unless, of course, the program is interrupted from outside of the program, such as: by the operating system, by a user/developer, by a power supply failure).

A measurement of the program's memory allocation layout cannot display "1st gap 2nd" because the memory allocator jumps from state "1st gap gap" directly to state "1st 3rd 2nd" without an intermediate state.

Another way of thinking about it is that "malloc(2nd); malloc(3rd)" is a fused statement, analogical to CMP+Jcc being a fused instruction in recent x86 CPUs, but with the extension that the memory allocator will treat it as a fused statement even if the actual sequence of the statements in the program's source code was "malloc(2nd); print(foo); malloc(3rd)". This is because from the viewpoint of the memory allocator the statement "print(foo)" is a NOP, assuming the print() function isn't making any requests to the memory allocator.

Another way of thinking about it is that malloc(3rd) will be executed by the memory allocator in an out-of-order fashion.

It is observable/measurable that the program has allocated memory sooner than expected (i.e: temporary memory overallocation until other parts of the program catch up to the state predicted by the memory allocator), but it isn't observable/measurable that there the program's memory is fragmented.

(In the above, I am assuming that "1st gap gap" (with a contiguous sequence of gaps on its right side till its right edge) is equivalent to "1st nothing nothing" and has zero fragmentation.)

-atom