United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-6725714 par compact - add a table to speed up bitmap searches
JDK-6725714 : par compact - add a table to speed up bitmap searches

Details
Type:
Enhancement
Submit Date:
2008-07-15
Status:
Resolved
Updated Date:
2013-11-15
Project Name:
JDK
Resolved Date:
2013-05-31
Component:
hotspot
OS:
generic
Sub-Component:
gc
CPU:
generic
Priority:
P3
Resolution:
Fixed
Affected Versions:
hs14
Fixed Versions:
hs25 (b36)

Related Reports
Backport:
Backport:
Backport:
Backport:
Backport:
Backport:
Backport:
Relates:
Relates:

Sub Tasks

Description
The parallel compacting collector (par compact, or par old) uses a table to track data about contiguous regions of the gc heap such as how much data is live in the region, whether a live object crosses onto the region, etc.  Each region is currently fairly small to limit the portion of the marking bitmap that must be searched to compute the new (after compaction) location of an object.  Regions could be made significantly larger (100x or more) by adding a very small table which holds data about object starts.  Making regions larger would shrink the size of the data used by par compact, would translate directly into speed ups of phases that operate on regions, and may also speed up pointer updates by reducing the length of bitmap searches.

                                    

Comments
EVALUATION

The additional table, likely to be called the Block table, would have one entry for each heap Region (formerly called a Chunk; see 6725697).  Each entry would hold a non-negative integer which is the amount of data in the Region that is to the left of the first object that starts in the Block.  When updating pointers, the length of the bitmap that would have to be searched is then determined by the Block size (likely 128 words or 256 words), instead of the Region size.  This allows regions to become much larger, reducing data overhead since each Region table entry contains 5 or 6 word-sized fields.  For a Region size of up to 64K, the Block table can be an unsigned short (16 bits).

The problem is filling in the new table.  A single-threaded pass over the bitmap is simple, but would take too long and limit scalability.  A parallel pass over the bitmap would be significantly better, but has the downside of introducing an additional barrier sync and would also spend time updating portions of the block table that would never be used (because the region contains a large array and so no object starts within the region).  Filling the table lazily during compaction implicitly parallelizes it and avoids filling unused sections, but requires synchronization when filling sections of the table or runs the risk of some sections being filled more than once; lazy filling also adds a branch to the very hot pointer update path.
                                     
2008-07-15
The implementation under development increases the region size to 64K words, which allows the block table elements to be unsigned short.  This reduces the size of the main data structures used for compaction (the sum of region table size + block table size) by ~74%.  Since the data structures are sized based on the java heap size, the reduction amounts to ~1.1% of the heap size.
                                     
2013-05-23
URL:   http://hg.openjdk.java.net/hsx/hotspot-gc/hotspot/rev/5534bd30c151
User:  jcoomes
Date:  2013-05-31 01:39:12 +0000

                                     
2013-05-31
URL:   http://hg.openjdk.java.net/hsx/hsx25/hotspot/rev/5534bd30c151
User:  amurillo
Date:  2013-06-07 19:51:24 +0000

                                     
2013-06-07



Hardware and Software, Engineered to Work Together