contiguous ranges

[Pasqui23 via Digitalmars-d]

On Wednesday, 18 February 2015 at 23:11:07 UTC, Vlad Levenfeld 
wrote:
> On Wednesday, 18 February 2015 at 16:10:30 UTC, Pasqui23 wrote:
>> No.The main strenght of the range api is its ability to
>> preserve range categories.The loss of range categories is a
>> *price* we pay for lazy  evalutation,categories wich can be
>> restored by .array in exchange for the usual price for dynamic
>> allocation.
>
> The argument naturally extends to ContiguousRanges:
> The loss of contiguity is the price paid for lazy evaluation 
> (note that retro is lazily evaluated), and the result of .array 
> is always contiguous.
>
The point is that you want to pay the less possible for the most 
gain:)
>> you are describing ContiguousRange as
>> a type implicitly convertable to T[]
>
> Not implicitly, but otherwise this may be a much nicer way to 
> define ContiguousRange than what I had proposed.
>
> I see a ContiguousRange as an underlying T[] with user-defined 
> operations and constraints, e.g. a Bitmap, or an AudioClip. 
> This would enable a generic function to operate on a custom 
> ranges without losing information by decaying the argument into 
> a T[]. For example, you could perform some generic search 
> operation on an AudioClip and return a slice while preserving 
> the AudioClip's sampling rate.
>

My proposal and yours are not mutually exclusive.
A range wich can be casted to T[] is automatically considered 
contiguous,but not all contiguous ranges are castable to T[](see 
for example BinaryHeap!(T[]) ).

As an aside,I prefer implicit cast as it ease the burden of both 
range authors and algorithms authors:
range authors have to just add
   T[]array;
   alias array this;
algorithms need to just accept T[](or R:T[] if it returns the 
range parameter)

>>> for an array r, is r.retro contiguous or not?
>>
>> I would say yes.In general,a good rule of thumb would be:this
>> range can be copied via memcpy?Then preserve contiguous-ness.
>
> The problem with this rule is illustrated with an example:
>
>   void copy (R1 src, R2 tgt)
>   out {
>     foreach (i; 0..min (src.length, tgt.length))
>       assert (tgt[i] == src[i]);
>   }
>   body {
>     memcpy (tgt.ptr, src.ptr, ElementType!R1.sizeof * min 
> (src.length, tgt.length));
>   }
>
>   auto s = [0,1,2,3,4,5];
>   auto r = [9,8,7,6,5,4].retro;
>   s.copy (r);
>
> Originally, r == [4,5,6,7,8,9].
> What's the value of r at the end of this program?
>
> If *r.ptr == 4, then we have
>   r == [0,5,6,7,8,9]
> and a segfault if we're lucky.
>
> If *r.ptr == 9, then we have
>   r == [5,4,3,2,1,0]
> and a failing postcondition.
>
> There is no scalable, generic way to satisfy the postcondition 
> and get our expected behavior, i.e.
>   r == [0,1,2,3,4,5]
>
The second interpretation(*r.ptr==9) is the correct 
interpretation.
You are raising an important point:the optimization I gave for 
copy is valid
only if r1 and r2 are of the same type(in fact i gave it the 
signature
   void copy(R)(R r1,R r2)if(isContiguousRange!R);//only one type 
of range
),as different types indicate different access implementation.In 
general the use of contiguous ranges force the user to check that 
both source and destination range are of the same type,and this 
can be a source of errors.
>> Optimized data transfers don't care at all that the
>> bytes are in order,only that the data are in the slice you gave
>> them.
>
> I have to disagree with this. While the transfer itself is free 
> to occur out-of-order, if the result is out of order, then the 
> program is most likely incorrect.
>

memcpy(src,dest,len) in general give undefined behavour if src or 
dest are of
different types or their size is different than len,the same is 
true of contiguous ranges(that's why toContiguous is an explicit 
cast returning void[])

>> My proposal allow simple extension to multiple dimension.
>> if  r is a n-dimensional range,then then the following must
>> hold true:
>>
>> void[]s=r.toContiguous;
>> foreach(i1;r)foreach(i2;i1)...foreach(in;inprev)
>>  assert(s.ptr<=&in<s.ptr+s.lenght);
>
> So, the catch here is illustrated with another example:
>
> Consider a 2D array in row-major order (where [i,j] is adjacent 
> to [i,j+1]). Here, slicing along the rows will yield a 
> ContiguousRange r[x..y, 0..$], but r[x..y, z..w] where z > 0 || 
> w < r.length will be non-contiguous at the column boundaries. 
> There's contiguity hiding in there, but it can't be leveraged.
>
> This could be solved by considering r[x..y, z..w] as a 
> RandomAccessRange of ContiguousRanges, which would imply that 
> r[a,b] is equivalent to r[a][b].
> On the other hand, it could be considered a RandomAccessRange 
> which yields ContiguousRanges under 1-dimensional slicing... 
> more verbose, but avoids the former interpretation's 
> implications.
>

The first implication(r[a,b]==r[a][b])is checked by controlling 
that r is a contiguous range,the second one(r[a,b]!=r[a][b]) is 
checked by checking if r[a] is itself contiguous

> But, like I said, extending range concepts to multiple 
> dimensions is tricky. I've been working on the problem on my 
> own for the last few months, and so far my solution has been to 
> define linear spaces which convert to ranges under certain 
> conditions.

This can be compatible with my proposal:both the 'linear space' 
and the single ranges are contiguous.

My proposal in general term aims to allow container to be copied 
by memcpy when possible and safe,and in general to call C funcion 
expecting untyped arrays(that's why toContiguous returns 
void[])like the splice api on linux.
Yours aims to safely call C funcion wich expects arrays of a 
given type.
Those are two use cases wich are more different than  what I gave 
it credit,and so our proposal are orthogonal,maybe even 
complementary,as I've already said.