weak key dictionary

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

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 <[hidden email]> wrote:

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

Thanks for the tests. I found the problem: it was giving up on finding
a new slot too early. Attached is a fix; please let me know how it goes.

I will produce a new patch set.

Regards,
Martin

'From Squeak3.9 of 7 November 2006 [latest update: #7067] on 28 March 2007 at 10:28:47 am'! !WeakKeyDictionary methodsFor: 'finalization' stamp: 'mvl 3/28/2007 10:26'! noCheckAdd: anAssociation "Add anAssociation to the receiver. Discard expired associations. Put nil keys at the beginning." | key | key := anAssociation key. "Hold on to the key during this method" anAssociation expired ifFalse:[ key ifNotNil:[ super noCheckAdd: anAssociation ] ifNil: [ 1 to: array size do:[:n| (array at: n) ifNil:[ array at: n put: anAssociation. tally := tally + 1. ^self ]. ]. self error: 'could not find an empty slot.' ]. ].! !