Change representation of dynamic arrays?

[Bill Baxter]

Walter Bright wrote:
> Janice Caron wrote:
>> On 10/20/07, Daniel Keep <daniel.keep.lists at gmail.com> wrote:
>>> but what
>>> about slicing code?  I know that I use a lot of [lower..$-something]
>>
>> While this may be optimised for simple arrays, it poses much more of a
>> problem for classes and structs which override opIndex() and
>> opSlice(). The problem is that indeces in those functions are always
>> specified as being relative to the beginning - there is no way to
>> specify that an index should be considered relative to the end - so
>> when you do a[0..$-1] in such a struct, the compiler has to convert
>> $-1 into (a.length()-1). Then, inside opSlice(), to turn it back to a
>> pointer you'd have to do (start+index).

'$' doesn't work in user defined types.  So the rest of your comment is 
only relevant to some hypothetical future D where $ is allowed for user 
types.  Andrei strongly favored making it mean .length everywhere if I 
recall correctly, so if anything happens with it that's probably what it 
will be, and your comment will be relevant.

>> I know adds and subtracts are not that expensive, but given that this
>> change is being talked about /because/ we want to get rid of a
>> subtract, it is worth thinking about this.
>>
>> Presumably this will all sort itself out if we get iterators? When
>> that happens, slice expressions could be rewritten by the compiler as
>> iterator operations, which in turn would call opDereference() or
>> opRange(), taking iterator parameters. Is that likely to happen, or
>> will user-defined types always take the slow route?
> 
> If you have a user-defined struct, you get to decide how it is 
> implemented. How the built-in arrays are done under the hood shouldn't 
> be relevant.

It becomes relevant if $ becomes a synonym for .length as was previously 
proposed.  In that case you don't get to decide how $ is implemented. 
It has to compute the length, even if that's O(N) and not really needed 
for computing the $-1'th node.

Or if all you're trying to do is make a light wrapper around a built-in 
array (to, say, add an extra data member to it), then it means that your 
opIndex could be significantly less efficient than the built-in one.

--bb