CTFE Overhaul (Was: RFC: Thrift project proposal (draft))

[Don]

Robert Jacques wrote:
> On Sun, 27 Mar 2011 08:36:39 -0400, spir <denis.spir at gmail.com> wrote:
> 
>> On 03/26/2011 09:57 PM, Don wrote:
>>>>> The basic problem with the current implementation of CTFE is that it
>>>>> uses copy-on-write. This means that references (including dynamic
>>>>> arrays) don't work properly -- they just copy a snapshot of the thing
>>>>> they are referencing. This is bug 1330. It also means it burns up 
>>>>> memory
>>>>> like you wouldn't believe.
>>>>
>>>> Right.  IIUC there's also no way to free the memory from copies that 
>>>> are no
>>>> longer referenced.  I can see where this would leak memory like a 
>>>> sieve.
>>>
>>> That's not the big problem, actually. The issue is that x[7]=6;
>>> duplicates x, even if x has 10K elements.
>>> Now consider:
>>>    for(int i=0; i<x.length; ++i) x[i]=3;
>>>    // creates 100M new elements!! Should create none, or 10K at most.
>>
>> Hello Don,
>>
>> I don't understand your point. I have once implemented a toy dynamic 
>> language, using the common trick of boxed elements (à la Lisp). But I 
>> wanted to maintain value semantics as standard. A cheap way to do that 
>> is copy on write; it is actually cheap since simple, atomic, elements 
>> are never copied (since they cannot be changed on place), thus one 
>> just just needs to trace complex elements (array-lists & named tuples 
>> in my case):
>>     x := [1,2,3]    // create the array value, assign its ref
>>     y := x        // copy the ref, mark the value as shared
>>     x[1] := 0    // copy the value, reassign the ref, then change
>> But the new value is not shared, thus:
>>     x[1] := 1    // change only
>>
>> So that in your loop example, at most one array copy happens (iff it 
>> was shared). This is as far as I know what is commonly called 
>> copy-on-write. There is no need to copy the value over and over again 
>> on every change if it is not multiple-referenced, and noone does that, 
>> I guess.
>>
>> Side-Note: assignments of the form of "y := x" are really special, at 
>> least conceptually; but also practically when pointers or refs enter 
>> the game. I call them "symbol assignments" as the source is a symbol.
>>
>> Denis
> 
> Hi Denis,
> What Don is explaining is not how you should implement copy-on-write, 
> etc., but the actual implementation of arrays in DMD's CTFE system. 
Exactly.

> Right now, any access to an array in CTFE causes the entire array to be 
> duplicated, which is a major memory and performance issue, to say 
> nothing of the fact that D arrays are supposed to have reference, not 
> value semantics. I don't know how or why this behavior was ever 
> introduced, only that it is awesome that Don is fixing it.

I believe it was a quick hack to get things working. But it needs to 
disappear.