Browse Prior Art Database

Building a break table when the heap must be walked in the same direction as compaction is to be performed Disclosure Number: IPCOM000010941D
Original Publication Date: 2003-Feb-03
Included in the Prior Art Database: 2003-Feb-03
Document File: 2 page(s) / 59K

Publishing Venue



The literature describes the use of a break table for compaction of the Java heap. As described in the literature, the break table contains the accumulated amount of free space below an object an is used to compact the heap by moving objects to lower addresses. To gather such information efficiently it is necessary to walk the heap from low address to higher and it is quite common to be able to walk the heap in this direction only. It might seem that it is therefore only possible to build break tables for compaction downwards. In fact it is possible also to build a break table for compaction upwards, even when walking the heap from low to high, and this publication describes how to do so.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 2

  Building a break table when the heap must be walked in the same direction as compaction is to be performed

Disclosed is a method for using a break table to help compact a portion of the Java* heap, where it is only possible to walk the heap in the same direction as the compaction is to be performed.

     In the IBM** JVM every piece of storage in the heap, whether allocated or free, contains its own length as the first field. It is possible to "walk the heap" starting at the lowest point and stepping block by block to the top. It is only possible to walk the heap in this way from from low address to high. The use of break tables to perform compaction has been described before (see references below) and in all cases involves walking the heap from low address to high, and compacting by sliding objects in the opposite direction, downwards, from high address to lower. However it might be desirable to compact a section of the heap by sliding objects upwards instead from low address to higher.

     Partial compaction of the heap involves compacting only a section or sections of the heap at a time. The goal of compacting a section is to provide the largest possible chunks of free space to the allocator. If contiguous sections of the heap are compacted in the same direction (all objects slid in the same way) then large chunks of free space are accumulated at the top of each section. If adjacent sections are compacted in opposite directions (lower section slides objects down, upper section slides objects up) then the free space accumulated in each section will be adjacent and hence the free area will be in a larger chunk.

The diagram above depicts a region of the heap to be compacted. There are three blocks of allocated storage, each of which may contain a number of objects, and four stretches of free space. The areas are labelled with their lengths: l1, l2 and l3 for the allocated areas, and f1, f2, f3 and f4 for the stretches of free space.

     To compact the heap from right to left (i.e. from low addresses to high) the following break table is built which is searched from top to bottom to find how far to sli...