Re: [Boost-users] [MultiIndex] re-indexing on load
Hi Joaquin.
As you have found out, loading involves some amount of reindexing, though the algorithm is designed to minimize this, let me summarize how serialization of multi_index_containers is performed:
Saving a multi_index_container internally consists in:
1. Saving each of the elements, in the order they are traversed with index #0. 2. For each index other than #0, some "readjusting" info is saved if necessary. More on this later.
Loading on the other hand reduces to:
1. Loading each element and inserting them with hinted insertion at the end of the container: for index #0, hinting the end() position reduces the nomber of key comparisons performed: for the rest of key based indices, hinting end() usually does not have any impact and insertion takes as many comparison ops as a regular insertion. 2. After step 1 the elements in index #0 are listed in the exact order they were originally saved, as it should be. As for the rest of the indices, they can be differences in traversal order for non key-based indices (sequenced and random_access) and for ordered non-unique indices (equivalent elements will be adjacent as ordered non-unique indices guarantee, but they might be shuffled with respect to the original situation). The "adjusting" info stored in saving step 2 is used here to restore the exact original traversing order for every index of the container.
So, to try to minimize your loading time you'd need to first make a guess about where the most overhead lies: is it in step 1 or step 2? Step 2 can only be significant if any of your indices *other than #0* is of type ordered_non_unique, sequenced or random_access. Assuming you indeed have a situation where step 2 causes some impact, you can:
a) if affordable, move the problematic index to position #0, so that it won't get any adjustment later. b) replace Boost.MultiIndex built-in serialization with the a handmade method so as to avoid step 2 altogether. Please find attached a sketchy implementation example of this idea. Note that this method does not guarantee exact traversal order replication for indices other than #0.
In any case, do not expect spectacular improvements after applying any of the approaches above, as more likely most of the overhead comes from step 1 anyway. A more radical solution, but also one with a very high impact in your application code, is to put the multi_index_container in a memory-mapped file, so that serialization reduces to dumping the memory segment. You can find an example of this technique at:
http://www.boost.org/doc/libs/1_35_0/libs/multi_index/doc/examples.html#exam...
Thanks for the explanation and ideas. Based on the information you provided, I guessed that moving from hashed indices (where the hash function is relatively expensive) to sorted_non_unique (with a cheap comparison function) would improve things; and indeed that change has got the load hugely quicker. I then tried the 'poor man serialization' example that you attached. As you suspected, the performance effect of this was pretty small and so I guess it is indeed step 1 that is causing the issue (I have several ordered_non_uniques). I do like the memory mapped file idea, but as you say, the impact on the code is large; I think too large for the time being, though it may be sometime I come back to if needs be in the future. I think, for the time being at least, the performance is ok now (using ordered rather than hashed indices). Is there any chance that future versions of MI might be able to store the hashes/complete ordering whilst serializing, or is that Just Not Possible (TM)? Thanks again, Mark
Mark Westcott escribió:
Hi Joaquin.
[...]
I think, for the time being at least, the performance is ok now (using ordered rather than hashed indices). Is there any chance that future versions of MI might be able to store the hashes/complete ordering whilst serializing, or is that Just Not Possible (TM)?
I think this would pose problems, as hashes are not guaranteedly platform portable, so storing them transparently to the user could trigger subtle bugs. But maybe for your particular applicatin you can consider caching the hash values --from your description, this can not only accelarate serialization, but also the general lookup ops, given that your hash algorithm is expensive. A more or less encapsulated way to do it would be defining a class like: template<typename Derived,typename KeyExtractor> struct cached_hash{...}; that is meant to be derived from in the following manner: struct element_base { element_base(const std::string& str,unsigned int n):str(str),n(n){} std::string str; unsigned int n; }; struct element: element_base, cached_hash<element,member<element_base,std::string,&element_base::str> >, cached_hash<element,member<element_base,unsigned int,&element_base::n> > { element(const std::string& str,unsigned int n):element_base(str,n){} }; That is, cached_hash<> is provided with a key extractor to access the key whose hash it must cache. With a little magic relying on appropriately specializing boost::hash and std::equal_to for cached_hash and making use of the so-called compatible key lookup (http://tinyurl.com/4t7jyk ) we can use cached_value in Boost.Multindex almost transparently: typedef multi_index_container< element, indexed_by< hashed_non_unique< identity< cached_hash<element,member<element_base,std::string,&element_base::str> > > >, hashed_non_unique< identity< cached_hash<element,member<element_base,unsigned int,&element_base::n> > > > >
multi_t;
int main() { multi_t m; m.insert(element("hello",0)); m.insert(element("boost",1)); m.insert(element("bye",2)); assert(m.find("hello")->n==0); assert(m.find("boost")->n==1); assert(m.find("bye")->n==2); assert(m.get<1>().find(0)->str=="hello"); assert(m.get<1>().find(1)->str=="boost"); assert(m.get<1>().find(2)->str=="bye"); } A complete example program is provided, use freely if of any use. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo #include <boost/functional/hash.hpp> #include <boost/multi_index_container.hpp> #include <boost/multi_index/hashed_index.hpp> #include <boost/multi_index/identity.hpp> #include <boost/multi_index/member.hpp> #include <boost/type_traits/remove_const.hpp> #include <boost/type_traits/remove_reference.hpp> #include <cassert> #include <string> template<typename Derived,typename KeyExtractor> struct cached_hash { typedef typename boost::remove_const< typename boost::remove_reference< typename KeyExtractor::result_type >::type
::type value_type;
cached_hash():h(0){} /* Call whenever the associated key changes. Automatically called the * first time boost::hash accesses the object. */ void touch()const { KeyExtractor key; boost::hash<value_type> hsh; h=hsh(key(static_cast<const Derived&>(*this))); if(h==0)h=1; } private: mutable std::size_t h; friend std::size_t hash_value(const cached_hash& x) { if(x.h==0)x.touch(); return x.h; } friend bool operator==(const cached_hash& x,const cached_hash& y) { KeyExtractor key; return key(static_cast<const Derived&>(x))==key(static_cast<const Derived&>(y)); } friend bool operator==(const cached_hash& x,const value_type& y) { KeyExtractor key; return key(static_cast<const Derived&>(x))==y; } friend bool operator==(const value_type& x,const cached_hash& y) { KeyExtractor key; return x==key(static_cast<const Derived&>(y)); } }; namespace boost{ template<typename Derived,typename KeyExtractor> struct hash<cached_hash<Derived,KeyExtractor> > { std::size_t operator()(const cached_hash<Derived,KeyExtractor>& x)const { return hash_value(x); } std::size_t operator()(const typename KeyExtractor::result_type& x)const { std::size_t h=hash_value(x); return h==0?1:h; } }; } /* namespace boost */ namespace std{ template<typename Derived,typename KeyExtractor> struct std::equal_to<cached_hash<Derived,KeyExtractor> > { bool operator()( const cached_hash<Derived,KeyExtractor>& x, const cached_hash<Derived,KeyExtractor>& y)const { return x==y; } bool operator()( const cached_hash<Derived,KeyExtractor>& x, const typename KeyExtractor::result_type& y)const { return x==y; } bool operator()( const typename KeyExtractor::result_type& x, const cached_hash<Derived,KeyExtractor>& y)const { return x==y; } }; } /* namespace std */ using namespace boost::multi_index; struct element_base { element_base(const std::string& str,unsigned int n):str(str),n(n){} std::string str; unsigned int n; }; struct element: element_base, cached_hash<element,member<element_base,std::string,&element_base::str> >, cached_hash<element,member<element_base,unsigned int,&element_base::n> > { element(const std::string& str,unsigned int n):element_base(str,n){} }; typedef multi_index_container< element, indexed_by< hashed_non_unique< identity< cached_hash<element,member<element_base,std::string,&element_base::str> > > >, hashed_non_unique< identity< cached_hash<element,member<element_base,unsigned int,&element_base::n> > > >
multi_t;
int main() { multi_t m; m.insert(element("hello",0)); m.insert(element("boost",1)); m.insert(element("bye",2)); assert(m.find("hello")->n==0); assert(m.find("boost")->n==1); assert(m.find("bye")->n==2); assert(m.get<1>().find(0)->str=="hello"); assert(m.get<1>().find(1)->str=="boost"); assert(m.get<1>().find(2)->str=="bye"); }
participants (1)
-
joaquin＠tid.es -
Mark Westcott