On Fri, Mar 23, 2012 at 07:01:46PM +0100, Timon Gehr wrote:
> Why do you not just do the conversion and then compute the hash, even if the representation is the same?

Because Andrei says that the .idup shouldn't be performed unless it's necessary (e.g., you should be able to lookup char[] in a string-keyed AA without incurring the overhead of an .idup each time). The conversion is not needed if the hash computation doesn't change and we don't need to create a new entry.


T

-- 
Lawyer: (n.) An innocence-vending machine, the effectiveness of which depends on how much money is inserted.

On 03/23/2012 07:10 PM, H. S. Teoh wrote:
> On Fri, Mar 23, 2012 at 07:01:46PM +0100, Timon Gehr wrote:
>> Why do you not just do the conversion and then compute the hash, even
>> if the representation is the same?
>
> Because Andrei says that the .idup shouldn't be performed unless it's
> necessary (e.g., you should be able to lookup char[] in a string-keyed
> AA without incurring the overhead of an .idup each time). The conversion
> is not needed if the hash computation doesn't change and we don't need
> to create a new entry.
>
>
> T
>

That does not apply to your example with double and int. (I'd argue that actually the other overload should be chosen in that case, because the conversion is implicit)

For implicit .idup, one solution would be to compare immutable(Key) and immutable(T). If they are the same, then the representation is the same.

On Fri, Mar 23, 2012 at 07:18:05PM +0100, Timon Gehr wrote:
> On 03/23/2012 07:10 PM, H. S. Teoh wrote:
> >On Fri, Mar 23, 2012 at 07:01:46PM +0100, Timon Gehr wrote:
> >>Why do you not just do the conversion and then compute the hash, even if the representation is the same?
> >
> >Because Andrei says that the .idup shouldn't be performed unless it's necessary (e.g., you should be able to lookup char[] in a string-keyed AA without incurring the overhead of an .idup each time). The conversion is not needed if the hash computation doesn't change and we don't need to create a new entry.
[...]
> 
> That does not apply to your example with double and int. (I'd argue that actually the other overload should be chosen in that case, because the conversion is implicit)

Sorry, I didn't understand that... which other overload?


> For implicit .idup, one solution would be to compare immutable(Key)
> and immutable(T). If they are the same, then the representation is the
> same.

Excellent idea! I didn't think about using qualifier collapsing to check for representation equivalence. Thanks! :-)

I think this issue is now solvable: if a key is implicitly convertible to the AA key but it's *not* equivalent, then convert it first. Otherwise, convert it later via .idup or some analogous mechanism.

	template isEquiv(T,U) {
		enum isEquiv = is(immutable(T)==immutable(U));
	}
	...
	static if (is(InputKey : Key) && !isEquiv!(InputKey,Key))
		// convert now
	else
		// convert later


T

-- 
The irony is that Bill Gates claims to be making a stable operating system and Linus Torvalds claims to be trying to take over the world. -- Anonymous

On Fri, Mar 23, 2012 at 01:31:28PM -0500, Andrei Alexandrescu wrote: [...]
> Let's see what requirements need to be satisfied by []. Say k is a value of the key type and x is a value being looked up.
> 
> First, we need to be able to evaluate k == x. So the types must be comparable.
> 
> Second, we need if x == k, then hash(k) == hash(x). This is tricky
> in general, but let's say we can approximate to the compile-time
> requirement that the hash function resolves to the same entity for
> both typeof(x) and typeof(k). This would rule out e.g. int and
> double but would leave char[] and string.

How do we check at compile time whether the hash function resolves to the same entity?


> To include int and double correctly, we'd amend the second rule as
> follows. If typeof(x) converts implicitly to typeof(k), then use
> hash(cast(typeof(k)) x) instead of hash(x). This makes it possible
> to look up for an int in a hash of doubles, but not vice versa,
> which is great.

OK.


> These two are sufficient for lookup. For store, we also need the
> third rule, which is to!(typeof(k))(x) must compile and run.
[...]

Isn't this already required by the hash lookup? Or is casting different from to!X, in which case it might be messy to import the relevant parts of phobos into druntime. :-/


T

-- 
"A man's wife has more power over him than the state has." -- Ralph Emerson

On 3/23/12 1:48 PM, H. S. Teoh wrote:
> How do we check at compile time whether the hash function resolves to
> the same entity?

int fun(T)(T x) {
    return 42;
}

void main() {
    static assert(&fun!int != &fun!double);
}

This actually reveals a compiler bug:

Assertion failed: (d->purity != PUREfwdref), function typeMerge, file cast.c, line 1909.

A cast would be needed anyway because they have different types, too. Anyway upon more thinking maybe this is too restrictive a rule. It won't catch e.g. functions that are, in fact, identical, but come from distinct instantiations.

So perhaps you need some conservative approximation, i.e. look if the two types are qualified versions of the same type and then assume they hash the same.

>> To include int and double correctly, we'd amend the second rule as
>> follows. If typeof(x) converts implicitly to typeof(k), then use
>> hash(cast(typeof(k)) x) instead of hash(x). This makes it possible
>> to look up for an int in a hash of doubles, but not vice versa,
>> which is great.
>
> OK.
>
>
>> These two are sufficient for lookup. For store, we also need the
>> third rule, which is to!(typeof(k))(x) must compile and run.
> [...]
>
> Isn't this already required by the hash lookup? Or is casting different
> from to!X, in which case it might be messy to import the relevant parts
> of phobos into druntime. :-/

Casting is very different from to, and useless for your purposes. You must use to.


Andrei

On 03/23/2012 08:06 PM, Andrei Alexandrescu wrote:
>
> Casting is very different from to, and useless for your purposes. You
> must use to.
>
>
> Andrei

druntime mustn't depend on Phobos, and I don't see why it is necessary. What kind of functionality do you want to provide that depends on std.conv.to ?

On Fri, Mar 23, 2012 at 02:06:15PM -0500, Andrei Alexandrescu wrote: [...]
> A cast would be needed anyway because they have different types, too. Anyway upon more thinking maybe this is too restrictive a rule. It won't catch e.g. functions that are, in fact, identical, but come from distinct instantiations.
> 
> So perhaps you need some conservative approximation, i.e. look if the two types are qualified versions of the same type and then assume they hash the same.

OK. Would the following be enough?

	template isEquiv(T,U) {
		enum isEquiv = is(immutable(T)==immutable(U));
	}


[...]
> >Isn't this already required by the hash lookup? Or is casting different from to!X, in which case it might be messy to import the relevant parts of phobos into druntime. :-/
> 
> Casting is very different from to, and useless for your purposes.  You must use to.
[...]

Wouldn't that require moving std.conv into druntime?  And std.conv does depend on std.traits as well...


T

-- 
Without outlines, life would be pointless.

On 3/23/12 2:28 PM, Timon Gehr wrote:
> On 03/23/2012 08:06 PM, Andrei Alexandrescu wrote:
>>
>> Casting is very different from to, and useless for your purposes. You
>> must use to.
>>
>>
>> Andrei
>
> druntime mustn't depend on Phobos, and I don't see why it is necessary.
> What kind of functionality do you want to provide that depends on
> std.conv.to ?

Casting from char[] to string is not what you want, and .idup is specific to arrays. There must be one coherent method of "truely" converting across types, and std.conv.to is the closest I can think of.

Andrei

On 3/23/12 2:30 PM, H. S. Teoh wrote:
> Wouldn't that require moving std.conv into druntime?  And std.conv does
> depend on std.traits as well...

Not sure how it's best to address this.

Andrei

On 03/23/2012 09:05 PM, Andrei Alexandrescu wrote:
> On 3/23/12 2:28 PM, Timon Gehr wrote:
>> On 03/23/2012 08:06 PM, Andrei Alexandrescu wrote:
>>>
>>> Casting is very different from to, and useless for your purposes. You
>>> must use to.
>>>
>>>
>>> Andrei
>>
>> druntime mustn't depend on Phobos, and I don't see why it is necessary.
>> What kind of functionality do you want to provide that depends on
>> std.conv.to ?
>
> Casting from char[] to string is not what you want, and .idup is
> specific to arrays. There must be one coherent method of "truely"
> converting across types, and std.conv.to is the closest I can think of.
>
> Andrei

This will statically allow looking up an int in a T[string].
I don't think that is desirable. I even think implicit .idup may be overkill.