Hi,

⚛ (0xe2.0x9a.0x9b.delete@this.gmail.com) on July 4, 2022 5:34 am wrote:
> Brendan (btrotter.delete@this.gmail.com) on July 2, 2022 1:56 pm wrote:
> > ⚛ (0xe2.0x9a.0x9b.delete@this.gmail.com) on July 2, 2022 3:12 am wrote:
> > > Brendan (btrotter.delete@this.gmail.com) on June 30, 2022 4:08 pm wrote:
> > > > ⚛ (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%).
> >
> > This is the fragmentation you get for current/normal systems that don't make
> > any attempt to compute the deallocation order, as a baseline for comparison.
> >
> > > > ... 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).
> >
> > Why do I care if the sequence "malloc(2nd); do_millions_of_other_things(); malloc(3rd)" is "uninterruptible
> > unless it's interrupted"? If the system isn't using page tables (and has no "paging tricks") and
> > is using linear physical RAM; that gap caused by fragmentation that you failed to avoid means that
> > you're wasting extra physical RAM while you're doing millions of other things.
> >
> > If you compare this to the "current/normal system baseline" (which has an equal amount of fragmentation
> > at a different time, and an equal risk of wasting physical RAM due to fragmentation) it's easy to
> > see that your attempt to compute the complete deallocation order has achieved nothing.
> >
> > > 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.
> >
> > No. This only makes sense if you use word games to deceive people. For example;
> > instead of calling it a "gap caused by fragmentation" you can call it "pre-allocated
> > before its needed memory that isn't actually being used (but isn't free)".
> >
> > Of course you can also use word games to deceive people for the baseline - instead of freeing memory
> > just call it "allocated but unused memory that's waiting to be recycled (that isn't free)".
> >
> > > 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.
> >
> > Translation: It's so horrifically broken that you can't do anything between 2 completely
> > unrelated memory allocations (on top of the original impracticality of computing the complete
> > deallocation order, especially in non-deterministic multi-threaded systems).
> >
> > > 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.)
> >
> > Another way of thinking of it is that it's a deluded joke that achieves nothing while creating massive
> > additional headaches. Tell me, what do you think happens for "malloc(1st); malloc(2nd); realloc(1st)"?
>
> I do not reply to ridicules and do not reply to hate speeches.
>
> The ideas presented in your responses are too simple.
>
> You haven't even figured out yet that any new theory in _most
> cases_ redefines the meaning of past/established terms.
>
> It is curious/unfortunate that you are incapable of answering the question of "What do you think
> happens for "malloc(1st); malloc(2nd); realloc(1st)" by yourself. The answer is trivial.

Claiming "the answer is trivial" to avoid providing an answer won't obscure the fact that your post deserves ridicule. To obscure your shame you should've pretended your mistake was a joke and claimed "Poe's law"; but it's too late for that to be plausible now - you will forever remain the person who seriously believed what you've suggested.

- Brendan