[gclist] write-barrier implementation in Java VM?

Fridtjof Siebert fridi@fridi.de
Wed, 8 Nov 2000 13:09:30 +0100

Dear Okehee,

>I am just curious if there is any known theory  or paper that explains
>incremental GC is not proper for small heap size system.

The overhead of incremental GC is typically that of

 a) write barrier code
 b) root scanning support
 c) incremental GC work

while for a blocking GC, the overhead is only

 d) blocking GC work.

a) and b) are typically independent of the heap size, while the amount of
incremental work c) is typically linear in the heap size or in the amount
of allocated memory. BTW, Several incremental GC implementations have a
quadratic worst case overhead for c), but I would not seriously consider
using such an implementation for any time-critical application.

For a blocking GC, d) is linear in the heap size or the amount of allocated.

So there is no fundamental difference between these two approaches when
regarding the total GC overhead for different heap sizes. The main
difference is the pauses you get when using blocking GC. Since the time
required for these pauses is linear in the heap size or amount of allocated
memory, these pauses might be more tolerable in small heap systems. But
when you think of embedded controllers, they often have small heaps but
also real-time requirements that are much more demanding than thos in a
desktop system.

>Do you have any idea how JVM's GC can support most devices which has small
>memory and requires real-time requirements?

I am working on an incremental GC for a real-time implementation of Java,
and we are using GC even for small heaps (small meaning between 256kB and
1MB). The collector is activated on allocation of an object and performs
some GC work to 'pay' for each allocation. For this GC work, a WCET can be
determined and it can be proven that the GC work is sufficent for the GC to
recycle sufficient memory (as long as the total amount of memory used by
the application is limited).

The highest cost of the implementation is the support for exact incremental
root scanning. This causes approx. 10% runtime overhead. The percentage of
time spent for GC itself largely depends on the application, with
allocation-intensive applications requiring more GC work.



Fridtjof Siebert                    E-Mail:   siebert@jamaica-systems.de
Jamaica Systems                     Phone:      office +49/721/78 18 611
Oberfeldstr. 34B                            university +49/721/60 87 358
76149 Karlsruhe, Germany            Home: http://www.jamaica-systems.de/