Re: contiguous ranges
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.
Re: contiguous ranges
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.
Re: contiguous ranges
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.
Re: contiguous ranges
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)
Re: contiguous ranges
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.
Re: contiguous ranges
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.
Re: contiguous ranges
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.
Re: contiguous ranges
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.
Re: contiguous ranges
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...
Re: contiguous ranges
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.
Re: contiguous ranges
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.
Re: contiguous ranges
On Fri, Feb 20, 2015 at 07:09:14PM +, 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.
Re: contiguous ranges
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.
Re: contiguous ranges
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.
Re: contiguous ranges
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;
Re: contiguous ranges
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
Re: contiguous ranges
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.
Re: contiguous ranges
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).
Re: contiguous ranges
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
Re: contiguous ranges
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).
Re: contiguous ranges
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
Re: contiguous ranges
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 ?
Re: contiguous ranges
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.
Re: contiguous ranges
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=is.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=ins.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.
Re: contiguous ranges
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=ins.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.
Re: contiguous ranges
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=ins.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
Re: contiguous ranges
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
Re: contiguous ranges
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
Re: contiguous ranges
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
Re: contiguous ranges
On Mon, 16 Feb 2015 12:16:50 +, rupert wrote: 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 why he *should* to that? he *may* submit it. when someone sees people doing shit, he is not obliged to immediately go and fix that shit. signature.asc Description: PGP signature
Re: contiguous ranges
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).
Re: contiguous ranges
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.
Re: contiguous ranges
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
Re: contiguous ranges
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. ;)
contiguous ranges
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.
