[Gc] RE: about bitmap marking

Boehm, Hans hans.boehm at hp.com
Mon Feb 27 15:30:50 PST 2012

> From: lijun [mailto:lijun at ialab.cs.tsukuba.ac.jp]
> I asked 2 questions (marked with 「★★」 ) 2 days ago.
> Do you also think so?
> Best regards.
> Li Jun
> -----Original Message-----
> From: lijun [mailto:lijun at ialab.cs.tsukuba.ac.jp]
> Sent: Sunday, February 26, 2012 4:35 PM
> To: 'Boehm, Hans'; 'boehm at acm.org'
> Cc: 'gc at linux.hpl.hp.com'
> Subject: RE: about bitmap marking
> > > In general, there are three advantages of using mark bit
> table(bitmap marking).
> > >+ it is friendly to copy-on-write.
> Probably.  The writes during marking are certainly better isolated.
> > >+ it helps to attain a higher locality of reference.
> ⇒① In some senses.  As I pointed out earlier, the main goal is to
> avoid
> touching pages containing pointer-free objects, which is a special kind
> of locality.
> > >+ in sweep phase, scanning/clearing the mark bit table is faster
> than
> > > scanning/clearing the mark bits in object headers because of
> putting the mark bits together.
> Right.  Kind of.  It makes it much faster to tell whether a page is
> entirely empty.  I'm not sure it helps when building a free list,
> since we write free-list links in any case.  The trade-off there may be
> complicated.
> >>so I want to know whether the implememtation of bitmap marking in
> boehm gc(gc6.8) has the advantages listed above if I use the default
> configuration(boehm gc 6.8).
> >> If I only use GC_malloc(not GC_malloc_atomic) to allocate memories,
> >> does the collector(boehm gc6.8) access pages containing pointer-free
> >> objects?
> ⇒②No, to first-order approximation.  (There are some minor
> exceptions.)  But performance-critical uses are likely to use
> GC_malloc_atomic.
> ★★From ①②、can I come to the following conclusion?
> a)Boehm gc(6.8) helps to attain a higher locality of reference in some
> senses(because boehm gc uses mark bit table(bitmap marking) as default)
> even if I only use GC_malloc(not GC_malloc_atomic) to allocate
> memories.
> b)Higher locality of reference maybe shorten the process time of gc.
Probably.  To answer this authoritatively would require some experiments.  Those may be difficult to carry out, since the separate mark bit table has influenced other parts of the design, notably the way in which the sweep phase works.

> >>You really need both pointer-free objects (to avoid having them
> scanned during a GC)
> >>and a separate mark-bit table (to avoid setting in-object mark bits
> during a GC)
> >>if you want to not touch objects during the GC.
> >>The combination means that often a significant fraction of heap pages
> can potentially remain paged out during a GC.
> ★★Can I come to the following conclusion?
> If I only use GC_malloc(not GC_malloc_atomic) to allocate pointer-free
> objects, boehm gc(6.8) will not touch those objects(pointer-free
> objects) because boehm gc uses mark bit table(bitmap marking) as
> default.
By "touch", I meant access at all.  If you only use GC_malloc, the collector will not know that those objects are pointer-free and hence will still have to trace them.  Thus the collector will need access to those pages, though it won't have to write to those pages while it's marking.  Thus the marker doesn't dirty pages, but it needs read access.  If you use GC_malloc_atomic, it doesn't need read access either, which is often a large win.


> Best regards.
> Li Jun

More information about the Gc mailing list