How to implement a memory heap

Question

Wasn't exactly sure how to phrase the title, but the question is:

I've heard of programmers allocating a large section of contiguous memory at the start of a program and then dealing it out as necessary. This is, in contrast to simply going to the OS every time memory is needed. I've heard that this would be faster because it would avoid the cost of asking the OS for contiguous blocks of memory constantly.

I believe the JVM does just this, maintaining its own section of memory and then allocating objects from that.

My question is, how would one actually implement this?

Answer 1

Most C and C++ compilers already provide a heap memory-manager as part of the standard library, so you don't need to do anything at all in order to avoid hitting the OS with every request.

If you want to improve performance, there are a number of improved allocators around that you can simply link with and go. e.g. Hoard, which wheaties mentioned in a now-deleted answer (which actually was quite good -- wheaties, why'd you delete it?).

If you want to write your own heap manager as a learning exercise, here are the basic things it needs to do:

• Request a big block of memory from the OS
• Keep a linked list of the free blocks
• When an allocation request comes in:
  • search the list for a block that's big enough for the requested size plus some book-keeping variables stored alongside.
  • split off a big enough chunk of the block for the current request, put the rest back in the free list
  • if no block is big enough, go back to the OS and ask for another big chunk
• When a deallocation request comes in
  • read the header to find out the size
  • add the newly freed block onto the free list
  • optionally, see if the memory immediately following is also listed on the free list, and combine both adjacent blocks into one bigger one (called coalescing the heap)