February 2005 - Boost - lists.boost.org

Review managers needed
by Tom Brinkman 21 Feb '05

21 Feb '05

The following libraries are scheduled to be reviewed in the coming weeks. Finite State Machine (FSM) Andreas Huber Review Manager - Pavel Vozenilek Policy Pointer David Held Fixed Strings Reece Dunn FOREACH Macro Eric Niebler typeof Arkadiy Vertleyb,Peder Holt If you are familiar with one of the these libraries and would like to volunteer to be the review manager, please contact me at reportbase(a)yahoo.com. Tom Brinkman Review Wizard __________________________________ Do you Yahoo!? Yahoo! Mail - Helps protect you from nasty viruses. http://promotions.yahoo.com/new_mail

3 2

[Boost-bugs] [ boost-Bugs-1145183 ] Can't build on cygwin
by SourceForge.net 21 Feb '05

21 Feb '05

Bugs item #1145183, was opened at 2005-02-20 21:32 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1145183&group_… Category: None Group: None Status: Open Resolution: None Priority: 5 Submitted By: Nobody/Anonymous (nobody) Assigned to: Nobody/Anonymous (nobody) Summary: Can't build on cygwin Initial Comment: boost 1.32.0 from cvs while i'm trying to compile it under cygwin with: bjam -sTOOLS=gcc install i have an error: unknown target type for <@boost!libs!test! build>libboost_prg_exec_monitor. Anybody can help me? Thank you, diabolo(a)gcnet.ru ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1145183&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

wave gcc "bits/c++config.h" invalid name
by Larry Evans 21 Feb '05

21 Feb '05

Getting: cd ~/prog_dev/boost-release/boost_1_32_0/lje/libs/fields_visitor/test/ wave -S/usr/include/c++/3.3 test_link.cpp #line 42 "/usr/include/c++/3.3/iostream" #pragma GCC system_header /usr/include/c++/3.3/iostream(42): exception caught: boost::filesystem::path: invalid name "c++config.h" in path: "bits/c++config.h" Should the criteria for valid name be changed?

4 10

Two more typos
by Julio M. Merino Vidal 21 Feb '05

21 Feb '05

Hi again, another fix for two more typos is attached. Cheers, -- Julio M. Merino Vidal <jmmv84(a)gmail.com> http://www.livejournal.com/users/jmmv/ The NetBSD Project - http://www.NetBSD.org/

1 0

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