[review][unordered] Review summary

Hi to all, This post tries to summarize the review of the new Boost.Unordered library. In general, there were no serious implementation change requests and most reviewers had only documentation issues. Here we go: * * * begin of summary * * * Thosten Ottosen's review: ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131372.php) Thorsten questioned about the convenience of supporting throwing hash or predicates. This started a thread about the exception safety guarantees of STL containers and Daniel explained the thread-safety guarantees of Unordered. Basically, Daniel's implementation uses an smart double-buffering technique to obtain strong safety guarantees (stricter than the requirements of the standard) in some operations. There's an slight size overhead (the container must allocate space for two equality functors and hashers) but according to Daniel, speed should not suffer. Chung Ping Wang's review: ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131372.php) The only complain was the packaging of the library (there was an "unordered" directory at the top). Since the library has been accepted it will be packaged as the rest of Boost libraries so the problem disappears. Mathias Gaunard's comment: ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131426.php) Mathias suggested adding move semantics and in-place construction. Daniel said that these features were likely to be added in the future. He pointed that we have no standard move emulation library in Boost so we'll need to push that first. Regarding in-place construction, there is a problem with allocators, since containers are now required to call allocator::construct() to construct values. Hervé Brönnimann's review: ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131435.php) Hervé praised the library and suggested adding operator==(). Daniel replied that he was trying to limit himself to obvious design decisions for extensions so he didn't want to go into this area. He also cited some problems with non-unique key unordered containers. Hervé suggested extending the prime number list and Daniel agreed. Daniel also agreed to correct some documentation issues. "Swap" semantics wrt allocators was also discussed. "Swap" and its effect on containers is an active issue in the committee, so Daniel is free to implement what he thinks best until we have a firm resolution. John Torjo's review: ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131557.php) A concise and positive review with no comments. Jamie Allsop's review: ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131762.php) Documentation suggestions that Daniel found interesting and a request to include a comparison with other implementations. Steven Watanabe's comments ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131817.php) Several implementation comments regarding (ADL, BOOST_DEDUCED_TYPENAME, warnings...). See the post for details. Cromwell Enage's review ---------------------- (http://lists.boost.org/boost-users/2007/12/32706.php) Suggested the addition of local_cbegin() and similar, and some documentation suggestions Daniel agreed to solve. Paul A Bristow's review ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131545.php) A brief and positive review with no comments. * * * end of summary * * * Regards, Ion

Ion Gaztañaga skrev:
Hi to all,
Unordered. Basically, Daniel's implementation uses an smart double-buffering technique to obtain strong safety guarantees (stricter than the requirements of the standard) in some operations. There's an slight size overhead (the container must allocate space for two equality functors and hashers) but according to Daniel, speed should not suffer.
Can boost::compressed_pair not be used to remove the overhead of stateless functors and hashers? -Thorsten

On 03/01/2008, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Can boost::compressed_pair not be used to remove the overhead of stateless functors and hashers?
I used to do that but I found that in practice the difference was so slight it didn't seem worth it. If you have 4 zero-sized function objects (2 hash functions, 2 equality functions), it's the difference between 1 or 2 bytes and 4 bytes. Which often doesn't make a difference because of padding. The pointer to the current pair of objects (typically 4 bytes) is where the real cost lies. I could possibly use a different implementation for empty objects so that the pointer isn't required, but I'm not sure about the technicalities or if it would be worth the extra complexity. I could also use a bool instead of a pointer but that has costs elsewhere (I haven't measured this, so I'm not entirely sure how expensive it would be). It might be worth using compressed_pair (or something similar) for allocators, but I never got round to doing that. I've generally not been that concerned about the size of the container object, as it tends to be small compared to the memory required for the buckets and nodes. Daniel
participants (3)
-
Daniel James
-
Ion Gaztañaga
-
Thorsten Ottosen