Linear Address Spaces: Unsafe at any speed [article]

By: rwessel (rwessel.delete@this.yahoo.com), July 2, 2022 6:16 am
Room: Moderated Discussions
Adrian (a.delete@this.acm.org) on July 1, 2022 11:00 pm wrote:
> ⚛ (0xe2.0x9a.0x9b.delete@this.gmail.com) on July 1, 2022 4:01 am wrote:
> >
> > The worst-case scenario for the memory allocator you are describing IS NOT when first allocating
> > 1_000_000 objects of the same size and then deallocating 999_999 of those objects. The reason
> > for that is that the pattern remaining after deallocation of the 999_999 objects - which
> > leaves only 1 object allocated - has a very low descriptive complexity.
> >
> > The worst-case scenario is: allocate 1_000_000 objects and then use an RNG (random number generator) to
> > deallocate 500_000 randomly selected objects. The reason why this is the worst-case scenario is that the
> > resulting sequence of 0 and 1 (zeroes and ones, or it can
> > be interpreted as boolean values) is incompressible
> > (assuming we want to avoid re-running the RNG every time a malloc() or free() is called to serve additional
> > allocation/deallocation requests after the 500_000 deallocations finish executing).
>
>
> No, maybe I have not explained clearly, but this case, with 1 million allocated objects then half of
> them, randomly chosen, being deallocated, is not the worst case. Moreover, it is not a bad case at
> all, but one in which such a memory allocator behaves perfectly, with no performance degradation.
>
> The case described by you is precisely the one that is the worst for a standard
> malloc implementation, being the most likely to cause heap fragmentation.
>
> On the other hand, when the heap is implemented as a set of stack containing the free memory blocks,
> each stack (implemented as a linked list) being dedicated to provide memory blocks of a fixed size,
> which are used to satisfy memory requests between 2 thresholds, e.g. 48-byte memory blocks for satisfying
> all the malloc calls with sizes from 33 to 48 bytes, then it becomes completely irrelevant in which
> order the "free" calls are done and which happened to be the freed allocations.
>
> The case described for you is bad only when the malloc and free calls attempt to resize the memory blocks, by
> dividing a larger block to better match the requested malloc size, or attempting to coalesce the freed block
> with another. Both these kinds of resizing attempts require searches through the heap, searches that may be unsuccessful
> and whose chances of failure increase with the number of random "free" calls that have happened.
>
> In contrast, when the heap is implemented with stacks, there are no searches through
> the heap and there is only one possible failure mode for "malloc": stack empty for
> the requested size. That is solved by requesting one or more memory pages from the
> OS, making free memory blocks out of them and pushing them in the empty stack.
>
>
>
>
>
> >
> > Basically, you are claiming that if a program has for example reached a point/state
> > in which it has the following counts and sizes of memory allocated (COUNT*SIZE):
> >
> > 4*AA 3*BBBB 1*CCCCCCCC
> >
> > then the memory layout (=L1):
> >
> > AA .... AA .... AA .... AA ....
> >
> > BBBB .... BBBB .... BBBB ....
> >
> > CCCCCCCC ....
> >
> > somehow results in lower _total_ memory consumption compared to a memory layout (=L2) such as:
> >
> > AA .... BBBB .... AA .... BBBB .... AA .... CCCCCCCC .... BBBB .... AA ....
> >
> > There exist many "...." regions in both cases. So, please post a sufficiently thorough explanation
> > why you believe that the combined/total memory usage of those "...." is lower in the memory
> > allocator layout L1 you are defending here and is higher in allocator L2.
> >
> > The main advantage of L1 over L2 isn't lower memory fragmentation - the main advantage
> > is that L1 can fulfill a request in O(1) time, but L2 requires O(log(N)) time.
> >
> > -atom
>
>
> First of all I have not defended the malloc implementation where the heap is implemented as a set
> of stacks in general, I have repeatedly stressed that this style of allocator is the best for long-lived
> processes, i.e. daemons/services, where it guarantees no performance degradation even after years
> of uptime, but it definitely is not the best kind of malloc implementation in other cases.
>
>
> There is no doubt that the total memory usage is worse for the
> stack-based allocator and this is its main disadvantage.
>
> The higher memory usage is mainly due to the allocated blocks being larger than the requested sizes in
> many cases, though this can be tuned for specific applications by choosing appropriate thresholds for
> the sizes so that the most frequent allocations will not need overhead. The size of each memory block
> is also increased by one pointer needed to allow linking into the stack, but that pointer can be used
> to point to a descriptor while the block is allocated, which can contain other information, like the
> size, which is also needed by most other malloc algorithms, so that may mean just an extra 4 bytes versus
> the other malloc algorithms, i.e. not all 8 bytes of the pointer are additional overhead.
>
>
> The "malloc" and "free" times for the stack-based allocator are almost constant for most invocations, i.e.
> almost O(1), consisting of making a push or a pop in a stack (i.e. only one link manipulation), and the
> stack that must be used is found in constant time by one LZCNT instruction when there is one stack per octave
> of malloc requested size. An extra stack per octave needs just one more bit test instruction.
>
> A "malloc" can occasionally request memory from the OS, but this becomes more and more rare after startup. "free"
> (or "malloc" or both, depending on an implementation choice) might need very seldomly a long time, only if the
> allocator is written to make attempts to detect the case when no allocation requests have been made in a long
> time with certain sizes and there is much memory in the stacks that could be returned to the OS.
>
>
> So regarding the execution times, no other kind of "malloc" can do better than this, therefore the choice
> between others and the stack-based heap implementation is mainly a choice between efficient use of heap memory
> versus guarantees of no performance degradation in time together with optimal times for malloc/free.
>


One problem with that sort of allocator is that you still "fragment" real/physical memory (and virtual address space, although that less of an issue on 64-bit machines), since pages can't generally be returned to the OS. It's rare, and relatively hard* to detect, that all entries on a page are empty, so that the page itself can be freed. That's not a problem if the usage of objects of size X is relatively constant over time, but once you allocate enough pages for a million of these objects, you're probably going to be stuck with a million objects worth of pages - and real/physical memory - until the program ends, even if you free most of those individual objects.


*In terms of overhead - it certainly can be done.
< 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? 🍊