[squeak-dev] The Inbox: Graphics-nice.446.mcz

Levente Uzonyi leves at caesar.elte.hu
Sat Feb 20 20:51:12 UTC 2021


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 <leves at caesar.elte.hu> 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 <leves at caesar.elte.hu> 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 <leves at caesar.elte.hu> 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 commits at source.squeak.org <commits at source.squeak.org>:
>       >       >       >
>       >       >       >       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.
>       >       >       >       !
>       >       >       >
>       >       >       >
>       >       >       >
>       >       >       >
>       >       >
>       >       >
>       >       >
>       >
>       >
>       >
> 
> 
>


More information about the Squeak-dev mailing list