[boost] Re: [review] hash functions

From: Daniel James (daniel_at_[hidden])
Date: 2005-03-09 13:18:32

Pavel Vozenilek wrote:
> ______________________________________________
> 1. Woudn't it be better to have separate
>    headers as hash_for_sets.hpp, hash_for_maps.hpp etc
>    instead of one header including the whole world?
> 
>    This way other Boost containers could be added
>    w/o affecting compile time.
> 
>    I remember long debates about this during
>    Serialization review. These resulted in solution
>    with separate headers + common header for all.

This is a popular view. I'll see what people say in response to other mails.

>    And if possible, other containers (slist,
>    few Boost ones) should be added.

Well, this is possibly beyond the scope of the library (as it's a TR1 
implementation) and, thanks to Peter's design, it's very easy to do this 
yourself. But, extra headers could be made available.

>    It may be considered whether support for
>    shared_ptr etc could be added.

I'm not sure what the semantics would be for shared_ptr, I think if it 
was based on the pointer this could suprise some people.

> ______________________________________________
> 2. The reference documentation says string
>    and wstring are passed by value, while they
>    are by const&.

I am obviously a very clumsy user of boost book. Thanks.

> ______________________________________________
> 3. __int64/long long should be supported.

I want to put this of for now. I'm sticking to what's specified by the 
standard and Peter's proposal. The idea is to get this into boost as 
quickly as possible, so that it can be used by MultiIndex. I'm trying to 
keep things simple.

Also, it will need a different hash function to the other integer type 
as the current one won't take account of the higher bits. I want to take 
my time over things like this and get it right.

> ______________________________________________
> 4. What if I would like hash result other
>    than size_t, frex unsigned char?
> 
> 
>    I may be memory constrained or may want to save
>    data on disk.

Then you'll probably want to use your own hash function ;)

This library is not going to be appropriate for every possible use of 
hash functions. It is only intended to meet the needs specified by TR1.

> ______________________________________________
> 5. namespace detail would be better hash_detail
>    to avoid possible clashes.

OK. Will do something like this.

> ______________________________________________
> 6. Maybe the struct hash::operator() could use
>    boost::call_traits<T>::param_type to
>    optimize value passing for primitive types.

Maybe, I'll think about that.

> ______________________________________________
> 7. compiling hash_float_test.cpp with Intel C++ 7.0
>    plugged in VC6 IDE (with old Dinkumware) I get:
> 
> 
> hash_float_test.cpp
> C:\work\reviews\hash\hash\libs\functional\hash\test\hash_float_test.cpp(56):
> error: identifier "denorm_present" is undefined
>           if(std::numeric_limits<T>::has_denorm == denorm_present) {
> 
> 
> 
> BCB 6.4 with STLport 4.5.1 says:
> 
> [Linker Error] Unresolved external '_STL::_LimG<bool>::_F_inf' referenced 
> from C:\WORK\REVIEWS\HASH\HASH\LIBS\FUNCTIONAL\HASH\TEST\HASH_FLOAT_TEST.OBJ

Getting the float functions to work on different compilers is not going 
to be easy, they vary a lot. Borland seems to have particularly bad 
support for floats. That stlport link error is a little odd - it looks 
like it might be an stlport error. The best thing to do is probably to 
add appropriate macros and tests to config.

> ______________________________________________
> 8. old Dinkumware fix: hash_custom_test.cpp:
> 
> return hasher(std::tolower(x));
> 
> ==>>
> 
> using namespace std;
> return hasher(tolower(x));

Will do.

> ______________________________________________
> 9. Win32 Intel fix: by default I get error:
> 
> C:\work\reviews\hash\hash\boost/functional/hash.hpp(226): error:
> no instance of overloaded function "boost::hash_value" matches the argument 
> list
>             argument types are: (const test::custom)
>               return hash_value(val);
> 
> 
> 
> one needs to add compiler option:
>     /Qoption,c,--arg_dep_lookup
> 
> to enable ADL with Intel when emulating VC6.

The custom test is only going to work on compilers with ADL - that's 
deliberate so that the test results will show what works and what doesn't.

On compilers without ADL, you'll have to add the overload to the boost 
namespace.

> ______________________________________________
> 10. performance: wouldn't it be better to provide
>     hand written specialization for std::string/wstring
>     instead of relying on hash_range/combine?
> 
> 
>     The compiler may not optimize chain of functions
>     out/pass parameters in most efficient way/
>     keep most data in registers.
> 
> 
>     It's just feeling, I didn't do any measurements.

Maybe. I would want to do some profiling before doing that sort of 
optimisation.

> ______________________________________________
> 12. BCB compiles and runs all tests (w/o floats).
>     Intel 7 dtto (with the fix from [9] for custom test).
>     VC6 doesn't floats and custom test (due to lack ADL).

I think VC6 worked for floats on my computer, but I'll double check that.

> ______________________________________________
> 13. The headers may have
> 
> #if (defined _MSC_VER) && (_MSC_VER >= 1200)
> #  pragma once
> #endif
> 
> on the top.

OK.

> ______________________________________________
> 14. some rationale may be given for hash function
> 
>   seed ^= hash_value(v) + (seed<<6) + (seed>>2);
> 
> - link where does it come from or so.

There's a link in Peter's proposal, I'll add it.

> If one creates different algorithm the code
> may be prepared for such situation by:
> 
> #ifdef BOOST_HASH_USER_HASH_COMBINE_OFFERED
>    BOOST_HASH_USER_HASH_COMBINE_OFFERED;
> #else
>   seed ^= hash_value(v) + (seed<<6) + (seed>>2);
> #endif
> 
> or something like that.

If you want to use a different algorithm, I think you should just use 
your own function.

> ______________________________________________
> 15. Complete example how to write e.g. case
>     insensitive hash and how to plug it in should
>     be shown in docs.

That would be an inappropriate use for this library. To do something 
like this you should use your own hash function. I've written an example 
of this for the unordered associative container library where it is 
appropriate.

What might be appropriate here is to write versions of hash_range & 
hash_combine which let you use a different hash function.

thanks for your review,

Daniel