While I was on vacation, John Brant pinged me encouraging me to use a #changeClassTo: strategy instead of #become:. To do so, first I cloned the Chain class as a new class called Rope (and the Empty variant as well).
Then we make EmptyRope a subclass of Rope. This is important, because we need an EmptyRope to have the same instance variable layout as a Rope. #changeClassTo: will only change the type or class of an object, if they have the same instance variable layout. We'll just make sure that never actually set or reference the key, value, or nextKnot variables in the EmptyRope subclass.
In the case of adding a new key/value pair, when our #at:put: reaches the end of the list, the EmptyRope subclass can just implement it as
And the only thing #removeKey: has to do in addition to the original #replace: trick is do a
at: aKey put: anObject
next: EmptyRope basicNew.
self changeClassTo: Rope
to get the last link to be an EmptyRope.
previousKnot changeClassToThatOf: self
Most of the rest of the code stays the same. We can reduce a couple of duplicates since the classes are now in a parent-child relationship, rather than a sibling one.
The at:put:/removeKey: test is the interesting one to rerun and see how things fair. First of all, we compare the new Rope approach to the original Chain one.
That shows some improvement across the board. The real test though, is how does it compare to the original IdentityDictionary?
The good news is, it's actually faster. Not by a huge amount. But it removes it from something you have to worry about.
I've replicated the Rope code up to the Open Repository (package TAG-Ropes). If you know you're using smallish dictionaries (size <= 15) and need to care about performance, then this might be the thing for you.
It would be interesting to see how such an approach fared in GNU Smalltalk or one of the other Smalltalks.