Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I understand the Heap memory divisions such as Young, tenured and Perm Gen. But I'm just curious from where is the memory used for performing the Garbage Collector itself? Is it from any of these memory spaces or in the thread stacks ?

share|improve this question
    
could help stackoverflow.com/a/2070994/169922 –  ZJR Nov 23 '12 at 2:37
    
Nice question, I like it! –  Chiron Nov 27 '12 at 12:19

4 Answers 4

up vote 4 down vote accepted

The answer depends on what you mean by "the memory used for performing the Garbage Collect[ion]" ... and what garbage collector you are talking about.

The general answer is that different garbage collection algorithms use space differently. This is a very high level / simplified summary:

  • Just about all garbage collectors make use of one or more "mark" bits in each object's header to record that the object has been processed by the GC.

  • Copying collectors work by copying live objects from a "from" space to a "to" space, and in the simple case don't need any extra space.

  • Mark / sweep collectors work by recursively walking the graph of "reachable" objects. The recursion can be done explicitly (which requires a separate stack), or by means of a clever pointer-reversal trick (look up Cheney's algorithm).

  • Concurrent collectors typically require extra memory to track objects that get mutated while the garbage collector is running.

There are whole books on the topic of garbage collection. If you want to really understand how garbage collectors work under the hood, you've got a lot of reading to do.


In general, any additional memory that the GC needs to do its job will typically be allocated outside of the live heap spaces. Thread stack memory is not used ... apart from the thread stack for the garbage collection thread or threads themselves.

Your mention of "young", "tenured" and "permgen" suggests that you are talking about classical Java GCs. These are generational collectors, which is a subtype of copying collectors.

share|improve this answer
    
Note that an object header need not be located in the object's memory. I know several memory management systems which store it (completely or partially) in separate tables. –  delnan Nov 23 '12 at 17:11
    
@Stephen C So the heap is not always divided as Young, tenured and Permgen ??? –  Siva Nov 24 '12 at 2:29
1  
@Siva - that is correct. Those are Hotspot specific concepts, and even within that context, specific garbage collectors don't necessarily work that way. –  Stephen C Nov 24 '12 at 2:33

Garbage Collectors perform a search of the program's heap from its GC Roots in order to identify what is live.

There's a cunning trick that you can perform when undertaking this task that avoids requiring any stack memory at all for the traversal. When doing a DFS at any given node you need to know what your predecessor node was, so your invert the pointers within the heap structure itself. For example, if your heap looks like this:

A -> B

B -> C

B -> D

And you search from A, to B, to C. You invert the pointers, so they'll look like this:

B -> A

C -> B

B -> D

That way when doing a garbage collection you can walk a graph of arbitrary size, whilst only needing a constant amount of memory to do so. You only need two pointers in memory in order to walk any graph: One to reference your current node, and one for siblings.

Its a pretty neat trick.

share|improve this answer
    
The assumption here is that it's a common trick that the JVM more than likely uses. –  Martijn Verburg Nov 23 '12 at 12:03

Because Java was designed around the idea of having a virtual machine, there really isn't a single, correct answer for this question.

The only certainty is that the VM will implement the instruction set correctly. There are two JVM instructions, new and newarray, that allocate space for objects and arrays. Anything beyond that is an implementation detail which is intended to remain hidden.

AlexGaynor's malloc() answer probably holds true in most implementations for POSIX-y environments (Unix, Windows, VxWorks, etc.), where the usual practice is for dynamically-allocated memory to be put on the host system's heap. Nothing in the JVM spec precludes implementations in other environments with other memory models:

The Java virtual machine assumes no particular type of automatic storage management system, and the storage management technique may be chosen according to the implementor's system requirements.

As long as the JVM implements something that appears to the Java program as a heap, all is good. The spec does explicitly state that there must be garbage collection, and on a hypothetical host with infinite memory, it would be completely unnecessary.

share|improve this answer

Any memory the GC itself needs to operate is either stack memory (for temporary computations it does), or from the "raw" heap, that is using the system malloc, or manually calling mmap.

share|improve this answer
    
I think the question is about Java garbage collection, not C or C++ –  Jay Elston Nov 23 '12 at 6:38
7  
@Jay Elson: I think Java garbage collection is usually implemented in C or C++ –  Michael Borgwardt Nov 23 '12 at 10:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.