TypeFunction example: ImplictConvTargets

[Adam D. Ruppe]

On Tuesday, 6 October 2020 at 15:24:31 UTC, Bruce Carneal wrote:
> I believe we should aim for the simplest code that admits the 
> desired performance.

Sure, but the desired performance here, for this stuff, is the 
clear priority. Especially at lower levels where the costs 
compound. Here's some princely advice: it is better to be both 
feared and loved, but if you can be only one or the other, it is 
better to be feared than to be loved. That's the reason why 
Phobos does it the way it does. It'd love to have both, but if it 
is one or the other, fast compiles are far more important than 
pretty code.

> Well, what is a "real problem"?

That code compiles slowly and/or with excessive memory. That's 
why type functions are being investigated.

There's no new functionality gained by the type functions. Their 
whole reason for existing is to make faster, less memory hungry 
builds. (right now anyway, that might change if it gains 
capabilities, but right now an explicit design goal is to make 
them a limited subset of template functionality in the name of 
improved performance).

I frequently take Stefan's examples, copy/paste them into a 
template, and use them. The code doesn't even look that different.

The problem is there's several usages where this version is slow.

type function version:

alias type = alias;
type[] basicTypeConvTargets(type T)
{
     type[] targets;
     targets.length = basic_types.length;
     size_t n = 0;
     foreach(t;basic_types)
     {
         if (is(T : t))
         {
             targets[n++] = t;
         }
     }
     return targets[0 .. n];
}

template version:

alias type = string;
type[] basicTypeConvTargets(T)()
{
     type[] targets;
     targets.length = basic_types.length;
     size_t n = 0;
     foreach(t;basic_types)
     {
         if (is(T : mixin(t)))
         {
             targets[n++] = t;
         }
     }
     return targets[0 .. n];
}


Very little difference! The makeConvMatix was *identical* except 
for the function prototype (and even there, both return 
strings!). Filter's guts can be:

         size_t[Args.length] keep;
         size_t pos = 0;
         foreach(idx, alias arg; Args)
                 if(Pred!arg) keep[pos++] = idx; // note idx, not 
arg.
         return makeResult(keep[0 .. pos]);

In today's D. Again, *almost identical* to the typefunction 
version, just using an index into the list instead of storing the 
alias in the array directly.


What kills this approach is *not* the code being hideous. It is 
the performance aspect - additional CTFE code is necessary to 
convert it back to a type tuple, and secondarily, the foreach 
being unrolled leads to extra work. A type function can simply do 
`returned.tupleof` and keep the foreach how it is. Here, we'd 
have to `mixin(returned.doConversion)`. (Where doConversion is a 
similarly reusable lib function.)

Again, minor syntax difference, but significant performance hit 
because doConversion must rebuild a new string out of stuff the 
compiler already knows. Phobos' current implementation is uglier, 
but also faster and uses less memory than the mixin version. So 
it wins over it.

This is the place the typefunction has a potential win. It might 
combine the nice code AND get a performance improvement. But if 
the TF ends up slower than Phobos has now... it is going to be 
rewritten into the faster version, even if uglier, because it is 
the compile performance driving this evolution.

The Phobos implementation started life with a very simple 
implementation too. It became what it is because it *had to*, 
specifically for performance reasons.