[squeak-dev] The Inbox: Graphics-nice.446.mcz
Nicolas Cellier
nicolas.cellier.aka.nice at gmail.com
Fri Feb 19 10:05:02 UTC 2021
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 <tomjonabc at gmail.com> 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 <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
|