[OpenJDK 2D-Dev] [OpenJDK Rasterizer] Path2d needRoom very slow for huge paths

[Laurent Bourgès]

Jim,

Here is the first webrev:
http://cr.openjdk.java.net/~lbourges/path2D/Path2D_needRoom.0/

I created a test Path2DGrow that also gives some timings:

Without patch:
 - Test(Path2D.Double[0]) ---
testAddMoves[1000000] duration= 21.848986999999997 ms.
testAddLines[1000000] duration= 2883.4139689999997 ms.
testAddQuads[1000000] duration= 11663.965977 ms.
testAddCubics[1000000] duration= 26407.056027 ms.
testAddMoveAndCloses[1000000] duration= 3348.6948319999997 ms.
...

With patch applied:
 - Test(Path2D.Double[0]) ---
testAddMoves[1000000] duration= 19.43655 ms.
testAddLines[1000000] duration= 61.026067999999995 ms.
testAddQuads[1000000] duration= 96.781376 ms.
testAddCubics[1000000] duration= 128.759678 ms.
testAddMoveAndCloses[1000000] duration= 81.86097099999999 ms.
...

PS: I have not yet created the bug so the bugid is TODO in the test.


Some comments below:

All of your comments are spot on (modulo the confusion over Pisces/Marlin
> vs Path2D).  And you are right that 500 seems pretty lean to me.  800K path
> segments seems to be a pretty large outlier, though, do we really see paths
> that large other than via a test case?
>

Yes, my spiral test is insane !
but it may happen sometimes in GIS to have huge polygons ~ 300 000 segments.


>
> I think I'm good with the proposed fix, though.  RAM sizes have also
> changed dramatically since 1998... ;)
>

thanks.


>
> And trim() couldn't hurt.
>

No yet implemented; maybe at the next  iteration or finally not necessary ?

>
> Another option for growable arrays that can deal with scalability is a
> chain of arrays rather than a single growing array.  It can get more
> complicated to do the bookkeeping, but you can find a decent value of how
> many entries can hide the incremental growth without having to deal with
> the overhead of:
>
> - GC'ing the previous array
> - needing 2x the storage for the N-1 and Nth arrays
> - copying the data constantly from array i to i+1
>

That's a good idea to keep in mind:
it would be great to have such efficient growable array for primitive types
in Arrays 2.0 ?
Maybe the JVM could implement such "magic" undercover.

Laurent
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/2d-dev/attachments/20150403/c2d50057/attachment.html>