www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - newCTFE Status August 2017

reply Stefan Koch <uplink.coder googlemail.com> writes:
Hi Guys,

At the end of July newCTFE became capable of executing the 
bf-ctfe[1] code and pass the tests.
At 5 times the speed. While using 40% the memory.
(It should be noted that the code generated by bf-ctfe is 
optimized to put as little pressure on ctfe as possible and tries 
to avoid the pathological paths which is why the speed 
improvement is not as high as some other code I showed before)

[1] https://github.com/UplinkCoder/bf-ctfe

I've been hard at work to support complex structs.
which means things like trees or lists which have pointers slices 
and stuff in them :)
as well as multi-dimensional arrays and/or slices.

Sadly I temporarily broke the support for string-members in 
structs.
This Month I intend to fix it again :)
As well as working on supporting bounds-checked pointers.
(meaning pointers created from array literals will still carry 
the array-bounds with them)
The easiest way to do this is unifying the way pointers and 
slices are handled.

As all of these changes affect the ABI they are quite tricky to 
actually execute even if they are not that hard in principle.

If all things go smoothly I will implement union support as well.
(nice safe-unions with a hidden type-field that makes sure you 
can only deref where you previously assigned to)

So stay tuned for updates.

Cheers,
Stefan
Aug 01 2017
next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 Sadly I temporarily broke the support for string-members in 
 structs.


Fixed now.

The issue was ABI related.
we used to store pointers to sliceDescriptors, but I changed that 
to store the sliceDescriptors directly. Because otherwise slicing 
of initializes of type string does not work.

I am happy I thought about this briefly two months ago, and to 
have had the foresight to put in stubs for that, otherwise this 
would have gotten much messier.

Another issue I want to deal with are void initalized struct 
members.
In a few instances we can statically determine that they are 
always initialized.
i.e. when there are no branches.
In most instances this is not the case though .... this requires 
us to store a bitfield next to the this pointer of the struct 
which indicated if a paricular member has been initialized or not.
Luckily we only need to do that for `= void` members. So I think 
we can get away with 32bit.

I should mention that newCTFE does currently not support structs 
with more then 96 member-variables anyway.
So far I have not come close to hitting that limit.

Talking about limits, this are the current limits I am aware of.
you can only use 16000 local variables per function.
you can only allocate around 265 Megabyte of heap-space per 
evaluation.
Only functions with up to 64 parameters are supported.
you can only have up to 65535 instructions per function (roughly 
16000 lines of code)
The call-stack can only be 2000 calls deep. (This is an artifical 
limtation that the old interpreter imposed because it would die 
and use insane amounts of memery wehen it went over that limit. 
(With newCTFE you can safely bump that limit up to 5000 levels of 
recursion .... but in order to pass all unittests we need to keep 
the old limit))
You can only have about 12000 different struct types per 
evaluation.
And only about 16000 assertions.
Similarly there may only be 7000 array-literals per function.

I don't see anyone reaching those limits soon.

Cheers,
Stefan
Aug 01 2017
prev sibling next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [ ... ]


After a surprisingly small amount of work we are now supporting 
pointers to array-items.
It should be quite doable to add bounds-checked pointer with 
minimal amount of work.
(Note this is only for 1D arrays/Slices ... Mulidimensional 
Arrays/Slices still have issues preventing that)

The following video shows what needed to happen:
https://www.youtube.com/watch?v=QHwIEd8E5mE

example code that now works:

int* getAPtr(int[] arr)
{
   // assert(a.length > 1);
   return &arr[1];
}

static assert(getAPtr([1, 2, 3]) == 2);
Aug 05 2017
prev sibling next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [ ... ]


The following code does now compile with newCTFE,
and it's a little faster then the old interpreter.
Not much though since that is not a pathological case.

     pure nothrow  nogc  safe uint[256][8] genTables32(uint 
polynomial)
     {
         uint[256][8] res = 0u;
         {
             int __key479 = 0;
             int __limit480 = 256;
             for (; __key479 < __limit480; __key479 += 1)
             {
                 int i = __key479;
                 uint crc = cast(uint)i;
                 {
                     int __key481 = 0;
                     int __limit482 = 8;
                     for (; __key481 < __limit482; __key481 += 1)
                     {
                         int _ = __key481;
                         crc = crc >> 1 ^ cast(uint)-cast(int)(crc 
& 1u) & polynomial;
                     }
                 }
                 res[0][i] = crc;
             }
         }
         {
             int __key483 = 0;
             int __limit484 = 256;
             for (; __key483 < __limit484; __key483 += 1)
             {
                 int i = __key483;
                 res[1][i] = res[0][i] >> 8 ^ res[0][(res[0][i] & 
255u)];
                 res[2][i] = res[1][i] >> 8 ^ res[0][(res[1][i] & 
255u)];
                 res[3][i] = res[2][i] >> 8 ^ res[0][(res[2][i] & 
255u)];
                 res[4][i] = res[3][i] >> 8 ^ res[0][(res[3][i] & 
255u)];
                 res[5][i] = res[4][i] >> 8 ^ res[0][(res[4][i] & 
255u)];
                 res[6][i] = res[5][i] >> 8 ^ res[0][(res[5][i] & 
255u)];
                 res[7][i] = res[6][i] >> 8 ^ res[0][(res[6][i] & 
255u)];
             }
         }
         return res;
     }


     static immutable tables = genTables32(0xEDB88320);
     static assert(tables[0][0] == 0x00000000 && tables[0][$ - 1] 
== 0x2d02ef8d && tables[7][$ - 1] == 0x264b06e6);
Aug 05 2017
prev sibling next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [ ... ]


I am quite surprised.
newCTFE comes far enough now, that it tries to interpret it's own 
interpreter (which is CTFEable)

Of course it fails in doing so since we do not yet handle newing 
arrays or associative arrays.

Though as soon as we do support newing arrays and remove the need 
for associative arrays  from the interpret_ function, we should 
indeed be able to self-host (so to speak.)
Aug 05 2017
prev sibling next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [ ... ]


After a bit of fixing and the unfortunate addition of 4 
blacklisted functions, phobos complies and passes the unittests 
under newCTFE. (Which implies that druntime compiles and works as 
well)

A few ABI issues were fixed.
and we are now able to execute lz4-ctfe[0] test[1] approximately 
10-15x faster.
Note: that 35% of the time is actually spend to convert the 
output from the newCTFE-representation to dmd ast nodes. (This is 
because the conversion is currently a recursive function which 
does not scale well with over 9000 (Yes it's over 9000) nodes to 
produce for an array.)

Hopefully the next preview release will be ready soon, then you 
can try it out yourself.

Cheers,
Stefan



[0] https://github.com/UplinkCoder/lz4-ctfe
[1] 
https://github.com/UplinkCoder/lz4-ctfe/blob/master/source/test.d
Aug 09 2017
parent reply 12345swordy <alexanderheistermann gmail.com> writes:
On Wednesday, 9 August 2017 at 15:47:09 UTC, Stefan Koch wrote:

 On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [...]


 After a bit of fixing and the unfortunate addition of 4 
 blacklisted functions, phobos complies and passes the unittests 
 under newCTFE. (Which implies that druntime compiles and works 
 as well)

 [...]


You mention something about the CTFE extensions, can you give us 
an example/link of this extension in action?
Aug 09 2017
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Wednesday, 9 August 2017 at 18:27:37 UTC, 12345swordy wrote:

 On Wednesday, 9 August 2017 at 15:47:09 UTC, Stefan Koch wrote:

 On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [...]


 After a bit of fixing and the unfortunate addition of 4 
 blacklisted functions, phobos complies and passes the 
 unittests under newCTFE. (Which implies that druntime compiles 
 and works as well)

 [...]


 You mention something about the CTFE extensions, can you give 
 us an example/link of this extension in action?


Extensions ?
I am not sure what you are referring to.

the mission-statement is to provide a faster, less memory 
trashing version of the CTFE feature.

newCTFE also aims to be extensible but using this for allowing 
more functionality then CTFE currently allows is not part of the 
current mission.

Cheers,
Stefan
Aug 09 2017
parent 12345swordy <alexanderheistermann gmail.com> writes:
On Wednesday, 9 August 2017 at 20:58:34 UTC, Stefan Koch wrote:

 On Wednesday, 9 August 2017 at 18:27:37 UTC, 12345swordy wrote:

 On Wednesday, 9 August 2017 at 15:47:09 UTC, Stefan Koch wrote:

 [...]


 You mention something about the CTFE extensions, can you give 
 us an example/link of this extension in action?


 Extensions ?
 I am not sure what you are referring to.

 the mission-statement is to provide a faster, less memory 
 trashing version of the CTFE feature.

 newCTFE also aims to be extensible but using this for allowing 
 more functionality then CTFE currently allows is not part of 
 the current mission.

 Cheers,
 Stefan


(I wish I can bold)

By extensions I mean examples of CTFE being extensible. A 
theoretical answer would be sufficient.
Aug 09 2017
prev sibling next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [ ... ]


Hey guys,

I just finished &&.

The following test works now:

int[2] aaa2(bool b1, bool b2, bool b3, bool b4)
{
   int x = 0;
   if (b1 && ++x && b2 && x++ && b3 && (b4 || x++))
   {
     return [x, 1];
   }
   else
   {
     return [x, 0];
   }
}

static assert(aaa2(0, 0, 0, 0) == [0, 0]);
static assert(aaa2(0, 1, 0, 0) == [0, 0]);
static assert(aaa2(0, 0, 1, 0) == [0, 0]);
static assert(aaa2(1, 0, 1, 0) == [1, 0]);
static assert(aaa2(1, 1, 1, 0) == [3, 1]);
static assert(aaa2(1, 1, 1, 1) == [2, 1]);

After a year of development we are finally able to keep all the 
side effects :)
Whoohoo!

Cheerful,

Stefan
Aug 11 2017
parent reply Dominikus Dittes Scherkl <dominikus scherkl.de> writes:
On Friday, 11 August 2017 at 09:27:47 UTC, Stefan Koch wrote:

 On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [ ... ]


 Hey guys,

 I just finished &&.


Hooray!
So what's still missing? Or is this now complete enough to 
release?
Aug 11 2017
parent Stefan Koch <uplink.coder googlemail.com> writes:
On Friday, 11 August 2017 at 20:13:04 UTC, Dominikus Dittes 
Scherkl wrote:

 On Friday, 11 August 2017 at 09:27:47 UTC, Stefan Koch wrote:

 On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [ ... ]


 Hey guys,

 I just finished &&.


 Hooray!
 So what's still missing? Or is this now complete enough to 
 release?


it's almost at the point where I am okay with making a 
newCTFE-1.0 release.
it will correctly coexist with the old engine such that the 
things it currently cannot do are still taken care of by the old 
engine.

Things left to do :

- Deal with more void initialization correctly.
- Unions
- Classes
- Exceptions
- some complex types such as int[][3][]
- string-decoding foreach. like: (foreach(dchar utf32; 
uft8someString))
- associative arrays (though we may change druntime to a 
ctfe-able version, which would also allow having aa-literals 
computed at ctfe usable at runtime)

There are a few corner-cases in the supported feature set where 
it will fallback to the old interpreter but fixing those is a 
matter of hand-work not head-work (as they _should_ not impact 
the design):)
Aug 11 2017
prev sibling next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [ ... ]


Hi Guys,

I've fixed a few ABI bugs and as a result my alternative to 
std.bitmanip.bitfields complies now.
I've also made an intrinsic for the concat operation.
Which causes ~= to be 6-10x faster when it's heavily used.

The huge space requirements for heavy ~= are not yet solved 
though.
To pass the unittests regardless which does ~= 4096 times on a 
moderately long string;
I've had to bump the ctfe heapSpace.
Therefore newCTFE will allocate 1GB at startup which causes it to 
die on 32bit targets.
This issue will be worked when _most_ of the ABI is finalized 
(i.e. when classes and unions are in)
Aug 13 2017
prev sibling next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [ ... ]


Hi there,

I've just adjusted the memory allocation behavior.
newCTFE will now start-out allocating 32M of memory at startup.
and increase the allocated space in 8x steps if it hits the limit 
while executing concat code.
In which case of course it needs to copy 32meg in the worst-case.
Therefore you will feel a noticeable slowdown if are using ~= and 
happen to just go slightly over the limit.
But if you overstep the limit by much the increased speed of 
concat will compensate for the hit.

The new behavior enables us to compile on 32bit targets again.
Aug 13 2017
prev sibling next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [ ... ]


Guys,

newCTFE is green on 64 and 32bit!

I've finally fixed || and &&.
For good!

whooooohooooo ;)

Release is coming closer!
Aug 14 2017
next sibling parent jmh530 <john.michael.hall gmail.com> writes:
On Monday, 14 August 2017 at 11:25:14 UTC, Stefan Koch wrote:

 Guys,

 newCTFE is green on 64 and 32bit!

 I've finally fixed || and &&.
 For good!

 whooooohooooo ;)

 Release is coming closer!


Cool.
Aug 14 2017
prev sibling next sibling parent Biotronic <simen.kjaras gmail.com> writes:
On Monday, 14 August 2017 at 11:25:14 UTC, Stefan Koch wrote:

 On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [ ... ]


 Guys,

 newCTFE is green on 64 and 32bit!

 I've finally fixed || and &&.
 For good!

 whooooohooooo ;)

 Release is coming closer!


There are times I wish the D forum had upvote buttons. This is 
one of those times.

--
   Biotronic
Aug 14 2017
prev sibling next sibling parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Monday, 14 August 2017 at 11:25:14 UTC, Stefan Koch wrote:

 On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [ ... ]


 Guys,

 newCTFE is green on 64 and 32bit!

 I've finally fixed || and &&.
 For good!

 whooooohooooo ;)

 Release is coming closer!


Wow, I can't wait!
Aug 14 2017
parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Mon, Aug 14, 2017 at 01:54:26PM +0000, Per Nordlöw via Digitalmars-d wrote:

 On Monday, 14 August 2017 at 11:25:14 UTC, Stefan Koch wrote:

 On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [ ... ]


 
 Guys,
 
 newCTFE is green on 64 and 32bit!
 
 I've finally fixed || and &&.
 For good!
 
 whooooohooooo ;)
 
 Release is coming closer!


 
 Wow, I can't wait!


+1, me too!


T

-- 
Famous last words: I *think* this will work...
Aug 14 2017
prev sibling parent Ryion <ryion 4210x.com> writes:
On Monday, 14 August 2017 at 11:25:14 UTC, Stefan Koch wrote:

 Release is coming closer!


Nice, keep up the good work.
Aug 24 2017
prev sibling next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [ ... ]


Hi Guys,

many stabilty fixed have happened and as a result the new 
preview-build is green on the auto-tester and project tester.

However it might still produce !!invalid code!! if a certain 
combination of features triggers a case I have overlooked! -- you 
have been warned :) (then again .... that is the case with every 
compiler ..... (except maybe CompCert ?))

the preview builds are available here:

https://nightlies.dlang.org/dmd-newCTFE/
Aug 31 2017
prev sibling parent reply Tourist <gravatar gravatar.com> writes:
On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 Hi Guys,

 At the end of July newCTFE became capable of executing the 
 bf-ctfe[1] code and pass the tests.
 At 5 times the speed. While using 40% the memory.
 (It should be noted that the code generated by bf-ctfe is 
 optimized to put as little pressure on ctfe as possible and 
 tries to avoid the pathological paths which is why the speed 
 improvement is not as high as some other code I showed before)

 [...]


What about October 2017? I miss your frequent updates on newCTFE.
Oct 11 2017
next sibling parent Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 11 October 2017 at 07:39:47 UTC, Tourist wrote:

 What about October 2017? I miss your frequent updates on 
 newCTFE.


Me too.
Oct 11 2017
prev sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Wednesday, 11 October 2017 at 07:39:47 UTC, Tourist wrote:

 On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 Hi Guys,

 At the end of July newCTFE became capable of executing the 
 bf-ctfe[1] code and pass the tests.
 At 5 times the speed. While using 40% the memory.
 (It should be noted that the code generated by bf-ctfe is 
 optimized to put as little pressure on ctfe as possible and 
 tries to avoid the pathological paths which is why the speed 
 improvement is not as high as some other code I showed before)

 [...]


 What about October 2017? I miss your frequent updates on 
 newCTFE.


Sorry about that, I am quite with my job at sociomantic.

As soon as I find time I'll post a detailed report about my 
latest work and the directions I am planning to explore next.
Oct 11 2017
parent Stefan Koch <uplink.coder googlemail.com> writes:
On Wednesday, 11 October 2017 at 10:45:32 UTC, Stefan Koch wrote:

 On Wednesday, 11 October 2017 at 07:39:47 UTC, Tourist wrote:

 On Tuesday, 1 August 2017 at 21:27:32 UTC, Stefan Koch wrote:

 [...]


 What about October 2017? I miss your frequent updates on 
 newCTFE.


 Sorry about that, I am quite with my job at sociomantic.

 As soon as I find time I'll post a detailed report about my 
 latest work and the directions I am planning to explore next.


+ busy (insert where appropriate)
Oct 11 2017