Linear Address Spaces: Unsafe at any speed [article]

By: Adrian (a.delete@this.acm.org), July 5, 2022 1:36 am
Room: Moderated Discussions
Foo_ (foo.delete@this.nomail.com) on July 4, 2022 3:11 am wrote:
> Adrian (a.delete@this.acm.org) on July 3, 2022 10:04 pm wrote:
> >
> > The reason why this is possible is that when a new "malloc" invocation happens (for
> > a given size range), it will be possible to satisfy the request by pulling the last
> > freed memory block from the list of free memory block, because it has the same size.
>
> Sure. But that only happens *when* a new malloc invocation for the same size occurs. You are assuming
> that N frees for a given size are always followed, in very short order, by N mallocs for that size.
>
> That's an idealistic view of long-running applications or servers, which may match the behaviour
> of some of them, but is certainly not the norm. Most systems responding to outside requests will
> be faced with bursts of activity followed by quietness periods; they will also be faced - more or
> less sporadically - with unusually long-running requests due to degraded conditions (e.g. network
> connectivity blips), which will still complicate the temporal distribution of memory activity.


No, in a real "malloc" implementation of this type, a new "malloc" request always has the same size as the last "free" invocation.

The reason why this is true is that the stream of "malloc" requests is demultiplexed into multiple streams of "malloc" invocations, each stream corresponding to a fixed size range.

For the allocation requests that fall in a size range, a free memory block having a size equal to the upper limit of the range is returned.

Therefore, all the malloc requests within a range are equivalent with requests for a single size, the maximum size of that range.

So the heap is not implementing as a single stack, but as a set of stacks, e.g. 1 stack for requested sizes between 255 bytes and 512 bytes, 1 stack for requested sizes between 513 bytes and 1024 bytes, and so on.

For large sizes, the thresholds between size ranges are typically chosen to be 1 per octave, but for small sizes, e.g. under 512 bytes, it may be better to choose 2 to 4 size ranges per octave, to avoid wasting too much heap memory for the most frequent allocation requests.


The stream of "malloc" and "free" requests that reach the same stack are equivalent with requests for a fixed size (the upper limit of the range), so the last freed block is always the first allocated again.

The streams of requests that are demultiplexed to be handled by different stacks are completely independent, so the order in which the requests with different sizes had been interleaved at their origin does not matter at all.

The demultiplexing of the request streams can be optimized to be done in constant time, by replacing the comparison of the requested size with the many thresholds separating the size ranges with bit string operations, i.e. with a LZCNT instruction to determine the octave where the size belongs, optionally followed by 1 or by 2 additional bit tests (no branches are needed to construct the index of the stack), when 2 or 4 size ranges per octave are desired instead of 1 size range per octave.

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