Re: [boost] A C++ puzzler

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-04-13 17:38:35

[I have sent an incomplete message by mistake... here is the conclusion]
On Sun, Apr 13, 2008 at 11:31 PM, Giovanni Piero Deretta
<gpderetta_at_[hidden]> wrote:
> On Sun, Apr 13, 2008 at 9:42 PM, Eric Niebler <eric_at_[hidden]> wrote:
>  > Giovanni Piero Deretta wrote:
>  >
>  >  >> conditional operator. Wish I thought of that. But it requires
>  >  >>  types to be associated with integers via a global registry, so I can't
>  >  >>  use it. Is there a way to avoid select() and result<>? It's easy with
>  >  >>  typeof, but can you do it without?
>  >  >>
>  >  >
>  >  > Here is a try. it probably will look more at home at an obfuscated C++ context.
>  >  >
>  >  > It works up to 5 types. Extending it beyond is a matter of a little of
>  >  > pp metaprogramming.
>  >  >
>  >  > The only O(N) template (that I can see) instantiation is
>  >  > template<class T> default_type::operator T();
>  >
>  >  Not a problem. It's a function template, so instantiating it would be
>  >  cheaper than instantiating a class template (I think), but you're not
>  >  even instantiating it. It doesn't even have a definition.
>
>  D'oh right! I assumed that generating the function signature counted
>  as instantiation. Obviously it doesn't.
>  I have even introduced a bug in a mindless try to eliminate all template usage:
>  while the following:

   struct C{};
   struct D : C{};

   assert(is_same<C,common<C, D>::type>);

works as expected,
this doesn't:

  assert(is_same<C, common<D, C>::type)

The fix is simple:
add the overload

  template<class T> true_& match(T&, T&);

and change the result type of the match(...) overload to false.

>
>  >
>  >
>  >  > And you do not pay for it if you do not use default_type (partially
>  >  > specializing common_type may work as an optimization).
>  >  >
>  >  > I'll try to get rid even of this.
>  >  >
>  >  > Even if there are very few template instantiations, compile time isn't
>  >  > that good. I thought that compile time integral expression
>  >  > computations were basically free. Maybe I'm missing something.
>  >
>  >  This solution is very clever! Why do you say that compile time is poor?
>  >  What are you benchmarking against?
>  >

I have used a very scientific benchmark: I run the test and was mildly
annoyed by the time it took to compile :).

Anyways, there are actually N^2 applications of operator:? . The
"inner loop" is always the same, but I do not know if compilers do
memoization of constant expressions,
so it might be worthwhile to do this optimization by hand.

-- 
gpd