DOC PREVIEW
vee05

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Using Page Residency to Balance Tradeoffsin Tracing Garbage CollectionDaniel Spoonhower∗[email protected] [email protected] [email protected] of Computer ScienceCarnegie Mellon UniversityPittsburgh, PA 15213ABSTRACTWe introduce an extension of mostly copying collection thatuses page residency to determine when to relocate objects.Our collector promotes in place pages with high residency,avoiding unnecessary work and wasted space. It predicts theresidency of each page, but when its predictions prove to beinaccurate, our collector reclaims unoccupied space by usingit to satisfy allocation requests.Using residency allows our collector to dynamically bal-ance the tradeoffs of copying and non-copying collection.Our technique requires less space than a pure copying col-lector and supports object pinning without otherwise sacri-ficing the ability to relocate objects.Unlike other hybrids, our collector does not depend onapplication-specific configuration and can quickly respondto changing application behavior. Our measurements showthat our hybrid performs well under a variety of conditions;it prefers copying collection when there is ample heap spacebut falls back on non-copying collection when space becomeslimited.General Termsalgorithms, languages, measurement, performanceCategories and Subject DescriptorsD.3.2 [Programming Languages]: Language Classifica-tions—C#; D.3.4 [Programming Languages]: Proces-sors—Memory management (garbage collection)Keywordspredicted residency, fragmentation, compaction, pinning∗This work was supported by a Microsoft Graduate Fellow-ship and a generous gift from Microsoft.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.VEE’05, June 11-12, 2005, Chicago, Illinois, USA.Copyright 2005 ACM 1-59593-047-705/0006 ...$5.00.1. INTRODUCTIONGarbage collectors in modern virtual machines must sat-isfy the demands of both a high-level language and a nativeruntime implementation. While the former takes an abstractview of memory, the latter requires a transparent interfacewhere the position and layout of heap objects are made ex-plicit. To interoperate with existing libraries, many lan-guages also provide foreign function interfaces (e.g. Haskell[10], Java [27]). Each of these imposes constraints on howgarbage can be collected, for example by limiting when ob-jects can be relocated.In this work, we explore the tradeoffs of tracing garbagecollection. We show how the two simplest forms of trac-ing collection, mark-sweep and semi-space collection, com-plement each other not only in terms of their benefits andcosts, but also in their approaches to reducing fragmenta-tion. We observe that there is a smooth continuum of trac-ing collectors that spans both mark-sweep and semi-spacecollection and use this insight to design a garbage collectorthat combines these two techniques dynamically. We haveimplemented our collector as part of a virtual machine forC# [19] and measure the overhead of the collector for sev-eral benchmarks. Our experiments show that our collectormimics the behavior of either a copying or a non-copying col-lector depending on which would yield better performance.Many collectors combine copying and non-copying collec-tion by grafting several smaller heaps together and usinga different technique to manage each heap. For example,large objects are often relegated to a separate heap that ismanaged using a mark-sweep collector [29, 9]. In additionto size, objects in these separate heaps may also be distin-guished using profiling information [12, 5].Some generational collectors [22, 28] also combine copyingand non-copying collection by distinguishing objects basedon their age and using different techniques for the nurseryand the older generations. Generational collectors improvecollector performance in two ways. First, they improve la-tency (on average) by performing partial traversals of theheap during minor collections. Second, they may improvethroughput by focusing on portions of the heap that containfew reachable objects: if the (weak) generational hypothesisholds, most objects will die young and the nursery will berelatively sparse.Bartlett’s mostly copying collector [3] combines copyingand non-copying collection to support compaction in an en-vironment with ambiguous roots (i.e. where the types ofroots are unknown). It divides the heap into a set of pagesand uses a different technique for each page depending onthe presence of one or more ambiguous roots.Mostly copying collection forms the foundation for ourwork. Unlike hybrid collectors where each portion of theheap is statically configured to use either copying or non-copying collection, our collector allows the technique usedto manage each page to vary from one collection to the next.Instead of “syntactic” properties such as size or alloca-tion point, our collector relies on page residency to deter-mine which pages should be managed using copying collec-tion and which using non-copying collection. Since residencyreflects the runtime behavior of the mutator, we claim thatour collector can adapt more easily to shifting memory usagepatterns.Although age has been shown to be a good indicator of theexpected lifetime of young objects [18], we count age as onlyone of many predictors of residency. To take advantage ofthe relationship between age and expected lifetime, genera-tional collectors must group objects of similar age together.The generational hypothesis implies that the residency ofthe nursery will be low because the nursery contains onlyyoung objects. We present a set of heuristics for predictingresidency in Section 4 and a description of our algorithm inSection 5.The experiments described in Section 6 show that ourcollector performs well under a variety of conditions usinga single configuration. For example, our collector makeseffective use of space regardless of the overall residency ofthe heap.In this work, we focus primarily on the tradeoffs of trac-ing collection and on improving collector throughput. Weextended our hybrid collector with a form of replicating in-cremental collection [24] to improve its latency,


vee05

Download vee05
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view vee05 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view vee05 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?