JDK-4667078 : REGRESSION: OutOfMemoryError in Graphics2D.fill(Area) on Win2K
  • Type: Bug
  • Component: client-libs
  • Sub-Component: 2d
  • Affected Version: 1.4.0,1.4.1
  • Priority: P4
  • Status: Open
  • Resolution: Unresolved
  • OS: windows_2000
  • CPU: x86
  • Submitted: 2002-04-12
  • Updated: 2009-06-06
Related Reports
Relates :  
Description
Name: gm110360			Date: 04/11/2002


FULL PRODUCT VERSION :
java version "1.4.0"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.0-b92)
Java HotSpot(TM) Client VM (build 1.4.0-b92, mixed mode)

FULL OPERATING SYSTEM VERSION : Microsoft Windows 2000
[Version 5.00.2195] Service Pack 2 Build 2195


EXTRA RELEVANT SYSTEM CONFIGURATION :
C Drive Free space 120MB
RAM: 326,192KB

A DESCRIPTION OF THE PROBLEM :
I had created a small program to draw shapes and create
images. It was working fine on jdk 1.3.1. The sample
program that i have attached works on 1.3.1 with following
resource usage:

52% - 90% - 10% - 00% CPU usage
8,292K Memory

On jdk 1.4.0 it gives a OutofMemory Exception after using:
55% - 90% - 99% CPU
74,764K Memory

I found the problem is in the clip() method.

REGRESSION.  Last worked in version 1.3.1

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
1. javac Test.java
2. java Test
3. Check Memory and CPU Usage
4. Compare it with jdk 1.3.1

EXPECTED VERSUS ACTUAL BEHAVIOR :
I expect it to take very less resources as in jdk 1.3.1

The results i saw: In a system having low virtual memory
you get java.lang.OutOfMemoryError

ERROR MESSAGES/STACK TRACES THAT OCCUR :
java.lang.OutOfMemoryError

This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.awt.*;
import java.awt.geom.*;

public class Test extends Frame  {
  
  
  public Test()  {
    super("Test");
    setSize(300,300);
    show();
  }
  
  public static void main(String args[])  {
    Test t = new Test();
  }
  
  public void paint(Graphics g)  {
    Graphics2D g2 = (Graphics2D)g;

    float dash[] = new float[2];
    dash[0] = 3.0f;
    dash[1] = 7.0f;

    Rectangle2D r = new Rectangle2D.Double(25,25,200,200);
    Stroke s = new BasicStroke
(5,BasicStroke.CAP_ROUND,BasicStroke.JOIN_ROUND,1.0f,dash,1.0f);

    Shape border = s.createStrokedShape(r);
    Area clip1 = new Area(r);
    clip1.subtract(new Area(border));
    g2.clip(clip1);

    g2.setPaint(Color.red);
    g2.fill(clip1);

    g2.translate(25,25);

    Rectangle2D r2 = new Rectangle2D.Double(0,0,300,300);
    border = s.createStrokedShape(r2);
    clip1 = new Area(r2);
    clip1.subtract(new Area(border));
    g2.clip(clip1);

    g2.setPaint(Color.blue);
    g2.fill(clip1);  /* <- OutofMemory */
  }
}
---------- END SOURCE ----------

Release Regression From : 1.3.1_03
The above release value was the last known release where this 
bug was known to work. Since then there has been a regression.

(Review ID: 144890) 
======================================================================

Comments
EVALUATION The test case involves intersecting two pieces of geometry that share a large number of identical or nearly identical curves that were generated in two different ways. The current Area code uses subdivision to find where two curves intersect. It keeps subdividing until the pieces of curve are very tiny or until their bounding boxes diverge. It then moves to the next section of curve and repeats the process until it reaches a section where the curves diverge enough that it can distinguish them. It sometimes makes several "baby steps" along a section where the curves intersect before it starts to see the divergence. Unfortunately, when the curves are very close to each other (identical or nearly identical) then it may keep making these "baby steps" ad infinitum and never find a region where they differ enough to start taking larger steps. One fix that would help here would be to put in code to detect when 2 curves with the same geometry are being compared. The problem with such a test is that often the two curves are not strictly identical in all of their endpoints, but are simply "so close that they will never be distinguished" so the test needs to be a little smarter than simply comparing all of the control points. This problem is further complicated by the fact that one curve could be a subset of another and "identical or very close" for the duration of its defined range, but proving that is very difficult and time consuming when using parametric definitions of curves - you typically would have to subdivide over and over to determine this anyway which puts us back in the same ballpark. Finally, some more efficient bookkeeping of the curve pieces being accumulated in the process of comparing the entire paths might prevent the runaway use of memory to store huge numbers of piecewise adjacent curve pieces. This is also complicated by the fact that floating point calculation anomalies can conspire to cause two curves that are very close to each other to swap positions back and forth many times over a small range of coordinates - each swapping thereby preventing any consolidation of adjacent curve pieces. In the end, a lot of very difficult logic needs to be unraveled and reworked and revetted to fix a problem like this...
13-07-2006

EVALUATION I haven't actually done any analysis. However, the test program seems to be using 2D APIs. ###@###.### 2002-04-12 It's reproducible on Win2K on my laptop in hopper, and not reproducible on Solaris. It is the last fill that seems to generate this out of memory. ###@###.### 2002-07-23 Targetted for tiger. ###@###.### 2002-09-30 Name: spR10137 Date: 08/07/2003 The problem is not in "fill" method but "clip" method. Certainly, it's calculation of two Areas intersection. First clip call just create clip, second call find the intersection of current clip and new one. On windows platform we have unlimited grow of number of sun.awt.geom.CurveLink instances. Probably it's infinite loop. ======================================================================
21-08-2004