Rope: an evolved Chain

One of the areas my Chain did not come out ahead was in the area of adding truly new keys to a Dictionary (as opposed to just updating what already was stored at a given key) or removing them. Both of these operations potentially involve #become: sends. While VisualWorks #become: is very fast, it's not as fast as some other operations. And not all Smalltalk implementations have a fast #become:. Here's the chart of how well Chain compared to IdentityDictionary for original key add/removal.


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

at: aKey put: anObject
   self
      setKey: aKey
      value: anObject
      next: EmptyRope basicNew.
   self changeClassTo: Rope

And the only thing #removeKey: has to do in addition to the original #replace: trick is do a

   previousKnot changeClassToThatOf: self

to get the last link to be an EmptyRope.

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.