I dun a DIP, possibly the best DIP ever

[Manu]

On Thu, Apr 23, 2020 at 12:05 AM Steven Schveighoffer via Digitalmars-d <
digitalmars-d at puremagic.com> wrote:

> 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 at puremagic.com <mailto:digitalmars-d at 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?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20200423/44e25e3e/attachment-0001.htm>