The Inbox: Graphics-nice.446.mcz

Am 13.02.2021 17:05:07 schrieb [hidden email] <[hidden email]>:

Nicolas Cellier uploaded a new version of Graphics to project The Inbox:
http://source.squeak.org/inbox/Graphics-nice.446.mcz

==================== Summary ====================

Name: Graphics-nice.446
Author: nice
Time: 13 February 2021, 5:04:52.453325 pm
UUID: d13c1db2-370f-4fa6-b7ae-e6766bf0c8fb
Ancestors: Graphics-dtl.445

Let Rectangle merging:/encompassing: an unordered collection.

=============== Diff against Graphics-dtl.445 ===============

Item was changed:
----- Method: Rectangle class>>encompassing: (in category 'instance creation') -----
encompassing: listOfPoints
"A number of callers of encompass: should use this method."
| topLeft bottomRight |
+ topLeft := bottomRight := listOfPoints anyOne.
+ listOfPoints do:
- topLeft := bottomRight := listOfPoints first.
- listOfPoints allButFirstDo:
[:p |topLeft := topLeft min: p.
+ bottomRight := bottomRight max: p].
- bottomRight := bottomRight max: p].
^self origin: topLeft corner: bottomRight
!

Item was changed:
----- Method: Rectangle class>>merging: (in category 'instance creation') -----
merging: listOfRects
"A number of callers of merge: should use this method."
+ | aRectangle bottomRight topLeft |
+ aRectangle := listOfRects anyOne.
+ topLeft := aRectangle topLeft.
+ bottomRight := aRectangle bottomRight.
- | bottomRight topLeft |
- topLeft := listOfRects first topLeft.
- bottomRight := listOfRects first bottomRight.
listOfRects
+ do: [:r | topLeft := topLeft min: r topLeft.
- allButFirstDo: [:r | topLeft := topLeft min: r topLeft.
bottomRight := bottomRight max: r bottomRight].
^self origin: topLeft corner: bottomRight.
!

Am 20.02.2021 21:51:24 schrieb Levente Uzonyi <[hidden email]>:

On Sat, 20 Feb 2021, Tom Beckmann wrote:

> Hi Levente, hi Nicolas,
>
> To Levente's comment:
> > You left an #asSet send in the above benchmark.
>
> 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.
>
> To Nicolas' comment:
> > 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.
>
> 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?

My stance on library methods is that they need to be optimized because you
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.

This discussion exists, because Karl changed the method last year and
noticed that the performance got worse[1]. And, while he was convinced
about arguments always being sequenceable, it turned out that they may be
sets as well.


Levente

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

>
> Best regards,
> Tom
>
> On Fri, Feb 19, 2021 at 6:53 PM Levente Uzonyi wrote:
> Hi Tom,
>
> On Fri, 19 Feb 2021, Tom Beckmann wrote:
>
> > Hi everyone,
> >
> > just another idea for your consideration:
> >
> > merging3: listOfRects
> >     ^ listOfRects reduce: [:a :b |
> >          self origin: (a origin min: b origin) corner: (a corner max: b corner)]
> >
> > If you care more about performance than idioms (not even sure if this is legal):
> > merging4: listOfRects
> >     ^ listOfRects reduce: [:a :b |
> >          a setOrigin: (a origin min: b origin) corner: (a corner max: b corner)]
> >
> > And finally, the, in my opinion, most elegant version. Sadly, it's also the slowest.
> > merging5: listOfRects
> >      ^ listOfRects reduce: [:a :b | a quickMerge: b]
> >
> >
> >
> > Some unrepresentative benchmarks:
> >
> > " Levente's version from above with temps "
> > [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.'
> > " the 'clean' version "
> > [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.'
> > " the version that mutates rectangles "
> > [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.'
>
> You left an #asSet send in the above benchmark.
>
>
> Levente
>
> > " using quickMerge "
> > [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.'
> >
> > Best,
> > Tom
> >
> > On Thu, Feb 18, 2021 at 11:17 PM Levente Uzonyi wrote:
> >       Hi Chris,
> >
> >       On Wed, 17 Feb 2021, Chris Muller wrote:
> >
> >       > This is what I would do:
> >       >
> >       > merging: listOfRects
> >       >     "A number of callers of merge: should use this method."
> >       >     ^ listOfRects
> >       >         inject:
> >       >             (self
> >       >                 origin: Float infinity @ Float infinity
> >       >                 corner: Float infinity negated @ Float infinity negated)
> >       >         into: [ : rect : each | rect quickMerge: each ]
> >       >
> >       > 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
> >       analysis of how
> >       > 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
> >       multiple methods and
> >       > making the system's code harder to read and understand and maintain.
> >
> >       With my benchmark, your version is slower than the one from 2003,
> >       especially when the collection is small. And it doesn't handle the case of
> >       empty listOfRects the same way: it silently returns a rectangle instead of
> >       raising an error.
> >
> >       Here's the version I came up with the other day:
> >
> >
> >       merging: listOfRects
> >               "A number of callers of merge: should use this method."
> >
> >               | minTopLeftX minTopLeftY maxBottomRightX maxBottomRightY |
> >               listOfRects do: [ :rectangle |
> >                       | topLeft bottomRight |
> >                       topLeft := rectangle topLeft.
> >                       bottomRight := rectangle bottomRight.
> >                       minTopLeftX
> >                               ifNil: [
> >                                       minTopLeftX := topLeft x.
> >                                       minTopLeftY := topLeft y.
> >                                       maxBottomRightX := bottomRight x.
> >                                       maxBottomRightY := bottomRight y ]
> >                               ifNotNil: [
> >                                       topLeft x < minTopLeftX ifTrue: [ minTopLeftX := topLeft x ].
> >                                       topLeft y < minTopLeftY ifTrue: [ minTopLeftY := topLeft y ].
> >                                       bottomRight x > maxBottomRightX ifTrue: [ maxBottomRightX := bottomRight x ].
> >                                       bottomRight y > maxBottomRightY ifTrue: [ maxBottomRightY := bottomRight y ] ] ].
> >               ^self origin: minTopLeftX @ minTopLeftY corner: maxBottomRightX @ maxBottomRightY
> >
> >
> >       Levente
> >
> >       >
> >       >  - Chris
> >       >
> >       >
> >       > On Wed, Feb 17, 2021 at 11:27 AM Levente Uzonyi wrote:
> >       >       On Wed, 17 Feb 2021, Marcel Taeumel wrote:
> >       >
> >       >       > Hmm... looking at performance ... why not just add #asSequenceableCollection, which would only impact Set arguments?
> >       >
> >       >       I don't think we have such method. Adding one would raise the usual
> >       >       question: should it create a new collection or return self if self
> >       >       already to the requested collection kind?
> >       >       IIRC currently the only outlier is #asOrderedCollection which always
> >       >       creates a copy when the receiver is an OrderedCollection, and that
> >       >       property is being relied on, so it can't be changed...
> >       >
> >       >       > As a programmer, I do not want to choose between #merge: and #quickMerge:. Or similar. :-)
> >       >
> >       >       IMO, we simply need one quick solution. If you have a Set, you may need
> >       >       that help from the library even more.
> >       >       #quickMerge: is only good for merging two rectangles. It does not solve
> >       >       the GC issue #merge: has.
> >       >
> >       >
> >       >       Levente
> >       >
> >       >       >
> >       >       > Best,
> >       >       > Marcel
> >       >       >
> >       >       >       Am 13.02.2021 17:05:07 schrieb [hidden email] :
> >       >       >
> >       >       >       Nicolas Cellier uploaded a new version of Graphics to project The Inbox:
> >       >       >       http://source.squeak.org/inbox/Graphics-nice.446.mcz
> >       >       >
> >       >       >       ==================== Summary ====================
> >       >       >
> >       >       >       Name: Graphics-nice.446
> >       >       >       Author: nice
> >       >       >       Time: 13 February 2021, 5:04:52.453325 pm
> >       >       >       UUID: d13c1db2-370f-4fa6-b7ae-e6766bf0c8fb
> >       >       >       Ancestors: Graphics-dtl.445
> >       >       >
> >       >       >       Let Rectangle merging:/encompassing: an unordered collection.
> >       >       >
> >       >       >       =============== Diff against Graphics-dtl.445 ===============
> >       >       >
> >       >       >       Item was changed:
> >       >       >       ----- Method: Rectangle class>>encompassing: (in category 'instance creation') -----
> >       >       >       encompassing: listOfPoints
> >       >       >       "A number of callers of encompass: should use this method."
> >       >       >       | topLeft bottomRight |
> >       >       >       + topLeft := bottomRight := listOfPoints anyOne.
> >       >       >       + listOfPoints do:
> >       >       >       - topLeft := bottomRight := listOfPoints first.
> >       >       >       - listOfPoints allButFirstDo:
> >       >       >       [:p |topLeft := topLeft min: p.
> >       >       >       + bottomRight := bottomRight max: p].
> >       >       >       - bottomRight := bottomRight max: p].
> >       >       >       ^self origin: topLeft corner: bottomRight
> >       >       >       !
> >       >       >
> >       >       >       Item was changed:
> >       >       >       ----- Method: Rectangle class>>merging: (in category 'instance creation') -----
> >       >       >       merging: listOfRects
> >       >       >       "A number of callers of merge: should use this method."
> >       >       >       + | aRectangle bottomRight topLeft |
> >       >       >       + aRectangle := listOfRects anyOne.
> >       >       >       + topLeft := aRectangle topLeft.
> >       >       >       + bottomRight := aRectangle bottomRight.
> >       >       >       - | bottomRight topLeft |
> >       >       >       - topLeft := listOfRects first topLeft.
> >       >       >       - bottomRight := listOfRects first bottomRight.
> >       >       >       listOfRects
> >       >       >       + do: [:r | topLeft := topLeft min: r topLeft.
> >       >       >       - allButFirstDo: [:r | topLeft := topLeft min: r topLeft.
> >       >       >       bottomRight := bottomRight max: r bottomRight].
> >       >       >       ^self origin: topLeft corner: bottomRight.
> >       >       >       !
> >       >       >
> >       >       >
> >       >       >
> >       >       >
> >       >
> >       >
> >       >
> >
> >
> >
>
>
>

Am 22.02.2021 08:48:36 schrieb Marcel Taeumel <[hidden email]>:

Hi Levente.

> My stance on library methods is that they need to be optimized because you
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.

+1 =)

Best,

Marcel

Am 20.02.2021 21:51:24 schrieb Levente Uzonyi <[hidden email]>:

On Sat, 20 Feb 2021, Tom Beckmann wrote:

> Hi Levente, hi Nicolas,
>
> To Levente's comment:
> > You left an #asSet send in the above benchmark.
>
> 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.
>
> To Nicolas' comment:
> > 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.
>
> 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?

My stance on library methods is that they need to be optimized because you
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.

This discussion exists, because Karl changed the method last year and
noticed that the performance got worse[1]. And, while he was convinced
about arguments always being sequenceable, it turned out that they may be
sets as well.


Levente

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

>
> Best regards,
> Tom
>
> On Fri, Feb 19, 2021 at 6:53 PM Levente Uzonyi wrote:
> Hi Tom,
>
> On Fri, 19 Feb 2021, Tom Beckmann wrote:
>
> > Hi everyone,
> >
> > just another idea for your consideration:
> >
> > merging3: listOfRects
> >     ^ listOfRects reduce: [:a :b |
> >          self origin: (a origin min: b origin) corner: (a corner max: b corner)]
> >
> > If you care more about performance than idioms (not even sure if this is legal):
> > merging4: listOfRects
> >     ^ listOfRects reduce: [:a :b |
> >          a setOrigin: (a origin min: b origin) corner: (a corner max: b corner)]
> >
> > And finally, the, in my opinion, most elegant version. Sadly, it's also the slowest.
> > merging5: listOfRects
> >      ^ listOfRects reduce: [:a :b | a quickMerge: b]
> >
> >
> >
> > Some unrepresentative benchmarks:
> >
> > " Levente's version from above with temps "
> > [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.'
> > " the 'clean' version "
> > [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.'
> > " the version that mutates rectangles "
> > [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.'
>
> You left an #asSet send in the above benchmark.
>
>
> Levente
>
> > " using quickMerge "
> > [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.'
> >
> > Best,
> > Tom
> >
> > On Thu, Feb 18, 2021 at 11:17 PM Levente Uzonyi wrote:
> >       Hi Chris,
> >
> >       On Wed, 17 Feb 2021, Chris Muller wrote:
> >
> >       > This is what I would do:
> >       >
> >       > merging: listOfRects
> >       >     "A number of callers of merge: should use this method."
> >       >     ^ listOfRects
> >       >         inject:
> >       >             (self
> >       >                 origin: Float infinity @ Float infinity
> >       >                 corner: Float infinity negated @ Float infinity negated)
> >       >         into: [ : rect : each | rect quickMerge: each ]
> >       >
> >       > 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
> >       analysis of how
> >       > 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
> >       multiple methods and
> >       > making the system's code harder to read and understand and maintain.
> >
> >       With my benchmark, your version is slower than the one from 2003,
> >       especially when the collection is small. And it doesn't handle the case of
> >       empty listOfRects the same way: it silently returns a rectangle instead of
> >       raising an error.
> >
> >       Here's the version I came up with the other day:
> >
> >
> >       merging: listOfRects
> >               "A number of callers of merge: should use this method."
> >
> >               | minTopLeftX minTopLeftY maxBottomRightX maxBottomRightY |
> >               listOfRects do: [ :rectangle |
> >                       | topLeft bottomRight |
> >                       topLeft := rectangle topLeft.
> >                       bottomRight := rectangle bottomRight.
> >                       minTopLeftX
> >                               ifNil: [
> >                                       minTopLeftX := topLeft x.
> >                                       minTopLeftY := topLeft y.
> >                                       maxBottomRightX := bottomRight x.
> >                                       maxBottomRightY := bottomRight y ]
> >                               ifNotNil: [
> >                                       topLeft x < minTopLeftX ifTrue: [ minTopLeftX := topLeft x ].
> >                                       topLeft y < minTopLeftY ifTrue: [ minTopLeftY := topLeft y ].
> >                                       bottomRight x > maxBottomRightX ifTrue: [ maxBottomRightX := bottomRight x ].
> >                                       bottomRight y > maxBottomRightY ifTrue: [ maxBottomRightY := bottomRight y ] ] ].
> >               ^self origin: minTopLeftX @ minTopLeftY corner: maxBottomRightX @ maxBottomRightY
> >
> >
> >       Levente
> >
> >       >
> >       >  - Chris
> >       >
> >       >
> >       > On Wed, Feb 17, 2021 at 11:27 AM Levente Uzonyi wrote:
> >       >       On Wed, 17 Feb 2021, Marcel Taeumel wrote:
> >       >
> >       >       > Hmm... looking at performance ... why not just add #asSequenceableCollection, which would only impact Set arguments?
> >       >
> >       >       I don't think we have such method. Adding one would raise the usual
> >       >       question: should it create a new collection or return self if self
> >       >       already to the requested collection kind?
> >       >       IIRC currently the only outlier is #asOrderedCollection which always
> >       >       creates a copy when the receiver is an OrderedCollection, and that
> >       >       property is being relied on, so it can't be changed...
> >       >
> >       >       > As a programmer, I do not want to choose between #merge: and #quickMerge:. Or similar. :-)
> >       >
> >       >       IMO, we simply need one quick solution. If you have a Set, you may need
> >       >       that help from the library even more.
> >       >       #quickMerge: is only good for merging two rectangles. It does not solve
> >       >       the GC issue #merge: has.
> >       >
> >       >
> >       >       Levente
> >       >
> >       >       >
> >       >       > Best,
> >       >       > Marcel
> >       >       >
> >       >       >       Am 13.02.2021 17:05:07 schrieb [hidden email] :
> >       >       >
> >       >       >       Nicolas Cellier uploaded a new version of Graphics to project The Inbox:
> >       >       >       http://source.squeak.org/inbox/Graphics-nice.446.mcz
> >       >       >
> >       >       >       ==================== Summary ====================
> >       >       >
> >       >       >       Name: Graphics-nice.446
> >       >       >       Author: nice
> >       >       >       Time: 13 February 2021, 5:04:52.453325 pm
> >       >       >       UUID: d13c1db2-370f-4fa6-b7ae-e6766bf0c8fb
> >       >       >       Ancestors: Graphics-dtl.445
> >       >       >
> >       >       >       Let Rectangle merging:/encompassing: an unordered collection.
> >       >       >
> >       >       >       =============== Diff against Graphics-dtl.445 ===============
> >       >       >
> >       >       >       Item was changed:
> >       >       >       ----- Method: Rectangle class>>encompassing: (in category 'instance creation') -----
> >       >       >       encompassing: listOfPoints
> >       >       >       "A number of callers of encompass: should use this method."
> >       >       >       | topLeft bottomRight |
> >       >       >       + topLeft := bottomRight := listOfPoints anyOne.
> >       >       >       + listOfPoints do:
> >       >       >       - topLeft := bottomRight := listOfPoints first.
> >       >       >       - listOfPoints allButFirstDo:
> >       >       >       [:p |topLeft := topLeft min: p.
> >       >       >       + bottomRight := bottomRight max: p].
> >       >       >       - bottomRight := bottomRight max: p].
> >       >       >       ^self origin: topLeft corner: bottomRight
> >       >       >       !
> >       >       >
> >       >       >       Item was changed:
> >       >       >       ----- Method: Rectangle class>>merging: (in category 'instance creation') -----
> >       >       >       merging: listOfRects
> >       >       >       "A number of callers of merge: should use this method."
> >       >       >       + | aRectangle bottomRight topLeft |
> >       >       >       + aRectangle := listOfRects anyOne.
> >       >       >       + topLeft := aRectangle topLeft.
> >       >       >       + bottomRight := aRectangle bottomRight.
> >       >       >       - | bottomRight topLeft |
> >       >       >       - topLeft := listOfRects first topLeft.
> >       >       >       - bottomRight := listOfRects first bottomRight.
> >       >       >       listOfRects
> >       >       >       + do: [:r | topLeft := topLeft min: r topLeft.
> >       >       >       - allButFirstDo: [:r | topLeft := topLeft min: r topLeft.
> >       >       >       bottomRight := bottomRight max: r bottomRight].
> >       >       >       ^self origin: topLeft corner: bottomRight.
> >       >       >       !
> >       >       >
> >       >       >
> >       >       >
> >       >       >
> >       >
> >       >
> >       >
> >
> >
> >
>
>
>

Am 22.02.2021 11:11:12 schrieb Douglas Brebner <[hidden email]>:

On 20/02/2021 20:51, Levente Uzonyi wrote:
> My stance on library methods is that they need to be optimized because
> you 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.

Cuis has a PerformanceImprovements package that holds the fast but
difficult to understand versions of methods that use simpler but slower
versions in the base image. Maybe that idea could be adopted?

Am 22.02.2021 12:08:45 schrieb Tobias Pape <[hidden email]>:

> On 22. Feb 2021, at 11:32, Marcel Taeumel wrote:
>
> > Cuis has a PerformanceImprovements package that holds the fast but
> difficult to understand versions of methods that use simpler but slower
> versions in the base image. Maybe that idea could be adopted?
>
> A central package for performance improvements would violate the idea of information hiding and hence impede modularity unless there would be such a package for each specific domain (e.g., CollectionImprovements, KernelImprovements etc.) ... but even then ... if any, extra versions of particular methods should be as close to the original artifact as possible. When programmers would stumble upon a hard-to-understand method in the code browser or debugger, the respective tool should point to the more readable version. And the other way around. I think. :-)
>

Mabye we can achive this with baseclasses that use the "simple" version?
-t

> Best,
> Marcel
>> Am 22.02.2021 11:11:12 schrieb Douglas Brebner :
>>
>> On 20/02/2021 20:51, Levente Uzonyi wrote:
>> > My stance on library methods is that they need to be optimized because
>> > you 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.
>>
>> Cuis has a PerformanceImprovements package that holds the fast but
>> difficult to understand versions of methods that use simpler but slower
>> versions in the base image. Maybe that idea could be adopted?
>>
>>
>>
>