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.

share|improve this question
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 '14 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 '14 at 2:30
surprisingly, afaik/ afaict, nearly all (?) gc literature does not seem to analyze OS paging except abstractly. idea: a memory allocation system that keeps track of pointers between objects in a structure separate from the objects themselves might be more local/ paging friendly because only the pointers themselves are traversed (during gc) in a tightly compacted space instead of all the objects of varying sizes that may be spread out in memory (and some infrequently accessed & so paged). there might be some modest overhead but it might work out to savings overall depending on implementation. –  vzn Apr 29 at 1:46
Flash drives need to use a form of copying garbage collection which takes into account the arrangement of memory into blocks, though I don't know how well such things are discussed in academic literature. The problems to be solved there are very different (flash drives need GC because space can only be recycled in very large blocks, so if a block has a few live pages and lots of dead pages, the live data must be copied elsewhere before the page can be recycled) but the principles of consolidating data could be helpful. –  supercat Jun 27 at 17:35
A pattern I've used in cases where data items were all small relative to my memory-chunk size was to have each data item consist of a fixed-sized header which was allocated front-to-back, and variable-sized data which would be allocated back-to-front. A table kept mapped logical chunk addresses to physical addresses and the amount of free space in each chunk; after each scan it would also identify how much space was dead. References were stored in flash, and each reference had the form "Item #3 of logical chunk #7". A GC cycle would copy all live data from one chunk to a new one, and... –  supercat Jun 27 at 17:44

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
am dubious of the idea of copy collectors actually being more "local" than tracing. copy collectors seem conceptually quite similar in memory access dynamics (maybe nearly indistinguishible) to tracing over the "old space". think this needs a reference. that said there is some possibility of the copy mechanism improving contiguity in the new space. the new space starts out perfectly contiguous, but then this "locality" decreases or degrades over time. –  vzn Apr 24 at 5:28
Well, you found most of the answer. So do not be dubious. It is in the basic references on the topic. Locality from the fact that storage is compacted, and from the copying that replace close to each other data cells that are logically close according to pointer structure (which may evolve with pointer reassignment). –  babou Apr 24 at 5:46
am still skeptical/ dubious. it seems intuitively the old space will have poor locality and/or contiguity when the copy/ gc cycle is initiated. locality is related to reads (from the old space) and writes (to the new space). to analyze it, the gestalt/ emergent behavior has to be studied. possibly much of this can only be effectively/ accurately/ realistically studied empirically & not a lot theoretically. –  vzn Apr 24 at 5:48
I am saying it is in the literature, like many other things. But I do not have time to search for it and I think my answer is long and crammed with information., You can google: garbage collection copy locality, and there is a reference to a previous question. Sorry for being terse, got a train to catch. –  babou Apr 24 at 5:54
Sorry ... confuse this question with another... that has more. –  babou Apr 24 at 6:01

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


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.