[nem-en] Re: tuples as keys in Hashtable

[Michal Moskal]

On 6/7/07, Radu Grigore <radugrigore at gmail.com> wrote:
> Michal,
>
> While trying to figure out why Pruner.Alignment is soooo slow I bumped
> into the following problem (which is probably not the main culprit):
> If you run Tmp.n with TupleCache it works about 20 times faster than
> if you run it with Hashtable. The difference seems rather big.

It seems to be related to boxing. Right now, the Tuple classes and
structs do not implement the IEquatable interface, which means that
the hashtable uses Equals(object) overload (I'm not sure about
GetHashCode calls). This of course causes boxing.

We also do not require tuple elements to support the IEquatable[T]
interface, which means the elements are boxed when calling Equals on
them.

The first one can be fixed, and the second one doesn't seem to be
possibly to fix easily, but the good news seems to be that at least in
case of structs (tuple-2 and tuple-3), the JIT seems to manage to
optimize calls to Equals() and get rid of boxing. It also doesn't seem
to matter when we know the type to be int, to use == or Equals (see
attached testcase).

I'll try modifying tuples to support IEqutable, which should make
hashtabling them several times faster, but still about 4 times slower
than your two level hashtable (which is in fact 70 times faster than
hashtabling the tuples).

> Unrelated: What's the idea with %^ ? It seems to do the same as ^ but
> I couldn't find (on nemerle.org) why there are two versions.

Because we couldn't use |, so we used %| and to be consistent also
other bit operators got their %-versions.

> regards,
>  radu
> http://rgrig.blogspot.com/


-- 
   Michał
-------------- next part --------------
A non-text attachment was scrubbed...
Name: radu-testcase.n
Type: application/octet-stream
Size: 841 bytes
Desc: not available
Url : /mailman/pipermail/devel-en/attachments/20070607/06b466a7/radu-testcase.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: several-versions.n
Type: application/octet-stream
Size: 5352 bytes
Desc: not available
Url : /mailman/pipermail/devel-en/attachments/20070607/06b466a7/several-versions.obj