[squeak-dev] Association >> #hash performance

christoph.thiede at student.hpi.uni-potsdam.de christoph.thiede at student.hpi.uni-potsdam.de
Thu May 26 21:00:09 UTC 2022

Hi all!

while playing around with code simulation recently, I found out that the following dictionary lookup consumes extremely many bytecodes:

    UserInterfaceTheme current get: #return for: SHTextStylerST80.

Dictionary >> #scanFor: takes 59 (sic!) attempts to find the right item in the dictionary. In other words, almost 20% of the property table is traversed, which does not conform my idea of a hashtable.

The reason for this can be found in Association >> #hash: Since Collections-ar.304, it does not take the value of an association into consideration for the hash any longer. As UserInterfaceTheme uses Associations as keys in the Dictionary, we have a lot of "hash misses". Even though you might not notice this in practice, I noticed this indeed during debugging und simulating, I can tell you. :-)

On the other hand, reverting Association >> #hash to honor the value slows down Unicode class compileAll indeed (significantly: 60 ms vs. 2100 ms), as noted in Andreas' original comment:

    Name: Collections-ar.304
    Author: ar
    Time: 11 February 2010, 11:52:58.959 pm
    UUID: 9e97b360-adf1-f745-8f8c-562aa08d566e
    Ancestors: Collections-ar.303
    Fix an age-old bug in Association>>hash which causes extreme slowdowns in compiling Unicode methods. Association>>hash does not need to hash the value; it's slow and useless.

So my question is: What would be the right fix for this situation? Is it
a) Do not use Associations in Dictionarys when its value matters for the lookup; or
b) Do only use Associations in Dictionarys when its value maters for the lookup?
For a), the dictionary layout of UserInterfaceTheme needs to be changed, for which I am attaching a changeset that replaces Associations by Arrays there.* For b), the layout of litIndSet in Encoder needs to be changed, for instance by using Bindings instead of Associations for classPool entries. However, I'm not familiar enough with Encoder etc. to answer this question.

*The changeset will automatically update all UserInterfaceTheme instances. Benchmark:

    theme := UserInterfaceTheme current.
    random := Random seed: 20220526.
    properties := (1 to: 10000) collect: [:i | theme properties keys atRandom: random].
    [properties collect: [:ea | theme get: ea]] bench.

Old: 45 ms | New: 10 ms

Looking forward to your opinion: How should we treat Associations in Dictionarys? Of course, this is not release-critical. :-)


=============== Postscript (accelerateUserInterfaceTheme.2.cs) ===============

"Postscript: Update UserInterfaceTheme instances"

UserInterfaceTheme allSubInstancesDo: [:theme |
	| newProperties |
	newProperties := theme properties copyEmpty.
	theme properties keysAndValuesDo: [:key :value |
			at: ((key isKindOf: Association)
				ifTrue: [{key key. key value}]
				ifFalse: [key])
			put: value].
	theme instVarNamed: 'properties' put: newProperties].

=============== Diff ===============

UserInterfaceTheme>>get: {private} · ct 5/26/2022 21:15 (changed)
get: keyObject 
	"keyObject is intended to be an Association. We have two lookup strategies: 1) along the superclass chain *of the client*, 2) via a linked theme. Evaluate the result because there can be message sends stored or blocks."
	| k |
		at: keyObject
		ifPresent: [:prop | ^ prop value].
- 	keyObject isVariableBinding "simple key objects"
+ 	keyObject isArray "simple key objects"
		ifFalse: [^ self getViaLink: keyObject].
- 	k := keyObject key.
+ 	k := keyObject at: 1.
	(self getViaSuperclasses: keyObject)
		ifNotNil: [:prop | ^ prop].
- 	keyObject key: k. "restore"
+ 	keyObject at: 1 put: k. "restore"
	^ self getViaLink: keyObject

UserInterfaceTheme>>get:for: {private} · ct 5/26/2022 21:02 (changed)
get: propertySymbol for: scope
	"For convenience. Does support access to non-class keys."
	| aClass |
	aClass := (scope isNil or: [scope isBehavior])
		ifTrue: [scope]
		ifFalse: [Smalltalk classNamed: scope].

- 	aClass ifNotNil: [^ self get: aClass -> propertySymbol].
+ 	aClass ifNotNil: [^ self get: {aClass. propertySymbol}].
- 		at: scope -> propertySymbol
+ 		at: {scope. propertySymbol}
		ifPresent: [:prop | ^ prop value].
- 	^ self getViaLink: scope -> propertySymbol
+ 	^ self getViaLink: {scope. propertySymbol}

UserInterfaceTheme>>getViaSuperclasses: {private} · ct 5/26/2022 21:15 (changed)
getViaSuperclasses: keyObject 
	"keyObject is intended to be an Association.
	Find the superclass of the key of the keyObject (which will initially be the client's class) and make a new keyObject using that and the original message name, then try searching for that."
	"We know we're the only referencer of keyObject.  Update it rather than create new ones, for performance reasons."
- 	keyObject key: keyObject key superclass.
+ 	keyObject at: 1 put: (keyObject at: 1) superclass.

- 	keyObject key ifNil: [^ nil].
+ 	(keyObject at: 1) ifNil: [^ nil].
		at: keyObject
		ifPresent: [:prop | ^ prop value].
	^ self getViaSuperclasses: keyObject

UserInterfaceTheme>>set:for:to: {building} · ct 5/26/2022 21:03 (changed)
set: propertySymbol for: aClassOrSymbol to: valueObject
	"Where aClass asks its userInterfaceTheme for propertySymbol, provide valueObject."
	| aClass |
	aClass := aClassOrSymbol isBehavior ifTrue: [aClassOrSymbol] ifFalse: [Smalltalk classNamed: aClassOrSymbol].
	aClass ifNil: [^ self].
	^ self atomicUpdate:
		[ : props | | key |
- 		key := aClass -> propertySymbol.
+ 		key := {aClass. propertySymbol}.
				[ props
					removeKey: key
					ifAbsent: [ "already cleared, don't error" ] ]
				[ props
					at: key
					put: valueObject ] ]

UserInterfaceThemeRequest>>doesNotUnderstand: {lookup} · ct 5/26/2022 21:02 (changed)
doesNotUnderstand: aMessage 
	"Look up the visual attribute specified by aMessage's #selector in the current theme for the current target object."

	aMessage numArgs = 0 ifTrue: [
- 		^ (self theme get: self target class -> aMessage selector)
+ 		^ (self theme get: {self target class. aMessage selector})
			ifNil: [(self theme respondsTo: aMessage selector)
				ifTrue: [self theme perform: aMessage selector]
				ifFalse: [nil "unset property"]]].
	aMessage numArgs = 1 ifTrue: [
		^ self theme
- 			set: self target class -> aMessage selector asSimpleGetter
+ 			set: {self target class. aMessage selector asSimpleGetter}
			to: aMessage arguments first].
	^ self theme
		perform: aMessage selector
		withArguments: aMessage arguments.

Sent from Squeak Inbox Talk
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20220526/1f359210/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: accelerateUserInterfaceTheme.2.cs
Type: application/octet-stream
Size: 3567 bytes
Desc: not available
URL: <http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20220526/1f359210/attachment.obj>

More information about the Squeak-dev mailing list