[LLVMdev] We need better hashing

[Talin]

OK committed. Let the shaving begin! :)

On Sat, Feb 18, 2012 at 3:20 AM, Chris Lattner <clattner at apple.com> wrote:

> On Feb 18, 2012, at 1:11 AM, Talin wrote:
>
> +  /// Add an ArrayRef of arbitrary data.
>> +  template<typename T>
>> +  GeneralHash& add(ArrayRef<T> ArrayVal) {
>> +    addBits(ArrayVal.begin(), ArrayVal.end());
>> +    return *this;
>> +  }
>>
>> Doesn't this have the same host-specificity problem, except that it will
>> cause things that *are* stable to vary, such as arrays of char, or is the
>> alignment check enough?
>>
>> I thought about whether it would be possible to prevent people from
> passing in ArrayRefs with unstable things, and I came to the conclusion
> that there's no simple way to distinguish between stable and unstable
> ArrayRefs. This is why I decided not to make a special "addPointer" method
> for pointers, because you could easily subvert it by wrapping it in a
> singleton ArrayRef.
>
>
> Ok.
>
>  +  /// Add a float
>> +  GeneralHash& add(float Data) {
>>
>> It is worth adding a comment here that this does a bitwise hash, so -0.0
>> and +0.0 will hash to different values even though they compare equal and
>> two identical NaN's will hash to the same value even though they compare
>> unequal.
>>
>> BTW, are there in fact any maps in LLVM that use floats as keys, other
> than uniquing of constants? And in the latter case, would you not want to
> distinguish between a -0.0 and +0.0 constant?
>
>
> I don't know of any.  I think that the ConstantFP uniquing code
> specifically has to unique things as integers to avoid problems with FP
> comparisons.   In any case, I'm sure that the desired behavior is client
> specific - adding the comment just makes it obvious what the semantics are.
>
>
>    Actually, how much do we care about host instability here?  If this is
> used by hashing containers, we can just declare that iteration order is
> undefined even for non-pointer values.  The real problem I guess is that
> we'd have to go check out all the existing DenseMap's etc to make sure
> people aren't doing well-defined iteration right now and fixing the code.
>  What do you think?
>
>>
>> I think that you are thinking that existing uses of DenseMap and other
> ADT containers will be affected by this. That wasn't my plan - I was going
> to basically use the hashing class to create a custom DenseMapInfo for
> specific maps which could benefit from the optimization. Other DenseMaps
> would remain as they are.
>
>
> Ok.
>
>
>> Is there a specific observed concern here (e.g. when built with Clang) or
>> is this a historical problem?  Compilers have gotten much better about
>> inlining stuff that is actually small, if Clang handles it then I think
>> we're good.  Marking these attribute(always_inline) is massive overkill.
>>
>> Well, it is historical from about 5 years ago when I was working on
> EASTL. The compilers we were using at the time were gcc and MSVC. We found
> cases in the standard STL where inlines were nested up to 10 levels deep,
> and in some of those cases the compiler just gave up trying to inline
> things that deeply.
>
>
> Ok, LLVM uses a completely different (bottom-up, incremental, simplifying
> as it goes) approach to inlining.  I wouldn't worry about it.  Please just
> remove the always inline markers and if it is a measured performance
> problem later we can add them back.
>
>
>
>> Overall the code is looking great.  I'd recommend checking in the new API
>> separately from switching Constants.cpp to use it though (just so that any
>> problems doesn't cause both to get reverted).
>>
>> OK. I'm still working on getting a consensus from the hashing experts :)
>
>
> My advise is to check in when you have to make forward progress.  If
> people want to reshave your yak into another hairdo, then then can do that
> at some later time.  No reason to block your progress as long as the API is
> good.
>
> Thanks again for working on this!
>
> -Chris
>
>


-- 
-- Talin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120218/8362ce6d/attachment.html>