Re: [Boost-users] [MultiIndex] re-indexing on load

From: joaquin_at_[hidden]
Date: 2008-04-28 10:17:31

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");
}