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