0

C++ has two main memory types: heap and stack. With stack everything is clear to me, but concerning heap a question remains:

How is heap memory organised? I read about the heap data structure, but that seems not the applicable to the heap, because in C++ I can access any data from the heap, not just a minimum or maximum value.

So my question is: how is heap memory organized in C++? When we read "is allocated on the heap" what memory organization do we have in mind?

trincot
  • 317,000
  • 35
  • 244
  • 286
Hate
  • 1,185
  • 3
  • 12
  • 24
  • 3
    C++ doesn't have a "heap" or "stack". C++ *implementations* often have a heap and stack, but the standard doesn't use the terms even once when talking about memory, AFAICR. – cHao Mar 09 '13 at 18:42
  • SO has an answer for you: [What and where are the stack and heap?](http://stackoverflow.com/questions/79923/) – masoud Mar 09 '13 at 18:46
  • The heap is general purpose memory. *Typically* the OS will split it into blocks for each application. You can access any memory within your own block, but access other memory and you get a SEGFAULT (for security). The memory is reserved with `malloc` (lots of things use `malloc` internally, like `new`), resized with `realloc` and released with `free`. If you try to malloc more memory than your application currently has available, the OS will usually provide more. Sometimes this means expanding into the hard-drive instead of RAM (a "swap file"), but sometimes there's just no space left. – Dave Mar 09 '13 at 18:47
  • *This article is about the programming data structure. For the dynamic memory area, see Dynamic memory allocation.* Have you followed that link? – n. m. could be an AI Mar 09 '13 at 18:48
  • @MM. one question there mention that heap is linked list, that seems like the answer my question – Hate Mar 09 '13 at 18:49
  • 1
    *The* heap is not the same as *my* implementation of a `heap` as a data structure which is what your article is referring to. The first sentence in your link says so. – ChiefTwoPencils Mar 09 '13 at 18:55
  • What is Wikipedia for? - http://en.wikipedia.org/wiki/Heap_memory#Implementations – SChepurin Mar 09 '13 at 19:09
  • Look up "Doug Lea Malloc" and read the comments. – brian beuning Mar 09 '13 at 19:15
  • Does this answer your question? [What's the relationship between "a" heap and "the" heap?](https://stackoverflow.com/questions/756861/whats-the-relationship-between-a-heap-and-the-heap) – trincot Jun 11 '22 at 11:23

4 Answers4

3

A common (though certainly not the only) implementation of the free store is a linked list of free blocks of memory (i.e., blocks not currently in use). The heap manager will typically allocate large blocks of memory (e.g., 1 megabyte at a time) from the operating system, then split these blocks up into pieces for use by your code when you use new and such. When you use delete, the block of memory you quit using will be added as a node on that linked list.

There are various strategies for how you use those free blocks. Three common ones are best fit, worst fit and first fit.

In best fit, you try to find a free block that's closest in size to the required allocation. If it's larger than required (typically after rounding the allocation size) you split it into two pieces: one to return for the allocation, and a new (smaller) free block to put back on the list to meet other allocation requests. Although this can seem like a good strategy, it's often problematic. The problem is that when you find the closest fit, the left-over block is often too small to be of much use. After a short time, you end up with a huge number of tiny blocks of free space, none of which is good for much of anything.

Worst fit combats that by instead finding the worst fit among the free blocks -- IOW, the largest block of free space. When it splits that block, what's left over will be as large as possible, maximizing the chance that it'll be useful for other allocations.

First fist just walks through the list of free blocks, and (as you'd guess from the name) uses the first block that's large enough to meet the requirement.

Quite a few also start with a search for an exact fit, and use that in preference to splitting a block.

Quite a few also keep (for example) a number of separate linked lists for different allocation sizes to minimize searching for a block of the right size.

In quite a few cases, the manager also has some code to walk through the list of free blocks, to find any that are right next to each other. If it finds them, it will join the two small blocks into one larger bock. Sometimes this is done right when you free/delete a block. More often, it's done lazily, to avoid joining then re-splitting blocks when/if you're using a lot of the same size of blocks (which is fairly common).

Another possibility that's common when dealing with a large number of identically-sized items (especially small ones) is an array of blocks, with a bitset to specify which are free or in use. In this case, you typically keep track of an index into the bitset where the last free block was found. When a block is needed, just search forward from the last index until you find the next one for which the bitset says the block is free.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
1

Heap has two main meanings with two different concepts:

  1. A data structure for arrange data, a tree.
  2. A pool of available memory. It manages memory by allocate/free available memory blocks.

An introduction about Heap in Memory Management:

The heap is the other dynamic memory area, allocated/freed by malloc/free and their variants....

masoud
  • 55,379
  • 16
  • 141
  • 208
0

Here heap doesn't mean the heap data structure. That memory is termed as heap memory where global, static variables are stored. Also when we allocate memory dynamically, it is allocated in the heap memory.

Uttam Malakar
  • 684
  • 1
  • 6
  • 15
0

When you read "allocated on the heap", that's usually an implementation-specific implementation of C++'s "dynamic storage duration". It means you've used new to allocate memory, and have a pointer to it that you now have to keep track of til you delete (or delete[]) it.

As for how it's organized, there's no one set way of doing so. At one point, if memory serves, the "heap" used to actually be a min-heap (organized by block size). That's implementation specific, though, and doesn't have to be that way. Any data structure will do, some better than others for given circumstances.

cHao
  • 84,970
  • 20
  • 145
  • 172