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

Levente Uzonyi leves at caesar.elte.hu
Thu Feb 18 23:16:48 UTC 2021


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