COW vs. in-place.

[Reiner Pope]

Oskar Linde wrote:
> Dave wrote:
>>
>> What if selected functions in phobos were modified to take an optional 
>> parameter that specified COW or in-place? The default for each would 
>> be whatever they do now.
> 
> There are at least three ways an array algorithm can operate:
> - in-place
> - copying
> - CoW
To the caller, however, there are only two situations (in an ideal world 
with adequate const protection*):
  - modifies my copy (in-place)
  - doesn't modify my copy

As long as the function sticks to what it promises, then it should be 
free to implement it in the fastest/easiest way possible.

*I know that there is a difference at the moment: with CoW, you have to 
be careful about modifying the returned value, because it might also be 
your original, in which case you would be modifying both. However, this 
is where const protection helps, especially the runtime flag included in 
rocheck.

> It would make more sense to have separate in-place and copying 
> functions, and add a possible runtime CoW-flag to the copying function.
> 
When would ever want the copying function instead of the CoW function? 
At most times, the overhead from keeping track of CoW is generally 
minimal, but in the situations where CoW requires no copying, it gets a 
huge advantage. The only situation where choosing copying makes sense is 
if you have determined that the CoW is too much. In that case, however, 
you probably wouldn't want to send the flag at runtime, but change it at 
compile time, I would say.

> I don't think a runtime flag for CoW vs in-place does make much sense 
> when the compile time semantics are different.
> 
> An efficient implementation of a copying algorithm would also often be 
> quite different from an in-place version, speaking for separate functions.
There's a simple solution to this:

// If the implementations for in-place and copying are substantially 
different, then wrap them like this
rocheck T[] sort(rocheck T[] array)
{
     if (array.isMutable())
         return inPlaceSort(array.ensureWritable());
     else
         return copyingSort(array);
}

// If there is no real difference, put them together in the one function
rocheck dchar[] toupper(rocheck dchar[] array)
{
     // Do some stuff and call ensureWritable() when required, which 
manages whether copying is necessary behind the scenes
}

The point behind the runtime flag is that the required checking can be 
made to be low overhead, with O(1) cost, whereas unnecessary copying has 
O(n) cost.

Cheers,

Reiner