On Friday, 20 September 2013 at 16:38:29 UTC, Andrei Alexandrescu wrote:
> On 9/20/13 8:13 AM, Joseph Rushton Wakeling wrote:
>> On 20/09/13 16:48, H. S. Teoh wrote:
>>> A container should not be confused with a range. That way leads to
>>> dragons. :-P  (It's rather unfortunate that built-in arrays conflate the
>>> two, it leads to a lot of wrong code that works only with arrays but not
>>> with "real" ranges.)
>>
>> Built-in arrays are not _always_ ranges.  Consider const(int[]) ... as I
>> found out recently, it's _not_ a range, because you can't popFront on a
>> const entity.
>>
>
> Well you can't call popFront on any const range.
>

What is even the purpose of const ranges? It makes little sense imho. Why would GoF iterator be immutable? It is like trying to iterate over collection bu indexing but only having const int as index variable. If anything it only make sense to have ranges to const (abstraction over const_iterator).

On 20.09.2013 17:28, Andrei Alexandrescu wrote:
> On 9/20/13 2:36 AM, bearophile wrote:
>> In D it's often better to use std.algorithm/range instead of raw foreach
>> loops (despite probably unlike C++ in D a heavy use of ranges leads to a
>> lower performance, even if you use the LDC2 compiler).
>
> Why would there be a performance loss?

Because range concept underutilize current CPUs. I don't know if all empty/front/popFront are inlined. I suppose some templated functions are, but surely not all of them.  What will be faster, calling all of those functions for each element or traversing memory using a loop?

Of course 2nd option will be faster, because the act of traversing (cached) memory does not have the overhead of a function call.

Some time ago I proposed a hybrid range concept where the front() is an array. All algorithms would first traverse the memory in this array, then call popFront to get another array (slice). In this way, function call overhead is minimized because it's paid sparsely rather than for each range element.

On Friday, September 20, 2013 18:46:34 Szymon Gatner wrote:
> On Friday, 20 September 2013 at 16:38:29 UTC, Andrei Alexandrescu
> 
> wrote:
> > On 9/20/13 8:13 AM, Joseph Rushton Wakeling wrote:
> >> On 20/09/13 16:48, H. S. Teoh wrote:
> >>> A container should not be confused with a range. That way
> >>> leads to
> >>> dragons. :-P  (It's rather unfortunate that built-in arrays
> >>> conflate the
> >>> two, it leads to a lot of wrong code that works only with
> >>> arrays but not
> >>> with "real" ranges.)
> >> 
> >> Built-in arrays are not _always_ ranges.  Consider
> >> const(int[]) ... as I
> >> found out recently, it's _not_ a range, because you can't
> >> popFront on a
> >> const entity.
> > 
> > Well you can't call popFront on any const range.
> 
> What is even the purpose of const ranges? It makes little sense imho. Why would GoF iterator be immutable? It is like trying to iterate over collection bu indexing but only having const int as index variable. If anything it only make sense to have ranges to const (abstraction over const_iterator).

If an object is const, then all of its members are const, which means that any ranges you get from its members will be const, making such ranges useless. But it still makes sense to iterate over such a range (in most cases, you care about the elements in the range, not the range itself). But since you can't iterate over the range (because it's const), you need to get a tail-const slice of it to iterate over instead. If you can do that, then const ranges aren't a huge problem. The problem is that making it so that you can get a tail-const slice of a const user-defined range is incredibly difficult. The compiler understands arrays, so it works there, but it doesn't work anywhere else. So, at this point, const and ranges don't play nicely at all.

- Jonathan M Davis

On Friday, 20 September 2013 at 16:57:43 UTC, Jonathan M Davis wrote:

>
> If an object is const, then all of its members are const, which means that any
> ranges you get from its members will be const, making such ranges useless.
>

That is so weird to hear considering I added ranges to my C++ code and my Vector<T>::all() const can easily return non-const range even tho container is itself const. This kinda looks like D is more limited in that area than C++... Or I really am not getting something.

Piotr Szturmaj:

> Some time ago I proposed a hybrid range concept where the front() is an array. All algorithms would first traverse the memory in this array, then call popFront to get another array (slice). In this way, function call overhead is minimized because it's paid sparsely rather than for each range element.

There are papers on this topic, like:
http://lafstern.org/matt/segmented.pdf

Bye,
bearophile

On 9/20/13 8:54 AM, Joseph Rushton Wakeling wrote:
> On 20/09/13 17:28, Andrei Alexandrescu wrote:
>> Why would there be a performance loss?
>
> Depends on the particular case, but my experience is that _in practice_
> stuff based around range interfaces can often be slower than raw iteration.
>
> I don't think anyone's saying a performance loss is inevitable or
> unavoidable, but there currently is one.

With dmd that's indeed the case. But LLVM is good at enregistering small structs, which is how ranges are implemented.

Andrei

On 9/20/13 9:28 AM, Joseph Rushton Wakeling wrote:
> On 20/09/13 18:01, Walter Bright wrote:
>> I know that, at least with dmd's back end, it's because the optimizer
>> was built
>> around the kinds of things that C++ programmers tend to write. The D
>> range/algorithm generates unusual code (for the back end) that the
>> back end
>> doesn't optimize for.
>>
>> For example, ranges tend to lump several variables together and call
>> them a
>> 'struct'. The back end is not tuned to deal with structs as an
>> aggregate of
>> discreet 'variables', meaning that such variables don't get assigned to
>> registers. Structs are treated as a lump.
>>
>> This is not a fundamental performance problem with D.
>>
>> The back end needs to be improved to "dis-aggregate" structs back into
>> discreet
>> variables.
>
> I wouldn't single out DMD for criticism -- I don't know to what extent
> the underlying reasons overlap, but all the compilers cope less well
> with range-based material than they might in theory.
>
> The canonical example would be something like,
>
>      foreach (i; iota(10)) { ... }
>
> which in theory shouldn't be any slower than,
>
>      foreach (i; 0 .. 10) { ... }
>
> but in practice is, no matter what the compiler.

I think I know how to fix that. I hypothesize it's about using actual increment instead of a stored value "step" for the particular case when step is 1.

Andrei

On 9/20/13 9:46 AM, Szymon Gatner wrote:
> On Friday, 20 September 2013 at 16:38:29 UTC, Andrei Alexandrescu wrote:
>> On 9/20/13 8:13 AM, Joseph Rushton Wakeling wrote:
>>> On 20/09/13 16:48, H. S. Teoh wrote:
>>>> A container should not be confused with a range. That way leads to
>>>> dragons. :-P  (It's rather unfortunate that built-in arrays conflate
>>>> the
>>>> two, it leads to a lot of wrong code that works only with arrays but
>>>> not
>>>> with "real" ranges.)
>>>
>>> Built-in arrays are not _always_ ranges.  Consider const(int[]) ... as I
>>> found out recently, it's _not_ a range, because you can't popFront on a
>>> const entity.
>>>
>>
>> Well you can't call popFront on any const range.
>>
>
> What is even the purpose of const ranges? It makes little sense imho.

I'd agree. As an aside, they don't have to make sense.

Andrei

On 9/20/13 9:51 AM, Piotr Szturmaj wrote:
> On 20.09.2013 17:28, Andrei Alexandrescu wrote:
>> On 9/20/13 2:36 AM, bearophile wrote:
>>> In D it's often better to use std.algorithm/range instead of raw foreach
>>> loops (despite probably unlike C++ in D a heavy use of ranges leads to a
>>> lower performance, even if you use the LDC2 compiler).
>>
>> Why would there be a performance loss?
>
> Because range concept underutilize current CPUs. I don't know if all
> empty/front/popFront are inlined. I suppose some templated functions
> are, but surely not all of them.  What will be faster, calling all of
> those functions for each element or traversing memory using a loop?

This is just a supposition. Inlining is automatic and just works subject to the constraints chosen by the implementers. It's not like there's a guy sitting there and getting bored of inlining.

> Of course 2nd option will be faster, because the act of traversing
> (cached) memory does not have the overhead of a function call.

No, no.

> Some time ago I proposed a hybrid range concept where the front() is an
> array. All algorithms would first traverse the memory in this array,
> then call popFront to get another array (slice). In this way, function
> call overhead is minimized because it's paid sparsely rather than for
> each range element.

That's a good idea but for completely different reasons.


Andrei

On 9/20/13 10:02 AM, Szymon Gatner wrote:
> On Friday, 20 September 2013 at 16:57:43 UTC, Jonathan M Davis wrote:
>
>>
>> If an object is const, then all of its members are const, which means
>> that any
>> ranges you get from its members will be const, making such ranges
>> useless.
>>
>
> That is so weird to hear considering I added ranges to my C++ code and
> my Vector<T>::all() const can easily return non-const range even tho
> container is itself const. This kinda looks like D is more limited in
> that area than C++... Or I really am not getting something.

Yah, it should be possible for a const container to offer ranges over its (non-modifiable) elements.

Andrei