On Monday, 16 May 2016 at 12:13:14 UTC, Martin Nowak wrote:
>
> Last time people forced me to spend several hours on reimplementing and debugging a BitArray implementation

Ouch.
src/tk/vec.(h|c) already contained an implementation.

On Sunday, 15 May 2016 at 12:17:30 UTC, Daniel Murphy wrote:
> On 15/05/2016 9:57 PM, Martin Nowak wrote:
>> On 05/15/2016 01:58 PM, Daniel Murphy wrote:
>>> The biggest advantage of bytecode is not the interpreter speed, it's
>>> that by lowering you can substitute VarExps etc with actual references
>>> to memory without modifying the AST.
>>>
>>> By working with something lower level than the AST, you should end up
>>> with something much less complex and with fewer special cases.
>>
>> Which is a bad assessment, you can stick variable indexes into
>> VarDeclaration (we already do that) and thereby access them in O(1).
>> Converting control flow and references into byte code is far from
>> trivial, we're talking about another s2ir and e2ir here.
>>
>> -Martin
>>
>
> For simple types that's true.  For more complicated reference types...
>
> Variable indexes are not enough, you also need heap memory, but slices and pointers (and references) can refer to values either on the heap or the stack, and you can have a slice of a member static array of a class on the stack, etc.  Then there are closures...
>
> Neither e2ir or s2ir are actually that complex.  A lot of the mess there comes from the backend IR interface being rather difficult to work with.
>  We can already save a big chunk of complexity by not having to translate the frontend types.  E.g.  implementing the logic in the interpreter to correctly unwind through destructors is unlikely to be simpler than lowering to an IR.

Exactly. I think the whole idea of trying to avoid a glue layer is a mistake.
CTFE is a backend. It really is. And it should be treated as one. A very simple one, of course.
Once you do this, you'll find all sorts of commonalities with the existing glue layers.
We should end up with at least 4 backends: DMD, GCD, LDC, and CTFE.

Many people here are acting like this is something complicated, and making dangerous suggestions like using Phobos inside the compiler. (I think everyone who has fixed a compiler bug that was discovered in Phobos, will know what a nightmare that would be. The last thing compiler development needs is another level of complexity in the compiler).

As I've tried to explain, the problems with CTFE historically were never with the CTFE engine itself. They were always with the interface between CTFE and the remainder of the compiler -- finding every case where CTFE can be called, finding all the bizarre cases (tuple variables, variables without a stack because they are local variables declared in comma expressions in global scope, local 'ref' variables, etc), finding all the cases where the syntax trees were invalid...

There's no need for grandiose plans, as if there is some almost-insurmountable problem to be solved. THIS IS NOT DIFFICULT. With the interface cleaned up, it is the well-studied problem of creating an interpreter. Everyone knows how to do this, it's been done thousands of times. The complete test suite is there for you. Someone just needs to do it.

I think I took the approach of using syntax trees about as far as it can go. It's possible, but it's really vile. Look at the code for doing assignments. Bleagh. The only thing in its favour is that originally it was the only implementation that was possible at all. Even the first, minimal step towards creating a ctfe backend -- introducing a syntax-tree-validation step -- simplified parts of the code immensely.

You might imagine that it's easier to work with syntax trees than to start from scratch but I'm certain that's not true. I'm pretty sure that the simplest approach is to use the simplest possible machine-independent bytecode that you can come up with. I had got to the point of starting that, but I just couldn't face doing it in C++.

TL;DR:  CTFE is actually a backend, so don't be afraid of creating a glue layer for it.

On Tuesday, 17 May 2016 at 10:42:30 UTC, Don Clugston wrote:
>
> TL;DR:  CTFE is actually a backend, so don't be afraid of creating a glue layer for it.

My point exactly.
The AST is not something I want to handle while inside the interpreter.
It introduces too much complexity.
There needs to be some kind of further lowering.

On Sunday, 15 May 2016 at 10:29:21 UTC, Martin Nowak wrote:
> On 05/10/2016 08:45 AM, Jacob Carlborg wrote:
>> 
>> I was listening to a discussion Don and Daniel had about the current implementation of CTFE. They talked about using a byte code interpreter. Even implementing a really crappy byte code interpreter would be a huge improvement.
>
> No need for a byte-code interpreter, it mostly just adds overhead and complexity over an AST interpreter. If you want to go really fast you need some sort of JIT anyhow, but a proper interpreter will be orders of mangnitude faster than the current implementation.
>
> I might refer you to
> http://dconf.org/2013/talks/chevalier_boisvert.pdf
> page 59 ff.

+1 . One need to walk the tree anyway to generate bytecode, which makes it impossible to make it faster for a one time execution.

For frequent executions, then a JIT is preferable, which let the bytecode the favorite choice for more than one, but not too many executions.

On 05/17/2016 12:42 PM, Don Clugston wrote:
> There's no need for grandiose plans, as if there is some almost-insurmountable problem to be solved. THIS IS NOT DIFFICULT. With the interface cleaned up, it is the well-studied problem of creating an interpreter. Everyone knows how to do this, it's been done thousands of times. The complete test suite is there for you. Someone just needs to do it.

Yes, exactly my words.

> I think I took the approach of using syntax trees about as far as it can go. It's possible, but it's really vile. Look at the code for doing assignments. Bleagh. The only thing in its favour is that originally it was the only implementation that was possible at all. Even the first, minimal step towards creating a ctfe backend -- introducing a syntax-tree-validation step -- simplified parts of the code immensely.

Yes, this
https://github.com/dlang/dmd/blob/7d00095301c4780b41addcfeb50f4743a9a6c5d4/src/dinterpret.d#L3418
is really ugly and complex, but you won't get rid of this inherent
complexity. The e2ir code for AssingExp looks almost the same
https://github.com/dlang/dmd/blob/7d00095301c4780b41addcfeb50f4743a9a6c5d4/src/e2ir.c#L2466.

> You might imagine that it's easier to work with syntax trees than to start from scratch but I'm certain that's not true. I'm pretty sure that the simplest approach is to use the simplest possible machine-independent bytecode that you can come up with. I had got to the point of starting that, but I just couldn't face doing it in C++.

All I'm saying is that interpreting the AST to generate bytecode is going to be as complex as interpreting the AST directly, but then you still a bytecode interpreter and later might still want a JIT.

Using dedicated value types during interpretation instead of recycling the AST for that will also make the transitions clearer and get rid of some of the lifetime complexities in the current code.

-Martin

On 18/05/2016 9:01 AM, Martin Nowak wrote:
>
> Yes, this
> https://github.com/dlang/dmd/blob/7d00095301c4780b41addcfeb50f4743a9a6c5d4/src/dinterpret.d#L3418
> is really ugly and complex, but you won't get rid of this inherent
> complexity. The e2ir code for AssingExp looks almost the same
> https://github.com/dlang/dmd/blob/7d00095301c4780b41addcfeb50f4743a9a6c5d4/src/e2ir.c#L2466.
>


IMO this is a different problem, that AssignExp is stupidly complex and needs to be split up.

>> You might imagine that it's easier to work with syntax trees than to
>> start from scratch but I'm certain that's not true. I'm pretty sure that
>> the simplest approach is to use the simplest possible
>> machine-independent bytecode that you can come up with. I had got to the
>> point of starting that, but I just couldn't face doing it in C++.
>
> All I'm saying is that interpreting the AST to generate bytecode is
> going to be as complex as interpreting the AST directly, but then you
> still a bytecode interpreter and later might still want a JIT.

The bytecode generator and bytecode interpreter can be debugged (and tested!) independently.  So the total amount of code will increase but the components themselves will be better isolated and easier to work with.

I don't think a possible future need for a JIT is a good reason to avoid an bytecode interpreter.  A large part of the work of adding a new (JIT) backend is pinning down the semantics, and adding a bytecode interpreter will certainly help to do that.

>
> Using dedicated value types during interpretation instead of recycling
> the AST for that will also make the transitions clearer and get rid of
> some of the lifetime complexities in the current code.
>

Meh, sure.  But this feels just as difficult as switching to a simple bytecode, without all the benefits.

On Wednesday, 18 May 2016 at 14:59:09 UTC, Daniel Murphy wrote:

>
> Meh, sure.  But this feels just as difficult as switching to a simple bytecode, without all the benefits.

Indeed.

I am currently designing an IR to feed into the CTFE Evaluator.
I am aware that this could potentially make it harder to get things merged since DMD already has the glue-layer.

However I do think that the benefits outweigh the drawbacks by far.
Especially when one looks at the possibility to eventually plug llvm or the gcc-jit in.

My CTFE needs are rather heavy weight. So I will go for a solution that can support this.
I believe the pressure on CTFE performance will increase as soon as the preformance increases. Since this will enable much more things.

I.E. running a query optimizer at compile-time.

On 19/05/2016 3:50 AM, Stefan Koch wrote:
> I am currently designing an IR to feed into the CTFE Evaluator.
> I am aware that this could potentially make it harder to get things
> merged since DMD already has the glue-layer.
>

It's always more difficult to justify merging more complexity.  But if you can present a working and superior solution the specific implementation is less important.  It is still important that it matches the existing style of the compiler, especially with respect to adding dependencies.

Also be aware that even with agreement on the eventual goal, it is still very slow to get big changes approved.  eg ddmd took more than twice as long as it should have.  This is why I suggested looking for incremental improvements, so you can overlap getting earlier things merged and developing later parts.  I would be on the lookout for things that can be justified on their own (untangling AssignExp :) ) and try to push those through first.

On 05/18/2016 07:50 PM, Stefan Koch wrote:
> Indeed.
> 
> I am currently designing an IR to feed into the CTFE Evaluator.
> I am aware that this could potentially make it harder to get things
> merged since DMD already has the glue-layer.

As a compat layer between different interpreters or as a compat layer between all backends? Adding another translation might not be acceptable, at least for real backends.

> However I do think that the benefits outweigh the drawbacks by far. Especially when one looks at the possibility to eventually plug llvm or the gcc-jit in.

Indeed, but it heavily increases the chance that your project lands on the unfinished D project pile.

> My CTFE needs are rather heavy weight. So I will go for a solution that
> can support this.
> I believe the pressure on CTFE performance will increase as soon as the
> preformance increases. Since this will enable much more things.
> I.E. running a query optimizer at compile-time.

That might be true, but scripting languages are still fast enough to be used everywhere. You won't need native CTFE performance for it to be an enabling technique.

-Martin

On 05/18/2016 04:59 PM, Daniel Murphy wrote:
> The bytecode generator and bytecode interpreter can be debugged (and tested!) independently.  So the total amount of code will increase but the components themselves will be better isolated and easier to work with.

It's simpler to debug an AST interpreter working with a stack of high-level values, than it is to debug a bytecode interpreter where lots of context has been converted to jumping goto code.

Just to illustrate my point, here are an AST and a BC interpreter for
very simplistic functional language I wrote recently. The later one
still missing the actual interpretation.
https://github.com/MartinNowak/CC1/commit/ed28b8966de86e7449f93ce4e4cf7aed3082180b
https://github.com/MartinNowak/CC1/commit/899e67cf7038050b86eed533c9165bd2ba06e609

There is nothing simpler about a BC interpreter. Instead you have to deal with converting control flow and computing addressing.

The debugging metaphor would be comparing a program that only uses pointer arithmetic against one that is memory safe, the former can randomly write everywhere from anywhere, the latter could use the wrong reference.

> I don't think a possible future need for a JIT is a good reason to avoid an bytecode interpreter.

It's a very good reason, b/c once you work on JIT, there is no benefit
for BC left, e.g. all the extra work for nothing.
That said, I doubt we'll need a JIT anytime soon.

> A large part of the work of adding a new (JIT) backend is pinning down the semantics, and adding a bytecode interpreter will certainly help to do that.

The semantic problem is already solved, in a file called interpret.d by sth. that's an AST interpreter, that just happens to use the wrong value structures and leaks memory. Converting that to BC will be quite difficult, cleaning it up and changing it to use a better stack and deterministic memory management is rather straightforward.

Last but not least, don't forget that we have the same situation since over 3 years already. It has always been similarly easy to write a better interpreter, it just never happened b/c the ambitions never matched the available resources.

-Martin