Re: [Boost-users] Flyweight: wrapping shared_ptr

Subject: Re: [Boost-users] Flyweight: wrapping shared_ptr
From: Akim Demaille (akim_at_[hidden])
Date: 2014-10-12 13:07:31

Hi Joaquín,

Le 10 oct. 2014 à 22:02, Joaquin M Lopez Munoz <joaquin_at_[hidden]> a écrit :

>> Well, I couldn't get this work.  In fact b neither. [...]
> 
> All the problems you describe are precisely the ones Boost.Flyweight
> tries to solve :-)

Yes.  The more I was writing code, failing, and working around
issues, the more I realized everything Flyweight needs to do.

>> The bench was as follows [...]
> 
> I think the main penalty in your per-type test comes from the fact that
> you're maintaining two separate refcounting systems (flyweight and
> shared_ptr<Holder>) and two virtual hierarchies (Exp_impl and
> Holder) in parallel, which effectively doubles the bookkeeping
> load of the program.

Indeed.

> On the other hand, I think the benchmark is
> probably too lightweight to really discern whether per-type hashing
> is beneficial or detrimental: the number of elements involved is
> too low, so everything will fit in the working memory very comfortably,
> and hash collision, either in the single or in the per-type case, is
> almost certain not to occur. May I suggest you extend the benchmarking
> to deal with tens of thousands of unique values *at a given time*:
> this would yield, I guess, fairer results.

You are right, and I am amazed by the figures below.  Actually, I
have checked several times if I did something wrong, but I don't
think so.

The new bench is as follows:

  {
    size_t n = 10 * 1000;
    Exp exp = num(0);
    for (unsigned j = 1; j <= n; ++j)
      {
        Exp e = bin('*',
                    bin('+', num(j), num(j)),
                    bin('+', num(j), num(j)));
        Exp f = bin('/', e, e);  // <======== a fancy "1"
        exp = bin('+', exp, f);  // <======== so this is ++exp
      }
    assert(exp->eval() == n);
  }

which I ran on several implementations:

1.cc: basic implementation using inheritance
http://coliru.stacked-crooked.com/a/840ddd39842323e8

7.cc: inheritance, single Flyweight factory for the base class
http://coliru.stacked-crooked.com/a/0d9a4eb64cbbe820

9.cc: inheritance, per-concrete types factories and custom
      wrapper
http://coliru.stacked-crooked.com/a/e0c2e130fc668e30

10.cc: variant based implementation, no flyweight at all
http://coliru.stacked-crooked.com/a/d51374d1272915d2

11.cc: variant based implementation, single flyweight for
       the resulting variant type (i.e., same as your example
       in the doc).
http://coliru.stacked-crooked.com/a/44d2c491dcfcaf6c

The results are:

./1     0,02s user 0,00s system 93% cpu    0,031 total
./7     0,06s user 0,00s system 97% cpu    0,070 total
./9    46,19s user 0,09s system 99% cpu   46,424 total
./10  171,29s user 9,71s system 99% cpu 3:01,09  total
./11   17,25s user 0,04s system 99% cpu   17,296 total

The variants are amazingly costly compared to "native" polymorphism.
It seems to consume so much space that the system part is now visible.

As to whether it is better to have per-derived or per-base factory,
it's not even a close call.  Of course it is even better not to
share at all, but that's expected by the bench itself.  In my
case, I expect to get ROI by getting faster hash/operator== in
my library.  I originally planed to implement a variant of
flyweights per-type, but it does not seem like an interesting
alternative any longer.