March 2005 - Boost - lists.boost.org

Re: [boost] [review] hash functions
by brangdon＠cix.compulink.co.uk 15 Mar '05

15 Mar '05

In-Reply-To: <002901c527e7$9f9fb620$6501a8c0@pdimov2> pdimov(a)mmltd.net (Peter Dimov) wrote (abridged): > The problem is that hash functions vary wildly in quality. Leaving the > default function unspecified (or implementation defined) is good if you > are lucky and the implementation you happen to use is good. It's a > tradeoff. I think if we provide a good quality default implementation, and also a good rational (and the rational is important here), then vendors are unlikely to change it to something worse. Vendors avoid unnecessary work. The eventual standard could recommend a specific implementation in a non-normative Note. > A fixed and predictable default means that you don't have to measure > the quality of the hash function for every implementation to which you > port your program. Your original tests are still valid. In general, performance varies between platforms. If one implementation has the fixed string optimisation and the other doesn't, my benchmarks for one will not apply to the other. I am not yet convinced that hashing deserves to be a special case. On the other hand, it does seem to be an area which can benefit from innovation. Eg a platform may have a super-fast near-cryptographic-strength algorithm implemented in hardware, and we're saying they can't use it? > The other side of predictability - that the hash function is not > affected by types or the particular representation of a sequence of > values - means that you don't necessarily have to re-run the > performance benchmark of your unordered_maps when you refactor the key > to use int[3] instead of struct { short, short, short }, or a wstring > instead of a string. I think you need to repeat your benchmarks anyway. You may find that values which used to fit in cache no longer do so. Or vice versa. If you are hashing pointer values then the collisions will vary from one run of the program to the next. Even if you can get stability for some set of program edits, there will always be other edits which don't get it. Reordering the hash_combines, or refactoring an object's state, for example. -- Dave Harris, Nottingham, UK

2 1

Re: [boost] Re: [review] hash functions
by brangdon＠cix.compulink.co.uk 15 Mar '05

15 Mar '05

In-Reply-To: <d1409a$kc1$1(a)sea.gmane.org> daniel(a)calamity.org.uk (Daniel James) wrote (abridged): > Think about how such a class would be stored in the proposed unordered > associative containers. If you use unordered_set<base*> then the hash > function will be called for the pointer, not the class. I imagine you would use a hasher which dereferenced the pointer. template<typename T> struct hash_ptr { size_t operator()(const T *p) const { return hash_value( *p ); } }; And perhaps this should be included in boost too? Eg this: unordered_set< shared_ptr<MyType>, hash_ptr<MyType> > looks reasonable to me. > If Thorsten writes ptr_unordered_set<base> then there might be a > problem with boost::hash<base>. Although it will equally apply to > std::equal_to<base>. Absolutely. In general when writing hash_value() you need to look at the corresponding equality operator. For example: bool Derived::operator==( const Base &base ) const { if (Base::operator==( base )) if (const Derived *p = dynamic_cast( const Derived * >(&base)) if (m_value == p->m_value) return true; return false; } Ideally we look at this and we decide there ought to be something in the hash_value which corresponds to the dynamic_cast. But what? We can try using hash_value( typeid(*this) ). However, that will be relatively slow and may not give good results, depending on how it is implemented. We could use our own type IDs, but allocating them is tricky. So it is tempting not to bother, and instead use: size_t Derived::hash_value() const { // return combine_hash( Base::hash_value(), m_value ); size_t hash = Base::hash_value(); combine_hash( hash, m_value ); return hash; } which is correct, but will produce more collisions than if we'd used the typeid. If hash_value( m_value ) yielded different results for different types of value, then the number of collisions would be reduced. The stability requirement compromises the quality of hashing. -- Dave Harris, Nottingham, UK

3 2

Re: [Boost-testing] Re: [test] numerous tests broken
by Caleb Epstein 15 Mar '05

15 Mar '05

On Tue, 15 Mar 2005 11:44:51 -0500, Gennadiy Rozental <gennadiy.rozental(a)thomson.com> wrote: > > errors_handling_test > > ifstream_line_iterator_test > > test_fp_comparisons > > test_tools_test > > Most of this test/compiler combination should pass. Failures caused by some > mix-up between test, Boost.Build and configuration file. I did not have a > time to localize the issue. I don't understand this answer. Are you saying the problem is fixed or you haven't yet had time to investigate it? -- Caleb Epstein caleb dot epstein at gmail dot com

1 0

Logo: version for candidate libs
by rasmus ekman 15 Mar '05

15 Mar '05

When the winning logo is selected, ask the designer to please create a version with the word "Candidate" stamped over or just below. It could also be somewhat greyed-out or whatever. This logo may be used in docs for libraries at all steps until acceptance; the Boost logo should be reserved for acccepted libs. (sorry if already suggested - haven't read all posts) re

2 2

Re: FSM Review
by Johannes Brunen 15 Mar '05

15 Mar '05

David B. Held and Paul A Bristow wrote: >> It will be a sad day when Boost rejects a good library because >> another library in a different part of the design space is >> theoretically faster. > IMO this hits the nail on the head. > As with too many reviews, there have been very interesting, > but essentially speculative, alternative ideas, > produced not during the 'proposed library' development phase, > but somewhat destructively and at the 'last minute'. > > These should not be a reason for rejection, > but should spur development of different > (and hopefully in some ways better) ideas to submit in future. I would like to second that. With best regards Johannes Johannes Brunen DataSolid GmbH Nobelstr. 3-5 41189 Mönchengladbach Tel.: 02166 / 955 789 Email: JBrunen(a)DataSolid.com Internet: www.DataSolid.com ____________ Virus checked by G DATA AntiVirusKit Version: AVK 15.0.3667 from 15.03.2005 Virus news: www.antiviruslab.com

1 0

Re: [boost] Re: Sockets: proposal for a library design
by Willam Lee 15 Mar '05

15 Mar '05

A C++ framework for network is very useful and long for. I have seen the ACE, but felt it too weight. The proposed library seems a lightweight one and the socket wrapper is appropriate. I think if user manage the sockets one by one, the proposed library will work perfectly. But in common network applications, a server usually serves on several sockets or ports with a select() style function. In this condition, how to process multiple socket class for different connection the proposal ? In the pseudo code, select() function is a member function of socket, maybe it can only process the 'this' socket. Finally I don't like build socket lib based on iostream, but the net lib can provide some operator like "<<" , ">>" to simulate the iosteam-style calling. Thanks Boris's work. best regards William Lee _________________________________________________________ Do You Yahoo!? 150万曲MP3疯狂搜，带您闯入音乐殿堂 http://music.yisou.com/ 美女明星应有尽有，搜遍美图、艳图和酷图 http://image.yisou.com 1G就是1000兆，雅虎电邮自助扩容！ http://cn.rd.yahoo.com/mail_cn/tag/1g/*http://cn.mail.yahoo.com/event/mail_…

3 2

boost::begin/end disappeared?
by Caleb Epstein 15 Mar '05

15 Mar '05

A number of regression tests failed today on gcc-3.4.3+ (both mine and Martin Wille's runs) for failure to find boost::begin and boost::end. I'd suspect something changing in the Range library, but nothing looks obivous. Anyone? -- Caleb Epstein caleb dot epstein at gmail dot com

1 0

[test] numerous tests broken
by Caleb Epstein 15 Mar '05

15 Mar '05

This has been happening for several days. A number of the Boost.Test regression tests are failing across most/all platforms: http://www.meta-comm.com/engineering/boost-regression/cvs-head/developer/te… errors_handling_test ifstream_line_iterator_test test_fp_comparisons test_tools_test Gennadiy? -- Caleb Epstein caleb dot epstein at gmail dot com

1 0

Re: [boost] Re: [review] hash functions
by brangdon＠cix.compulink.co.uk 15 Mar '05

15 Mar '05

In-Reply-To: <018201c52567$1b710ca0$6601a8c0@pdimov> pdimov(a)mmltd.net (Peter Dimov) wrote (abridged): > But as I said, benchmarking hash functions is pointless. Real programs > do not compute the hash value of a random 256 byte buffer five million > times. They usually need to do something with the hash value. This > something typically involves a division on a prime to obtain a modulus, > several pointer chasings, and at least one equality comparison (which > on a 256 byte buffer will have considerable impact). I'd add that my own application caches the results of the hash at highish level, so it doesn't actually matter that much if it is slow. The equality comparison is only needed if the hashes are equal. If you are doing something like adding values to a set, and all the values are in fact different, then hopefully the hashes will be different and the equality tests never needed. In my own code I use a mixture of hashing and interning. This means that if objects are equal they probably have the same address. If they are different they probably have different (cached) hashes. Full byte-by-byte compares of all the data are rarely needed. -- Dave Harris, Nottingham, UK

1 0

template_assert
by Johan Paulsson 15 Mar '05

15 Mar '05

(If this is off topic, has already been discussed, or is stupid, I'm sorry) I wanted a static assert without #define, I ended up with this: template<bool MustBeTrue, int TemplateAssertError = 1 / static_cast<int>(MustBeTrue)> class template_assert {}; so template_assert<true> means TemplateAssertError = 1 / 1, no error template_assert<false> means TemplateAssertError = 1 / 0, error The only compiler I have is MSVC++ 2003. I have no idea how other compilers like it, but to me this seems like a better alternative to BOOST_STATIC_ASSERT. Is it? An example, with the code that will trigger template_assert commented out: // template<class Type> struct test { typedef template_assert<sizeof(Type) == sizeof(int)> assert_type; void do_nothing() {} }; template<bool Boo> void function() { template_assert<Boo>(); test<int> works; works.do_nothing(); //test<char> fails; //fails.do_nothing(); } void start() { function<true>(); //works //function<false>(); //fails } // In MSVC++ 2003 i can also use: template<bool Boo> void function() { template_assert<Boo>; //<-- no parenthesis ... but i suppose this is not portable (I don't have a copy of the C++ standard). Thank you all for making boost! /Johan Paulsson

2 1