<div id="__MailbirdStyleContent" style="font-size: 10pt;font-family: Arial;color: #000000;text-align: left" dir="ltr"><div>Hi Levente.</div><div><br></div>

                                        > <span style="font-family: Arial, Helvetica, sans-serif;font-size: 13px">My stance on library methods is that they need to be optimized because you</span><br style="font-family: Arial, Helvetica, sans-serif;font-size: 13px"><span style="font-family: Arial, Helvetica, sans-serif;font-size: 13px">don't know how people will use them. If they are fast, people will be</span><br style="font-family: Arial, Helvetica, sans-serif;font-size: 13px"><span style="font-family: Arial, Helvetica, sans-serif;font-size: 13px">happy. If they are not, you'll leave a bad impression.</span><div class="mb_sig"></div>

                                        <div><span style="font-family: Arial, Helvetica, sans-serif;font-size: 13px"><br></span></div><div><span style="font-family: Arial, Helvetica, sans-serif;font-size: 13px">+1 =)</span></div><div><span style="font-family: Arial, Helvetica, sans-serif;font-size: 13px"><br></span></div><div><span style="font-family: Arial, Helvetica, sans-serif;font-size: 13px">Best,</span></div><div><span style="font-family: Arial, Helvetica, sans-serif;font-size: 13px">Marcel</span></div><blockquote class="history_container" type="cite" style="border-left-style: solid;border-width: 1px;margin-top: 20px;margin-left: 0px;padding-left: 10px;min-width: 500px">

                        <p style="color: #AAAAAA; margin-top: 10px;">Am 20.02.2021 21:51:24 schrieb Levente Uzonyi <leves@caesar.elte.hu>:</p><div style="font-family:Arial,Helvetica,sans-serif">On Sat, 20 Feb 2021, Tom Beckmann wrote:

<br>

<br>> Hi Levente, hi Nicolas,

<br>> 

<br>> To Levente's comment:

> > You left an #asSet send in the above benchmark.

<br>> 

> 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.

> 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.

<br>> 

<br>> To Nicolas' comment:

<br>> > But that's precisely what we try to avoid here: create lots of

> > intermediate short-lived objects (Rectangle and Point).

> > This is because it may be a performance critical routine.

<br>> 

<br>> 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>

<br>My stance on library methods is that they need to be optimized because you 

<br>don't know how people will use them. If they are fast, people will be 

happy. If they are not, you'll leave a bad impression.

<br>

<br>This discussion exists, because Karl changed the method last year and 

<br>noticed that the performance got worse[1]. And, while he was convinced 

<br>about arguments always being sequenceable, it turned out that they may be 

sets as well.

<br>

<br>

<br>Levente

<br>

<br>[1] http://forum.world.st/The-Inbox-Graphics-kfr-434-mcz-tp5119541p5119584.html

<br>

<br>> 

<br>> Best regards,

<br>> Tom

<br>> 

<br>> On Fri, Feb 19, 2021 at 6:53 PM Levente Uzonyi <leves@caesar.elte.hu> wrote:

<br>>       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>>       >

>       > 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>>

>       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 <leves@caesar.elte.hu> 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. 

<br>>       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

>       >       > 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 <leves@caesar.elte.hu> wrote:

<br>>       >       >       On Wed, 17 Feb 2021, Marcel Taeumel wrote:

<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

>       >       >       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

>       >       >       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 commits@source.squeak.org <commits@source.squeak.org>:

<br>>       >       >       >

<br>>       >       >       >       Nicolas Cellier uploaded a new version of Graphics to project The Inbox:

<br>>       >       >       >       http://source.squeak.org/inbox/Graphics-nice.446.mcz

<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>> 

<br>> 

<br>><br></commits@source.squeak.org></leves@caesar.elte.hu></leves@caesar.elte.hu></leves@caesar.elte.hu></div></blockquote></div>