Subject: Re: [boost] [dynamic_bitset] expression template?
From: Ben Coates (ben_at_[hidden])
Date: 2012-11-21 11:55:59
Beman Dawes <bdawes <at> acm.org> writes:
> On Wed, Nov 21, 2012 at 3:36 AM, Ben Coates <ben <at> blueskylabs.com> wrote:
> > dynamic_bitset currently allocates temporary vectors for most
> > operations, and all the allocating and deallocating can easily
> > dominate the running time for a program that makes heavy use of them.
> > You can work around some of it with careful use of named temporaries
> > around loops but some operations like intersection of 3 sets ( (a & b
> > & c).any() ) result in a lot of unwanted copies and allocations.
> > I've had good results converting it to use expression templates for
> > intermediary operations, with the outcome of being able to do
> > arbitrary non-resizing operations without allocating. Is there any
> > interest in changing the boost version to do this?
> Yes, but...
> Does the interface change? If so, How?
The only breaking change to the published interface that would be required
is what happens when you capture a return value from an operator using type
dynamic_bitset<> a = foo(), b = bar();
auto x = a&b; // dynamic_bitset<> x = a&b would behave as before
dynamic_bitset<> c = x; // will be all zeroes
The expression evaluation is delayed until the construction of a
dynamic_bitset<> typed result, or a call to a scalar function like .count()
or .any(). At that point all the arguments of the expression must still
be valid and it's their values at that time that are used.
There would likely also be substantial breaking changes to the non-published
interface of what happens when you use BOOST_DYNAMIC_BITSET_PRIVATE or the
template friend function hack to manipulate m_bits directly.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk