Re: [boost] flyweight - gsoc idea - multikey-value flyweight

16 Feb 2016

      Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
...
Le 15/02/2016 07:51, Joaquin M LópezMuñoz a écrit :
...
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
...
Hi Joaquin,
I have a use case where I have several keys to the same flyweight.
[...]
Let say you are writing an application that manage with some entities. 
You have two kind of operator that use a specific protocol and each 
protocol identify these entities using a key MOi. Suppose that you 
application use a library that has an interface that use different keys 
to identify these same entities, because it is using an internal 
protocol. You want also to have some CLI for debugging purposes that 
uses strings to identify these same entities.
All these keys are isomorphic so you can move from one key to the other 
using a specific algorithm[...]
OK, let's sketch these ideas. Let's say

  key1=int
  key2=char
  value=std::string

and we want to minimize conversion from keyi to keyj and construction
of values, because they're all expensive operations (not in this
particular case, but you get the idea). We make the converting functions
output to the console to keep track of if/when they're called:

    char key2_from_key1(int i)
    {
      std::cout<<"key2_from_key1\n";
      return static_cast<char>(i);
    }

    int key1_from_key2(char c)
    {
      std::cout<<"key1_from_key2\n";
      return static_cast<int>(c);
    }

    std::string value_from_key1(int i)
    {
      std::cout<<"value_from_key1\n";
      return boost::lexical_cast<std::string>(i);
    }

    std::string value_from_key2(char c)
    {
      std::cout<<"value_from_key2\n";
      return boost::lexical_cast<std::string>(c);
    }

Now, we can store all of this in an internal element class like:

    struct element
    {
      int         key1;
      char        key2;
      std::string value;

      element(int i):
        key1{i},
        key2{key2_from_key1(i)},
        value{value_from_key1(i)}
      {}

      element(char c):
        key1{key1_from_key2(c)},
        key2{c},
        value{value_from_key2(c)}
      {} 
    };

(key1,value) flyweights are easy to define:

    struct element_key1
    {
      const int& operator()(const element& e)const{return e.key1;}
    };

    using key1_flyweight=flyweight<key_value<int,element,element_key1>>;

but now we want to use key2 as well. One way to bring key2 into
the scene while referring to the same entities as with key1 (so as to
not duplicate values) is to have key2_flyweight defined on top of the
previous key1_flyweight:

    struct element_key2
    {
      const char& operator()(const key1_flyweight& f)const
      {
        return f.get().key2;
      }
    };

    struct key2_flyweight:
      flyweight<key_value<char,key1_flyweight,element_key2>>
    {
      using super=flyweight<key_value<char,key1_flyweight,element_key2>>;

      key2_flyweight(char c):super{c}{}

      const element& get()const{return super::get().get();}
    };

And we want to go a step further so that flyweights created with key1
interoperate with those created with key2 --that is, we want both kinds
of objects to be realizations of the same type:

    struct multi_flyweight:boost::variant<key1_flyweight,key2_flyweight>
    {
      using super=boost::variant<key1_flyweight,key2_flyweight>;

      multi_flyweight(int i):super{key1_flyweight{i}}{}
      multi_flyweight(char c):super{key2_flyweight{c}}{}
      multi_flyweight(const element& e):super{key1_flyweight{e}}{}

      const element& get()const
      {
        return boost::apply_visitor(
          [](const auto& f)->decltype(auto){return f.get();},
          *this);
      }

      operator const element&()const{return this->get();}
    };

    bool operator==(const multi_flyweight& x,const multi_flyweight& y)
    {
      return &x.get()==&y.get();
    }

All of this allows us to do

    int main()
    {
      multi_flyweight f1{124};
      multi_flyweight f2{char{124}};
      multi_flyweight f3{f2.get()};
      multi_flyweight f4{f1};

      std::cout<<f1.get().value<<"\n";
      std::cout<<f2.get().value<<"\n";
      std::cout<<f3.get().value<<"\n";
      std::cout<<f4.get().value<<"\n";
      std::cout<<(f1==f2)<<"\n";
      std::cout<<(f2==f3)<<"\n";
      std::cout<<(f3==f4)<<"\n";
    }

with output

    key2_from_key1
    value_from_key1
    124
    124
    124
    124
    1
    1
    1

which effectively shows that key and value creation is minimized, and
the resulting semantics is what we were after. You can play with a
complete example at

http://coliru.stacked-crooked.com/a/6dab2c556433fb03

Does this approach your use case? Some points:

* This can be easily generalized to N keys with some metaprogramming.
* Note that we haven't changed the internals of Boost.Flyweight to
use something like a multi-key factory (which is probably what you
had in mind). Instead, this is all done on top of the existing library,
which has the obvious drawback (among others) that
sizeof(multi_flyweight)==2*sizeof(void*), where sizeof(flyweight) is
typically sizeof(void*). Whether this is acceptable or not depends
really on the use cases, I'd say.
* Rewriting this in the most efficient way through multi-key factories
(likely based on Boost.MultiIndex) can be done but requires introducing
whole new concepts into the framework --current factories are by
definition one-key, so they simply can't be used for this.
* Is this a desireable extension to Boost.Flyweight? I don't have a
strong opinion myself, others' most welcome.
* Is this a good candidate for GSoC? If the answer to the above is yes,
I'd say this is certainly in the good ambition/impact ratio window for
a GSoC project, and I'd be happy to mentor.

Joaquín M López Muñoz
Telefónica

Re: [boost] flyweight - gsoc idea - multikey-value flyweight

Joaquin M López Muñoz