[Performance] java.awt.geom.Area#intersect should do basic bounds checking prior to calculating the intersection

[Jeremy Wood]

Taylor,

 > Is there a reason why `intersect` doesn't look something like 
[example]

I think (?) there isn’t an appetite in this group to improve the Area 
class. I agree there’s a lot of room for improvement in that class, but 
I’m a relative outsider (lurker) to this group.

(I proposed a simpler optimization 
<https://mail.openjdk.org/pipermail/client-libs-dev/2022-February.txt> 
to the Area class a few years ago, and it didn’t generate any 
enthusiasm.)

I like the Area class, but it’s definitely caused (avoidable) 
performance bottlenecks over the years.

I also started a project <https://github.com/mickleness/outline/> a few 
years ago that includes your proposed optimization and several others. 
Given a variety of shapes it can perform clipping operations in 10% of 
the time 
<https://github.com/mickleness/outline/blob/master/Clipping%20Shapes%20Output.log> 
the Area takes. And it can perform additions in 56% of the time 
<https://github.com/mickleness/outline/blob/master/Adding%20Shapes%20For%20Outline%20Output.log>. 
Unfortunately: I haven’t worked on it in over a year. It probably needs 
more attention. If anyone wants to discuss that off-list please feel 
free to email me.

(And if any contributor on this list wants to help sponsor/review work 
for openjdk Area optimizations: please let us know! I’m happy to help.)

Regards,
  - Jeremy

------ Original Message ------
>From "Taylor Smock" <taylor.smock at kaart.com>
To client-libs-dev at openjdk.org
Date 2/13/24, 2:31:52 PM
Subject [Performance] java.awt.geom.Area#intersect should do basic 
bounds checking prior to calculating the intersection

>While I was investigating a way to improve performance in JOSM (see 
>https://josm.openstreetmap.de/ticket/23472 ), I saw that 
>java.awt.geom.Area#intersect was taking a disproportionate amount of 
>CPU cycles.
>
>I was able to decrease the amount of time spent in `intersect` by doing 
>bounds intersection checks prior to calling `intersect`.
>
>Is there a reason why `intersect` doesn't look something like
>
>     public void intersect(Area rhs) {
>         final var lhsBounds = this.getCachedBounds();
>         final var rhsBounds = rhs.getCachedBounds();
>         if (!lhsBounds.intersects(rhsBounds) || 
>!this.intersects(rhsBounds) || !rhs.intersects(lhsBounds)) {
>             curves = EmptyCurves;
>         } else {
>             curves = new AreaOp.IntOp().calculate(this.curves, 
>rhs.curves);
>         }
>         invalidateBounds();
>     }
>
>My assumption is that it wasn't a method that has been extensively 
>profiled, but it is entirely possible that there is something I don't 
>know.
>
>
>
>For reference, the bounds checking I did outside of the JDK looked like 
>this (simplified -- see link above for actual code):
>
>     public static Area calculateIntersection(Area lhs, Area rhs) {
>         final Rectangle lhsBounds = lhs.getBounds2d();
>         final Rectangle rhsBounds = rhs.getBounds2d();
>         if (!lhsBounds.intersects(rhsBounds) && 
>!lhs.intersects(rhsBounds) && !rhs.intersects(lhsBounds)) {
>             return new Area();
>         }
>         return lhs.intersect(rhs);
>     }
>
>
>
>For my specific use case, this lead to the following performance 
>improvements in my test workload (CPU and memory allocations as 
>measured by IntelliJ IDEA's profiler for the calling method):
>
>
>CPUMemory AllocationsTotal Validator Time
>No patch 522,778ms 54.13 GB ~840s
>Patch 22,581ms 1.13 GB ~210s
>Difference -500,197ms -53 GB -630s
>Difference % -95.7% -97.9% -77.7%
>
>Thanks,
>
>Taylor
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/client-libs-dev/attachments/20240225/ae0ad92d/attachment.htm>