Talk:Dynamic memory allocation

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Two meanings of heaps[edit]

Can someone please expand the section "Heap-based memory allocation"? How exactly is the Heap data structure utilized in it? thx!

It isn't! Just a coincidence in naming. Good point. Usually the heap is based on one of the discussed allocation algorithms such as free lists or the buddy system. Deco 01:53, 29 December 2005 (UTC)
Do we know of the history of why it got to be called 'heap' instead of an infinite number of other things and who was the person or company who used the term heap first?
The oldest reliable source is probably Donald E. Knuth's TAOCP Vol. 1, which says Several authors began about 1975 to call the pool of available memory a "heap." But in the present series of books, we will use that word only in its more traditional sense related to priority queues. --Cubbi (talk) 19:33, 30 August 2011 (UTC)
I'm guessing now, but the terms could be related: A simple implementation of the (memory allocation) heap is to represent the set of free blocks using a (max-)heap data structure, where the keys are block sizes. Allocation is greedy: Take the largest free block (top of the heap), allocate a sufficient portion of it, and perform decrease-key on the top of the heap. To deallocate memory, just add it to the heap. With this method, allocation and deallocation is simple and fast, but it probably gives huge problems with memory fragmentation. --Erik 16:18, 10 February 2006 (UTC)
That is an interesting point. But yes, consistently allocating from the largest block seems doomed to cause rapid fragmentation. However, although I don't have a source on this, historically I believe the terms both originated from the English concept of a heap of stuff, rather than having any relation to one another. Deco 18:40, 10 February 2006 (UTC)

please give me about heap memory allocation and deallocation explanation with example use of garbage collection.


My comment: This needs more description of specific designs and algorithms, for example, best-fit vs first-fit, free-lists vs rovers, linked-lists vs trees vs cells for space management, ...

Clearly there is a lot more that needs mention here than what is present. Cr88192 22:10, 12 May 2007 (UTC)

I agree. I just was searching for information on the so called worst-fit and best-fit algorithms. There were two redundant portugese pages on worst fit, and the german version of this page had some information, but no information on the english page about these different allocation algorithms. —Preceding unsigned comment added by (talk) 18:24, 26 October 2009 (UTC)


  • From this article:

Buddy block allocators are used both in real-time operating systems and in general-purpose operating systems (such as Microsoft Windows and Linux).

Compared to the memory allocation techniques (such as paging) that modern operating systems such as Microsoft Windows and Linux use, the buddy memory allocation is relatively easy to implement, and does not have the hardware requirement of a memory management unit (MMU).

  • So is it or isn't it used? -- 09:35, 23 September 2007 (UTC)
  •  :Its context dependant i thik. (talk) 14:58, 25 February 2008 (UTC)
Both are true. Large-scale modern OSs have multiple allocators, at the least one for the kernel and one for every process. Each uses its own system of allocation. The wording could be corrected to clarify this (e.g., "are one type of allocator used in"). Dcoetzee 22:45, 25 February 2008 (UTC)
  • Automatic allocation, especially of arrays with run-time bounds, is a subset of dynamic allocation. The introductory paragraphs have been modified to take that into consideration. The page on automatic allocation is no help at all. Gah4 (talk) 23:52, 10 June 2008 (UTC)


The section headed "Details" is very terse, uses sentence fragments, and is not very clear. It should be cleaned up a bit. —Preceding unsigned comment added by (talk) 15:34, 2 September 2009 (UTC)

Fundamental Error[edit]

In this article 'dynamic memory allocation' is described as heap-based, and is contrasted with static allocation. However, stack-based memory allocation is also dynamic. Does this article need renaming, or should there be substantial addition of stack-based allocation? Murray Langton (talk) 12:22, 23 June 2010 (UTC)

Stack based memory allocation is usually referred to as 'automatic'. I don't think there is any confusion with dynamic v. static which is the base of the article. karl m {{User electrical engineer}} (talk) 23:06, 23 June 2010 (UTC)

The title of this article is 'dynamic memory allocation'. Stack-based allocation is dynamic (as the program runs). So the article should cover both stack and heap allocation. The fact that stack allocation is also 'automatic' (behind the scenes, not under explicit user control) doesn't alter the fact that it is dynamic. Murray Langton (talk) 14:53, 24 June 2010 (UTC)