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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
prev 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