RE: GC Trouble on Embedded System

["Boehm, Hans" <hans_boehm at hp dot com>]

A couple of more pieces of information:

1) Your test program completes with about 25 MB of heap on Linux/X86.  If anything, that's a bit less than
I would have expected in light of my earlier message.  If yours needs substantially more space,
it's worth looking for Windows CE specific issues.  I would make sure that the only growth is in
the garbage collected heap.  In particular it's worth looking at the root sizes in the GC_dump()
output.

2) If you're seeing similar results, and large objects are really important for you, you might
try building the collector with -DUSE_MUNMAP.  That should cause the collector to unmap pages
that are unused due to fragmentation, and thus mostly eliminate the fragmentation issue.
I'm not sure it's much of a win for more typical workloads.

Hans

> -----Original Message-----
> From: Boehm, Hans [mailto:hans_boehm@hp.com]
> Sent: Monday, July 21, 2003 2:54 PM
> To: 'Craig A. Vanderborgh'
> Cc: java@gcc.gnu.org
> Subject: RE: GC Trouble on Embedded System
> 
> 
> I'm in the process of building a current gcc3.4 tree so that 
> I can test this,
> as well as try some other patches.
> 
> The next debugging step is generally to look at GC_dump() 
> output at several
> points during the heap growth.
> 
> To be honest, if your application's allocation pattern looks like your
> test program's, I doubt you will be happy with the current 
> garbage collector,
> or any garbage collector that doesn't compact.  And you may 
> find compacting
> collectors atrociously slow on this kind of test.
> 
> There are two issues here that make this very hard, 
> especially for a nonmoving collector:
> 
> 1) The average object size if 750K.  This is several orders 
> of magnitude
> higher than most applications.  Any garbage collector will 
> basically require
> per object allocation + GC time that's proportional to the 
> average object size.
> Thus no collector is likely to process many allocations per 
> second with this
> kind of object size.  A conservative collector often runs 
> into trouble with this
> kind of object size, since it becomes hard to find contiguous 
> space that is
> not "referenced" by false pointers.
> 
> 2) The object sizes and lifetimes are random.  Garbage 
> collectors generally
> try to gain performance by taking advantage of regularity in 
> object sizes and
> lifetimes.
> 
> For any nonmoving allocator (garbage collector or not), the 
> worst-case fragmentation
> overhead is on the order of at least a factor of 
> log(max_obj_size/min_obj_size).
> (This is a 1971 theorem due to Robson.)  The optimum space 
> overhead in your case
> is on the order of a factor of 10.  For any realistic 
> nonmoving garbage collector,
> it is probably unrealistic to expect less than a factor of 30 
> or so in the worst case.
> (For malloc/free you might be able to get that down to a 
> factor of 20.)  Thus
> I wouldn't expect this to work absolutely reliably in less 
> than about 200MB of memory.
> 
> There is some argument that if you perform random allocation 
> operations for long
> enough, you will eventually hit the worst case.  I'm a little 
> surprised it gets large
> that quickly, and there may be other problems affecting this.
> 
> Having said that, I have never seen a real program with this 
> kind of allocation behavior.
> For real behavior, fragmentation overhead is typically less 
> than a factor of two, and
> in my experience good nonmoving collectors typically end up 
> using less space than a
> simple two space copying collector.
> 
> Hans
> 
> > -----Original Message-----
> > From: Craig A. Vanderborgh [mailto:craigv@voxware.com]
> > Sent: Sunday, July 20, 2003 12:42 PM
> > To: java@gcc.gnu.org
> > Subject: GC Trouble on Embedded System
> > 
> > 
> > Hello Everyone,
> > 
> > We are working on a port of GCJ/libgcj to the arm-wince-pe 
> > platform.  We
> > have the port working very well and it is now very close to 
> being able
> > to run our application.
> > 
> > However, we have run into big problems with the Boehm GC.  We have
> > created a very small but very nasty test of garbage collection that
> > isolates the problem we're having in the application to a 
> half-page of
> > very simple Java code.  This code is the GCTest class 
> > presented below. 
> > What it does to do some allocations of random length, keep 
> > references to
> > the allocations around in a Vector, and then release references to
> > allocations to keep the grand total of allocations below some
> > command-line-defined value.  Here is the GCTest:
> > 
> > import java.util.Vector;
> > 
> > public class GCTest {
> > 
> >   public static int maxNumAllocations = 10000;
> >   public static int maxAllocationSize = 1000000;
> >   public static int maxTotalAllocation = 10000000;
> > 
> >   public static void main(String[] argv) {
> > 
> >     Vector allocations = new Vector();
> >     int    grandTotalAllocated = 0;
> > 
> >     if (argv.length > 0) {
> >       maxNumAllocations = Integer.parseInt(argv[0]);
> >       if (argv.length > 1) {
> >         maxAllocationSize = Integer.parseInt(argv[1]);
> >         if (argv.length > 2) maxTotalAllocation = 
> > Integer.parseInt(argv[2]);
> >       }
> >     }
> > 
> >     int numAllocations = 0;
> >     int totalAllocation = 0;
> >     while (numAllocations < maxNumAllocations) {
> >       long allocationSize = Math.round(Math.random() * 
> > (double)maxAllocationSize);
> >       totalAllocation += allocationSize;
> >       while (totalAllocation > maxTotalAllocation) {
> >         int index = (int)(allocations.size() * Math.random());
> >         byte[] deallocation = (byte[])allocations.elementAt(index);
> >         totalAllocation -= deallocation.length;
> >         allocations.removeElementAt(index);
> >         System.out.println("Deallocated " + 
> > deallocation.length + " bytes, leaving " + totalAllocation + 
> > " bytes allocated in " + allocations.size() + " blocks");
> >       }
> >       byte[] allocation = new byte[allocationSize];
> >       allocations.addElement(allocation);
> >       numAllocations++;
> >       System.out.println("[" + numAllocations + "]: Allocated 
> > " + allocationSize + " bytes, for a running total of " + 
> > grandTotalAllocated + " bytes");
> >       grandTotalAllocated += allocationSize;
> >     }
> >   }
> > }
> > 
> > For the current discussion, I am running the test as:
> > 
> > GCTest 100000 1500000 6000000
> > 
> > The 3 arguments are:
> > 1. iterations
> > 2. max individual allocation permitted
> > 3. grand total (sum) allocation limit
> > 
> > Running on Windows CE 3.0 on my ipaq 3765, this test fails 
> gracefully
> > after about 65K iterations with a 
> java.lang.OutOfMemoryError.  Leading
> > up to this failure, I can see that the Java heap is growing without
> > bound.  Why would the above use of Java memory allocation cause
> > unbounded heap growth?  This seems wrong.
> > 
> > On other platforms, notably Xscale-based CE machines (instead of
> > StrongARM), the above test is producing "prefetch aborts" and "data
> > aborts".  In other words, low-level memory management 
> faults that kill
> > the process, or in many cases cause a system crash.
> > 
> > We are embarking on a project to debug the Boehm GC with a 
> view toward
> > achieving operation that is robust enough to handle a large 
> > application
> > like ours.  Any ideas on how to proceed would be greatly 
> appreciated. 
> > The first question is obviously - should the above GCTest 
> work without
> > heap growth?  And, if not, why would there be the kind of 
> heap growth
> > we're experiencing.  Fragmentation?
> > 
> > TIA,
> > craig vanderborgh
> > voxware incorporated
> > 
>