United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
JDK-6620013 : Performance problem with dashed lines

Details
Type:
Bug
Submit Date:
2007-10-22
Status:
Open
Updated Date:
2014-08-11
Project Name:
JDK
Resolved Date:
Component:
client-libs
OS:
generic
Sub-Component:
2d
CPU:
generic
Priority:
P4
Resolution:
Unresolved
Affected Versions:
7
Targeted Versions:
9

Related Reports

Sub Tasks

Description
In some cases we have poor performance with rendering of dashed lines. Here is the report from the java2d mailing list:
----------------------------------------------------------------------------------------

Hi folks,

I've found what seems like a bug in the java2d drawing code.  I've
included a simple test application, at the end of this email, that
demonstrates the problem.  It involves drawing dashed lines whose
ratio of line length to dash length is very large.  I've tested it in
both java 1.4.2 and java 1.5 and found the problem in both cases.

Here are some results of my tests that demonstrate the issue.

Drawing a solid line seems fine no matter what the length...

ken@saturn> time java -cp . DrawDash 0 10000000

real    0m0.980s
user    0m0.752s
sys     0m0.052s

...However, when we add a dash to this long line it suddenly takes
much longer to draw...

ken@saturn> time java -cp . DrawDash 5
10000000

real    0m10.262s
user    0m9.865s
sys     0m0.080s

...however, if we simply drop the length of the line down by a factor
of 10 we are back to a reasonable length of time ...

ken@saturn> time java -cp . DrawDash 5 1000000

real    0m1.317s
user    0m1.212s
sys     0m0.016s

... The problem seems to be more based upon the ratio of the dash length to the
line length as evidenced by the following set of results.  First, this
short line length with this incredibly short dash length is mostly
fine...

ken@saturn> time java -cp . DrawDash .0005 100

real    0m2.426s
user    0m2.220s
sys     0m0.044s


...while these two, with a dash/length ratio 1/10th of that above, I
had to kill because they were taking longer than 2 minutes!...

time java -cp . DrawDash .0005 1000
time java -cp . DrawDash .00005 100

...which seems to suggest that it is not entirely based upon the ratio
since if that were the case they should take around 10 or 11 seconds
as the one above with the same ratio.  However, they take much longer
than that.  Maybe they will never finish!

But, anyway, something is going on that it seems should be easily
fixed.  Anyone have any ideas?

Cheers,

Ken


Here is the code for my tests...

import javax.swing.JDialog;
import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics2D;
import java.awt.geom.Line2D;

public class DrawDash
{
    public static void main( String[]    args )
    {
        double    lineSize = 1000.;
        float     dashLength = 10;

        if ( args.length >= 1 )
        {
            dashLength = Float.parseFloat( args[0] );
        }

        if ( args.length >= 2 )
        {
            lineSize = Double.parseDouble( args[1] );
        }

        JDialog    dialog = new JDialog();
        dialog.setSize( new Dimension( 800, 800 ) );
        dialog.show();

        Graphics2D    graphics = (Graphics2D) dialog.getGraphics();
        graphics.setPaint( Color.RED );

        if ( dashLength > 0 )
        {
            float[]    dashArray = new float[]{ dashLength, dashLength };

            BasicStroke    stroke;
            stroke = new BasicStroke( 1,
                                      BasicStroke.CAP_ROUND,
                                      BasicStroke.JOIN_ROUND,
                                      10.0f,
                                      dashArray,
                                      0 );
            graphics.setStroke( stroke );
        }

        graphics.draw( new Line2D.Double( -lineSize,
                                          -lineSize,
                                          lineSize,
                                          lineSize ) );

        System.exit( 0 );
    }
}

                                    

Comments
EVALUATION

I've looked through the experiments from the message using performance analyzer. Here is two different bottlenecks  that affects the performance.

1. memory allocation code inside the ShapeSpanIterator.c. We have it in case of drawing small dashes (DrawDash .0005 100)

...
                           997.     /* We will need to insert this segment, check for room. */
   0,         0,           998.     if (pd->numSegments >= pd->segmentsSize) {
                           999.     segmentData *newSegs;
   0,         0,          1000.     int newSize = pd->segmentsSize + GROW_SIZE;
   0,         7,795       1001.     newSegs = (segmentData *) calloc(newSize, sizeof(segmentData));
   0,         0,          1002.     if (newSegs == NULL) {
   0,         0,          1003.         return JNI_FALSE;
                          1004.     }
   0,         0,          1005.     if (pd->segments != NULL) {
                          1006.         memcpy(newSegs, pd->segments,
   0,        15,681       1007.            sizeof(segmentData) * pd->segmentsSize);
   0,         0,          1008.         free(pd->segments);
                          1009.     }
   0,         0,          1010.     pd->segments = newSegs;
   0,         0,          1011.     pd->segmentsSize = newSize;
                          1012.     }
                          1013.
   0,         0,          1014.     dx = x1 - x0;
   0,         0,          1015.     dy = y1 - y0;
   0,         0,          1016.     slope = dx / dy;
...

I've done some experimenting with GROW_SIZE parameter. Here is the results:

GROW_SIZE = 20 (default)
time java DrawDash .0005 100
real    0m49.161s
user    0m48.811s
sys     0m0.185s

GROW_SIZE = 40
bash-3.2$ time java DrawDash .0005 100
real    0m25.726s
user    0m25.442s
sys     0m0.173s

GROW_SIZE = 80
bash-3.2$ time java  DrawDash .0005 100
real    0m14.211s
user    0m13.742s
sys     0m0.163s

GROW_SIZE = 160
bash-3.2$ time java  DrawDash .0005 100
real    0m8.232s
user    0m7.870s
sys     0m0.162s

So, probably we should choose another default value for GROW_SIZE. 


2. Creating caps for dashes. I case of lines with huge amount of dashes (DrawDash 5 10000000).

...
                        358. clockwiseCap(doeE env, dcPathStrokerData* st, f32 x, f32 y, i32 dir)
   0,060      0,060        359. {
                                <Function: clockwiseCap>
   0,010      0,010        360.     dcPathConsumer  out = st->out;
                           361.     i32             bnorm, enorm;
   0,010      0,010        362.     bnorm  = anglesAdd(dir, anglesDEG090);
   0,         0,           363.     enorm  = anglesAdd(dir, anglesDEG270);
   0,         0,           364.     if (st->caps == dcPathStroker_ROUND) {
   0,040      5,734        365.         penSection(env, st, x, y, bnorm, dir);
   0,090      0,090        366.     if (doeError_occurred(env)) return;
   0,100      5,574        367.         penSection(env, st, x, y, dir, enorm);
                           368.
   0,         0,           369.     } else if (st->caps == dcPathStroker_BUTT) {
   0,         0,           370.         lineToPenPoint(env, st, x, y, enorm);
                           371.
                           372.     } else /* if (st->caps == dcPathStroker_SQUARE) */ {
   0,         0,           373.         i32 bcor = anglesAdd(bnorm, -anglesDEG045),
   0,         0,           374.             ecor = anglesAdd(enorm, anglesDEG045);
   0,         0,           375.         f32 cr   = st->penRadius * 1.414213562F;
                           376.
   0,         0,           377.         lineToPolarPoint(env, st, x, y, cr, bcor);
   0,         0,           378.     if (doeError_occurred(env)) return;
   0,         0,           379.         lineToPolarPoint(env, st, x, y, cr, ecor);
   0,         0,           380.     if (doeError_occurred(env)) return;
   0,         0,           381.         lineToPenPoint(env, st, x, y, enorm);
                           382.     }
   0,030      0,030        383. }
...

So, we are performing lot's of work for creating round dashes. Perhaps, we should use BUTT codepath instead in case of lines having width=1. Actually, I don't see more general optimizations at the moment.

BTW,
Ductus has some commented out fp enabling code (in angles.c) that is equivalent to the current one but when I tried to use it I got even worse performance results.
                                     
2007-10-22
 - this is an issue reported against 7(7u),
 - there are now affected version 9 filed for this issue
 - 7u issues are transferred to Sustaining
Nevertheless if someone have a report against 9 - please reopen and add affectedVersion 9
or
7u specific escalations might be reopen to Sustaining
                                     
2014-08-10
 - this is an issue reported against 7(7u),
 - there are now affected version 9 filed for this issue
 - 7u issues are transferred to Sustaining
Nevertheless if someone have a report against 9 - please reopen and add affectedVersion 9
or
7u specific escalations might be reopen to Sustaining
                                     
2014-08-10



Hardware and Software, Engineered to Work Together