<html><head>
<style id="css_styles" type="text/css"><!--blockquote.cite { margin-left: 5px; margin-right: 0px; padding-left: 10px; padding-right:0px; border-left: 1px solid #cccccc }
blockquote.cite2 {margin-left: 5px; margin-right: 0px; padding-left: 10px; padding-right:0px; border-left: 1px solid #cccccc; margin-top: 3px; padding-top: 0px; }
a img { border: 0px; }
table { border-collapse: collapse; }
li[style='text-align: center;'], li[style='text-align: center; '], li[style='text-align: right;'], li[style='text-align: right; '] { list-style-position: inside;}
body { font-family: Helvetica; font-size: 9pt; }
.quote { margin-left: 1em; margin-right: 1em; border-left: 5px #ebebeb solid; padding-left: 0.3em; }
--></style></head>
<body style="overflow-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div>Taylor,</div><div><br /></div>
<div style="clear:both">> <span>Is there a reason why `intersect` doesn't look something like [example]</span></div><div style="clear:both"><span><br /></span></div><div style="clear:both"><span>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.</span></div><div style="clear:both"><span><br /></span></div><div style="clear:both">(I proposed a <a href="https://mail.openjdk.org/pipermail/client-libs-dev/2022-February.txt">simpler optimization</a> to the Area class a few years ago, and it didn’t generate any enthusiasm.)</div><div style="clear:both"><div id="xe60d14b5d8b648aeba552bbd4f295b18"><div style="clear:both;"><br /></div><div style="clear:both;">I like the Area class, but it’s definitely caused (avoidable) performance bottlenecks over the years.</div></div></div><div style="clear:both"><br /></div><div style="clear:both">I also <a href="https://github.com/mickleness/outline/">started a project</a> a few years ago that includes your proposed optimization and several others. Given a variety of shapes it can perform <a href="https://github.com/mickleness/outline/blob/master/Clipping%20Shapes%20Output.log" style="font-size: 9pt;">clipping operations in 10% of the time</a> the Area takes. And it <a href="https://github.com/mickleness/outline/blob/master/Adding%20Shapes%20For%20Outline%20Output.log" style="font-size: 9pt;">can perform additions in 56% of the time</a>. 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.</div><div style="clear:both"><br /></div><div style="clear:both">(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.)</div><div style="clear:both"><br /></div><div style="clear:both">Regards,</div><div style="clear:both"> - Jeremy</div>
<div><br /></div>
<div>
<div>------ Original Message ------</div>
<div>From "Taylor Smock" <<a href="mailto:taylor.smock@kaart.com">taylor.smock@kaart.com</a>></div>
<div>To <a href="mailto:client-libs-dev@openjdk.org">client-libs-dev@openjdk.org</a></div>
<div>Date 2/13/24, 2:31:52 PM</div>
<div>Subject [Performance] java.awt.geom.Area#intersect should do basic bounds checking prior to calculating the intersection</div></div><div><br /></div>
<div id="xeacf1ce295aa444"><blockquote cite="f673b36b-4ae4-415e-a4c4-1a1fc4bf8e9f@kaart.com" type="cite" class="cite2">
<p>While I was investigating a way to improve performance in JOSM
(see
<a class="moz-txt-link-freetext" href="https://josm.openstreetmap.de/ticket/23472">https://josm.openstreetmap.de/ticket/23472</a> ), I saw that
java.awt.geom.Area#intersect was taking a disproportionate amount
of CPU cycles.
</p>
<p>I was able to decrease the amount of time spent in `intersect` by
doing bounds intersection checks prior to calling `intersect`.
</p>
<p>Is there a reason why `intersect` doesn't look something like</p>
<p><code> public void intersect(Area rhs) {<br />
final var lhsBounds = this.getCachedBounds();<br />
final var rhsBounds = rhs.getCachedBounds();<br />
if (!lhsBounds.intersects(rhsBounds) ||
!this.intersects(rhsBounds) || !rhs.intersects(lhsBounds)) {
<br />
curves = EmptyCurves;<br />
} else {<br />
curves = new AreaOp.IntOp().calculate(this.curves,
rhs.curves);
<br />
}<br />
invalidateBounds();<br />
}</code><br />
</p>
<p>My <i>assumption</i> 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.
<br />
</p>
<p><br />
</p>
<p>For reference, the bounds checking I did outside of the JDK
looked like this (simplified -- see link above for actual code):
</p>
<code> public static Area calculateIntersection(Area lhs, Area
rhs) {
<br />
final Rectangle lhsBounds = lhs.getBounds2d();<br />
final Rectangle rhsBounds = rhs.getBounds2d();<br />
if (!lhsBounds.intersects(rhsBounds) &&
!lhs.intersects(rhsBounds) && !rhs.intersects(lhsBounds))
{
<br />
return new Area();<br />
}<br />
return lhs.intersect(rhs);<br />
</code>
<p><code> }</code></p>
<p><br />
</p>
<p>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):
</p>
<table class="wiki">
<tbody>
<tr>
<td><br />
</td>
<th>CPU</th>
<th>Memory Allocations</th>
<th>Total Validator Time
</th>
</tr>
<tr>
<th>No patch</th>
<td style="text-align: right"> 522,778ms</td>
<td style="text-align: right"> 54.13 GB</td>
<td style="text-align: right"> ~840s
</td>
</tr>
<tr>
<th>Patch</th>
<td style="text-align: right"> 22,581ms</td>
<td style="text-align: right"> 1.13 GB</td>
<td style="text-align: right"> ~210s
</td>
</tr>
<tr>
<th>Difference</th>
<td style="text-align: right"> -500,197ms</td>
<td style="text-align: right"> -53 GB</td>
<td style="text-align: right"> -630s
</td>
</tr>
<tr>
<th>Difference %</th>
<td style="text-align: right"> -95.7%</td>
<td style="text-align: right"> -97.9%</td>
<td style="text-align: right"> -77.7%
</td>
</tr>
</tbody>
</table>
<p></p>
<p>Thanks,</p>
<p>Taylor<br />
</p>
</blockquote></div>
</body></html>