tuples as keys in Hashtable

[Michal Moskal]

Michal,
While trying to figure out why Pruner.Alignment is soooo slow I bumped
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/

[Michal Moskal]

Post by Michal Moskal
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).

I wrote the `nested hashtables' solution in a (dumb) generic way and
hit something that might be a bug in the type inference. See the
attached file.

This is a case, which our type inference cannot handle. The only way
the compiler could deduce correct type for c.K(1).K is by looking at
all the classes which contains the field/method K, which we never do.

Basically you need to use type constraints in such cases, the minimal
type constraints that work in this case are:

def c : Cache[_, Cache[_, CacheVal [_]]] = Cache()

Hope this helps,
Micha³

[vc]

The following test work well, but similar C# program will fail (in C# we can
overload operators only for yours types).
This is expected behavior?

using System;
using System.Console;
using Overl; // This is expected behavior?

module Overl
{
public @+(date : DateTime, delta : long) : DateTime // This is expected
behavior?
{
def d = TimeSpan(delta);
date + d
}
}

module Program
{
Main() : void
{
def now = DateTime.Now;
WriteLine(now);
WriteLine(now + 20000000L);
_ = ReadLine();
}
}

[Kamil Dworakowski]

Post by vc
This is expected behavior?

Quite a useful feature, I'd say.

-- Kamil Dworakowski

[vc]

Post by Kamil Dworakowski

Post by vc
This is expected behavior?

Quite a useful feature, I'd say.

Yes. I agree with you. But, unfortunately, it feature cause a bug:
http://nemerle.org/bugs/view.php?id=1026

Vlad

[Kamil Skalski]

I thought that there was a similar check as in C# - one of parameters
(or return type?) must be the same as current class...

Post by vc

Post by Kamil Dworakowski

Post by vc
This is expected behavior?

Quite a useful feature, I'd say.

http://nemerle.org/bugs/view.php?id=1026
Vlad
_______________________________________________
https://nemerle.org/mailman/listinfo/devel-en

[vc]

Post by Kamil Skalski
I thought that there was a similar check as in C# - one of parameters
(or return type?) must be the same as current class...

Yes. This code:
class B { }

class A
{
public static implicit operator B (int x)
{
return new B();
}
}
in C# cause:
error CS0556: User-defined conversion must convert to or from the enclosing
type

But, this behavior is cool :).

If you fix this bug:
http://nemerle.org/bugs/view.php?id=1026
of course...

Post by Kamil Skalski

Post by vc

Post by Kamil Dworakowski

Post by vc
This is expected behavior?

Quite a useful feature, I'd say.

http://nemerle.org/bugs/view.php?id=1026
Vlad
_______________________________________________
https://nemerle.org/mailman/listinfo/devel-en

--
Kamil Skalski
http://nazgul.omega.pl
_______________________________________________
https://nemerle.org/mailman/listinfo/devel-en

[Dmitry Ivankov]

Post by vc
using Overl; // This is expected behavior?
module Overl { ........

Such forward using seems to be expected, I've found the same thing
in testsuite/positive/operators.n