Brook Milligan wrote:
John Bytheway writes:
I'm concerned about the behaviour of standard algorithms in this context. For example, consider a general 'power' function <snip> 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.
Indeed. It's always a good first step! :)
- 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.
A good point, but the implementation I was looking at (from the gcc 4.3.1 header ext/numeric) doesn't, because it actually supports arbitrary MonoidOperations, not just multiply (and that in turn makes me think that there's something missing in that implementation, but that's another issue).
- 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.
Could you easily write it such a way as to work well for both Domain-based types and other types? (Clearly this is possible with sufficient metaprogramming, but is it easy?)
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.
Indeed. I agree that's the best solution, but it might be overoptimistic to assume it's always a practical one. I feel runtime typing has its uses, but I can't come up with a concrete example, so perhaps I'm being too pessimistic. John