[squeak-dev] The Inbox: Graphics-nice.446.mczTom Beckmann tomjonabc at gmail.comSat Feb 20 12:28:48 UTC 2021
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 <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. > > > > ! > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20210220/ed1ae49d/attachment.html>
More information about the Squeak-dev mailing list |