SmallDictionary to RBSmallDictionary renaming

Why was SmallDictionary class renamed to RBSmallDictionary class in RC1?
I've used same class for a long time and was very happy when it appeared in
5.0. Sometimes it's very convenient to use dictionary with ordered keys and
values.
--
Dmitry Zamotkin

"Dmitry Zamotkin" <[hidden email]> wrote in message
news:[hidden email]...
> Why was SmallDictionary class renamed to RBSmallDictionary class in RC1?

Because it is part of the implementation of the Refactoring Browser, that
was mistakenly renamed during the original porting work, and is not
completely interchangeable with a Dictionary - it's missing quite a lot of
even the ANSI <abstractDictionary> protocol.

> I've used same class for a long time and was very happy when it appeared
in
> 5.0. Sometimes it's very convenient to use dictionary with ordered keys
and
> values.

The fact that the keys and values are stored (and enumerated) in insertion
order is really an implementation detail, and not guaranteed. The purpose of
RBSmallDictionary is purely to provide a more efficient implementation for
small numbers of key/value pairs, not to impose any particular ordering.
There is no guarantee that the implementation will remain the same in the
future, and the dictionary is inefficient for more than a few elements (I'm
not sure exactly where the crossover point lies), so it isn't an ideal
implementation of an ordered map in any case.

To load old packages that reference SmallDictionary, just create a global
alias as follows:

    SmallDictionary := RBSmallDictionary

Regards

Blair

Blair McGlashan wrote:

> the dictionary
> is inefficient for more than a few elements (I'm not sure exactly
> where the crossover point lies)

A quick test suggests that break-even comes at 3 elements (compared with a
LookupTable).

Since there's only a 1 usec difference (for #at:) even when it has only one
element (on a slowish machine), the class seems to be of questionable utility.
(Maybe the tradeoffs are different on different Smalltalk implementations).

    -- chris

Chris

You wrote in message news:3e9d65f1$0$45182$[hidden email]... one
> element (on a slowish machine), the class seems to be of questionable
utility.

I would tend to agree, but...

> (Maybe the tradeoffs are different on different Smalltalk
implementations).

Yes I imagine that is the case. Perhaps John Brant could comment, but I
imagine that RBSmallDictionary was helpful in improving the performance of
the Refactoring Browser in either VW or VA implementations. On Dolphin it
might not actually make much difference relative to a LookupTable, and an
alias over to that might eliminate the need for the class with no
perceptible performance difference.

Regards

Blair

"Blair McGlashan" <blair@no spam object-arts.com> wrote in message
news:3e9d8097$[hidden email]...
>
> You wrote in message news:3e9d65f1$0$45182$[hidden email]...
> > Blair McGlashan wrote:
> >
> > > the dictionary
> > > is inefficient for more than a few elements (I'm not sure exactly
> > > where the crossover point lies)
> >
> > A quick test suggests that break-even comes at 3 elements (compared with
a
> > LookupTable).
> >
> > Since there's only a 1 usec difference (for #at:) even when it has only
> one
> > element (on a slowish machine), the class seems to be of questionable
> utility.
>
> I would tend to agree, but...

It also depends on what is thrown in the dictionary. The RBSmallDictionary
doesn't send the #hash message, so if you have a slow hash function it can
be faster. If I recall correctly, I found the break-even point being ~5 for
the parse trees. Since most search/replace expressions have ~3 items, it is
somewhat faster. My tests were from 6 years ago, so they might be somewhat
different on today's machines and VM's.

If you want to know the main reason for implementing the RBSmallDictionary,
look at the #empty method :-). Normal dictionaries don't have methods for
emptying themselves so we needed to create a new dictionary for every match
attempt. Furthermore, using a normal dictionary requires creating an
association for every item in the dictionary. All of these little objects
were stressing the garbage collector so I opted to implement a dictionary
that one could empty. One of my tests from 6 years ago showed that running
the Smalllint checks on a VA image resulted in over 177 million match
attempts. Prior to the RBSmallDictionary, this would have resulted in over
177 million dictionary objects created (and that doesn't count the
associations for each of the objects stored in the dictionary).

BTW, I know that the current implementation of the #empty method leaks
objects (i.e., the key and value arrays still hold on to their previous
contents). However, this is normally not a problem with parse tree searching
since the old items will soon be overwritten.


John Brant

John Brant wrote:

> If you want to know the main reason for implementing the
> RBSmallDictionary, look at the #empty method :-). Normal dictionaries
> don't have methods for emptying themselves

I have never understood why there is no standard operation for emptying
Collections; it is, after all, hardly an obscure operation.

Blair, would adding #removeAll (selector chosen to avoid the ambiguity of, say,
#clear or  #empty, which could be tests rather than operations) be an undue
"fattening" of the Collections interface ?

    -- chris