www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - contiguous ranges

reply "Vlad Levenfeld" <vlevenfeld gmail.com> writes:
Since C++17, there's a new iterator category: the contiguous 
iterator. Check it out: http://en.cppreference.com/w/cpp/iterator

So, by extension, I think a ContiguousRange would be any 
RandomAccessRange which has a member called ptr which supports a 
dereferencing operator * that yields an ElementType!R. This 
notion is useful for functions which might otherwise perform an 
element-by-element transfer to an OutputRange via put, instead 
perform an optimized batch transfer directly to a ContiguousRange 
via ptr. (Not that Contiguous implies Output; this example 
assumes the ContigiousRange has enough length to accomodate the 
transfer or otherwise has mutable length, e.g. builtin arrays.)

I've been using the idea implicitly in my code with static if (is 
(typeof(*R.init.ptr) == ElementType!R)), but seeing that table 
made me realize it could be formally abstracted out to a range 
concept.
Feb 15 2015
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Vlad Levenfeld:


 a ContiguousRange would be any RandomAccessRange which has a 
 member called ptr which supports a dereferencing operator * 
 that yields an ElementType!R. This notion is useful for 
 functions which might otherwise perform an element-by-element 
 transfer to an OutputRange via put, instead perform an 
 optimized batch transfer directly to a ContiguousRange via ptr.


Increasing the number of basic ranges will lead to a little more 
complexity, but this seems a nice idea.

Bye,
bearophile
Feb 16 2015
prev sibling next sibling parent reply FG <home fgda.pl> writes:
On 2015-02-16 at 07:06, Vlad Levenfeld wrote:

 *ContigiousRange* has enough length [...]


LOL. The clearly masochistic C++ committee needs to be applauded for
introducing what may become the biggest source of typos.  :)

Adjoining would be easier on the non-native English speakers than contiguous.
Not to mention that contiguous sounds almost like contagious. Let's better not
catch that infection. ;)
Feb 16 2015
next sibling parent reply "rupert" <rupet.wallberg gmail.com> writes:
On Monday, 16 February 2015 at 11:57:36 UTC, FG wrote:

 On 2015-02-16 at 07:06, Vlad Levenfeld wrote:

 *ContigiousRange* has enough length [...]


 LOL. The clearly masochistic C++ committee needs to be 
 applauded for introducing what may become the biggest source of 
 typos.  :)

 Adjoining would be easier on the non-native English speakers 
 than contiguous. Not to mention that contiguous sounds almost 
 like contagious. Let's better not catch that infection. ;)


If you think you could do a better job than the C++ committee you 
should submit a proposal.

https://isocpp.org/std/submit-a-proposal


Cheers,
uri.
Feb 16 2015
parent ketmar <ketmar ketmar.no-ip.org> writes:
On Mon, 16 Feb 2015 12:16:50 +0000, rupert wrote:


 If you think you could do a better job than the C++ committee you should
 submit a proposal.
=20
 https://isocpp.org/std/submit-a-proposal


why he *should* to that? he *may* submit it. when someone sees people=20
doing shit, he is not obliged to immediately go and fix that shit.=
Feb 16 2015
prev sibling parent "Vlad Levenfeld" <vlevenfeld gmail.com> writes:
On Monday, 16 February 2015 at 11:57:36 UTC, FG wrote:

 On 2015-02-16 at 07:06, Vlad Levenfeld wrote:

 *ContigiousRange* has enough length [...]


 LOL. The clearly masochistic C++ committee needs to be 
 applauded for introducing what may become the biggest source of 
 typos.  :)

 Adjoining would be easier on the non-native English speakers 
 than contiguous. Not to mention that contiguous sounds almost 
 like contagious. Let's better not catch that infection. ;)


Well, if you're that worried about the proximity of the 'i' and 
'u' keys, you might be happier with AddressableRange, though 
you'll want to watch out for those tricky double consonants :)

I think I may do my senior thesis on range/iterator categories, 
so I make the post more out of curiosity than as a proposal for 
an addition to Phobos (though I wouldn't mind seeing it 
formalized, the use cases are certainly there).
Feb 16 2015
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/15/15 10:06 PM, Vlad Levenfeld wrote:

 Since C++17, there's a new iterator category: the contiguous iterator.
 Check it out: http://en.cppreference.com/w/cpp/iterator

 So, by extension, I think a ContiguousRange would be any
 RandomAccessRange which has a member called ptr which supports a
 dereferencing operator * that yields an ElementType!R. This notion is
 useful for functions which might otherwise perform an element-by-element
 transfer to an OutputRange via put, instead perform an optimized batch
 transfer directly to a ContiguousRange via ptr. (Not that Contiguous
 implies Output; this example assumes the ContigiousRange has enough
 length to accomodate the transfer or otherwise has mutable length, e.g.
 builtin arrays.)

 I've been using the idea implicitly in my code with static if (is
 (typeof(*R.init.ptr) == ElementType!R)), but seeing that table made me
 realize it could be formally abstracted out to a range concept.


Interesting. This needs, however, a few more implementations that 
motivate the concept. Also, I see potential for misuse already: for an 
array r, is r.retro contiguous or not? One might argue it is because its 
layout is still contiguous; however, in that case people shouldn't 
assume that .ptr necessarily points to the first element.

Contiguous ranges would help two useful primitives: r1.before(r2) yields 
the portion of r1 before r2 (assumes r2 overlaps r1), and r1.after(r2) 
yields the portion of r1 after r2 (same assumption). Basically 
r1.before(r2) is r1[0 .. r2.ptr - r1.ptr] and r1.after(r2) is r1[r2.ptr 
+ r2.length - r1.ptr .. $].


Andrei
Feb 17 2015
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:


 for an array r, is r.retro contiguous or not?


Is the most useful contiguous range forward? So can you name it 
ForwardContiguousRange?

Bye,
bearophile
Feb 17 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/17/15 8:13 AM, bearophile wrote:

 Andrei Alexandrescu:


 for an array r, is r.retro contiguous or not?


 Is the most useful contiguous range forward? So can you name it
 ForwardContiguousRange?


Ehm. Attractiveness of concepts increases with the number of cases 
(structures + algorithms) they cover successfully and decreases with 
"shrapnel" - the additional concepts/exceptions they need to define. -- 
Andrei
Feb 17 2015
prev sibling parent reply "Vlad Levenfeld" <vlevenfeld gmail.com> writes:
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 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.


  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);
   }

  ---

Extending the concept to multiple dimensions is thorny, but then, 
I've found that the same is true for everything but 
RandomAccessRanges.
Feb 18 2015
parent reply "Pasqui23" <ppp23 example.com> writes:
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.
Feb 18 2015
parent reply "Vlad Levenfeld" <vlevenfeld gmail.com> writes:
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.


 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.


 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]


 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.


 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.

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.
Feb 18 2015
parent "Pasqui23" <ppp23 example.com> writes:
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.
Feb 18 2015
prev sibling next sibling parent reply "Guillaume Chatelet" <chatelet.guillaume gmail.com> writes:
On Monday, 16 February 2015 at 06:06:19 UTC, Vlad Levenfeld wrote:

 Since C++17, there's a new iterator category: the contiguous 
 iterator. Check it out: 
 http://en.cppreference.com/w/cpp/iterator

 So, by extension, I think a ContiguousRange would be any 
 RandomAccessRange which has a member called ptr which supports 
 a dereferencing operator * that yields an ElementType!R. This 
 notion is useful for functions which might otherwise perform an 
 element-by-element transfer to an OutputRange via put, instead 
 perform an optimized batch transfer directly to a 
 ContiguousRange via ptr. (Not that Contiguous implies Output; 
 this example assumes the ContigiousRange has enough length to 
 accomodate the transfer or otherwise has mutable length, e.g. 
 builtin arrays.)

 I've been using the idea implicitly in my code with static if 
 (is (typeof(*R.init.ptr) == ElementType!R)), but seeing that 
 table made me realize it could be formally abstracted out to a 
 range concept.


 From this discussion I understand you mainly want to be able to 
BitBlt ranges
http://en.wikipedia.org/wiki/Bit_blit

BitBlt covers multi dimensional arrays as well (2D textures) and 
might convey the semantic you want better than Contiguous (too 
fine grained ?).

Also the blitting term is already used in D (post-blit 
constructor).
Feb 19 2015
parent reply "Pasqui23" <ppp23 example.com> writes:
On Thursday, 19 February 2015 at 11:20:13 UTC, Guillaume Chatelet 
wrote:


 From this discussion I understand you mainly want to be able to 
 BitBlt ranges
 http://en.wikipedia.org/wiki/Bit_blit

 BitBlt covers multi dimensional arrays as well (2D textures) 
 and might convey the semantic you want better than Contiguous 
 (too fine grained ?).


Effectively bit blit range is a better name than contiguous 
range,but as I have said this and range castable to T[] are not 
mutually exclusive concepts.

 Also the blitting term is already used in D (post-blit 
 constructor).


Unfotunately the post-blit constructor covers only the copy of 
structures(like smart pointers)and is inadequate for ranges(it 
would be surprising if
auto cp=r;
would copy the entire range and not the position in the container 
only).
Feb 19 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/19/15 11:29 AM, Pasqui23 wrote:

 On Thursday, 19 February 2015 at 11:20:13 UTC, Guillaume Chatelet wrote:


 From this discussion I understand you mainly want to be able to BitBlt
 ranges
 http://en.wikipedia.org/wiki/Bit_blit

 BitBlt covers multi dimensional arrays as well (2D textures) and might
 convey the semantic you want better than Contiguous (too fine grained ?).


 Effectively bit blit range is a better name than contiguous range,but as
 I have said this and range castable to T[] are not mutually exclusive
 concepts.


I don't see a need for contiguous ranges if the only embodiment is T[]. 
-- Andrei
Feb 19 2015
parent reply "Pasqui23" <ppp23 example.com> writes:
On Thursday, 19 February 2015 at 19:32:26 UTC, Andrei 
Alexandrescu wrote:

 I don't see a need for contiguous ranges if the only embodiment 
 is T[]. -- Andrei


Yeah,but it could be useful to access where  the range is located
Feb 19 2015
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 19 February 2015 at 23:11:16 UTC, Pasqui23 wrote:

 On Thursday, 19 February 2015 at 19:32:26 UTC, Andrei 
 Alexandrescu wrote:

 I don't see a need for contiguous ranges if the only 
 embodiment is T[]. -- Andrei


 Yeah,but it could be useful to access where  the range is 
 located


So that you can assess whether "a pointer" (iterator) is in a 
range on or not at O(1)? Seems there is a different between:

1. uniform spacing
2. with strides or not
3. dense packing (plain array)
Feb 20 2015
prev sibling next sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Monday, 16 February 2015 at 06:06:19 UTC, Vlad Levenfeld wrote:

 Since C++17, there's a new iterator category: the contiguous 
 iterator. Check it out: 
 http://en.cppreference.com/w/cpp/iterator

 So, by extension, I think a ContiguousRange would be any 
 RandomAccessRange which has a member called ptr which supports 
 a dereferencing operator * that yields an ElementType!R. This 
 notion is useful for functions which might otherwise perform an 
 element-by-element transfer to an OutputRange via put, instead 
 perform an optimized batch transfer directly to a 
 ContiguousRange via ptr. (Not that Contiguous implies Output; 
 this example assumes the ContigiousRange has enough length to 
 accomodate the transfer or otherwise has mutable length, e.g. 
 builtin arrays.)

 I've been using the idea implicitly in my code with static if 
 (is (typeof(*R.init.ptr) == ElementType!R)), but seeing that 
 table made me realize it could be formally abstracted out to a 
 range concept.


Isn't it what a slice is already ?
Feb 19 2015
parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Friday, 20 February 2015 at 01:25:34 UTC, deadalnix wrote:

 On Monday, 16 February 2015 at 06:06:19 UTC, Vlad Levenfeld 
 wrote:

 Since C++17, there's a new iterator category: the contiguous 
 iterator. Check it out: 
 http://en.cppreference.com/w/cpp/iterator

 So, by extension, I think a ContiguousRange would be any 
 RandomAccessRange which has a member called ptr which supports 
 a dereferencing operator * that yields an ElementType!R. This 
 notion is useful for functions which might otherwise perform 
 an element-by-element transfer to an OutputRange via put, 
 instead perform an optimized batch transfer directly to a 
 ContiguousRange via ptr. (Not that Contiguous implies Output; 
 this example assumes the ContigiousRange has enough length to 
 accomodate the transfer or otherwise has mutable length, e.g. 
 builtin arrays.)

 I've been using the idea implicitly in my code with static if 
 (is (typeof(*R.init.ptr) == ElementType!R)), but seeing that 
 table made me realize it could be formally abstracted out to a 
 range concept.


 Isn't it what a slice is already ?


Yeah...

Maybe I'm missing something, but I don't see anything here that 
isn't already covered by built-in slices, opSlice, opSliceAssign 
and put.
Feb 20 2015
parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Friday, 20 February 2015 at 08:22:38 UTC, John Colvin wrote:

 Maybe I'm missing something, but I don't see anything here that 
 isn't already covered by built-in slices, opSlice, 
 opSliceAssign and put.


That's the wrong direction. What you want is a means to query a 
unknown container for it's properties so that you can bypass 
builtin operators:

1. by comparing addresses of elements and be able to assume 
strict order as you progress

2. by assessing compile time uniformity in distribution so that 
you can iterate using SIMD.
Feb 20 2015
parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Friday, 20 February 2015 at 08:45:23 UTC, Ola Fosheim Grøstad 
wrote:

 On Friday, 20 February 2015 at 08:22:38 UTC, John Colvin wrote:

 Maybe I'm missing something, but I don't see anything here 
 that isn't already covered by built-in slices, opSlice, 
 opSliceAssign and put.


 That's the wrong direction. What you want is a means to query a 
 unknown container for it's properties so that you can bypass 
 builtin operators:

 1. by comparing addresses of elements and be able to assume 
 strict order as you progress

 2. by assessing compile time uniformity in distribution so that 
 you can iterate using SIMD.


Eh? Knowing the ordering and that the distribution is uniform* 
isn't going to be enough to iterate by SIMD. You need to know the 
complete iteration scheme.

*what do you even mean by that? Jargon is only useful when it's 
used with precision.
Feb 20 2015
next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Friday, 20 February 2015 at 09:44:36 UTC, John Colvin wrote:

 Eh? Knowing the ordering and that the distribution is uniform* 
 isn't going to be enough to iterate by SIMD. You need to know 
 the complete iteration scheme.


That's the point of a "concept". The concept provides constraints 
that in turn provides certain guarantees. E.g.

1. that the addresses of elements provided by the iterator (or 
range) are in order
2. that they are evenly spaced
3. a means to obtain the stride (distance between elements)

So if you obtain the address of a start element and and end 
element you can iterate using SIMD.


 *what do you even mean by that? Jargon is only useful when it's 
 used with precision.


That elements are evenly spaced in storage.
Feb 20 2015
prev sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Friday, 20 February 2015 at 09:44:36 UTC, John Colvin wrote:

 *what do you even mean by that? Jargon is only useful when it's 
 used with precision.


Well, it is also very useful to sound smart and you have no 
content to show for it.
Feb 20 2015
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Friday, 20 February 2015 at 19:06:29 UTC, deadalnix wrote:

 On Friday, 20 February 2015 at 09:44:36 UTC, John Colvin wrote:

 *what do you even mean by that? Jargon is only useful when 
 it's used with precision.


 Well, it is also very useful to sound smart and you have no 
 content to show for it.


Broke your promise already?

Well, I'll be happy to be your nanny:

«uni» = one/single

«form» = shape

«distribution» = how things are spread out

«SIMD» = Single Instruction Multiple Data

=>

the properties of data layout with respect to executing SIMD 
instructions over the dataset

No surprising jargon here.
Feb 20 2015
prev sibling parent reply "Vlad Levenfeld" <vlevenfeld gmail.com> writes:
I feel the bigger picture is being missed amid the focus on 
blitting.

On Thursday, 19 February 2015 at 11:20:13 UTC, Guillaume Chatelet 
wrote:

 From this discussion I understand you mainly want to be able to 
 BitBlt ranges


BitBlit is useful, yes, but not the main point. Interfacing with 
C APIs and supporting in-place transformations is also important.

On Thursday, 19 February 2015 at 19:32:26 UTC, Andrei 
Alexandrescu wrote:

 I don't see a need for contiguous ranges if the only embodiment 
 is T[]. -- Andrei


Agreed. I don't think that defining contiguous ranges as 
implicitly convertible to T[] is useful - in this case, you could 
just write functions to take a T[], and forget the original range 
type entirely. For a range concept to be useful for generic 
programming, it needs to enable templates to lift algorithms to 
the argument type's category. Instead, lowering a range to T[] 
loses the capabilities and constraints defined in the original 
range and obviates the need for the category in the first place.

On Friday, 20 February 2015 at 01:25:34 UTC, deadalnix wrote:

 Isn't it what a slice is already ?


Yes. A slice is the simplest realization of a contiguous range. I 
argue that it is useful to have structures which have slice-like 
behavior without actually being slices.

On Friday, 20 February 2015 at 08:20:50 UTC, Ola Fosheim Grøstad 
wrote:

 So that you can assess whether "a pointer" (iterator) is in a 
 range on or not at O(1)?


Hadn't thought of that, it could be useful.

On Friday, 20 February 2015 at 08:22:38 UTC, John Colvin wrote:

 I don't see anything here that isn't already covered by 
 built-in slices, opSlice, opSliceAssign and put.


opSlice.* and put are defined in the data structure, whereas 
range concepts inform the algorithm.

//////////////////////////

I claim that the practical benefit of range concepts as type 
predicates is:
   1) to make overloading logic more succinct and uniform.
   2) to concentrate implementation decisions in the appropriate 
abstraction layer.
both of which serve to make generic code more robust, expressive 
and efficient.

Sometimes you want something like a slice (in that it guarantees 
contiguous memory layout) but with additional capabilities and 
constraints which you would like to have preserved under certain 
transformations. This can be encapsulated in a contiguous range 
concept.

Let me illustrate with an example:

   struct AudioClip {
     float[2][] samples;
     uint sampling_rate;
     this (string path) {load (path, samples);}
     void play () {some_C_audio_lib_call (samples.ptr, 
samples.length, sampling_rate);}
   }

   // we'll start with an audio clip with contiguous layout in 
memory
   auto ac = AudioClip ("90 minutes of screaming cats.flac");

   // now we define two implementations of the same filter
   auto ref declaw_filter1 (R)(R r) if (isContiguousRange!R) {
     // pattern match to get the size of the sample
     static if (is (ElementType!R == float[stride], uint stride)) 
{}

     // i know the gsl functions don't work like this, just bear 
with me
     gsl_fft (ptr, stride, r.length);
     gsl_fgemm (/*pretend this is sensible*/);
     gsl_fft_inverse (ptr, stride, r.length);

     return r;
   }

   auto declaw_filter2 (uint n)(float[n][] slice) {
     // like declaw_filter1 but without the contiguous stuff
   }

   // now, we can finish this one of two ways
   // the easy way:
   ac.declaw_filter1.play; // UFCS all day
   // or, if we passed a T[] made from AudioClip or defined 
AudioClip to be implicitly convertible to T[]:
   AudioClip ac2;
   ac2.samples = ac.declaw_filter2;
   ac2.sampling_rate = ac.sampling_rate; // this could 
desynchronize after the code is refactored, opening us up for bugs
   ac2.play;

THE UPSHOT:
Both variants of declaw_filter are generic - they'll operate on 
data in an arbitrary number of channels, it could be an audio 
file or voltages from a DAQ or whatever.
Variant 1 lifts the algorithm to accommodate the range, while 
variant 2 lowers the range to accommodate the algorithm.
The use of variant 2 is more verbose, error-prone, and bubbles 
implementation details up to a layer where they don't belong.
Variant 1 uses the concept of a contiguous range to keep the 
knowledge of its implementation (specifically, that it calls 
functions which expect pointers) encapsulated.

THE DOWNSIDE:
Slicing and in-place transformations are pretty much the only 
things that will preserve contiguity. Piping ac through map or 
something will take us back to manually propagating the sampling 
rate. In general, deciding how and when to preserve what 
information under which transformations is tough. Lazily mapping, 
say, to increase the volume could meaningfully preserve sampling 
rate, but under filtering, zipping or striding it doesn't make 
sense.
Feb 20 2015
next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Friday, 20 February 2015 at 12:23:49 UTC, Vlad Levenfeld wrote:

 Slicing and in-place transformations are pretty much the only 
 things that will preserve contiguity. Piping ac through map or 
 something will take us back to manually propagating the 
 sampling rate. In general, deciding how and when to preserve 
 what information under which transformations is tough. Lazily 
 mapping, say, to increase the volume could meaningfully 
 preserve sampling rate, but under filtering, zipping or 
 striding it doesn't make sense.


The sensible thing to do is to have ranges of contiguous ranges:

1. to get better cache locality

2. to iterate over btrees (which are popular now due to memory 
bus issues)

3. to do intermediate buffering for higher speed (SIMD)

In the worst case the contiguous range will degrade to 1 element, 
which is OK for prototyping. Then you can insert an intermediate 
buffer where needed after profiling performance.
Feb 20 2015
prev sibling next sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Friday, 20 February 2015 at 12:23:49 UTC, Vlad Levenfeld wrote:

 Yes. A slice is the simplest realization of a contiguous range. 
 I argue that it is useful to have structures which have 
 slice-like behavior without actually being slices.


I'm still not sure what more complex continuous range exists, and 
if it is worth the complexity of adding them to the language.
Feb 20 2015
next sibling parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Fri, Feb 20, 2015 at 07:09:14PM +0000, deadalnix via Digitalmars-d wrote:

 On Friday, 20 February 2015 at 12:23:49 UTC, Vlad Levenfeld wrote:

Yes. A slice is the simplest realization of a contiguous range. I
argue that it is useful to have structures which have slice-like
behavior without actually being slices.


 
 I'm still not sure what more complex continuous range exists, and if
 it is worth the complexity of adding them to the language.


What do contiguous ranges offer that isn't already offered by a random
access range that hasSlicing? If it doesn't offer significantly more
power than what we already have, I doubt Andrei would agree to adding it
to Phobos. We already have enough work on our hands trying to maintain
the current diverse set of ranges.


T

-- 
What do you call optometrist jokes? Vitreous humor.
Feb 20 2015
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Friday, 20 February 2015 at 19:28:38 UTC, H. S. Teoh wrote:

 What do contiguous ranges offer that isn't already offered by a 
 random
 access range that hasSlicing? If it doesn't offer significantly 
 more
 power than what we already have,


hasSlicing:

«Returns true if R offers a slicing operator with integral 
boundaries that returns a forward range type.»

There is no way you can do be certain that you can do SIMD 
operations over this.
Feb 20 2015
prev sibling next sibling parent "Vlad Levenfeld" <vlevenfeld gmail.com> writes:
On Friday, 20 February 2015 at 19:09:15 UTC, deadalnix wrote:

 I'm still not sure what more complex continuous range exists,


My last post has an example.


 and if it is worth the complexity of adding them to the 
 language.


It might not be, I just find the concept itself interesting.
Feb 20 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/20/15 11:09 AM, deadalnix wrote:

 On Friday, 20 February 2015 at 12:23:49 UTC, Vlad Levenfeld wrote:

 Yes. A slice is the simplest realization of a contiguous range. I
 argue that it is useful to have structures which have slice-like
 behavior without actually being slices.


 I'm still not sure what more complex continuous range exists, and if it
 is worth the complexity of adding them to the language.


Reference counted slices would be the only one coming to mind.

There are several other ranges with contiguous _support_: retro, 
randomCover, map (over ranges with that property), and probably more.


Andrei
Feb 20 2015
parent "deadalnix" <deadalnix gmail.com> writes:
On Friday, 20 February 2015 at 19:54:20 UTC, Andrei Alexandrescu 
wrote:

 On 2/20/15 11:09 AM, deadalnix wrote:

 On Friday, 20 February 2015 at 12:23:49 UTC, Vlad Levenfeld 
 wrote:

 Yes. A slice is the simplest realization of a contiguous 
 range. I
 argue that it is useful to have structures which have 
 slice-like
 behavior without actually being slices.


 I'm still not sure what more complex continuous range exists, 
 and if it
 is worth the complexity of adding them to the language.


 Reference counted slices would be the only one coming to mind.

 There are several other ranges with contiguous _support_: 
 retro, randomCover, map (over ranges with that property), and 
 probably more.


 Andrei


The RCSlice I can buy it, but map is certainly not contiguous.

If an RCSlice can decay to a borrowed slice, then even this one 
goes away.
Feb 20 2015
prev sibling parent reply "Pasqui23" <ppp23 example.com> writes:
On Friday, 20 February 2015 at 12:23:49 UTC, Vlad Levenfeld wrote:


 Let me illustrate with an example:

   struct AudioClip {
     float[2][] samples;
     uint sampling_rate;
     this (string path) {load (path, samples);}
     void play () {some_C_audio_lib_call (samples.ptr, 
 samples.length, sampling_rate);}
   }

   // we'll start with an audio clip with contiguous layout in 
 memory
   auto ac = AudioClip ("90 minutes of screaming cats.flac");

   // now we define two implementations of the same filter
   auto ref declaw_filter1 (R)(R r) if (isContiguousRange!R) {
     // pattern match to get the size of the sample
     static if (is (ElementType!R == float[stride], uint 
 stride)) {}

     // i know the gsl functions don't work like this, just bear 
 with me
     gsl_fft (ptr, stride, r.length);
     gsl_fgemm (/*pretend this is sensible*/);
     gsl_fft_inverse (ptr, stride, r.length);

     return r;
   }

   auto declaw_filter2 (uint n)(float[n][] slice) {
     // like declaw_filter1 but without the contiguous stuff
   }

   // now, we can finish this one of two ways
   // the easy way:
   ac.declaw_filter1.play; // UFCS all day
   // or, if we passed a T[] made from AudioClip or defined 
 AudioClip to be implicitly convertible to T[]:
   AudioClip ac2;
   ac2.samples = ac.declaw_filter2;
   ac2.sampling_rate = ac.sampling_rate; // this could 
 desynchronize after the code is refactored, opening us up for 
 bugs
   ac2.play;


You could have the best of both worlds this way:
   R declaw_filter3(R)(R r)if(is(R:float[stride][],size_t stride))
and write
   ac.declaw_filter3.play;
Feb 20 2015
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Friday, 20 February 2015 at 19:47:24 UTC, Pasqui23 wrote:

 You could have the best of both worlds this way:
   R declaw_filter3(R)(R r)if(is(R:float[stride][],size_t 
 stride))
 and write
   ac.declaw_filter3.play;


Stride is tied to alignment and not value type size in the 
general case (float being a special case), so stride should be in 
bytes...
Feb 20 2015