[gclist] write-barrier implementation in Java VM?

Fridtjof Siebert fridi@fridi.de
Wed, 8 Nov 2000 13:37:39 +0100

Here a small correction to what I just wrote:

> 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.

The time to complete one GC cycle is linear in the heap size or the amount
of allocated memory for c) and d). The total overhead for c) and d) instead
depends on how frequently a GC cycle needs to be completed, which depends
on the amount of allocation performed by the application and the ratio of
total heap size to reachable memory.

Assuming that the amount of reachable memory r is a constant fraction of
the heap size (say, 60%), at the latest after allocating 1-r (40%) of the
total heap size a GC cycle needs to be completed. Since the time required
for one cycle is linear in the heap size, and one cycle needs to be
completed while a certain fraction of the heap size is allocated (1-r), the
overhead per allocation for c) and d) is independent of the heap size.

(the situation is actually a bit more complex for the incremental case
since an incremental GC typically cannot guarantee to detect all garbage
that is generated during the current GC cycle, such that it is required to
complete 2 cycles while allocating the remaining 1-r (40%) of the total
heap size).

> 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/