From: Brook Milligan (brook_at_[hidden])
Date: 2008-07-30 18:18:31
John Bytheway writes:
> I'm concerned about the behaviour of standard algorithms in this
> context. For example, consider a general 'power' function
> template<typename T, typename Integer>
> power(T, Integer);
> which will involve a lot of multiplying.
You are absolutely right that an algorithm like this could be much
less efficient if given the "wrong" type for T than if given a
"better" type for T. You are also correct to observe that this might
impose a requirement that the user of the algorithm know something
about the interaction between the algorithm and the type T in order to
understand the performance issues.
There are some benefits deriving from the Domain library that I hope
will reduce your concern.
- Use of the generic power() is guarranteed to give the correct
answer, regardless of the choice made for T. Perhaps that
guarrantee is worth something.
- A reasonable implementation of power() would use operator*=() and a
reasonable implementation of polynomial_c (as described) would not
define that. Thus, the user code you describe would never compile
and a search for the reason why would quickly lead to the
polynomial_pv type which gives the minimal conversions you seek.
- The actual difference in performance will be small for low-degree
polynomials as the scaling is asymptotic. A different library
design allowing multiplication of both polynomial types might be
appropriate. Alternatively, why not have a customizable polynomial
library that can be tuned for large (where even two conversions may
be preferred over one multiplication) versus small (where it may
matter little) polynomials? Any of these solutions could be
constructed using Domain.
- Developing a Domain-aware specialization of the power() algorithm
could resolve the performance issues altogether. The algorithm
would be generic and thus applicable to all types based upon the
library, not just polynomials.
> I'm not sure what the best solution is, but one possibility is this:
> Support a runtime-domained type, which acts something like a
> variant<polynomial_c, polynomial_pv>, but with operators defined on it.
Rather than have this runtime cost, the library has a type deduction
system that determines the appropriate return types based upon the
axioms that govern the library's design. Thus, a Domain-aware
implementation of the power() function can guarrantee that the
argument is transformed at most once and then only when necessary.
This, I believe, offers the best possibility: any Domain-based
argument type works, the minimum number of conversions is performed,
there are no runtime costs associated with deciphering the types, and
the algorithm is still completely generic.
My hope is that the Domain library successfully provides a framework
for developing application domain-specific libraries that provide both
correctness and performance, while maintaining generic approaches.
Please continue to raise issues to see if the library meets that goal.
I hope I can flesh out the documentation so that more of this is
apparent there, but in the meantime this discussion helps me
understand the issues that need better descriptions.
Thanks for the help.
 Perhaps two conversions are required if the return type _must_
conform to something specific that is incompatible with
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk