Jump to page: 1 2 3
Thread overview
August 01
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
August 02
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

August 05
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);
August 05
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);

August 06
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.)

August 09
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
August 09
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?
August 09
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
August 09
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.
August 11
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
« First   ‹ Prev
1 2 3