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.

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.

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.

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.

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.

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.

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.

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.

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.

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.