On 4/22/20 9:35 AM, Manu wrote:
> On Wed, Apr 22, 2020 at 11:20 PM Steven Schveighoffer via Digitalmars-d
> <digitalmars-d@puremagic.com <mailto:digitalmars-d@puremagic.com>> wrote:
>
> On 4/22/20 8:04 AM, Manu wrote:
> > We have a compile time problem, and this is basically the cure.
> > Intuitively, people imagine CTFE is expensive (and it kinda is), but
> > really, the reason our compile times are bad is
> template instantiation.
> >
> > This DIP single-handedly fixes compile-time issues in programs I've
> > written by reducing template instantiations by near-100%, in
> particular,
> > the expensive ones; recursive instantiations, usually
> implementing some
> > form of static map.
> >
> > https://github.com/dlang/DIPs/pull/188
> >
> > This is an RFC on a draft, but I'd like to submit it with a
> reference
> > implementation soon.
> >
> > Stefan Koch has helped me with a reference implementation, which
> has so
> > far gone surprisingly smoothly, and has shown 50x improvement in
> compile
> > times in some artificial tests.
>
> Yes please! Where is the reference implementation? I want to try some
> things out.
>
>
> The link is in the DIP.
Oops, it's at the top, I missed that. Thanks.
> Most tests we've done are working, except template instantiation
> expansion is not yet implemented: ie, Thing!(Tuple, x, y)...
> That's got a lot of implementation baggage attached to it in DMD.
Ugh, I think I won't be able to test then, most of this stuff works with
lists of types, not values.
Types work now, it just depends what you do with them.
For instance, `cast(TypeTup)ValueTup` works right now.
And come to think of it, staticMap works, but I need Filter as well. I
suppose it can help a bit, but I still am going to have tons of
"temporary" templates that are going to clog up the memory.
I'd like to see some of your use cases. I do expect you'll need some shim templates in some cases (ie, filter), but the major difference is that they won't tend to be recursive expansions. Recursive expansions have quadratic cost... without those, your compilation should return to a linear cost world.
Fold/reduce operations can be proposed similarly to this as a follow up. It might be possible to specify a filter combining a map + fold.
Stefan, where's that implementation of first class types for CTFE-only
functions you promised? ;)
We've been talking about this, and I actually think this lays some foundation for some of that work.
Type functions is a pretty big spec challenge. This will solve a huge amount of perf issues, simplify code, and it's a very simple addition relatively speaking.
Another development that would benefit us hugely would be first-class tuples which Timon (I think?) has been working on for some time.
That would eliminate the awkward AliasSeq hack, and simplify the implementation. In a first-class tuple world, we may be able to nest tuples, whereas today, nested AliasSeq flatten.
>
> I expect you won't be able to run practical tests on real code yet
> without TemplateInstance expansion.
> The problem is that existing code is factored exclusively into
> template instantiations, so a trivial experiment will apply to existing
> code in that form.
The trivial experiment to test is to take a list of types with possible
duplicates and remove all duplicates. It doesn't have to be in any order.
Probably not possible with nothing but a map operation. There will be additional logic, but an efficient map should improve the perf substantially.
I'm hoping something like this might work:
template NewFilter(pred, T...)
{
template process(U) {
static if(pred!U) alias process = U;
else alias process = AliasSeq!();
}
alias NewFilter = AliasSeq!(process!(T)...); // do I need the
AliasSeq here?
}
This should work. No, you don't need the AliasSeq.
template RemoveDuplicates(T...)
{
template keepIt(U) {
enum isSame(V) = __traits(isSame, U, V);
enum keepIt = NewFilter!(isSame, T).length == 1;
}
alias RemoveDuplicates = NewFilter!(keepIt, T);
}
I think efficient implementation here would depend on a static fold, which I plan for a follow-up, and it's a very trivial expansion from this DIP.
Static reduce would allow `...` as an argument to a BinOp
Ie; `Tup + ...` would expand `Tup[0] + Tup[1] + Tup[2] + ...`
You could do `is(FindType
== Tup) || ...`, and it would evaluate true if FindType exists in Tup, with no junk template instantiations!
Will this work better? You will still have a bunch of NewFilter,
process, keepIt, and isSame instantiations, all with horribly long
symbol names. But of note is there is no recursive instantiation patterns.
Using fold as above, you can eliminate the boilerplate.
I don't want to propose that here though. It's a relatively trivial expansion from this initial DIP.
One thing I noticed, in order to use a property on a static map
expansion (i.e. call a function with the resulting sequence, or access
.length), you will need extra parentheses to distinguish the ... token
from the . token.
>
call a function with the resulting sequence
Not sure what you mean exactly?
Calling a function that receives the sequence as var args:
f(TupExpr...)
Calling a function for each element in the sequence?
f(TupExpr)...
Is there an easier/better way to do this with the new feature?
Can you show an example? Maybe the precedence is wrong?