- Boost - lists.boost.org

Re: [boost][multi_index][hash][rfc] Hashed indices preview +Boost.Hash
by JOAQUIN LOPEZ MU?Z 20 Feb '05

20 Feb '05

Hi Howard, I'm glad you jumped into this discussion! ----- Mensaje original ----- De: Howard Hinnant <hinnant(a)twcny.rr.com> Fecha: Domingo, Febrero 20, 2005 5:31 pm Asunto: Re: [boost] [multi_index][hash][rfc] Hashed indices preview +Boost.Hash > On Feb 20, 2005, at 10:21 AM, JOAQUIN LOPEZ MU?Z wrote: > > >>> 1.4. Usual implementations use one pointer per bucket, whereas > >>> Boost.MultiIndex has two pointers per bucket. This addresses > >> potential> performance problems of insert() and erase() under low > >> load conditions, > >>> as discussed in > >>> http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf > >>> issue 6.14. Is this convenient? > >> > >> Well it's not unreasonable, you need what you need. > > > > BTW, have you read the committee's resolution to this > > issue? It doesn't make any sense to me (Bill Wade's concern, > > OTOH, seems very rasonable.) > > Imho the committee's resolution is quite logical. > > The hash containers exist for one reason: As an optimized > solution, in > both memory consumption and speed, compared to the tree-based > containers. The speed department especially concerns lookup, > insert > and erase (in that order), but not iteration (there are other > containers which optimize iteration, vector being the extreme > example). > The coder who carefully tunes his hash function and loading will > be > rewarded with significant optimization. The coder who doesn't, > may be > presented with a solution that performs worse than the tree-based > containers, and is better off sticking with the O(Log N) solution. > > Imho, the committee should do absolutely nothing to penalize the > coder > who has carefully tuned his hash function and loading, either in > memory > consumption nor speed. Of course if hash container writers would > like > to add safeguards which may also add such overhead, I see little > rationale for the committee to object to that either. > > Doubling the per element storage overhead for a perfect > distribution > with a loading of 1 is a serious hit in the memory consumption > department, and may well lead to a performance hit due to more L2 > cache > misses. Adding bidirectional iteration, again at the cost of > doubling > the per element overhead in a well tuned application makes little > sense > to me. The container is unordered. When you iterate in the > forward > direction, you access the elements in a generally unpredictable, > unordered order. What motivation is there (motivation high enough > to > double per element overhead), to iterate in the reverse of the > generally unpredictable, unordered order? > > Again, I have no wish for the committee to outlaw such hash > containers. > But I strongly feel that neither should they outlaw the more > traditional hash container design which favors uncompromising > performance when everything is tuned just right. > What strikes about the resolution is that it doesn't seem to address Bill Wade's concern: in a minimum overhead "classic" hash table implementation (one pointer per element + one pointer per bucket), iteration is not going to be amortized constant under low load conditions. This is in very strong disagreement with that the std requires about forward iterators. I think this cannot be just swept under the rug: if the committee is going to accept it, at least it should be noted somewhere. The implementation I adopted (2 pointers per node + 2 pointers per bucket) has O(1) iteration, insert() and erase(), whatever the load conditions (provided the hash function behaves, of course.) I agree with you bidirectional iteration is of little value, and my main motivation was to achieve O(1). So, I'll be happy to go for a lighter implementation if these issues can be solved in another way --or if there's consensum that costly iteration under low load conditions is acceptable. PS. The worst of all implementations seems to be Dinkum's, where iteration is O(1) but insertion will degrade to O(bucket_count()^2) when a previous rehashing is issued, as Wade points out. It also puzzled me that the comittee NADed the issue without at least a comment on this. Looking fwd to your comments, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

3 2

Re: [boost] [multi_index][hash][rfc] Hashed indices preview +Boost.Hash
by JOAQUIN LOPEZ MU?Z 20 Feb '05

20 Feb '05

Hi John, thanks for your comments! ----- Mensaje original ----- De: John Maddock <john(a)johnmaddock.co.uk> Fecha: Sábado, Febrero 19, 2005 6:02 pm Asunto: Re: [boost] [multi_index][hash][rfc] Hashed indices preview +Boost.Hash [...] > > > 1.4. Usual implementations use one pointer per bucket, whereas > > Boost.MultiIndex has two pointers per bucket. This addresses > potential> performance problems of insert() and erase() under low > load conditions, > > as discussed in > > http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf > > issue 6.14. Is this convenient? > > Well it's not unreasonable, you need what you need. BTW, have you read the committee's resolution to this issue? It doesn't make any sense to me (Bill Wade's concern, OTOH, seems very rasonable.) > > > 6. Yet, this hasn't undergone any formal review, so some of you > might> (with reason) object to its being commited to the CVS. From > our point > > of view, we have three valid alternatives: > > * Boost members agree to have it in CVS without more ado. > > * As this is used by Boost.MultiIndex, Boost.Hash is suitable for > > fasttrack review. > > * This is untolerable and the library should be push_back()'ed to > > the review queue. Meanwhile, Boost.Hash should live as an impl > > detail of Boost.MultiIndex. > > I don't see how you can place it in a detail namespace if users > are going to > be expected to (possibly) provide their own specialisations of the > hash > function object. > > I've no objection to either a fast track review, or just adding to > cvs, I think Daniel is going to ask for a fasttrack review, and Thorsten volunteered to manage it. In the meantime, I'll commit my update and Boost.Hash code only, and wait for the outcome of Daniel's review --it'll be his responsabiity to upload docs, test, etc. if the lib is accepted. Best, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

2 1

BOOST_NO_RTTI?
by Douglas Gregor 20 Feb '05

20 Feb '05

We've now had a user request that could be solved by adding a BOOST_NO_RTTI macro, that (when set) would disable Boost's use of constructs that use run-time type information (dynamic_cast, typeid, etc.), similar to our BOOST_NO_EXCEPTIONS. http://lists.boost.org/MailArchives/boost-users/msg09240.php I'll plan to add it unless there is violent disagreement. Doug

6 10

Two more patches
by Julio M. Merino Vidal 20 Feb '05

20 Feb '05

Hi again, I've attached two more patches (mostly nitpicking): - patch.diff fixes a typo in the Jamfile usage message (teh -> the). While solving this, I also splitted several long lines (over 80 cols) on several ones. Looks nicer, IMHO. This patch also fixes the indentation of a message in the python.jam file. I.e., PYTHON_INCLUDES explanation appears incorrectly indented WRT PYTHON_LIB_PATH (lacks some spaces). I also indented the second line of each message two more characters to match the PYTHON_VERSION message that appears at the very beginning (indented farther than the dash). I.e.: PYTHON_LIB_PATH - blahblahblah blahblah rather than: PYTHON_LIB_PATH - blahblahblah blahblah - patch2.diff fixes two typos in the web pages. First of all, in the filesystem's FAQ, a question ends with a dot, while there should be a question mark in there. (Just as in my previous message, I've added a blank line at the end of the file.) Then, in the mailing lists information page, there is a paragraph that does not end with a dot. I've added it and reformatted the affected lines to fit on screen. Hope they are correct and can be applied. Kind regards, -- Julio M. Merino Vidal <jmmv84(a)gmail.com> http://www.livejournal.com/users/jmmv/ The NetBSD Project - http://www.NetBSD.org/

1 0

Biconnected components patch
by Janusz Piwowarski 20 Feb '05

20 Feb '05

Hello, Because of recursion problem, i rewrote biconnected components algorithm using DFSVisitor. It needs one additional property map only. Patch is attached. Regards, Janusz

2 1

Confused CVS lock?
by Mark Deric 19 Feb '05

19 Feb '05

This may not be the right forum to surface this admin issue, so please redirect me if it's appropriate. I was just updating my boost cvs sandbox: [mark@laguna06 boost_current_cvs]$ cat CVS/Root :pserver:anonymous@cvs.sourceforge.net:/cvsroot/boost [mark@laguna06 boost_current_cvs]$ cvs -z3 -q up -d -P and have gotten cvs update: [18:42:34] waiting for agurtovoy's lock in /cvsroot/boost/boost/libs/utility/tmpw2001-paper ... cvs update: [19:24:11] waiting for agurtovoy's lock in /cvsroot/boost/boost/libs/utility/tmpw2001-paper I'm not used to a cvs lock blocking for 40 minutes unless it's toasted. Can anyone help? Regards, Mark

2 1

[multi_index][hash][rfc] Hashed indices preview + Boost.Hash
by Joaquín Mª López Muñoz 19 Feb '05

19 Feb '05

Hello all, You can find a preview version of Boost.MultiIndex including hashed indices plus Daniel James' Boost.Hash library at the Sandbox Files area: multi_index_140205_plus_hash_part_1.zip multi_index_140205_plus_hash_part_2.zip (split in two for maximum size reasons.) There are a number of things we'd like to ask you feedback about: 1. Hashed indices are modeled according to the latest TR1 draft, with some significant diversions: 1.1. erase() does not throw ever, even it the user-provided Hash object throws. This is imposed by the general framework of Boost.MultiIndex. This goodie does not come for free: if the Hash object throws, erase() decays to a linear search. Not that there's any alternative, but I'd like to point it out. 1.2. insert() has strong exception safety (TR1 only requires basic.) Again, the way Boost.MultiIndex is designed forces this. 1.3. hash indices iterators are bidirectional. 1.4. Usual implementations use one pointer per bucket, whereas Boost.MultiIndex has two pointers per bucket. This addresses potential performance problems of insert() and erase() under low load conditions, as discussed in http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf issue 6.14. Is this convenient? 2. The material is complete except for a section in the tutorial and possibly one more example (example 8 already exercises hashed indices.) Tests fully sport hashed indices. The reference is also updated. 3. All in all, I'd greatly appreciate your comments on this: suitability, documentation, performance, etc. I plan to commit this to the CVS if nobody objects in a reasonable amount of time (a couple of weeks.) I'm open to all kind of suggestions --I'm eager to recieve them, as it happens :) 4. As for Boost.Hash, this library by Daniel James' implements the ideas for std::tr1::hash (albeit in boost namespace) proposed by Peter Dimov in the aforementioned paper, issue 6.18. The idea is to provide a general purpose hash<> utility for use by * Boost.MultiIndex * TR1-based unordered containers (Daniel is working on this.) * Eventually, wrapping by Boost.TR1. 5. The library comes fully documented and tested, and in our view well prepared for uploading to the CVS. 6. Yet, this hasn't undergone any formal review, so some of you might (with reason) object to its being commited to the CVS. From our point of view, we have three valid alternatives: * Boost members agree to have it in CVS without more ado. * As this is used by Boost.MultiIndex, Boost.Hash is suitable for fasttrack review. * This is untolerable and the library should be push_back()'ed to the review queue. Meanwhile, Boost.Hash should live as an impl detail of Boost.MultiIndex. We hope you find the material useful and look forward to knowing your opinions about the issues brought forward. Best, Joaquín M López Muñoz Daniel James

2 1

Profiling Library suggestion
by christopher diggins 19 Feb '05

19 Feb '05

I was searching around boost for mention of a profiling library. A fellow by the name of Carl Daniels posted something about an invasive profiling library. I was wondering in anyone knows what happened to that project? Profiling seems lacking at Boost, is anyone else interested in such a thing? Would a trivial policy driven RAII type be sufficient to garner interest as a mini-library? e.g. struct ProfilerDefaultPolicy { OnElapsed(int msec) { cout << "time elapsed (msec): " << msec << endl; } }; template<typename Policy_T = ProfilerDefaultPolicy> class Profiler { public: Profiler() { mnStart = GetTickCount(); }; ~Profiler() { Policy_T::OnElapsed(GetMSecElapsed()); }; int GetMSecElapsed() { return GetTickCount() - mnStart; }; int GetTickCount() { return int(double(clock()) * 1000 / CLOCKS_PER_SEC); }; private: int mnStart; }; usage: void MyRoutine() { Profiler<> p; // do stuff } Pretty trivial (and probably not boost-worthy), but I find it very useful. Does anyone want to take this and run with it (i.e. boostify it)? Christopher Diggins Object Oriented Template Library (OOTL) http://www.ootl.org

14 67

Broken links to CVS information
by Julio M. Merino Vidal 19 Feb '05

19 Feb '05

Hi! first of all, I should say hi to everybody, since I'm new to the list. I hope this is the correct mailing list to send a patch against the website (according to the page about bug reporting, it should be). During the last past few days, I've been reading about Boost at the website because I'm interested in using it in one of my projects. I must say that the website is great. It has lots of information and is well organized. Anyway, while doing so, I've came across some broken links to the CVS access information. (As well as some typos, but I have to re-find them...) They point to the obsolete (according to the logs) download.html file, while they should be pointing to getting_started.html. I've attached a patch which corrects this. BTW, vim warned me saying that the files I changed in the patch do not have a newline at the end. It added one automatically, but I've removed that chunk from the patch. Is this behavior expected? IMHO, the newline should be there (otherwise, cat <file> looks ugly). Kind regards, -- Julio M. Merino Vidal <jmmv84(a)gmail.com> http://www.livejournal.com/users/jmmv/ The NetBSD Project - http://www.NetBSD.org/

3 3

New Logging Library
by John Eddy 19 Feb '05

19 Feb '05

I have continued working on a logging library as a possible contender for a new Boost library. I have made sweeping changes inspired by comments and requests from a number of people (all very helpful). Here are some of the properties of the library as it is now. All components are completely independent of one another and highly parameterized for flexibility. The primary components are: -Entries which can be anything at all (built-in or user-defined types). There are a number of custom entries that I have created that support for example ostream like formatting. -Logs which actually go about the job of storing/processing/whatevering entries. I have created a few logs for writing to files, ostreams, storing entries in a list, etc. -Log managers are intermediaries between users and logs. They can do whatever they wish prior to passing entries on to logs. I have implemented a few managers so far. 1 that does virtually nothing. 1 that discriminates based on logging levels (only entries of appropriate levels get logged) and one that discriminates on levels and supplies a callback mechanism for whatever levels desired. Many managers can be attached to the same log. -Level Policies are classes supplied to level log managers indicating what the different allowable levels are. The documentation is still in very rough shape but the code in its current state is available for simple download from www.eng.buffalo.edu/~johneddy. It is not well Boost-ified yet but the directory structure is in place and some example files are available. Everything is implemented in header files at this point so no library need be built. John

5 12