Re: [Boost-users] Flyweight: wrapping shared_ptr

Subject: Re: [Boost-users] Flyweight: wrapping shared_ptr
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2014-10-14 05:34:44

Akim Demaille <akim <at> lrde.epita.fr> writes:

> 
> Hi!
> 
> Le 12 oct. 2014 Ã  20:46, Joaquin M Lopez Munoz <joaquin <at> tid.es> a >
écrit :
> 
> > If you change the creation of e to something like
> > 
> >        Exp e = bin('*',
> >                    bin('+', num(1+(j%m)), num(1+(j%m))),
> >                    bin('+', num(2+(j%m)), num(2+(j%m))));
> > 
> > for some constant m (in the range of 1000, for instance) then you
> > can modulate the level of redundancy (the lower m, the more duplicate
> > values): tuning m can tell you how Boost.Flyweight improves wrt the
> > shared_ptr case (which should not be affected by m at all). I bet
> > by having m sufficient low and n sufficiently high #7 can get to beat
> > #1.
> 
> I couldn't find such n and m.  Actually, too large a n gives
> not so nice errors:
> 
> $ time ./7
> Assertion failed: (pthread_mutex_lock(&m_)==0), function scoped_lock, file
> /opt/local/include/boost/flyweight/detail/recursive_lw_mutex.hpp, line 72.
> 
> but I'm not surprised: the tree must be too deep, and I'm not even
> sure my stack is in good shape.  I have not tried to disable locking,
> as I'd be happy to go multithread in the future, but currently it
> wouldn't be a problem.

Yep, this definitely looks like the reentrant lock recursion limit has
been hit (Pthreads ERECURSE error).

Expression depth is limiting how far you can go with n in your
becnhmark. If you changed the code so that the complexity of e
remains bounded as n grows (10,000 is not that large), the performance
of Boost.Flyweight would be better and better with respect to #1. An
alternative could be to maintain a vector of expressions so that
redundancy is higher even for moderately high n's. Anyway, this is
just trying to prove a point that at the end of the day might not be
too interesting for your purposes.

> >> ./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
> >> 
> > 
> > Well, seems like there's a clear winner here (ruling out #1, which
> > I understand from what you say it's not an acceptable alternative,
> > presumably because of memory limitations).
> 
> No, my hope is that I can get faster hashing and operator== on
> my expressions in all the algorithms that are on top of these
> expressions.  I am not yet worried about memory consumption.
> But maybe I'm hoping for something I won't get...

Hashing and equality comparison of flyweight'd expressions is going
to be blazingly fast as compared with recursive non-flyweight'd
versions. Also, have you considered memoizing eval(), either by
storing eval result in the expressions themselves or using something
like the following?

http://www.boost.org/libs/flyweight/doc/examples.html#example5

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