On Thu, 8 Jun 2000 [EMAIL PROTECTED] wrote:
> >So, OrderedCollections are an order of magnitude faster (which I
> >expected), but IdentityDictionarys are consistently slower than
> >ictionarys, which surprised me. I wonder if that's because of using
> >SmallIntegers for the keys.
>
> Is there an implementation of LookupTable (is this name correct?)
It is in Dolphin :)
> for Squeak. This is supposed to be a Dictionary which does not use
> associations,
That was my understanding of Identity dictionary...to wit that it was
standardly implemented as a pair of arrays.
>From Dolphin's IdentityDictionary class comment (which is a subclass of
LookupTable):
IdentityDictionaries are Dictionaries which use identity (==) for key
comparison.
IdentityDictionaries do not actually store associations, but maintain the
keys and values in separate arrays
> and I understand it is speedier.
It sure would be. IDs do get better than plain Ds as the cost of #== grows
over #=. I didn't even *think* that Squeak's IDicts would use
associations.
>Maybe an
> implementation of IdentityDictionary would also be helpfully
> speedier done this way.
Argle! I would have thought so, but I ran a similar bench for Dolphin and
got (Dictionary IDic OrderedCollection)
#(100 184 83)
Remember Squeak got:
(254 239 62 )
(This is using SmallInteger indicies).
Hmm. Dolphin is whipping our pants!
But I still can't get IDicts to be faster for SmallInteger indicies :)
Oops, I did for Squeak, but not for Dolphin.
Er.. ok, multiruns reveal:
#(157 125 36)#(88 105 30) #(231 111 71)
Clearly, something like GC is interfering, which just goes to show how
crappy my crappy benchmarks were ;)
ARRRRRRRRRRRGH :)
Not that in Dolphin, MethodDictionary is a subclass of
IdentityDictionary. In Squeak, it's a subclass of *Dictionary* *but*
(from the class comment):
I am just like a normal Dictionary, except that I am implemented
differently.
[snip I love this first line :)]
In a normal Dictionary, the instance variable 'array' holds an array of
Associations. Since there are thousands of methods in the system, these
Associations waste space.
Each MethodDictionary is a variable object, with the list of keys
(selector Symbols) in the variable part of the instance. The variable
'array' holds the values, which are CompiledMethods.
-----------
This is exactly the parallel array implementation.
But the SmallInteger index test give (using Method- instead of
Identity-) yields:
(207 272 56 ) (242 256 61 ) (218 213 76 )
So who *knows* what's going on?!?
(I do! My benchmarks *reeeeeeeeeeally* suck. :))
So, I'll say some more stupid things! ;)
Fast MethodDictionaries are good. Make insertion slow as hell if you like
(though doit's won't like it :))...increasing lookup speed in
MethodDictionary increases method dispatching speed...which speeds up just
about everything.
Cheers,
Bijan Parsia.
