Re: [boost] [review] hash functions

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2005-03-09 06:36:43

Thorsten Ottosen ha escrito:

> Dear All,
>
> It's a pleasure to announce that the review of Daniel James' hash functions
> library
> starts today (8th of March) and ends the 12th of March.
>
> The library is fairly small and can be seen as an extension to
> boost.functional.
> Therefore the review is a fast-track review.
>

Here's my review:

* What is your evaluation of the design?

The design follows Peter Dimov's proposal at

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1756.pdf

(item 6.18.) I think the design is fine, and Peter explains its advantages
over the laxer TR1 hash<> spec better than I would do.

* What is your evaluation of the implementation?

The implementation follows the aforementioned spec and it's up
to Boost coding standards. I've got some comments on it, later.

* What is your evaluation of the documentation?

Fine in general, though I've got some comments below.

* What is your evaluation of the potential usefulness of the library?

I need it! I think this is a general purpose utility that must be in Boost,
perhaps most importantly with regard to the ongoing effort to provide
a Boost.TR1 implementation.

* Did you try to use the library?  With what compiler?  Did you have any problems?

Yes, with GCC 3.2, MSVC++6.5 (+STLport), ICC 7.1. No problems.

* How much effort did you put into your evaluation? A glance? A quick reading?
In-depth study?

I've been following this lib closely for at least a month.

* Are you knowledgeable about the problem domain?

Not really an expert in hashing algorithms, but I'm familiar
with hashed containers, TR1 hash<> proposal and Dimov's
extension proposal.

* Do you think the library should be accepted as a Boost library?

Yes, definitely. My comments on impl and docs do not change my voting
(though I'd like them to be addressed, of course.)

Comments on the implementation.

1. The overloads of hash_value for STL containers forces the implementation
to include <vector>, <list>, etc., which makes the header a little
heavier than desired. Of course, this could be avoided if only there
exist <vector_fwd> style headers :( I propose that, instead of including
the STL containers headers, they are forward declared:

namespace std{
template<typenameT,typename A> class std::vector<T, A>;
...
}

As is known, stdlib implementors are free to add extra template
params, so this is not 100% safe, but:
* All stdlibs that I'm aware of do not include extra template params
* The forward declarations can be tweaked  for those stdlibs for
which they don't match.

2. It is said in hash.cpp that BCB has problems with the overload
of hash_value for bool. This should be fixed in one way or another
(possibly by not defining it for this compiler, I guess.)

3. Possible future enhancement: compatibility of hash_range
with Boost.Range.

Comments on the documentation.

1. If this lib is going to claim adherence to Peter Dimov's proposal, the
reference should state what the algortihms are for overloads of
hash_value for:

int
unsigned int
long
unsigned long
std::pair
std::basic_string
STL containers

Currently all these overloads appear without a mention of what their
exact behavior is. A mention to Peter's proposal is included, but I think
it'd be better to replicate the spec entirely rather than rely on an external
paper.

2. The overload of hash_value for bool is not documented. Its
exact behavior should probably be documented, also.

3. The navigation buttons look cluttered (at least in my browser, IE 5.0.)

4. Introduction: the "It is being proposed" thing should be removed if the
lib is accepted.

5. The docs talk of overloads for string and wstring, yet Peter's proposal
and the implementation itself overload for basic_string<E,T,A>.

6. hash_combine is incorrecly documented to return a std::size_t (it doesn't
return anything.)

Thanks to Daniel for his contribution! Best,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo