[Gc] RE: about bitmap marking

Boehm, Hans hans.boehm at hp.com
Mon Feb 20 23:21:13 PST 2012


> 
> Thank you for your reply.
> 
> You emphasized that the main goal of keeping mark bits in a separate
> region(mark bit table) is to avoid touching pages containing pointer-
> free objects.
> 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.
> 
> Is the following conclusion correct?
> ・In essence, Not GC_malloc_atomic but mark bit table(keeping mark bits
> in a separate region, even if I use the default configuration) avoids
> touching pages containing pointer-free objects during a GC,
> but if I use GC_malloc_atomic to allocate pointer-free or untraced
> memory, I can obtain better performance.
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.

Hans
> 
> Best regards.
> Li jun
> 
> -----Original Message-----
> From: Hans Boehm [mailto:Hans.Boehm at hp.com]
> Sent: Sunday, February 19, 2012 4:26 AM
> To: lijun
> Cc: 'Boehm, Hans'; boehm at acm.org; gc at linux.hpl.hp.com
> Subject: RE: about bitmap marking
> 
> 
> 
> On Sat, 18 Feb 2012, lijun wrote:
> 
> >
> > I sent 2 emails 2 days ago, but I didn’t get an answer.
> >
> >
> >
> > Can you tell me whether the implememtation of bitmap marking in boehm
> > gc(gc6.8) has the advantages listed in my previous email(February 16,
> 2012
> > 1:52 AM) if I use the default configuration(boehm gc 6.8).
> >
> >
> >
> > >>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.
> 
> >
> > >>(the collector will run faster because of having a mark bit
> table)
> >
> > >>
> >
> > >>There are several differences between the usual bitmap marking
> and that
> > of boehm gc
> >
> > >>(For example, because each page has a separate mark bit table in
> boehm
> > gc, in most cases, there are many mark bit tables in the collector.),
> I'm not sure that matters much for the issues you brought up.  The mark
> bit tables tend to be in adjacent sections of memory.
> 
> >
> > >>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).
> Generally yes.  But the fact that you're not touching pointerfree
> objects
> is probably still the most important one.
> 
> Hans
> >
> >
> >
> > Best regards
> >
> > Li Jun
> >
> >
> >
> >
> >
> > From: lijun [mailto:lijun at ialab.cs.tsukuba.ac.jp]
> > Sent: Thursday, February 16, 2012 1:52 AM
> > To: 'Boehm, Hans'; 'boehm at acm.org'
> > Cc: 'gc at linux.hpl.hp.com'
> > Subject: RE: about bitmap marking
> >
> >
> >
> > <this is a continuation of the mail sent 2 hours ago>
> >
> >
> >
> > In general, there are three advantages of using mark bit table(bitmap
> > marking).
> >
> > + it is friendly to copy-on-write.
> >
> > + it helps to attain a higher locality of reference.
> >
> > + 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.
> >
> > (the collector will run faster because of having a mark bit table)
> >
> >
> >
> > There are several differences between the usual bitmap marking and
> that of
> > boehm gc
> >
> > (For example, because each page has a separate mark bit table in
> boehm gc,
> > in most cases, there are many mark bit tables in the collector.),
> >
> > 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).
> >
> >
> >
> > Best regards
> >
> > Li Jun
> >
> >
> >
> >
> >
> > From: lijun [mailto:lijun at ialab.cs.tsukuba.ac.jp]
> > Sent: Thursday, February 16, 2012 12:39 AM
> > To: 'Boehm, Hans'; 'boehm at acm.org'
> > Cc: 'gc at linux.hpl.hp.com'
> > Subject: RE: about bitmap marking
> >
> >
> >
> > Because each page has a separate mark bit table, in most cases, there
> are
> > many mark bit tables in the collector.
> >
> >
> >
> > If I use the default configuration, the mark bit tables(gc6.8) help
> to
> > attain a higher locality of reference? (in comparison with not using
> the
> > mark bit tables)
> >
> >
> >
> > In sweep phase(gc6.8, default configuration), the collector will run
> faster
> > because of having mark bit tables?
> >
> > (scanning/clearing the mark bit tables is faster than
> scanning/clearing the
> > mark bits in object headers because of putting the mark bits
> together?)
> >
> >
> >
> > Best regards
> >
> > Li Jun
> >




More information about the Gc mailing list