- Boost - lists.boost.org

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

15 Mar '05

In-Reply-To: <001201c527e4$7405efa0$6501a8c0@pdimov2> pdimov(a)mmltd.net (Peter Dimov) wrote (abridged): > > In my experience, if you want two different things to hash the same, > > you need to write their hash functions with that in mind. It is a > > special case which justifies not using the default hash function. > > Maybe, but this is not an argument for making the hash values different. True. Arguments for that have been given elsewhere. One argument is to maximise variation (and for types like bool it is desperately needed). Another is to allow treating of 32-bit values as bytes. For example, size_t hash_range( const int *first, const int *last ) { return hash_range( static_cast<const unsigned char *>(first), static_cast<const unsigned char *>(last) ); } may be a good implementation on some platforms. It does 4 times as many mixing steps (assuming sizeof(int) == 4) as the proposed algorithm. It is, I think, how the designer of the proposed hash_combine algorithm expected it to be used. However, it yields hash values for int * different to the values for char *, so with the current design aims we can't use it. > > But doesn't this mean that hash_value( pair<int,int> ) also needs a > > seed argument, if you want it to match hash_range( int[2] ) ? > > No. The seed version of hash_range is used when you want to compute the > hash function of a sequence, but you don't have access to the whole > sequence at once. It's goal is not to provide a way to change the > initial seed, but to make it possible to continue from an intermediate > seed. But suppose I have pair< pair<int,int>, pair<int,int> > ? Shouldn't that yield the same hash value as int[4] ? -- Dave Harris, Nottingham, UK

5 5

ANN: review of FSM library starts
by Pavel Vozenilek 15 Mar '05

15 Mar '05

Review of Finite State Machine library written by Andreas Huber starts today, February 21, and lasts 10 days. The library can be found at: http://boost-sandbox.sf.net/fsm.zip (781 kB). FSM is feature rich library to design finite state machines without need for external generator. It is accompanied by extensive documentation. Here are some questions you might want to answer in your review: * What is your evaluation of the documentation? How easy (or hard) it is to understand library features? What can be improved? * What is your evaluation of the design? What features are supported better by alternative FSMs? What could be added (or removed) from the library? * The library documentation contains few not yet solved issues (name, separating the library into two parts, exception handling). What is you opinion here? * What is your evaluation of the implementation? Are there parts of code too obscure or duplicating exiting Boost functionality? Can something be factored out to standalone library or among general utilities? * Are there performance bottlenecks? Does the library design fit requirements of real-time systems? How is it useable for embedded systems? Is the documentation clear on performance tradeoffs? * What is your evaluation of the potential usefulness of the library? Can you compare this FSM to other implementations? * Did you try to use the library? With what compiler? Did you have any problems? Do you have tips for better support of older compilers? What are possible portability problems? * How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? * Are you knowledgeable about the problem domain? And finally, every reviewer should answer this question: * Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion. Pavel Vozenilek FSM review manager

7 19

FSM Review
by Jody Hagins 15 Mar '05

15 Mar '05

I am sorry this is late. I made the mistake of introducing my kids to snow skiing. Now they can not get enough of it. Thus, we were gone again until Wednesday (yes, I let them skip a few days of school to go skiing). * What is your evaluation of the documentation? How easy (or hard) it is to understand library features? What can be improved? I think the documentation is relatively complete. However, I am not exactly thrilled by the requirement on the reader to understand UML diagrams. On the other hand, this library is intended to represent UML in C++ (at least to my understanding), so I'm not sure what else can be done. A link to a basic tutorial on UML state machine diagrams would be appropriate in the "UML to boost::fsm Mapping Summary." I know you link to the 730 page OMG document on UML, but I'd also like to see something that describes the basic UML for state charts. * What is your evaluation of the design? What features are supported better by alternative FSMs? What could be added (or removed) from the library? I think the requirements dictate the design. Specifically, the desire to mimic UML statecharts in C++. As stated before, the design brings with it some performance tradeoffs that will make this library unusable to some. * The library documentation contains few not yet solved issues (name, separating the library into two parts, exception handling). What is you opinion here? I think it is obvious that the library should be separated, though I do not think this issue itself should be a stumbling block for acceptance. Exception handling is very important, and I do not buy the rationale that allowing destructors to throw is not a problem in practice. I also do not think I really understand "two stage exit." * What is your evaluation of the implementation? Are there parts of code too obscure or duplicating exiting Boost functionality? Can something be factored out to standalone library or among general utilities? I did not look too much at the implementation, so I can not comment much here. * Are there performance bottlenecks? Does the library design fit requirements of real-time systems? How is it useable for embedded systems? Is the documentation clear on performance tradeoffs? I think we have to define real-time. Traditionally, real-time systems have hard completion time requirements (e.g., the XYZ event must be processed in under 50ms). Even though I have performance issues with this library, I think it can still be utilized in many real-time situations. Andreas has stated several times that the dispatch time will be small compared to the handling time. However, I find this argument a bit lacking, especially for hard real-time requirements, where each cycle taken for dispatch is stolen from the reaction handler. My current application requirements do not fit the traditional definition of real-time. However, my SMs need to be as fast as possible, because in a real sense, my code is competing with other code. Without going into too much detail, when an "opportunity" is available, it is only available to the first one to see it, respond, and take that opportunity. Thus, my real-time requirement is that I have to be faster than anyone else playing my game. I think using this library would put me at a disadvantage in that particular space. However, I do have some applications in which this library could be used successfully (if I were inclined to learn enough UML to make sense of all the details). The documentation is clear enough about the performance issues. In fact, it may be too clear, as some people seem to see problems that may not exist in most applications. One last thing on performance, since it has been a hot topic in relation to this library. I do not think it has sufficient performance to warrant use in all my applications, and I assume the same for many others. However, it does have sufficient performance to be used in a large number of applications. If the docuemntation is clear (which it is), then users can decide when/how it can be used. I could make similar performance claims agains almost every boost library (and I have made them on this list about shared_ptr and signals). However, that does not mean we should eliminate those libraries from boost, nor does it mean that they should never have been accepted (but I would like to see a larger commitment to address performance issues in all currently accepted libraries). I would, however, like to see a separate submission which has a focus on performance, and I would really like to see the performance issue of this library revisited, especially with input from some of the folks here who claim expertise in that area. * What is your evaluation of the potential usefulness of the library? Can you compare this FSM to other implementations? I have used sevaral versions of SMC, solutions from Samek's "Practical Statecharts in C/C++," and my own hand-crafted stuff. I think SMC is the easiest to use, though it also offers the least flexibility. With moderate use, I think this library could become the standard tool for implementing state machines, with the caveat of every tool: it may need to be replaced if it is too slow. However, I also think that this tool requires a more structured design of your state machine than ad-hoc methods. Thus, if speed were an issue, translating this code to something else would not be too difficult. One thing I have not seen in other reviews is a comparison to GUI state machine tools. I know this is a library, with very different requirements. However, having virtually no experience with GUI tools that build FSMs, I'd be interested to see how this code stacks up with code generated by such tools. Specifically, I have avoided them because I want more control than they allow (or at least allowed when I first looked at them). Does anyone have experiences to offer in this regard? * Did you try to use the library? With what compiler? Did you have any problems? Do you have tips for better support of older compilers? What are possible portability problems? I used it on linux, with gcc. I am probably the last person in this community to offer porting advice to older compilers. * How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? I read all the documentation, and played with a few examples. Specifically, I tried to implement a subset of a current state machine to compare ease of use and performance. This library seemed more difficult to use, but I attribute most of that to inexperience. I am convinced that with some moderate level of experience, I could write state machines more easily with this tool. * Are you knowledgeable about the problem domain? I would not consider myself an expert, by any stretch of imagination. However, I have done my fair share of work coding state machines. I have used a small number of tools, and I have crafted my own, so I am at least comfortable with the problems represented by such a library. And finally, every reviewer should answer this question: * Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion. Yes, with two conditions. 1. The name should definitely be changed. I am not sure, however, what a new name should be. I tend to favor one of Andreas' alternatives: umlfsm. 2. I also think there should be some commitment to revisit the performance issues. I am not sure how this works, but I'd be satisfied with a commitment from Andreas, possibly accompanied by a request to the Boost community for assitance. I am not certain that an acceptable solution can be found, but I think the issue at least needs to be addressed again, specifically with input from the Boost community.

12 37

[Boost-bugs] [ boost-Feature Requests-1163952 ] handle double '/' in the boost::filesystem
by SourceForge.net 15 Mar '05

15 Mar '05

Feature Requests item #1163952, was opened at 2005-03-15 22:17 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=357586&aid=1163952&group_… Category: None Group: None Status: Open Resolution: None Priority: 5 Submitted By: Serg Repalov (rsrus) Assigned to: Nobody/Anonymous (nobody) Summary: handle double '/' in the boost::filesystem Initial Comment: Hi. Sometimes I make some path by hand. For example std::string str = "./"; //... some code .... std::string str2 = str + "/path/to/file"; The result is ".//path/to/file". If I try to make path from it: boost::filesystem::path fs_path2(str2, fs::native); I got exception. Is it possible to correct function path::m_path_append to handle this situation (double/triple/... separator in the middle of string)? ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=357586&aid=1163952&group_… ------------------------------------------------------- SF email is sponsored by - The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_id=6595&alloc_id=14396&op=click _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

Re: [boost] [FSM library] review result: accepted with fewconditions
by Iain Hanson 15 Mar '05

15 Mar '05

On Tue, 2005-03-15 at 19:10 +0100, Pavel Vozenilek wrote: > FSM library written by Andreas Huber has been > accepted into Boost, with few conditions > and few recomendations. > > > Thanks, Andreas, for your work and stamina > to get thus far! > Yes and congratulations to Andreas. > > The documentation is now very dense, splitting > it into smaller parts may help. More hyperlinking > would also help a lot. > Then could there also be a version suitable for printing structured pretty much as it is now please. /ikh

2 1

Re: Re: FSM review
by Dave Gomboc 15 Mar '05

15 Mar '05

> Rejection is not permanent. If a library has flaws and they > are substantial enough then it should be rejected so that > when changed, it can be reviewed again. > > I would like to see a state chart lib in boost but not as it > currently stands. I would not mind if it was accepted as > *beta* which would tell users that it has caveats. Given that the author has already had almost an entire year's notice on this issue, I think giving the current library some sort of "beta" status would be a mistake. This issue won't be resolved one way or the other until a) the review manager ignores the entirely reasonable expectation of constant-time state dispatch, and accepts the library into Boost anyway, or b) the existing code is changed to support constant-time dispatch, perhaps under certain constraints (e.g. when one doesn't use certain features), or c) code is added to the library that converts the specified machine during compilation into something that dispatches in O(1) (e.g. by an algorithm that converts M: S* x T -> S* into M': S' x T' -> S). If c) is the route chosen, whether to invoke this procedure could be made selectable by the user so that one can choose between a) minimizing compile-time (and minimizing risk of encountering compiler limitations, if such a risk exists), and b) maxmizing the performance (and optionally, minimizing the memory footprint) of the state machine at runtime. Dave

1 0

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

15 Mar '05

In-Reply-To: <d11prg$uvt$1(a)sea.gmane.org> daniel(a)calamity.org.uk (Daniel James) wrote (abridged): > Well, we did discus the type of review before it started, and nobody > raised any objections. That's partly because it sounded like the interface was fixed and known good. Where-as we are now agreed that hash_range is going to take at least one additional parameter and possibly be renamed (to hash_combine) and the return type maybe changed to void; so the interface is not fixed. Had I known that I might have objected to the fast-track, but the only way to know it would be to actually review the proposal. Maybe if we are in a hurry we should delete hash_range and hash_combine from the initial official interface, while still using them for the implementation. That would enable the containers to move forward. > On a related note, I am going to be requesting a review for the > unordered associative containers soon. It has been suggested that since > they are based on TR1 they should have a shorter than normal review > (but longer than this one). So I guess you think it should have a full > length review? I have no idea. I am less interested in the containers than in the hashing. I don't think I've ever implemented a hashing container in C++. I don't currently plan to contribute to the containers review. -- Dave Harris, Nottingham, UK

2 1

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