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
|