<div dir="ltr"><div>Hi Levente, hi Nicolas,<br></div><div><br></div><div>To Levente's comment:<br></div><div>> You left an #asSet send in the above benchmark.</div><div><br></div><div>Oups, indeed. But I think the actual measurement was done without the asSet, I just added it later for experimentation. The numbers appear consistent when I rerun the lines without #asSet.</div><div>After sending the mail, I also realized that the setOrigin:corner:/merging4: version is of course not legal, since we mutate the original rectangle that was passed in.</div><div><br></div><div>To Nicolas' comment:</div><div>
> But that's precisely what we try to avoid here: create lots of<br>> intermediate short-lived objects (Rectangle and Point).</div><div>>
This is because it may be a performance critical routine.</div><div><br></div><div>The most optimized version with the inlined temporaries is a great implementation but looks like quite a beast to me, which in my opinion would be sad for something that appears in our standard library. After looking for senders of Rectangle class>>merging: in my trunk image I only saw one critical path in recordInvalidRect:, which appears to on average trigger merging: only once per damaged frame. Is there another use case we know of?<br></div><div><br></div><div>Best regards,</div><div>Tom<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Feb 19, 2021 at 6:53 PM Levente Uzonyi <<a href="mailto:leves@caesar.elte.hu">leves@caesar.elte.hu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi Tom,<br>
<br>
On Fri, 19 Feb 2021, Tom Beckmann wrote:<br>
<br>
> Hi everyone,<br>
> <br>
> just another idea for your consideration:<br>
> <br>
> merging3: listOfRects<br>
> ^ listOfRects reduce: [:a :b |<br>
> self origin: (a origin min: b origin) corner: (a corner max: b corner)]<br>
> <br>
> If you care more about performance than idioms (not even sure if this is legal):<br>
> merging4: listOfRects<br>
> ^ listOfRects reduce: [:a :b |<br>
> a setOrigin: (a origin min: b origin) corner: (a corner max: b corner)]<br>
> <br>
> And finally, the, in my opinion, most elegant version. Sadly, it's also the slowest.<br>
> merging5: listOfRects<br>
> ^ listOfRects reduce: [:a :b | a quickMerge: b]<br>
> <br>
> <br>
> <br>
> Some unrepresentative benchmarks:<br>
> <br>
> " Levente's version from above with temps "<br>
> [Rectangle merging2: {0 @ 0 extent: 100 @ 100. -20 @ -20 extent: 80 @ 80. 30 @ 30 extent: 100 @ 100}] bench '3,740,000 per second. 267 nanoseconds per run. 37.46501 % GC time.'<br>
> " the 'clean' version "<br>
> [Rectangle merging3: {0 @ 0 extent: 100 @ 100. -20 @ -20 extent: 80 @ 80. 30 @ 30 extent: 100 @ 100}] bench '3,020,000 per second. 331 nanoseconds per run. 40.93181 % GC time.'<br>
> " the version that mutates rectangles "<br>
> [Rectangle merging4: {0 @ 0 extent: 100 @ 100. -20 @ -20 extent: 80 @ 80. 30 @ 30 extent: 100 @ 100} asSet] bench '3,330,000 per second. 300 nanoseconds per run. 40.53189 % GC time.'<br>
<br>
You left an #asSet send in the above benchmark.<br>
<br>
<br>
Levente<br>
<br>
> " using quickMerge "<br>
> [Rectangle merging5: {0 @ 0 extent: 100 @ 100. -20 @ -20 extent: 80 @ 80. 30 @ 30 extent: 100 @ 100}] bench '2,930,000 per second. 341 nanoseconds per run. 42.32 % GC time.'<br>
> <br>
> Best,<br>
> Tom<br>
> <br>
> On Thu, Feb 18, 2021 at 11:17 PM Levente Uzonyi <<a href="mailto:leves@caesar.elte.hu" target="_blank">leves@caesar.elte.hu</a>> wrote:<br>
> Hi Chris,<br>
><br>
> On Wed, 17 Feb 2021, Chris Muller wrote:<br>
><br>
> > This is what I would do:<br>
> ><br>
> > merging: listOfRects<br>
> > "A number of callers of merge: should use this method."<br>
> > ^ listOfRects<br>
> > inject:<br>
> > (self<br>
> > origin: Float infinity @ Float infinity<br>
> > corner: Float infinity negated @ Float infinity negated)<br>
> > into: [ : rect : each | rect quickMerge: each ]<br>
> ><br>
> > With #quickMerge:, you're only creating a new Rectangle when it needed to grow to accomodate the current element, but many of the elements might fit completely, resulting in no additional instantiation. Do an<br>
> analysis of how<br>
> > many temporary Point objects we create -- hint: it's a ton -- and my own attempts to optimize that in my Kml framework were not fruitful (e.g., ~1%), with a trade-off of duplicating implementation across<br>
> multiple methods and<br>
> > making the system's code harder to read and understand and maintain.<br>
><br>
> With my benchmark, your version is slower than the one from 2003,<br>
> especially when the collection is small. And it doesn't handle the case of<br>
> empty listOfRects the same way: it silently returns a rectangle instead of<br>
> raising an error.<br>
><br>
> Here's the version I came up with the other day:<br>
> <br>
><br>
> merging: listOfRects<br>
> "A number of callers of merge: should use this method."<br>
><br>
> | minTopLeftX minTopLeftY maxBottomRightX maxBottomRightY |<br>
> listOfRects do: [ :rectangle |<br>
> | topLeft bottomRight |<br>
> topLeft := rectangle topLeft.<br>
> bottomRight := rectangle bottomRight.<br>
> minTopLeftX<br>
> ifNil: [<br>
> minTopLeftX := topLeft x.<br>
> minTopLeftY := topLeft y.<br>
> maxBottomRightX := bottomRight x.<br>
> maxBottomRightY := bottomRight y ]<br>
> ifNotNil: [<br>
> topLeft x < minTopLeftX ifTrue: [ minTopLeftX := topLeft x ].<br>
> topLeft y < minTopLeftY ifTrue: [ minTopLeftY := topLeft y ].<br>
> bottomRight x > maxBottomRightX ifTrue: [ maxBottomRightX := bottomRight x ].<br>
> bottomRight y > maxBottomRightY ifTrue: [ maxBottomRightY := bottomRight y ] ] ].<br>
> ^self origin: minTopLeftX @ minTopLeftY corner: maxBottomRightX @ maxBottomRightY<br>
> <br>
><br>
> Levente<br>
><br>
> ><br>
> > - Chris<br>
> ><br>
> ><br>
> > On Wed, Feb 17, 2021 at 11:27 AM Levente Uzonyi <<a href="mailto:leves@caesar.elte.hu" target="_blank">leves@caesar.elte.hu</a>> wrote:<br>
> > On Wed, 17 Feb 2021, Marcel Taeumel wrote:<br>
> ><br>
> > > Hmm... looking at performance ... why not just add #asSequenceableCollection, which would only impact Set arguments?<br>
> ><br>
> > I don't think we have such method. Adding one would raise the usual<br>
> > question: should it create a new collection or return self if self<br>
> > already to the requested collection kind?<br>
> > IIRC currently the only outlier is #asOrderedCollection which always<br>
> > creates a copy when the receiver is an OrderedCollection, and that<br>
> > property is being relied on, so it can't be changed...<br>
> ><br>
> > > As a programmer, I do not want to choose between #merge: and #quickMerge:. Or similar. :-)<br>
> ><br>
> > IMO, we simply need one quick solution. If you have a Set, you may need<br>
> > that help from the library even more.<br>
> > #quickMerge: is only good for merging two rectangles. It does not solve<br>
> > the GC issue #merge: has.<br>
> ><br>
> ><br>
> > Levente<br>
> ><br>
> > ><br>
> > > Best,<br>
> > > Marcel<br>
> > ><br>
> > > Am 13.02.2021 17:05:07 schrieb <a href="mailto:commits@source.squeak.org" target="_blank">commits@source.squeak.org</a> <<a href="mailto:commits@source.squeak.org" target="_blank">commits@source.squeak.org</a>>:<br>
> > ><br>
> > > Nicolas Cellier uploaded a new version of Graphics to project The Inbox:<br>
> > > <a href="http://source.squeak.org/inbox/Graphics-nice.446.mcz" rel="noreferrer" target="_blank">http://source.squeak.org/inbox/Graphics-nice.446.mcz</a><br>
> > ><br>
> > > ==================== Summary ====================<br>
> > ><br>
> > > Name: Graphics-nice.446<br>
> > > Author: nice<br>
> > > Time: 13 February 2021, 5:04:52.453325 pm<br>
> > > UUID: d13c1db2-370f-4fa6-b7ae-e6766bf0c8fb<br>
> > > Ancestors: Graphics-dtl.445<br>
> > ><br>
> > > Let Rectangle merging:/encompassing: an unordered collection.<br>
> > ><br>
> > > =============== Diff against Graphics-dtl.445 ===============<br>
> > ><br>
> > > Item was changed:<br>
> > > ----- Method: Rectangle class>>encompassing: (in category 'instance creation') -----<br>
> > > encompassing: listOfPoints<br>
> > > "A number of callers of encompass: should use this method."<br>
> > > | topLeft bottomRight |<br>
> > > + topLeft := bottomRight := listOfPoints anyOne.<br>
> > > + listOfPoints do:<br>
> > > - topLeft := bottomRight := listOfPoints first.<br>
> > > - listOfPoints allButFirstDo:<br>
> > > [:p |topLeft := topLeft min: p.<br>
> > > + bottomRight := bottomRight max: p].<br>
> > > - bottomRight := bottomRight max: p].<br>
> > > ^self origin: topLeft corner: bottomRight<br>
> > > !<br>
> > ><br>
> > > Item was changed:<br>
> > > ----- Method: Rectangle class>>merging: (in category 'instance creation') -----<br>
> > > merging: listOfRects<br>
> > > "A number of callers of merge: should use this method."<br>
> > > + | aRectangle bottomRight topLeft |<br>
> > > + aRectangle := listOfRects anyOne.<br>
> > > + topLeft := aRectangle topLeft.<br>
> > > + bottomRight := aRectangle bottomRight.<br>
> > > - | bottomRight topLeft |<br>
> > > - topLeft := listOfRects first topLeft.<br>
> > > - bottomRight := listOfRects first bottomRight.<br>
> > > listOfRects<br>
> > > + do: [:r | topLeft := topLeft min: r topLeft.<br>
> > > - allButFirstDo: [:r | topLeft := topLeft min: r topLeft.<br>
> > > bottomRight := bottomRight max: r bottomRight].<br>
> > > ^self origin: topLeft corner: bottomRight.<br>
> > > !<br>
> > ><br>
> > ><br>
> > ><br>
> > ><br>
> ><br>
> ><br>
> ><br>
> <br>
> <br>
><br>
</blockquote></div>