ken.durden@augusttech.com (Ken Durden) wrote
> I've used boolean template arguments in the past to remove unnecessary
> conditional logic inside a large loop
> for efficiency reasons.
  ^^^^^^^^^^^^^^^^^^^^^^

Have you validated your optimization in the profiler?

> Ex:
>
> int main() {
>   bool b1;
>   cin >> b1;
>   for( long i = 0; i < 500L * 1000L * 1000L; ++i ) {
>     if( b1 ) <action1>
>     else     <action2>
>   } }

A common optimization is "loop invariant", which would
automatically transform your program into the equivalent
of this:

  int main() {
    bool b1;
    cin >> b1;
    if (b1)
        for (long i=0; i<500L * 1000L * 1000L; ++i) <action1>;
    else
        for (long i=0; i<500L * 1000L * 1000L; ++i) <action2>;
  }

> becomes:
>
> template< bool b1 >
> void f() {
>   for( long i = 0; i < 500L * 1000L * 1000L; ++i ) {
>     if( b1 ) <action1>
>     else     <action2>
>   } }
>
> int main() {
>   bool b1;
>   cin >> b1;
>   if( b1 ) f<true>();
>   else     f<false>();
>   }
>
> And thus the actual conditional is removed by effectively creating two
> copies of the f function (one with action1, and one with action2).

Which is a hand-crafted equivalent of the same optimization that
compilers do (except that your version also has function-call
overhead).

> My proposal is that the compiler allow me to write the following code:
>
> int main() {
>   bool b1;
>   cin >> b1;
>   f<b1>();
>   }

I'm sure that you already see the difficulty with this proposal.
It's no good specifying a language enhancement that cannot be
implemented. If we extend this to it's logical limit, we quickly
run into problems.

  #include <iostream>
  template<int i>void f() { std::cout << "Was " << i << std::endl; }
  int main() {
    int i;
    std::cin >> i;
    f<i>();
  }

When the compiler is compiling main(), what code should it generate?
If it somehow "knew" that i could be either 0 or 2 or 4, it could
instantiate all three of these. Since it can't "know" what value
you're going to type, should it instead instantiate f() for every
legal value of int? If int is 16 bits, that's 65,536 instantiations;
it gets MUCH worse if int is bigger. (For 64-bits we would need
18,446,744,073,709,551,616 instantiations!) And then there's long,
and float, and double, and complex<double>, and char[4], and char[5],
and..., and..., and...!

IMHO, that's why non-type template arguments have to be constants.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Allan_W@my-dejanews.com (Allan W) wrote in message news:<23b84d65.0207301755.7e1978d7@posting.google.com>...
>
> Have you validated your optimization in the profiler?

No, I haven't, but I would prefer to guarantee this behavior by using
the template non-type parameter method if possible.

>
> A common optimization is "loop invariant", which would
> automatically transform your program into the equivalent
> of this:
>
>   int main() {
>     bool b1;
>     cin >> b1;
>     if (b1)
>         for (long i=0; i<500L * 1000L * 1000L; ++i) <action1>;
>     else
>         for (long i=0; i<500L * 1000L * 1000L; ++i) <action2>;
>   }

What is the likelihood of that transformation happening if the loop
was more complicated, with 40 lines before the <action 1/2> and 40
lines after? Eventually the compiler would decide that code size is
too important to make this code duplication occur. By using the bool
template argument the programmer is telling the compiler that the
expansion is desired.

>
> I'm sure that you already see the difficulty with this proposal.
> It's no good specifying a language enhancement that cannot be
> implemented. If we extend this to it's logical limit, we quickly
> run into problems.

I don't see why it has to be extended to all integral types. It's
trivial to implement with bools, impossible to implement for other
integral types w/o significant syntax additions (to designate what
range of values are supported, what to do if the value is out of that
range).

Thanks,
-ken

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Steve Clamage <clamage@eng.sun.com> wrote in message news:<Pine.SOL.4.33.0207311255570.20023-100000@taumet>...
>
> You would need some additional syntax to tell the compiler that no
> explicit specializations exist, or if some do exist, which ones they are.

I don't see why this is necessary. If a specialization exists for true
or false, then that specialization will be called in the expanded form
of the if.

>
> As the language stands, an explicit specialization of the template
> might be provided elsewhere in the program, in which case the
> compiler must not generate a conflicting one.

The compiler is not generating a specialization of the template
function, it is merely writing the expanded form of the call.

>
> Do you intend this feature only for bool template arguments?

Its use seems most important with bool template arguments. I did
consider how to do it for other integral types, but I figured you
would have to have more syntax:

template< char c = 'A'..'Z' >
void f() {}

Syntax changes such as this would be way out of my realm of knowledge
to know what kinds of syntax would be parseable, nonambigious, etc...

>
> Expanding integer arguments would not be feasible. But what about
> char arguments?  Is 256 function versions too many?  (You might generate
> more than 256 functions in the scenario you present, just for type bool.)
> What about enums?  Expand for each enumerator?  Usually there are few,
> but sometimes there are hundreds or thousands.

At least with bool expansion it is clear than 2^N (N = # of bool
arguments) instantiations will exist. More than two char arguments
would immediately explode to unreasonable realms, so I think for
integral types there would have to be a method of specifying the
actual range supported. Of course, then there are weird issues about
what to do when the element is outside of the range supported. Due to
these other issues I felt it was best to leave it as bool
auto-expansion.

>
> I think you need to flesh out the details of your proposal some more.

We could also specify a required compiler expansion level, such as,
the compiler must support 4 bool arguments (16 instantiations), but is
free to support more than that. Must issue a diagnostic warning or
error if more than the supported # of arguments are used.

-ken

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

I've used boolean template arguments in the past to remove unnecessary
conditional logic inside a large loop for efficiency reasons.

Ex:

int main()
  {
  bool b1;
  cin >> b1;

  for( long i = 0; i < 500L * 1000L * 1000L; ++i )
    {
    if( b1 )
      <action1>
    else
      <action2>
    }
  }

becomes:

template< bool b1 >
void f()
  {
  for( long i = 0; i < 500L * 1000L * 1000L; ++i )
    {
    if( b1 )
      <action1>
    else
      <action2>
    }
  }

int main()
  {
  bool b1;
  cin >> b1;

  if( b1 )
     f<true>();
  else
     f<false>();
  }

And thus the actual conditional is removed by effectively creating two
copies of the f function (one with action1, and one with action2).

My proposal is that the compiler allow me to write the following code:

int main()
  {
  bool b1;
  cin >> b1;

  f<b1>();
  }

And use the knowledge that b1 is a non-ct-literal in order to expand
it to the earlier form. This can be somewhat important when there are
other arguments than the bool:

int main()
  {
  bool b1;
  cin >> b1;

  if( b1 )
    f<true, std::string, std::vector<std::string>,
std::queue<std::list> >();
  else
    f<false, std::string, std::vector<std::string>,
std::queue<std::list> >();
  }

The obvious replication of all the other template arguments presents a
maintainability risk & an obvious loss of elegance.

The other area (which is actually the one with which I was concerned)
is when there are many template bool arguments, thus making the
hand-expansion particularly cumbersome:

int main()
  {
  bool b1, b2, b3, b4, b5, b6;

  cin >> b1 >> b2 >> b3 >> b4 >> b5 >> b6;

  if( b1 )
    if( b2 )
       if( b3 )
         if( b4 )
           if( b5 )
             if( b6 )
               f<true,true,true,true,true,true>();
             else
               f<true,true,true,true,true,false>();
           else
             if( b6 )
               f<true,true,true,true,false,true>();
             else
               f<true,true,true,true,false,false>();

  <the rest ommited for space>
  }

In the actual code I was using, I had about 10 of these variables,
thus making the hand expansion practically impossible to do. Of
course, doing this would have a major impact on object code size
(creating 2^10 versions of the function listed above), but similar
arguments can be made about templatization in general.

Anyway, there's my idea, any thoughts about this? Anything in the
language I'm missing which would prevent it from implementing this?

-ken

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]