On Wednesday, 18 February 2015 at 08:34:49 UTC, Vlad Levenfeld
wrote:
I would argue that the only operations which preserve
contiguity are slicing, concatenating and appending; r.retro,
r.stride, r.map!f, etc should yield a RandomAccessRange.
I don't think this is a deal breaker, as conceptually its akin
to losing random-accessiblity under a filtering or grouping.
Input ranges are ubiquitous, RandomAccessRanges are more rare,
and ContiguousRanges are rarer still. It stands to reason that
contiguity is unlikely to be preserved under a given
transformation.
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.
This needs, however, a few more implementations that
motivate the concept.
The main use cases I had in mind was for optimized data
transfers and passing arguments to C APIs, and in this regard
the definition of ContiguousRange would need a bit of
refinement, maybe like so:
A ContiguousRange r of type R is a RandomAccessRange which
satisfies hasLValueElements and defines a member called ptr
which satisfies the following conditions:
1) *r.ptr == r[0] && r.ptr == &r[0]
2) for all 0 <= i < r.length, *(r.ptr + i) == r[i] && r.ptr
+ i == &r[i]
We could then have:
void load_data (R)(R r) {
static if (isContiguousRange!R)
auto ptr = r.ptr;
else {
auto cache = r.array;
auto ptr = cache.ptr;
}
some_C_lib_call (r.length, ptr);
}
and
void copy (R,S)(R r, S s) if (allSatisfy!(isContiguousRange,
R, S)) {
// type and length equality assertions
vectorized_blit (ElementType!R.sizeof, r.length r.ptr,
s.ptr);
}
---
You are on track when you say the main use case would be
optimized data transfer and comunication with C.However you are
describing ContiguousRange as
a type implicitly convertable to T[],wich I deem too
restrictive.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.
Instead a contiguous range is one wich satisfies the following
contract:
R r;
static assert(hasLValueElements!R && !isInfinite!R);
void[]s=r.toContiguous;
foreach(ref i;r)assert(s.ptr<=&i<s.ptr+s.lenght);
This allow,for example,to say:
void copy(R)(R r1,R r2)if(isContiguousRange!R){
void[]s1=r1.toContiguous,s2=r2.toContiguous;
memcpy(s1.ptr,s2.ptr,min(s1.lenght,s2.lenght);
}
It even give us a contiguous BinaryHeap,simply by
struct BinaryHeap(Store){
...
private Store store;
@propriety void[]toContiguous()if(isContiguousRange!Store){
return store.toContiguous;
}
}
and this BinaryHeap will be copied using only 1 call to memcpy.
Extending the concept to multiple dimensions is thorny, but
then, I've found that the same is true for everything but
RandomAccessRanges.
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);
On Tuesday, 17 February 2015 at 15:50:17 UTC, Andrei Alexandrescu
wrote:
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.
For funcion accepting ranges ia a bit more complicated:
If the function cares that r[i]==*(s+i) then it should accept
only T[]
else it should accept contiguous ranges.