0

My understanding is that memory allocated on the free store (the heap) should grow upwards as I allocate additional free store memory; however, when I run my code, occasionally the memory location of the next object allocated on the free store will be a lower value. Is there an error with my code, or could someone please explain how this could occur? Thank you!

int main()
{
    int* a = new int(1);
    int* b = new int(1); 
    int* c = new int(1);
    int* d = new int(1);
    cout << "Free Store Order: " << int(a) << " " << int(b) << " " << int(c) << " " << int(d) << '\n';
    // An order I found: 13011104, 12998464, 12998512, 12994240

    delete a;
    delete b;
    delete c;
    delete d;

    return 0;
}
woodwardsquidward
  • 3
  • 1
  • 3
    *My understanding is that memory allocated on the free store (the heap) should grow upwards as I allocate additional free store memory;* -- Where did you get this information from? – PaulMcKenzie May 03 '20 at 01:37
  • Your understanding about the heap is wrong. – drescherjm May 03 '20 at 01:39
  • Actually, the heap for dynamically allocated memory is limited. Therefore, if you don't use the memory anymore, you should free it out. – Hoang Nam May 03 '20 at 01:39
  • @OP [Memory algorithms](https://en.wikipedia.org/wiki/Memory_management#ALLOCATION). – PaulMcKenzie May 03 '20 at 01:43
  • 1
    The order in which chunks of dynamically allocated memory are organised in memoy are not specified. In fact, you can't rely on any particular relationship between two allocated blocks. – Peter May 03 '20 at 01:43

1 Answers1

3

The main problem with that code is that you are casting int * to int, an operation that may lose precision, and therefore give you incorrect results.

But, aside from that, this statement is a misapprehansion:

My understanding is that memory allocated on the free store (the heap) should grow upwards as I allocate additional free store memory.

There is no guarantee that new will return objects with sequential addresses, even if they're the same size and there have been no previous allocations. A simple allocator may well do that but it is totally free to allocate objects in any manner it wants.

For example, it may allocate in a round robin method from multiple arenas to reduce resource contention. I believe the jemalloc implementation does this (see here), albeit on an per-thread basis.

Or maybe it has three fixed-address 128-byte buffers to hand out for small allocations so that it doesn't have to fiddle about with memory arenas in programs with small and short-lived buffers. That means the first three will be specific addresses outside the arena, while the fourth is "properly" allocated from the arena.

Yes, I know that may seem a contrived situation but I've actually done something similar in an embedded system where, for the vast majority of allocations, there were less than 64 128-byte allocations in flight at any given time.

Using that method means that most allocations were blindingly fast, using a count and bitmap to figure out free space in the fixed buffers, while still being able to handle larger needs (> 128 bytes) and overflows (> 64 allocations).

And deallocations simply detected if you were freeing one of the fixed blocks and marked it free, rather than having to return it to the arena and possibly coalesce it with adjacent free memory sections.

In other words, something like (with suitable locking to prevent contention, of course):

def free(address):
    if address is one of the fixed buffers:
        set free bit for that buffer to true
        return
    call realFree(address)

def alloc(size):
    if size is greater than 128 or fixed buffer free count is zero:
        return realAlloc(size)
    find first free fixed buffer
    decrement fixed buffer free count
    set free bit for that buffer to false
    return address of that buffer

The bottom line is that the values returned by new have certain guarantees but ordering is not one of them.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • Thank you so much! I'd seen a few sources that describe the heap generally growing upwards (now, re-reading those sources, they seem to use poor wording). Additionally, a question in my textbook implied that the heap grows in a certain direction. Your answer is explicit and has cleared up any questions in my mind. And yes good point - casting the 'int *' to an 'int' may lose precision, so I will remove that casting. – woodwardsquidward May 03 '20 at 01:55
  • 1
    @woodwardsquidward You may be confused with the *stack* memory growing upwards or downwards. For the stack, there really is no choice but to hand a higher / lower address because -- it's a stack. – PaulMcKenzie May 03 '20 at 01:57
  • 1
    @woodwardsquidward: many *do* have the heap growing upward but that's really to do with expanding the heap itself. It tends to start at address N and be a certain size. If you exhaust it, it can ask for more memory and that will be placed at the end so as to not invalidate any pointers in use already. In other words, it affects the growth of the heap but not necessarily the order of things handed out from the heap. – paxdiablo May 03 '20 at 01:58