- Boost - lists.boost.org

Re: [boost] Re: Re: Re: [review] hash functions
by JOAQUIN LOPEZ MU?Z 10 Mar '05

10 Mar '05

Hi Peter, ----- Mensaje original ----- De: Peter Dimov <pdimov(a)mmltd.net> Fecha: Jueves, Marzo 10, 2005 11:51 pm Asunto: Re: [boost] Re: Re: Re: [review] hash functions > JOAQUIN LOPEZ MU?Z wrote: > > > > The idea is that you can alter only some part of the > > hashing scheme and benefit of the preexisting definitions: [...] > > I think I see your point. You want something like this: [...] > will automatically propagate it downwards if one invokes > hash_value on > vector<vector<vector<int> > >. Sort of, I think. Your formulation is somewhat more generic in that you pass combiners around where I rely on tag dispatching (the *_impl markers.) > Interesting, but overkill, IMO. ;-) Can't say the contrary :) I see it as I way to get everybody happy: regular users don't notice the difference and playful ones can easily plug in their superhashing schemes. Anyway. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

1 0

Re: [boost] Re: Re: Re: [review] hash functions
by JOAQUIN LOPEZ MU?Z 10 Mar '05

10 Mar '05

----- Mensaje original ----- De: Peter Dimov <pdimov(a)mmltd.net> Fecha: Jueves, Marzo 10, 2005 10:35 pm Asunto: Re: [boost] Re: Re: Re: [review] hash functions > JOAQUIN LOPEZ MU?Z wrote: > > > > Maybe the following approach could be taken to > > allow for alternative implementations to be plugged into > > the framework: [...] > > > unordered_set<my_type,boost::hash<my_type,crypto_impl> > us; > > The proposal is not a framework, it contains two simple tools for > constructing hash_value overloads for compound types and a suite > of > _default_ hash functions. > > Alternative implementations (who may or may not use the supplied > tools) are > supported by unordered_set by simply using > > unordered_set< my_type, my_hash > us; > > There's no need to plug them in. The idea is that you can alter only some part of the hashing scheme and benefit of the preexisting definitions: template<typename It> std::size_t hash_range(It first,It last,crypto_impl) { ... } // third_party_type is an external type with its own // hash_value overload unordered_set< std::vector<third_party_type>, boost::hash<std::vector<third_party_type>, crypto_impl> > us; // here, we automatically get an impl of hashing for // strings using the crypto_impl hash_range unordered_set< std::string, boost::hash<std::string, crypto_impl> > us2; But I won't defend this to death :) I just felt like throwing the idea in. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

2 1

stl-like containers of pointers
by Felipe Magno de Almeida 10 Mar '05

10 Mar '05

I heard that boost is going to have all the stl-like containers, but with reference semantics and will treat the indirection in the iterators and etc... I would like to know where I can get this. It is not in the cvs either... Thanks in advance, -- Felipe Magno de Almeida UIN: 2113442 email: felipe.almeida at ic unicamp br, felipe.m.almeida at gmail com, felipe at synergy com I am a C, modern C++, MFC, ODBC, Windows Services, MAPI developer from synergy, and Computer Science student from State University of Campinas(UNICAMP). To know more about: Unicamp: http://www.ic.unicamp.br Synergy: http://www.synergy.com.br current work: http://www.mintercept.com

2 10

Re: [boost] Re: Re: Re: [review] hash functions
by JOAQUIN LOPEZ MU?Z 10 Mar '05

10 Mar '05

----- Mensaje original ----- De: Peter Dimov <pdimov(a)mmltd.net> Fecha: Jueves, Marzo 10, 2005 6:01 pm Asunto: Re: [boost] Re: Re: Re: [review] hash functions > Thorsten Ottosen wrote: > > > > so basically you're saying that any collision is much worse than a > > slower hash function because we must use == to go through the > bucket ? > > Something like that, yes; of course it depends on the level of > slowness. > Cryptographic hash functions are typically overkill. Increasing > the number > of collisions slightly is tolerable (but can easily negate the > effect of the > faster hash function). Hitting a pathological case where a > significant > percentage of the key set maps to the same bucket is a serious > problem. > Maybe the following approach could be taken to allow for alternative implementations to be plugged into the framework: struct std_impl{}; template<typename T,typename Impl=std_impl> struct hash { std::size_t operator()(const T& x)const { return hash_value(x,Impl()); } }; template<typename T,typename Impl> std::size_t hash_value(const T& x,Impl impl) { return hash_value(x); } // standard hash_value overloads for integral types and pointers ... // template<typename T,typename Impl> void hash_combine(size_t& seed,const T& x,Impl impl) { seed^=hash_value(x,impl)+(seed<<6)+(seed>>2); } template<typename A,typename B,typename Impl> std::size_t hash_value(const std::pair<A,B>& x,Impl impl) { std::size_t seed=0; hash_combine(seed,x.first,impl); hash_combine(seed,x.second,impl); return seed; } template<typename It,typename Impl> std::size_t hash_range(It first,It last,Impl impl) { std::size_t=0; for(;first!=last;++first){ hash_combine(seed,*first,impl); } return seed; } template<typename E,typename T,typename A,typename Impl> std::size_t hash_value(const std::basic_string<E,T,A>& x,Impl impl) { return hash_range(x.begin(),x.end(),impl); } // same as previous for the rest of STL containers This framework is transparent to the regular user, who never specifies an alternative implementation and can define hashing for her own types as before: std::size_t hash_value(const my_type& x) { //... } unordered_set<my_type,/* boost::hash<my_type> */> us; But the "advanced" user can tweak one or more parts of the hashing framework ad libitum: struct crypto_impl{}; std::size_t hash_value(int x,crypto_impl) { // smart hash for ints } // we modify also range hashing template<typename It> std::size_t hash_range(It first,It last,crypto_impl) { std::size_t seed=0; std::size_t n=1; for(;first!=last;++first){ hash_combine(seed,*first,crypto_impl); seed*=n; // for instance n*=2; } return seed; } unordered_set<my_type,boost::hash<my_type,crypto_impl> > us; What do you think? Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

4 3

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

10 Mar '05

In-Reply-To: <d0pe8q$tdi$1(a)sea.gmane.org> daniel(a)calamity.org.uk (Daniel James) wrote (abridged): > But it will be easy to make mistakes for more complicated (possibly > recursive) types. Especially since hash_combine is not associative or > transitive. I could see that leading to mistakes. I can see that it's possible to call the function with the wrong arguments, but that kind of problem can be addressed with documentation and/or by careful naming. I don't think that's worth distorting the interface and introducing side effects and spurious variables and inefficiency to fix it. > And it would be quite easy to forget to call hash_value (because > many types are implicitly convertible to std::size_t) Since that conversion is all hash_value does, why does it matter? That said, I agree the second argument should not be hash value. If we care about the first argument, perhaps the problem could be identified with an overload or specialisation. template < typename T, typename S> size_t hash_combine( S seed, const T &v ) { BOOST_STATIC_ASSERT( false ); } template <typename T, typename S> size_t hash_combine<>( size_t seed, const T &v ) { const size_t c = 0x12345678; // Or some other value. return seed ^ (hash_value(v) + c + (seed<<6) + (seed>>2)); } (I'm not so hot on templates so the above may be wrong, but I hope it conveys the idea.) > size_t my_hash_function(int x[4]) { > using namespace boost; > > return hash_combine( > hash_combine(hash_value(x[0]), hash_value(x[1])), > hash_combine(hash_value(x[2]), hash_value(x[3]))); > } I agree this is wrong. I think: return hash_combine( hash_combine( hash_combine( hash_value( x[0] ), x[1] ), x[2] ), x[3] ); is reasonable and ideally would be supported. > An alternative would be to implement hash_combine as an object. > Something like: > > struct hash_seed { > hash_seed(); > template <class T> void combine(T const&); > std::size_t value() const; > }; > > Then it could initialise itself to whatever it wants. Do you mean the seed should be an object? I can see advantages to that, although it seems like overkill. Adding an optional seed argument to hash_range and/or hash_combine sounds like a good idea, though. -- Dave Harris, Nottingham, UK

3 2

[foreach] and reverse iteration
by Russell Hind 10 Mar '05

10 Mar '05

Is there a way to reverse iterator using BOOST_FOREACH? From a quick browse of the docs, it isn't mentioned. I guess it could be done using a std::pair of reverse iterators, but would it be easy to build a BOOST_REVERSE_FOREACH construct or BOOST_RFOREACH that just runs from rbegin to rend? Cheers Russell

2 1

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

10 Mar '05

In-Reply-To: <018901c52569$ea842610$6601a8c0@pdimov> pdimov(a)mmltd.net (Peter Dimov) wrote (abridged): > That would be bad because the hash value of the pair (x, y) would no > longer match the hash value of the sequence (x, y). Why is it necessary for pairs and sequences to have the same hash value? They are different things. If it is necessary, we can avoid the problem by fixing hash_range: template <typename It> size_t hash_range( It first, It last ) { if (first == last) return 0x87654321; // Or some other value; size_t seed = hash_value(*first); for (++first; first != last; ++first) seed = hash_combine( seed, *first ); return seed; } This also gives hash_range( &a, &a+1 ) the same result as hash_value(a), which your approach does not. > Do you have a different hash_combine in mind that doesn't suffer from > this problem and is better than the proposed implementation? ;-) > (Keeping in mind that even the current hash_combine is perceived as > slower than necessary, of course.) I had in mind something like: template <typename T> size_t hash_combine( size_t seed, const T &v ) { const size_t c = 0x12345678; // Or some other value. return seed ^ (hash_value(v) + c + (seed<<6) + (seed>>2)); } This costs one extra addition, which can probably be scheduled in parallel with other operations anyway. -- Dave Harris, Nottingham, UK

2 1

[test] missing test file
by Vladimir Prus 10 Mar '05

10 Mar '05

When running "bjam -n" in the libs/test/test directory, I get: don't know how to make <@boost!libs!test!test>foreach_test.cpp Gennadiy, seems like you either forgot to commit that file, or forgot to commit some changes to Jamfile. Can you fix this? - Volodya

2 1

review of proposed fsm library
by Dave Gomboc 10 Mar '05

10 Mar '05

Reviewer info: ============== I have an M.Sc. in computing science. Much of my experience is with state-space search, which has certain similarities to the topic at hand. Also, lately I have been working daily with code that ought to have been written using an FSM library, but wasn't! :-( I have been following the FSM discussion on the list, and have focussed on the library for one day, reading through the docs and rationale, plus Harel's initial statechart paper. The rationale document did not convince me of the correctness of some design choices, so I did not attempt to write code with the library. Reviewer comments: ================== Let us consider that we have multiple fsms and we would like to apply operations to these fsms, e.g. direct concatenation (the terminal state of one automata becomes the start state of another), or choice (depending on an action of, or an accept/reject by fsm a, proceed to execute fsm b or fsm c). This is apparently straightforwared when working at the level of states; however, the library draws a distinction between a state_machine and a state. This acts as a barrier to the direct composition of state machines that we would like to use as components within large state machines. The distinction made between state and state_machine, which I consider to be unfortunate, was not justified in the rationale. For naturally recursive structures, distinguishing between the structure's frontier and its interior by type is best avoided. (Analogously, the head of a (singly-linked) list and the root of a tree would not be distinguished by type from their successors and children, respectively.) Composition is critical! See, for instance, section 12.4 of Keller (http://www.cs.hmc.edu/claremont/keller/webBook/ch12/) An example of multiple-machine composition into a large machine should also exist in the tutorial. The simplest useful such case would likely be connecting two half-adders to make a full-adder machine. There is a brief note in the tutorial re: submachines that fails to do this topic justice. If the template approach recommended there is to be the canonical form for a reusable component, that style should be propagated through all but the simplest examples in the tutorial. Each submachine should clearly be labelled as part of its own .hpp file. I was pleased that the tutorial and rationale collectively contain considerable discussion of exception handling. In the speed vs. scalability trade-off section of the rationale page, it is claimed that using an fsm for a parsing task is an abuse, excusing the relatively low performance of the library. However, finite-state automata are inextricably linked with the acceptance of regular languages: see, for instance, section 12.2 of Keller (again, http://www.cs.hmc.edu/claremont/keller/webBook/ch12/) it is not too much to ask that an fsm library to be able to serve as the underpinning of a reasonably efficient regex library. The lack of support for dynamically-configurable automata is also unfortunate, though not unexpected given the requirements list. Other reviewers have also already commented upon the lack of a table-lookup dispatch method. From the rationale: "To warrant fast table lookup, states and events must be represented with an integer. To keep the table as small as possible, the numbering should be continuous, e.g. if there are ten states, it's best to use the ids 0-9. To ensure continuity of ids, all states are best defined in the same header file. The same applies to events. Again, this does not scale." However, I think that for table lookup there is no requirement that ids be consecutive -- a compile-time write-once read-many hash table could do the trick. But even that may be an aside. I am unconvinced by: "To satisfy requirement 6 [to support the development of arbitrarily large and complex state machines], it should be possible that to spread a single state machine over several translation units. This however means that the dispatch table must be filled at runtime and the different trnaslation units must somehow make themselves 'known' so that their part of the state machine can be added to the table. There simply is no way to do this automatically and portably." While perhaps each state (compilation module) must know of its successor states, no central table of "current state x action x next state" encompassing the entire machine need be explicitly created. Under the "Limitations" section, reference is made to "lost events": "It is currently not possible to specially handle events that have not triggered a recation (and would thus be silently discarded). However, a facility allowing this will probably be added in the not-too-distant future." If the event is irrelevant at that point in the state machine, it is most properly ignored. If it is not irrelevant, there ought to be a transition (perhaps a self-transition). Therefore, I don't understand the comment. I have an uneasy feeling about how differently asynchronous and synchronous machines are operated, but did not consider this issue in detail. Allowing the tracking of history is intruiging; the prohibition against deep history of states with orthogonal regions is suspicious. The explanation given is that it would be more complicated (but still possible) to implement. In my experience, that sort of reasoning just doesn't fly at Boost. The discussion of fork and join bars, combined with the event dispatch to orthogonal regions discussion immediately below that, suggests that the implementation is not truly designed to handle concurrent states. I think, however, if one is to claim that UML statecharts are supported that the semantics of execution ought to be the same! I can well imagine that this "would complicate the implementation quite a bit", but Boost is also about interface, not only implementation, and if the wrong interface is standardized (whether de jure or de facto) it's worse for everybody in the end. There is no explicit discussion of non-deterministic fsms. Of course, every such fsm can be re-expressed deterministically. Similarly, a given fsm may be non-minimal, but such minimization procedures exist. Both of these procedures necessarily require a global view of the fsm. As this is contrary to the scalability requirement listed in the rationale, I conclude that neither are present. :-) However, I would like to ask if (excepting possible compiler limitations) is there anything about the library that precludes extending it such that NDFAs could be specified in code, and converted into the minimized DFA during compilation? (http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/NODE207.HTM# SECTION03177000000000000000 gives a toy example of FSM minimization). We had tuple and mpl separately before fusion; it seems reasonable for boost to have both compile- and run-time fsm libraries, if ultimately they may be similarly fused. Reviewer conclusion: ==================== I like this library, but I'm not satisfied with it. What level of library is good enough for boost? The library is not ready for standardization, however, this doesn't appear to be the standard that most people use when deciding upon their vote. This library is certainly good enough for people to make successful use of. Ultimately, I think there are issues of design and rationale that must be sorted through, appropriate modifications made, followed by re-review. Less weighty issues: ==================== struct Greeting; struct Machine: fsm::state_machine<Machine, Greeting> {}; (and all similar) should be changed to struct Machine: fsm::state_machine<Machine, struct Greeting> {}; If necessary, the old way can be metioned as a workaround for older compilers in a footnote. The "default" black disc in the diagrams is too large! Maybe make the radius about 2/3s of what it is now. Change "Such transitions are currently flagged" to "Transitions across orthogonal regions are currently flagged". It's the first sentence in the last paragraph of the rationale.

4 4

Hash review: hash_float_test broken?
by John Maddock 10 Mar '05

10 Mar '05

Sorry if this has come up before, but all the compilers I tested with refuced to compile hash_float_test: hash_float_test.cpp ..\..\..\..\libs\functional\hash\test\hash_float_test.cpp(99) : error C2501: 'BOOST_META_FUNC_TEST_CASE' : missing storage-class or type specifiers ..\..\..\..\libs\functional\hash\test\hash_float_test.cpp(99) : error C2440: 'initializing' : cannot convert from 'void (__cdecl *)(T1 *)' to 'int' Context does not allow for disambiguation of overloaded function ..\..\..\..\libs\functional\hash\test\hash_float_test.cpp(105) : error C2275: 'float_types' : illegal use of this type as an expression ..\..\..\..\libs\functional\hash\test\hash_float_test.cpp(104) : see declaration of 'float_types' ..\..\..\..\libs\functional\hash\test\hash_float_test.cpp(105) : error C3861: 'BOOST_FUNC_TEMPLATE_TEST_CASE': identifier not found, even with argument-dependent lookup "cl" /Zm800 -nologo /EHsc -c /Z7 /Od /Ob0 /EHsc /GR /MDd /Op /Zc:forScope Zc:wchar_t -I"..\..\..\..\bin\boost\libs\functional\hash\test" -I"C:\Program Files\Microsoft Visual Studio .NET 003\VC7\include" -I"c:\data\boost\develop\boost" -Fo"..\..\..\..\bin\boost\libs\functional\hash\test\hash_float_test.test\vc-7_1\debug\threading-multi\hash_float_test.obj" -Tp"..\..\..\..\libs\functional\hash\test\hash_float_test.cpp" Thanks, John.

3 3