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

[Jim Graham]

Hi Laurent,

The new doc comment and method looks good.

Arrays.copyOf is often faster than allocation+arraycopy (typically 
because it doesn't need to clear the entire array first and then fill it 
with data in 2 separate passes - Hotspot optimizes that method into a 
single operation).  The new algorithm could simply use:

	return Arrays.copyOf(..., newSize);

inside the try/catch where it currently has:

	... = new <type>[newSize];

and then it wouldn't need to use "break" or have the arraycopy after the 
loop.  It might also benefit from the faster speed of arrayCopy.

In the needRoom() methods, there is one more potential overflow path. 
If the array grows to just under MAX_INT, then "numCoords + newCoords" 
may overflow to a negative number and the array would not be grown 
because the test in needRoom() would fail to trigger a call to the grow 
method.  We would still get an AIOOBE in the moveTo/lineTo/etc. routine, 
but we would insert the new path type into the types array (and 
increment numTypes) before we overflowed the coords array.  We'd also 
bump the numCoords by a couple of entries before we hit the true end of 
the array.  After the exception, we'd leave the path in a bad state 
where it had a recorded segment type that had no associated data (or 
partial data) in the coords array.  It would be cleaner to test the 
"numCoords + newCoords" for overflow in needRoom().  A simple test of 
the sum being < 0 should do since both numCoords and newCoords should 
always be positive numbers and all pos+pos overflows always result in 
negative numbers...

			...jim

On 4/10/15 8:07 AM, Laurent Bourgès wrote:
> Jim,
>
> Here is the new webrev:
> http://cr.openjdk.java.net/~lbourges/path2D/Path2D_needRoom.1/
>
> Changes:
> - needRoom() applies your pseudo-code; see expandPointTypes() and
> expandCoords()
> - added a new public trimToSize() method to Path2D implemented by both
> Path2D.Float and Path2D.Double classes
>
> Cheers,
> Laurent
>
> 2015-04-08 22:53 GMT+02:00 Jim Graham <james.graham at oracle.com
> <mailto:james.graham at oracle.com>>:
>
>     Hi Laurent,
>
>     I'd probably do:
>
>     int newsizemin = oldcount + newitems;
>     if (newsizemin < oldcount) {
>          // hard overflow failure - we can't even accommodate
>          // new items without overflowing
>          return failure, throw exception?
>     }
>     int newsize = <growth algorithm computation>;
>     if (newsize < newsizemin) {
>          // overflow in growth algorithm computation
>          newsize = newsizemin;
>          ... OR ...
>          newsize = MAX_INT;
>     }
>     while (true) {
>          try {
>              allocate newsize;
>              break;  (or return?)
>          } catch (OOME e) {
>              if (newsize == newsizemin) {
>                  throw e;
>              }
>          }
>          newsize = newsizemin + (newsize - newsizemin) / 2;
>     }
>