[prev in list] [next in list] [prev in thread] [next in thread]
List: openjdk-2d-dev
Subject: Re: [Performance] java.awt.geom.Area#intersect should do basic bounds checking prior to calculating
From: "Jeremy Wood" <mickleness () gmail ! com>
Date: 2024-02-25 21:50:30
Message-ID: em5d4fcb6e-2e8a-42d5-bb14-743134ee7915 () 76ca4640 ! com
[Download RAW message or body]
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@kaart.com>
To client-libs-dev@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
>
[Attachment #3 (text/html)]
<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>
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic