- Boost-users - lists.boost.org

[iostreams] - device ready for non-blocking operations?
by Oliver.Kowalke＠infineon.com 17 Mar '06

17 Mar '06

Hello, is a device, which read and write member-functions could be non-blocking, per default ready for non-blocking operations - or what do I have to do in order to make it properly working with iostreams? Regards, Oliver

1 0

[serialization] My implementation of serialization of STL iterators.
by Carlo Wood 17 Mar '06

17 Mar '06

I succeeded in writing code that successfully serializes my data structures, which contain a LOT a iterators, and even vectors of iterators. However, the end result turned out to be extremely slow (it takes several minutes), due to some inefficiency in boost::serialization (it should be possible to serialize this in a few seconds). I didn't investigate why boost::serialization becomes so slow, but I suppose it is caused by the fact that as a result of how things are serialized, the structure written to file is several thousands of levels deep (meaning, that in the XML file the indentation of the output is also many thousands of TAB's deep). I'm going to approach my problem of serialization in a different way now - making a copy of the data structure, such that the result can be serialized without needing to serialize iterators. Nevertheless, I don't want to keep my solution for the iterators from others; so below follows a brief overview of what I made. An average serialize() function looks as follows: template<class Archive> void Data::serialize(Archive& ar, unsigned int const) { ar & BOOST_SERIALIZATION_BASE_OBJECT_NVP(BaseClass); ar & BOOST_SERIALIZATION_NVP(M_variable); ar & BOOST_SERIALIZATION_ITERATOR_NVP(container, M_iterator); ar & BOOST_SERIALIZATION_ITERATOR_NVP(container, M_vector_of_iterators); } where BOOST_SERIALIZATION_ITERATOR_NVP is my invention ;). 'container' has to be the container that the iterator(s) point at. In the case of a vector of iterators, that is the container that the iterators point at, not the vector. Ie, M_iterator could of type std::set<FooBar>::iterator, then container is the std::set<FooBar> container, and M_vector_of_iterators would be of type std::vector<std::set<FooBar>::iterator>. Both, the container type (std::set<FooBar>) as well as the type of it's elements need to be tracked; hence, the above would need: BOOST_CLASS_TRACKING(FooBar, boost::serialization::track_always); BOOST_CLASS_TRACKING(std::set<FooBar>, boost::serialization::track_always); This would then first serialize the container (if not already done) and then serialize the element that the iterator points to (if not already done). I defined BOOST_SERIALIZATION_ITERATOR_NVP as follows: // This macro generates the name string (from 'name'). #define BOOST_SERIALIZATION_ITERATOR_NVP(container, name) \ serialization_iterator_nvp(container, BOOST_PP_STRINGIZE(name), name) where serialization_iterator_nvp is an heavily overload, inline template function: template<typename Container> inline boost::serialization::nvp<IteratorWrapper<Container, typename Container::iterator> > serialization_iterator_nvp(Container& container, char const* name, typename Container::iterator const& t) { IteratorWrapper<Container, typename Container::iterator> tmp(container, const_cast<typename Container::iterator&>(t)); return boost::serialization::nvp<IteratorWrapper<Container, typename Container::iterator> >(name, tmp); } template<typename Container> inline boost::serialization::nvp<IteratorWrapper<Container, typename Container::const_iterator> > serialization_iterator_nvp(Container& container, char const* name, typename Container::const_iterator const& t) { IteratorWrapper<Container, typename Container::const_iterator> tmp(container, const_cast<typename Container::const_iterator&>(t)); return boost::serialization::nvp<IteratorWrapper<Container, typename Container::const_iterator> >(name, tmp); } // Specialization for std::set, because for that container, the iterator and const_iterator are the same type! template<typename T> inline boost::serialization::nvp<IteratorWrapper<std::set<T>, typename std::set<T>::const_iterator> > serialization_iterator_nvp(std::set<T>& container, char const* name, typename std::set<T>::const_iterator const& t) { IteratorWrapper<std::set<T>, typename std::set<T>::const_iterator> tmp(container, const_cast<typename std::set<T>::const_iterator&>(t)); return boost::serialization::nvp<IteratorWrapper<std::set<T>, typename std::set<T>::const_iterator> >(name, tmp); } And in order for BOOST_SERIALIZATION_ITERATOR_NVP to also deal with vectors of iterators: template<typename Container> inline boost::serialization::nvp<VectorIteratorWrapper<Container, typename Container::iterator> > serialization_iterator_nvp(Container& container, char const* name, std::vector<typename Container::iterator> const& v) { VectorIteratorWrapper<Container, typename Container::iterator> tmp(container, const_cast<std::vector<typename Container::iterator>&>(v)); return boost::serialization::nvp<VectorIteratorWrapper<Container, typename Container::iterator> >(name, tmp); } template<typename Container> inline boost::serialization::nvp<VectorIteratorWrapper<Container, typename Container::const_iterator> > serialization_iterator_nvp(Container& container, char const* name, std::vector<typename Container::const_iterator> const& v) { VectorIteratorWrapper<Container, typename Container::const_iterator> tmp(container, const_cast<std::vector<typename Container::const_iterator>&>(v)); return boost::serialization::nvp<VectorIteratorWrapper<Container, typename Container::const_iterator> >(name, tmp); } // Specialization for std::set, because for that container, the iterator and const_iterator are the same type! template<typename T> inline boost::serialization::nvp<VectorIteratorWrapper<std::set<T>, typename std::set<T>::const_iterator> > serialization_iterator_nvp(std::set<T>& container, char const* name, std::vector<typename std::set<T>::const_iterator> const& v) { VectorIteratorWrapper<std::set<T>, typename std::set<T>::const_iterator> tmp(container, const_cast<std::vector<typename std::set<T>::const_iterator>&>(v)); return boost::serialization::nvp<VectorIteratorWrapper<std::set<T>, typename std::set<T>::const_iterator> >(name, tmp); } This uses two template class wrappers (which are declared before these functions in my file): IteratorWrapper and VectorIteratorWrapper. Their definitions are as follows: // A wrapper for iterators. template<class Container, typename Iterator> class IteratorWrapper { public: IteratorWrapper(Container& container, Iterator& iter) : M_container(container), M_iter(iter) { } private: Container& M_container; // The container. Iterator& M_iter; // The actual iterator. public: template<class Archive> void save(Archive& ar, unsigned int const) const { BOOST_STATIC_ASSERT(boost::serialization::tracking_level<Container>::type::value == boost::serialization::track_always); BOOST_STATIC_ASSERT(boost::serialization::tracking_level<typename Container::value_type>::type::value == boost::serialization::track_always); ar << boost::serialization::make_nvp("container", M_container); bool is_end = M_iter == M_container.end(); ar << boost::serialization::make_nvp("end", is_end); if (!is_end) ar << boost::serialization::make_nvp("element", *M_iter); } template<class Archive> void load(Archive& ar, unsigned int const) { ar >> boost::serialization::make_nvp("container", M_container); bool is_end; ar >> boost::serialization::make_nvp("end", is_end); if (!is_end) { typename Container::value_type* tmp_value; ar >> boost::serialization::make_nvp("element", tmp_value); } else M_iter = M_container.end(); } BOOST_SERIALIZATION_SPLIT_MEMBER() }; // A wrapper for a vector of iterators. template<class Container, typename Iterator> class VectorIteratorWrapper { public: VectorIteratorWrapper(Container& container, std::vector<Iterator>& iter) : M_container(container), M_vec(iter) { } private: Container& M_container; // The container. std::vector<Iterator>& M_vec; // The actual vector of iterators. public: template<class Archive> void save(Archive& ar, unsigned int const) const { BOOST_STATIC_ASSERT(boost::serialization::tracking_level<Container>::type::value == boost::serialization::track_always); BOOST_STATIC_ASSERT(boost::serialization::tracking_level<typename Container::value_type>::type::value == boost::serialization::track_always); int count = M_vec.size(); ar << BOOST_SERIALIZATION_NVP(count); for (typename std::vector<Iterator>::const_iterator iter = M_vec.begin(); iter != M_vec.end(); ++iter) { IteratorWrapper<Container, Iterator> iter_functor(M_container, const_cast<Iterator&>(*iter)); ar << boost::serialization::make_nvp("item", iter_functor); } } template<class Archive> void load(Archive& ar, unsigned int const) { int count; ar >> BOOST_SERIALIZATION_NVP(count); while(count--) { Iterator tmp_iter; IteratorWrapper<Container, Iterator> iter_functor(M_container, tmp_iter); ar >> boost::serialization::make_nvp("item", iter_functor); M_vec.push_back(tmp_iter); } } BOOST_SERIALIZATION_SPLIT_MEMBER() }; In both cases, the assertions make sure you didn't forget the two BOOST_CLASS_TRACKING lines. Have fun with it, Carlo Wood <carlo(a)alinoe.com> PS I didn't test the load() functions, but the resulting archive (I used xml) looked correct, thus, the serialization works.

1 0

Re: [Boost-users] boost::multi_index_container::erase very slow on FreeBSD 6.0
by JOAQUIN LOPEZ MU?Z 16 Mar '06

16 Mar '06

----- Mensaje original ----- De: bert hubert <bert.hubert(a)netherlabs.nl> Fecha: Jueves, Marzo 16, 2006 10:59 pm Asunto: [Boost-users] boost::multi_index_container::erase very slow on FreeBSD 6.0 > Ok, regarding my previous message, I've now boiled down the > problem of > quadratically slower erases to something that does happen on > FreeBSD 6.0 and > doesn't happen on my Linux machines. > > The problem may be due to: > 1) boost::multi_index container (highly unlikely) > 2) g++ allocator > 3) FreeBSD libc, if the g++ allocator relies on it > 4) FreeBSD kernel > > And I don't even know where to start. > Hello Bert, I've just compiled and run your benchmark in Windows (with minor modifications to substitute for Unix-specific timing functions) and the behavior is O(N). I'm sorry I can't be more helpful, the following is a series of steps you can use to gain more insight into the problem: 1) Use a multimap instead of the multi_index_container. Double the number of elements to compensate for the fact that the multi-index container takes more memory per element (as it has two indices.) 2) Undo 1) and try running the 100..5000 loop in reverse order 5000..100. What do you get? If the quadratic behavior shows as we approach n=100 (the opposite of the original benchmark) I would tend to think the issue has to do with memory fragmentation. 3) Try a pool allocator like for instance boost::fast_pool_allocator: http://boost.org/libs/pool/doc/interfaces/pool_alloc.html I hope some of this can shed some light. Joaquín M López Muñoz Telefónica, Investigsción y Desarrollo

2 1

Re: [Boost-users] [multi_index] modify_range?
by JOAQUIN LOPEZ MU?Z 16 Mar '06

16 Mar '06

----- Mensaje original ----- De: Jeff Flinn <TriumphSprint2000(a)hotmail.com> Fecha: Jueves, Marzo 16, 2006 11:09 pm Asunto: Re: [Boost-users] [multi_index] modify_range? > Joaquín Mª López Muñoz wrote: > > So wouldn't the only use of modify_unstable_range be for modifying > keys and > indirect members? So only a single modify_unstable_range calling > .modify_key > would suffice? Just thinking out loud here, until I have access to > the docs. I'm not sure I'm making my point. There are two orthogonal issues to consider here: 1 Whether you are modyfing whole elements (A) or keys (B). 2 Whether the modification is "stable" (1) or not (2). The four combinations are actual possibilities: A1: modify_range A2: modify_unstable_range B1: modify_key_range B2: modify_key_unstable_range where B1 and B2 (which are not given in my previous snippet) are written exactly as A1 and A2, respectively, except that where it read .modify(...) you've got to write .modify_key(...). "Stability" is not dependant on whether you're modifying elements or keys: you can get stable and unstable range modifications both ways. What defines a stable range modification of the form modify[_key]_range(i,first,last,mod) is that, after modifying an element pointed to by iterator it, the resulting repositioning does not lie inside [++it,last), i.e. we're sure we won't visit the element again. You can see in my previous snippets examples of stable and unstable range modifications. > > Thanks for your library and your help. :) > > Jeff You're welcome, thank you for using the Boost.MultiIndex. Joaquín M López Muñoz Telefónica, Inevstigación y Desarrollo _______________________________________________ Boost-users mailing list Boost-users(a)lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

1 0

purge_memory of fast_pool_allocator's singleton pool
by Michael Fawcett 16 Mar '06

16 Mar '06

Is there a way to purge the memory of the underlying singleton_pool used by a specific fast_pool_allocator? For example: typedef boost::fast_pool_allocator < std::pair<const int, astar_node *>, boost::default_user_allocator_new_delete, boost::details::pool::null_mutex > my_allocator; typedef std::map<int, astar_node *, std::less<int>, my_allocator> MyMap; // ...do lots of allocations // I don't care about destructors being called, just release ALL memory if (boost::singleton_pool < boost::fast_pool_allocator_tag, sizeof(my_allocator::value_type), my_allocator::user_allocator, my_allocator::mutex, my_allocator::next_size >::purge_memory() == false) { std::cout << "Failed to purge the fast_pool!!" << std::endl; } This always prints the error message for me. I suspect it has something to do with map's allocator rebinding to allocate map nodes, but I'm not sure how to solve this. Any help would be appreciated.

1 0

Re: [Boost-users] [multi_index] modify_range?
by JOAQUIN LOPEZ MU?Z 16 Mar '06

16 Mar '06

Jeff Flinn wrote: > It would be nice to have a modify_range/modify_key_range that would apply a > function object to each deref'd iterator in the range. Since the multi_index > iterator derefences to a const value_type&, one can not use std::for_each in > particular to apply modifications. Or am I missing something. Hello Jeff, I think it is possible to have what you want without requiring that a new facility be provided by Boost.MultiIndex itself. For you can write: template<typename Index,typename Modifier> void modify_range( Index& i,typename Index::iterator first,typename Index::iterator last, Modifier mod) { while(first!=last)i.modify(first++,mod); } and use it as in the following example: struct adder { adder(int n):n(n){} void operator()(int& x)const{x+=n;} private: int n; }; typedef multi_index_container< int, indexed_by< ordered_non_unique<boost::multi_index::identity<int> > > > multi_index_type; multi_index_type m; for(int i=0;i<10;++i)m.insert(i); modify_range(m,m.begin(),m.end(),adder(-2)); or with Boost.Lambda if you prefer: modify_range(m,m.begin(),m.end(),_1-=2); There is a problem, though: consider the following: // buggy call ro modify_range modify_range(m,m.begin(),m.end(),adder(2)); What's the problem with this? Well, after *increasing* the value of an element, this is repositioned further to the end of the container, and consequentely modify_range will visit it again and engage in a neverending loop (modulo overflows.) For this situations you can use a special (albeit slower) variation that records the range before starting modifying the elements: template<typename Index,typename Modifier> void modify_unstable_range( Index& i,typename Index::iterator first,typename Index::iterator last, Modifier mod) { typedef std::vector<typename Index::iterator> buffer_type; buffer_type v; while(first!=last)v.push_back(first++); for(typename buffer_type::iterator it=v.begin(),it_end=v.end(); it!=it_end;i.modify(*it++,mod)); } // calling modify_unstable_range is now OK modify_unstable_range(m,m.begin(),m.end(),adder(2)); I hope my explanations are clear enough. Does this satisfy your needs? You can find attached a complete example exercising these little utilities. modify_key_range would be a simple variation on this stuff. HTH, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

3 3

Re: [Boost-users] SOLVED! Re: multi_index 1.33.0, known problems withRHEL 3 compiler (gcc 3.2.3)?
by JOAQUIN LOPEZ MU?Z 16 Mar '06

16 Mar '06

----- Mensaje original ----- De: bert hubert <bert.hubert(a)netherlabs.nl> Fecha: Lunes, Marzo 13, 2006 8:32 pm Asunto: Re: [Boost-users] SOLVED! Re: multi_index 1.33.0,known problems withRHEL 3 compiler (gcc 3.2.3)? > On Mon, Mar 13, 2006 at 05:22:35PM +0100, Joaqu?n M? L?pez Mu?oz > wrote: > > I'd check the following for anomalies: > > Joaquin, I'm busy tonight with other things so I'm only able to > give you > some approximate answers, for which I apologise. I hope to be able > to give > more definitive answers Wednesday. Of course, come back when you can. > > > 1. Could you (just for tests), replace index #0, which now is > hashed,> with an ordered_unique index and rerun? A quadratic > behavior could > > be the result of a very bad hashing scheme: this is extremely > unlikely> for your current code, but who knows. > > The original container had ordered_unique as its first index and > showed a > similar (large) increase in pruning time when pruning more cache > entries. I > did not look for a power law or anything. OK, let's rule out hashing problems, then. > > > 2. Is the size of CacheEntry::d_records roughly the same between > > prunes? Could it be that the average number of records in CacheEntry > > elements is disproportionately larger on those prunes that take > > longer? > > The cache remains almost identical in size, around 50 million > entries. The > cache represents DNS records expiring, each run expires all DNS > entries that > have a 'time to die' ttd that is larger than the current time. I'm not referring here to d_entry.size(), but to the average x.d_records.size() for x in d_entry. How many records does a cache entry have on the average? Does this experience large variations? > > This holds, I think, a vital clue to the problem at hand. Records are > inserted with ever increasing ttds, generally. There is a number > of common > time-to-live numbers for DNS records, ie, 5, 60, 300, 3600, 7200, > 86400seconds. > > This means that we have a number of 'striding' ttd's being > inserted: now + > 5, now + 60, now +300 .. now +86400. Might this trigger a badly > balancedtree? It shouldn't, otherwise it would be a bug in Boost.MultiIndex. Not that I categorically deny this possibility, but I tend to think the problem might lie elsewhere. If we're left with nothing else, we could arrange a test for balancedness easily enough, please tell me so when you're ready to instrument that. > > On a related note, I wonder if chopping off the lower half of any > sort of > ordered tree might trigger worst case behaviour. Note that > CacheEntry::getTTD() which forms one index might be slow to call. The erase() part is not affected, as it doesn't invoke the comparison predicate nor the key extractor (getTTD in your case.) > > > 3. What percentage of elements of d_cache are visited on each > > prune? I.e. what is the typical value of looked/d_cache.size()? The > > nonvisited elements shoudn't have any impact on phase /*2*/, > > but they have a (minimal) impact on those operations of /*1*/ > > performing as O(n log n), such as replace(). Anyway, no amount > > on nonvisited elements can have such a huge impact on figures. > > Typically 500 elements are visited of a 50 million element > structure, so > 1e-5. Things get crazy once > 1000 elements are visited. Doesn't seem like large variatons on d_entry.size() are to be accounted for the problem, then. > > Thanks Joaquin, I hope to provide more measurements soon. > This problem is intriguing me... specially the fact that you observe quadratic behavior in a linearly-decomposable (and hence O(n)-behaved) problem. I think the following, easy test, can shed some light: to state facts, what you get is reasonably fast pruning when pruning period (and thus looked value) is low, with an explosion when pruning period reaches a given threshold, around say looked=800, right? And this happens even (quote) "without inserting something in the container in between", right? Why don't you try then the following: when pruning time is above a threshold, make doPrune do the pruning in two stages (and time each separately): 1. up to now/2. 2. up to now. According to the stated facts, making doPrune in two stages is about equivalent to making it in one fell swoop, wich implies the summed time won't change much. On the other hand, it is also equivalent to having a halved, below-threshold pruning period, thus implying contradictorily that the summed time will be much less than with one stage pruning. Why don't you do the test? Interesting things might come up... Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

2 3

[serialization] Problem deriving from text_oarchive_impl
by Robert S. Grimes 16 Mar '06

16 Mar '06

Hi, I'm starting to get the hang of this as I slog through, but it's still a bit rough! I'm able to derive a new archive from binary_oarchive_impl, but for some reason, I can't do the same with text_oarchive_impl. Specifically, I get the following error (from MS Visual C++ 8.0, using Boost 1.33.1): 1>..\rsg_text_oarchive.hpp(24) : error C2649: 'basic_text_oprimitive<class std::basic_ostream<char,struct std::char_traits<char> > >' : is not a 'class' 1> ..\rsg_text_oarchive.hpp(40) : see reference to class template instantiation 'rsg_text_oarchive_impl<Archive>' being compiled The similar line in the binary archive works fine. Attached are the two derived archives in question. All I'm trying to do (at this point) is add a short header in the constructor; next, I'll want to add a footer in the destructor. Thanks! -Bob

2 5

Question regarding dynamic_bitset -
by Michael 16 Mar '06

16 Mar '06

boost::dynamic_bitset<byte> m_patterndelta; // intialization of m_patterndelta .... std::vector<byte> pack; boost::to_block_range<byte>(m_patterndelta, pack.begin()); // GPF because of bad pointer in "pack". Cannot figure why, may be someone can help?

2 1

How to add linker options to installed test
by Smith Matt - matsmi 16 Mar '06

16 Mar '06

I am trying to run the tests that were installed with Boost.Regex and Boost.Function. Trouble is, the HP-UX 11.23 OS is requiring me to include "-lunwind" as one of my linker options. Is there a way to modify the Jamfile for those tests to include that option when linking? The compiler I am using is G++ 4.02. Thanks. Matt Smith Acxiom Corporation Data Compilation CWY0101-80 PO Box 2000 301 Industrial Blvd. Conway, AR 72033-2000 (501) 342-2434 Matt.Smith(a)acxiom.com *************************************************************************** The information contained in this communication is confidential, is intended only for the use of the recipient named above, and may be legally privileged. If the reader of this message is not the intended recipient, you are hereby notified that any dissemination, distribution or copying of this communication is strictly prohibited. If you have received this communication in error, please resend this communication to the sender and delete the original message or any copy of it from your computer system. Thank You. ****************************************************************************

1 0