The Inbox: Graphics-nice.446.mcz

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
24 messages Options
12
Reply | Threaded
Open this post in threaded view
|

The Inbox: Graphics-nice.446.mcz

commits-2
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.
  !


Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

marcel.taeumel
Hmm... looking at performance ... why not just add #asSequenceableCollection, which would only impact Set arguments?

As a programmer, I do not want to choose between #merge: and #quickMerge:. Or similar. :-)

Best,
Marcel

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




Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

Levente Uzonyi
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] <[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.
>       !
>
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

Chris Muller-3
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.

 - Chris


On Wed, Feb 17, 2021 at 11:27 AM Levente Uzonyi <[hidden email]> 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] <[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.
>       !
>
>
>
>



Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

Levente Uzonyi
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 <[hidden email]> 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] <[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.
>       >       !
>       >
>       >
>       >
>       >
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

Tom Beckmann
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.'
" 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 <[hidden email]> 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 <[hidden email]> 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] <[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.
>       >       !
>       >
>       >
>       >
>       >
>
>
>


Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

Nicolas Cellier
Hi Tom,
yes this looks cleaner.
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.

Le ven. 19 févr. 2021 à 09:01, Tom Beckmann <[hidden email]> a écrit :

>
> 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.'
> " 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 <[hidden email]> 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 <[hidden email]> 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] <[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.
>> >       >       !
>> >       >
>> >       >
>> >       >
>> >       >
>> >
>> >
>> >
>
>

Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

Levente Uzonyi
In reply to this post by Tom Beckmann
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 <[hidden email]> 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 <[hidden email]> 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] <[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.
>       >       >       !
>       >       >
>       >       >
>       >       >
>       >       >
>       >
>       >
>       >
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

Tom Beckmann
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?

Best regards,
Tom

On Fri, Feb 19, 2021 at 6:53 PM Levente Uzonyi <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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] <[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.
>       >       >       !
>       >       >
>       >       >
>       >       >
>       >       >
>       >
>       >
>       >
>
>
>


Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

Stéphane Rollandin
> 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?

Well yes, I am using #merging: and #encompassing: as primitive methods
in computational geometry stuff, and as such I want them as optimized as
possible.

Also, I do not get the rationale behind the idea that methods in the
standard library should be subpar.

Regards,

Stef

Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

Stéphane Rollandin
In reply to this post by Nicolas Cellier
> 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.

+1

Stef


Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

Levente Uzonyi
In reply to this post by Tom Beckmann
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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] <[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.
>       >       >       >       !
>       >       >       >
>       >       >       >
>       >       >       >
>       >       >       >
>       >       >
>       >       >
>       >       >
>       >
>       >
>       >
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

marcel.taeumel
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.
> >       >       >       !
> >       >       >
> >       >       >
> >       >       >
> >       >       >
> >       >
> >       >
> >       >
> >
> >
> >
>
>
>


Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

marcel.taeumel
And alternative implementations (e.g. being more readable but costly) could be documented in the method's comment, possible as pseudo code. Something like the fallback code for primitives, just as comment. Well, that alternative could be an actual method with a "self shouldNotBeUsed" warning in the beginning ... except for maybe in tests that check whether the two implementations yield the same effects.

Best,
Marcel

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


Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

Douglas Brebner-2
In reply to this post by Levente Uzonyi
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?



Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

marcel.taeumel
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. :-)

Best,
Marcel

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?





Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

Tobias Pape


> On 22. Feb 2021, at 11:32, Marcel Taeumel <[hidden email]> 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 <[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?
>>
>>
>>
>



Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

Nicolas Cellier
In reply to this post by marcel.taeumel
There are two things that bothers me:

1) a performance package can be a nightmare for maintenance, unless
the Kernel development freezes, or unless it's very restricted
  overrides opens a nest of problems, and it's a recipe for creeping
incompatibilities.
  maybe this can be mitigated with duplicated testing (with and
without performance), but still...
  I have maintained my own overrides for years in VW, and it's a never
ending fight.
2) more generally, the code base is an example
  Eliminating all the intermediate objects gives much less expressive
code as Tom underlined
  But providing only naive implementations hides the performance
problems that users will have to learn sooner or later...
  We do not want to optimize prematurely. But we do not want to
completely trade performance either.

I had this very questioning when developing the accelerated large arithmetic.
Maybe not everyone needs it, and it complexifies the base image.
An answer could have been to place hooks in the base image in order to
avoid overrides, so as to make the large arithmetic performance
package unloadable. Such hooks might appear as over-engineered to the
purist, but it's trade offs all the way down ;)
It would have the additional advantage of easing port to other
dialects (Cuis; Pharo, ...).

Ideally, we would write simple code, and the system would make it
efficient for us...
Maybe aggressive inlining could eliminate intermediate object creation
by itself ?

Le lun. 22 févr. 2021 à 11:32, Marcel Taeumel <[hidden email]> a écrit :

>
> > 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. :-)
>
> Best,
> Marcel
>
> 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?
>
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

marcel.taeumel
In reply to this post by Tobias Pape
Mabye we can achive this with baseclasses that use the "simple" version?

Hmm... maybe it should be in a form that does not promote re-use. Yet, it multiple methods would be involved and message/method categories wouldn't suffice --- sure --- an extra base class could work. It kind of reminds me of our RawBitsArray.

Best,
Marcel

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





Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Graphics-nice.446.mcz

Stéphane Rollandin
In reply to this post by Nicolas Cellier
>    Eliminating all the intermediate objects gives much less expressive
> code as Tom underlined
>    But providing only naive implementations hides the performance
> problems that users will have to learn sooner or later...

Exactly.

And code expressivity is a dubious criterion IMO: especially in
Smalltalk, the readability of a specific algorithm can be improved by
refactoring/renaming its primitive methods, or more simply by commenting
the non-obvious parts.

Real pedagogical value comes from explaining complex topics clearly, not
from simplifying them.

Stef

12