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

[Jim Graham]

Actually, one comment on the doc comment formatting.

I'd use "{@code Path2D}" instead of "<tt></tt>" formatting.  It gives 
the javadoc front end more control over the presentation...

		...jim

On 4/20/15 1:37 PM, Jim Graham wrote:
> 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;
>>     }
>>