- Boost - lists.boost.org

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

20 Feb '05

----- Mensaje original ----- De: Daniel James <daniel(a)calamity.org.uk> Fecha: Domingo, Febrero 20, 2005 7:53 pm Asunto: [boost] Re: [multi_index][hash][rfc] Hashed indices preview +Boost.Hash > JOAQUIN LOPEZ MU?Z wrote: > > 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. > > FWIW, if you can find a spare bit in a pointer, I've thought of a > non-portable way to get something closer to O(1) without the extra > memory load. The nodes are stored in a singly-linked list which > includes > the buckets, so the last node in a bucket points to the next > bucket. The > spare bit is used to indicate if a pointer is pointing to a node > or a > bucket. So the data structure is something like: > [...] Hi Daniel, We can get rid of the spare bit if only iterators store a pointer to the container: then we can test whether a pointer points to a true element or a bucket just by checking if it is in the range [buckets.begin(),buckets.end()). Still constant, though admittedly slower than the bit thing. Main problem with this is, as you point out, that traces of empty buckets will be left when erasing. Still, it seems somewhat better than the classic implementation, at least wrt to theoretical complexity (in practice it'd probably be significantly slower.) Joaquín M López Muñoz Telefónica, Investigación y Desarrpññp

2 1

is_convertible patch for HP/aCC
by Toon Knapen 20 Feb '05

20 Feb '05

The latest incarnation of the HP compiler (version 6.0) looks to be a hugh improvement in respect to earlier versions. I'm looking into porting boost to HP aCC and I suggest to apply following (minor) patch (see attach). OK to commit this? toon cvs diff: Diffing . Index: is_convertible.hpp =================================================================== RCS file: /cvsroot/boost/boost/boost/type_traits/is_convertible.hpp,v retrieving revision 1.28 diff -u -r1.28 is_convertible.hpp --- is_convertible.hpp 4 Sep 2004 10:34:48 -0000 1.28 +++ is_convertible.hpp 14 Feb 2005 13:09:41 -0000 @@ -125,7 +125,7 @@ }; #elif (defined(__EDG_VERSION__) && (__EDG_VERSION__ >= 245) && !defined(__ICL)) \ - || defined(__IBMCPP__) + || defined(__IBMCPP__) || defined(__HP_aCC) // // This is *almost* an ideal world implementation as it doesn't rely // on undefined behaviour by passing UDT's through (...). cvs diff: Diffing detail

3 4

profiling library and documentation update
by christopher diggins 20 Feb '05

20 Feb '05

I have now uploaded the new documentation for the library at: http://www.ootl.org/profiler/ I am no longer including the high-res timer as part of the library. I have moved the timer to http://www.ootl.org/ootl/misc/high_resolution_timer.hpp.htm for those that want, but I hope the library will be evaluated independantly of the design. I have tried to take into account as many suggestions and comments as possible, but it is hard to track their relevancy/urgency as the design has evolved. I would appreciate it if anyone has suggestions or concerns which they feel are still relevant, to please bring them up again. I am particularly interested in knowing how useful the library is in its current incarnation, and how far it is from something that could be seriously considered for Boost inclusion. Christopher Diggins Object Oriented Template Library (OOTL) http://www.ootl.org

1 1

Problem with multi_array and serialization
by Matthias Troyer 20 Feb '05

20 Feb '05

Hi, Trying to combine boost multi_array and serialization I found a very strange compiler bug (?) on MacOS X, using eother the Apple version of gcc-3.1. The following simple code will not compile: #include <boost/multi_array.hpp> namespace strange_namespace { class access { }; } int main() { boost::multi_array<int,2> x(boost::extents[3][3]); int y=x[0][0]; } It fails with the error message src/boost/boost/multi_array/multi_array_ref.hpp: In member function `typename boost::const_multi_array_ref<T, NumDims, T*>::reference boost::multi_array_ref<T, NumDims>::operator[](typename boost::const_multi_array_ref<T, NumDims, T*>::index) [with T = int, long unsigned int NumDims = 2]': test.C:11: instantiated from here src/boost/boost/multi_array/multi_array_ref.hpp:512: no matching function for call to `boost::const_multi_array_ref<int, 2, int*>::access( boost::type<boost::detail::multi_array::sub_array<int, 1> >, index&, int*, const size_type*, const index*, const index*)' src/boost/boost/multi_array/subarray.hpp: In member function `typename boost::detail::multi_array::const_sub_array<T, NumDims, T*>::reference boost::detail::multi_array::sub_array<T, NumDims>::operator[](typename boost::detail::multi_array::const_sub_array<T, NumDims, T*>::index) [with T = int, long unsigned int NumDims = 1]': test.C:11: instantiated from here src/boost/boost/multi_array/subarray.hpp:261: no matching function for call to `boost::detail::multi_array::const_sub_array<int, 1, int*>::access( boost::type<int&>, index&, int*&, const size_type*, const index*, const index*)' This looks like a compiler bug, since the code compiles when removing the class definition access in a completely unrelated namespace. Has something similar been observed before? Does anybody know a workaround? Matthias

1 0

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