Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Garbage collections have to visit all objects that are alive, so as to find the memory that can be reclaimed. (Having many generations’ just delays this a bit)

All things being equal, it is clearly better to first visit the object that are already paged into RAM, before paging other block in and therefore paging out some object.

Anther possibility is that when the OS wishes to take a page of ram away from the process, the GC is first asked if it has a page that can be given up without needing to be paged out. The GC may be mostly done with moving objects from a page, so can clear that page within the time limit the OS has for needing a page.

Yet, I cannot recall any garbage collector that integrates with the OS paging system that drive the order the GC works in.

(Please can someone with enough rep create an garbagecollector tag)

share|improve this question
    
Why do you think that memory-management is not adapted to cover also garbage collection. There are many topics to be considered. –  babou Mar 15 at 15:52
    
@babou, I tend to think of memory-management as being what application programmer do (mostly badly) when using a language that does not have a garbage collector. –  Ian Ringrose Mar 15 at 15:57
    
I think you may be off by one syllable. As you are explicitly aware of, this is better called memory mismanagement. More seiously, memory management covers lots of issues, and no so much what application programmers do, imho. However, it could cover paging as well, and it does not. So I guess your request is not unfounded. The next question, though, is how often it would be used, based on past history of the site. I did not count precisely, but it seems to be on the order of 10 questions at the very best. –  babou Mar 15 at 16:41
    
Not exactly paging but the ruby enterprise edition gc was rewritten to reduce the gc's effect on copy on write pages by moving object meta-data on to separate pages. –  user1937198 Mar 15 at 23:02
    
Somewhat related question about malloc/free implementations: Will malloc implementations return free-ed memory back to the system?, particularly this answer. Also: Does free() unmap the memory of a process? –  Paul A. Clayton Mar 16 at 2:30

2 Answers 2

As I recall, copy collectors are supposed to be paging friendly, as the tracing by copying tends to improve the locality of pointer references. This has a positive effect on the program (mutator) that will cause less page faults when following links, and will also improve the next collection cycle as tracing will also cause less page faults. The tracing agenda (which pointers should be processed first) can have an impact on the effectiveness for improving data locality. This may be improved by mesuring statistics on the number of access to different pointers in different types of cells.

Now, if you consider a tracing collector in general, you must usually maintain a structure that keeps track of the pointers that have not been traced yet. It may be possible to organize this structure so that all waiting pointers pointing in the same page will be kept together (though that may take more space, in some cases, depending on the available techniques to keep the list of such pointers). A possible policy is then to always trace first the largest set of waiting pointers pointing to the same page, when there is no waiting pointer left to the pages in memory.

Regarding the question in the third paragraph, that was added after I answered, copy collection is again an answer. The OS may reduce the number of allocated physical pages at collection time, since the pages are completely freed. With a mark and sweep collector, the event of a full page beeing free is probably much rarer, thus not worth a specific machanism to be taken into account.

This kind of ideas is natural, and is probably described in some of the papers. But I do not recall it off hand. I think the early papers on Lisp GC contain some of these ideas (such as: should car or cdr be followed first?).

The good news in this role of copy-collection is also that paging is friendly to copy collection since it increases the available storage space. Recall that the copy collector requires in principle twice as much space as used for actual data storage. Now, the effect of paging depends also on the address space of the machine, and the physical memory available. In older computer, physical memory was much less than available address space, so that paging was really a space bonus, allowing policies such as copy GC. Even when physical space is as big as the address space, one might want to share it, so that the process using a GC would have less address space without paging (see paging). These remarks are somewhat superseeded by the use of generational collectors. They generally use copy collection for the young generation precisely because of these qualities, and because the young generation is mostly short lived.

Then you have all the interactions of generational GC with the cache system, that has been discussed in a previous question: Are generational garbage collectors inherently cache-friendly?

For more information on these issue, I would search the web with, for example, the keywords garbage collection and locality.

share|improve this answer

Emery Berger, Matthew Hertz & Yi Feng did some work on this.

Garbage collection offers numerous software engineering advantages, but interacts poorly with virtual memory managers. Existing garbage collectors require far more pages than the application's working set and touch pages without regard to which ones are in memory, especially during full-heap garbage collection. The resulting paging can cause throughput to plummet and pause times to spike up to seconds or even minutes.

I present a garbage collector that avoids paging. This bookmarking collector cooperates with the virtual memory manager to guide its eviction decisions.

This is a video of Emery’s talk on it, and he wrote a paper Garbage Collection Without Paging

For some reasons there does not seem to be much later work on it, or any “real world” usage. At the end of the paper it says “We are developing a concurrent variant of the bookmarking collection algorithm”, but I can’t track it down.

CRAMM: Virtual Memory Support for Garbage-Collected Applications looks at changing the OS to make GC create less paging.

share|improve this answer

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.