Re: [boost] Domain library

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[1] 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.

Cheers,
Brook

[1] Perhaps two conversions are required if the return type _must_
conform to something specific that is incompatible with
multiplication.