weak key dictionary

Chris Muller asqueaker at gmail.com
Wed Mar 28 02:56:31 UTC 2007


Magma's test-cases have uncovered an apparent issue with the new
WeakKeyDictionary.  The serializer for Magma makes heavy-use of a
WeakKeyIdentityDictionary at its core to keep track of oids for
objects.

I've managed to create a workspace script that reproduces the problem
in a stock image.

After loading the weakfix[1-4].cs into a standard 3.9-7067 image, you
can reproduce the issue with the following script:

	|wd obj|
	500 timesRepeat:
	[ obj _ Object -> (Set withAll: 'a collection of strings' substrings).
	wd _ WeakIdentityKeyDictionary new.
	wd
		at: obj put: 66542 ;
		at: (IdentitySet with: ('hello->world')) put: 66543 ;
		at: Object put: 66544 ;
		at: obj value put: 66545.
	wd at: (#Object->103) put: 66546.
	nextOid _ 66545.
	obj value do:
		[ : each |
		wd at: each put: (nextOid _ nextOid+1) ].
	wd at: OrderedCollection new put: 66552.
	wd at: OrderedCollection new put: 66553.
	wd at: Array new put: 66554.
	wd at: #Association->104 put: 66555.
	wd at: #Association put: 66556.
	wd at: (Association allInstVarNames) put: 66557 ].

Sorry it's not simpler, (I culled it from Magma's serialization code).
 A simpler case may also fail too, but the problem appears to be
gc-timing related.  I have also posted the stack-trace from Magma
below.

WeakKeyIdentityDictionary has always been a bane of Magma's
performance, so I'm quite excited about the work you're doing here.

Thanks,
  Chris

Image: Squeak3.9 [latest update: #7067]

WeakIdentityKeyDictionary(Object)>>error:
	Receiver: a WeakIdentityKeyDictionary(Object->a Set('a' 'collection'
'of' 'strings')->66542 )
	Arguments and temporary variables:
		aString: 	'could not find an empty slot.'
	Receiver's instance variables:
		tally: 	1
		array: 	an Array(Object->a Set('a' 'collection' 'of'
'strings')->66542 nil nil n...etc...
		expired: 	0

WeakIdentityKeyDictionary(WeakKeyDictionary)>>noCheckAdd:
	Receiver: a WeakIdentityKeyDictionary(Object->a Set('a' 'collection'
'of' 'strings')->66542 )
	Arguments and temporary variables:
		anAssociation: 	nil->66546
		key: 	nil
		n: 	1
		nLimiT: 	20
	Receiver's instance variables:
		tally: 	1
		array: 	an Array(Object->a Set('a' 'collection' 'of'
'strings')->66542 nil nil n...etc...
		expired: 	0

[] in WeakIdentityKeyDictionary(Set)>>grow {[:each | each   ifNotNil:
[self noCheckAdd: each]]}
	Arguments and temporary variables:
		oldElements: 	an Array(Object->a Set('a' 'collection' 'of'
'strings')->66542 nil...etc...
		each: 	nil->66546

Array(SequenceableCollection)>>do:
	Receiver: an Array(Object->a Set('a' 'collection' 'of'
'strings')->66542 nil->66546 'collection'->66...etc...
	Arguments and temporary variables:
		aBlock: 	[] in WeakIdentityKeyDictionary(Set)>>grow {[:each | each
ifNotNil: [...etc...
		index: 	2
		indexLimiT: 	10
	Receiver's instance variables:
an Array(Object->a Set('a' 'collection' 'of' 'strings')->66542
nil->66546 'collection'->66...etc...


--- The full stack ---
WeakIdentityKeyDictionary(Object)>>error:
WeakIdentityKeyDictionary(WeakKeyDictionary)>>noCheckAdd:
[] in WeakIdentityKeyDictionary(Set)>>grow {[:each | each   ifNotNil:
[self noCheckAdd: each]]}
Array(SequenceableCollection)>>do:
 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
WeakIdentityKeyDictionary(Set)>>grow
WeakIdentityKeyDictionary(WeakKeyDictionary)>>grow
WeakIdentityKeyDictionary(Set)>>fullCheck
WeakIdentityKeyDictionary(WeakKeyDictionary)>>fullCheck
WeakIdentityKeyDictionary(Set)>>atNewIndex:put:
WeakIdentityKeyDictionary(WeakKeyDictionary)>>at:put:
MagmaOidManager>>oidOf:is:
[] in MagmaOidManager(MaOidManager)>>oidFor: {[self oidOf: anObject
is: self getNextOid]}
WeakIdentityKeyDictionary(Dictionary)>>maAt:ifPresent:ifAbsent:
MagmaOidManager(MaOidManager)>>oidFor:ifAbsent:
[] in MagmaOidManager>>oidFor:ifAbsent: {[super oidFor: anObject
ifAbsent: aBlock]}
WeakIdentityKeyDictionary(Dictionary)>>maAt:ifPresent:ifAbsent:
MagmaOidManager>>oidFor:ifAbsent:
MagmaOidManager(MaOidManager)>>oidFor:
MaObjectSerializer>>oidFor:
MaVariableObjectBuffer>>numberToStoreFor:using:
[] in Set>>maStreamVariablyInto:for: {[:eachLinkedObject |
aMaVariableBuffer   maInstVarAt: index   put: (aMaVari...]}
Set>>do:
Set>>maStreamVariablyInto:for:
MaVariableObjectBuffer>>populateBodyFor:using:
MaObjectSerializer>>bufferFor:storageObject:startingAt:
MaObjectSerializer>>append:
[] in MaObjectSerializer>>appendGraph:do: {[:path :parent :index |
(path last    maShouldAppendWithPath: path    parent...]}
Association(ProtoObject)>>maValueGraphNode:index:using:with:path:with:
Association(ProtoObject)>>maGraphDo:using:path:with:
MaRootAnchor(ProtoObject)>>maValueGraphNode:index:using:with:path:with:
MaRootAnchor(ProtoObject)>>maGraphDo:using:path:with:
IdentitySet(ProtoObject)>>maValueGraphNode:index:using:with:path:with:
[] in IdentitySet(Set)>>maGraphDo:using:path:with: {[:each |  self
maValueGraphNode: each   index: varIndex   using: aObjectTr...]}
IdentitySet(Set)>>do:
IdentitySet(Set)>>maGraphDo:using:path:with:
UndefinedObject(ProtoObject)>>maValueGraphNode:index:using:with:path:with:
IdentitySet(Object)>>maGraphDo:using:
MaObjectSerializer>>appendGraph:do:
MaObjectSerializer>>serializeGraph:do:
[] in MaCommitPackage>>serializeObjectsUsing: {[objects := serializer
   serializeGraph: objects     do: [:each |       (s...]}
BlockContext>>on:do:
MaCommitPackage>>serializeObjectsUsing:
MagmaSession>>newCommitPackageFor:
MagmaSession>>commitAndBegin:
MagmaSession>>commit
MagmaSession>>commit:
...etc...


On 3/27/07, Ralph Johnson <johnson at cs.uiuc.edu> wrote:
> There is a much faster version of WeakKeyDictionary discussed at
> http://bugs.squeak.org/view.php?id=6348
>
> If you have used it, please add a comment to the Manit issue.  If you
> are using WeakKeyDictionary, please try out the improved version and
> let us know how it works.
>
> I'd like to include this in 3.10.  It looks reasonable, but I don't
> use WeakKeyDictionary and so I don't have any projects to try it on.
> I don't want to include this code until we get positive feedback from
> people other than the author.
>
> -Ralph Johnson
>
>



More information about the Squeak-dev mailing list