Fragmentation: Both Size and Lifetime

By: (0xe2.0x9a.0x9b.delete@this.gmail.com), July 4, 2022 6:35 am
Room: Moderated Discussions
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
< Previous Post in ThreadNext Post in Thread >
TopicPosted ByDate
Linear Address Spaces: Unsafe at any speed [article]Kester L2022/06/29 12:49 PM
  Linear Address Spaces: Unsafe at any speed [article]Rayla2022/06/29 01:14 PM
    Linear Address Spaces: Unsafe at any speed [article]Kester L2022/06/29 01:43 PM
      Not just worse-is-betterMark Roulo2022/06/29 02:21 PM
        Not just worse-is-better---2022/06/29 06:07 PM
  Linear Address Spaces: Unsafe at any speed [article]2022/06/29 11:08 PM
    Linear Address Spaces: Unsafe at any speed [article]Groo2022/06/30 11:56 AM
      Linear Address Spaces: Unsafe at any speed [article]Michael S2022/06/30 01:17 PM
  Linear Address Spaces: Unsafe at any speed [article]Eric Fink2022/06/30 12:43 AM
  Linear Address Spaces: Unsafe at any speed [article]dmcq2022/06/30 02:17 AM
  Linear Address Spaces: Unsafe at any speed [article]Adrian2022/06/30 04:36 AM
    Linear Address Spaces: Unsafe at any speed [article]anonymou52022/06/30 06:28 AM
      Linear Address Spaces: Unsafe at any speed [article]Anon42022/06/30 03:37 PM
        Linear Address Spaces: Unsafe at any speed [article]anonymou52022/06/30 05:19 PM
          Linear Address Spaces: Unsafe at any speed [article]dmcq2022/07/01 03:16 AM
            Linear Address Spaces: Unsafe at any speed [article]anonymou52022/07/01 04:40 AM
              Linear Address Spaces: Unsafe at any speed [article]dmcq2022/07/01 05:11 AM
                Linear Address Spaces: Unsafe at any speed [article]anonymou52022/07/01 07:09 AM
              Linear Address Spaces: Unsafe at any speed [article]dmcq2022/07/01 05:11 AM
                Why the duplicates?dmcq2022/07/01 05:18 AM
              Linear Address Spaces: Unsafe at any speed [article]2022/07/01 09:41 PM
    Linear Address Spaces: Unsafe at any speed [article]Foo_2022/06/30 06:43 AM
      Fragmentation: Both Size and LifetimeMark Roulo2022/06/30 07:25 AM
        Fragmentation: Both Size and Lifetime2022/06/30 09:09 AM
          Fragmentation: Both Size and Lifetimedmcq2022/06/30 10:12 AM
          Fragmentation: Both Size and LifetimeBrendan2022/06/30 03:08 PM
            Fragmentation: Both Size and Lifetime2022/07/02 02:12 AM
              Fragmentation: Both Size and LifetimeBrendan2022/07/02 12:56 PM
                Fragmentation: Both Size and Lifetime2022/07/04 04:34 AM
                  Fragmentation: Both Size and LifetimeBrendan2022/07/04 05:33 AM
                    Fragmentation: Both Size and Lifetime2022/07/04 06:35 AM
                      Fragmentation: Both Size and LifetimeBrendan2022/07/04 03:21 PM
                    Atom is just living at the Dunning-Krueger peakHeikki Kultala2022/07/04 08:26 AM
                      Atom is just living at the Dunning-Krueger peak2022/07/04 08:57 AM
      Linear Address Spaces: Unsafe at any speed [article]Adrian2022/06/30 07:31 AM
        Linear Address Spaces: Unsafe at any speed [article]Foo_2022/06/30 08:07 AM
          Linear Address Spaces: Unsafe at any speed [article]Adrian2022/06/30 08:43 AM
            Linear Address Spaces: Unsafe at any speed [article]Foo_2022/07/01 02:21 AM
              Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/01 08:58 PM
                Linear Address Spaces: Unsafe at any speed [article]Foo_2022/07/03 01:45 AM
                  Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/03 09:04 PM
                    Linear Address Spaces: Unsafe at any speed [article]ananon2022/07/04 01:35 AM
                    Linear Address Spaces: Unsafe at any speed [article]Foo_2022/07/04 02:11 AM
                      Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/05 12:36 AM
                    Linear Address Spaces: Unsafe at any speed [article]2022/07/04 03:18 AM
                    Linear Address Spaces: Unsafe at any speed [article]TAG2022/07/04 06:50 AM
                    Linear Address Spaces: Unsafe at any speed [article]Brendan2022/07/04 03:54 PM
                      Linear Address Spaces: Unsafe at any speed [article]Brendan2022/07/04 04:05 PM
                      Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/05 01:18 AM
                        Linear Address Spaces: Unsafe at any speed [article]Brendan2022/07/06 04:16 PM
                          Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/06 11:33 PM
        Linear Address Spaces: Unsafe at any speed [article]2022/06/30 09:40 AM
    Linear Address Spaces: Unsafe at any speed [article]---2022/06/30 07:28 AM
      Linear Address Spaces: Unsafe at any speed [article]Michael S2022/06/30 12:00 PM
    Linear Address Spaces: Unsafe at any speed [article]Jörn Engel2022/06/30 04:34 PM
      Linear Address Spaces: Unsafe at any speed [article]Adrian2022/06/30 11:55 PM
        Sorry, typo correctionAdrian2022/07/01 12:04 AM
        Linear Address Spaces: Unsafe at any speed [article]2022/07/01 03:01 AM
          Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/01 10:00 PM
            Linear Address Spaces: Unsafe at any speed [article]rwessel2022/07/02 06:16 AM
        Linear Address Spaces: Unsafe at any speed [article]Jörn Engel2022/07/01 08:40 AM
          Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/01 10:15 PM
  Linear Address Spaces: Unsafe at any speed [article]Brendan2022/06/30 10:09 AM
    Linear Address Spaces: Unsafe at any speed [article]dmcq2022/06/30 10:20 AM
      Linear Address Spaces: Unsafe at any speed [article]Brendan2022/06/30 02:52 PM
        Linear Address Spaces: Unsafe at any speed [article]dmcq2022/07/01 05:06 AM
          Linear Address Spaces: Unsafe at any speed [article]Brendan2022/07/01 12:24 PM
            Linear Address Spaces: Unsafe at any speed [article]rwessel2022/07/01 07:55 PM
  Linear Address Spaces - Free lunch?Björn Ragnar Björnsson2022/07/02 05:44 PM
    Linear Address Spaces - Free lunch?dmcq2022/07/03 03:30 AM
      Linear Address Spaces - Free lunch?Björn Ragnar Björnsson2022/07/03 03:50 PM
  Linear Address Spaces: Unsafe at any speed [article]Paul A. Clayton2022/07/18 06:49 AM
    Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/18 09:21 AM
      Linear Address Spaces: Unsafe at any speed [article]Brendan2022/07/18 02:11 PM
        Linear Address Spaces: Unsafe at any speed [article]anon22022/07/18 03:54 PM
          Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/18 09:22 PM
            Linear Address Spaces: Unsafe at any speed [article]Michael S2022/07/19 12:00 AM
              Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/19 04:50 AM
        Linear Address Spaces: Unsafe at any speed [article]Adrian2022/07/18 10:02 PM
          Linear Address Spaces: Unsafe at any speed [article]Brendan2022/07/19 07:29 PM
Reply to this Topic
Name:
Email:
Topic:
Body: No Text
How do you spell tangerine? 🍊