Brendan (btrotter.delete@this.gmail.com) on July 4, 2022 6:33 am wrote:
> 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

You haven't posted anything that would indicate you understand the subject of my posts. Either present something of equivalent complexity - or do not post anything.

-atom