www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - range behaviour

reply Benjamin Thaut <code benjamin-thaut.de> writes:
I know that there was a recent discussion about how the methods of 
ranges should behave.

E.g.

- Does empty always have to be called before calling front or popFront?
- Is it allowed to call front multiple times between two calls to popFront?

Was there a result of that discussion? Is it documented somewhere?

Kind Regards
Benjamin Thaut
May 13 2014
next sibling parent reply Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Tue, 13 May 2014 18:38:44 +0200
Benjamin Thaut via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 I know that there was a recent discussion about how the methods of
 ranges should behave.

 E.g.

 - Does empty always have to be called before calling front or
 popFront?

Certainly, ranges are pretty much always used this way, but there was some debate as to whether empty could have work done in it (and thus _had_ to be called). However, I believe that the consensus was that yes, empty had to be called (certainly, both Walter and Andrei felt that way).
 - Is it allowed to call front multiple times between two calls to
 popFront?

Definitely. _Lots_ of range-based code would break otherwise - though there are casese where that can cause problems depending on what you rely on (e.g. map!(a => to!string(a)) will return equal strings, but they aren't the _same_ string).
 Was there a result of that discussion? Is it documented somewhere?

AFAIK, there's just the semi-recent newsgroup discussion on the matter, though maybe someone put something up on the wiki. - Jonathan M Davis
May 13 2014
parent luka8088 <luka8088 owave.net> writes:
On 13.5.2014. 19:40, H. S. Teoh via Digitalmars-d wrote:
 On Tue, May 13, 2014 at 01:29:32PM -0400, Steven Schveighoffer via
Digitalmars-d wrote:
 [...]
 Even in this case, I'd put an in-contract on f2 that verifies that the
 range is indeed non-empty:
 
 	...
 		void f2(R)(R r)
 			if (isInputRange!R)
 		in { assert(!r.empty); }
 		body {
 			doSomething(r.front);
 		}
 
 [...]

This is a potential issue because if it turns out that empty _must_ be called than the author could put the front population logic inside empty. Consider: struct R { bool empty () { front = 1; return false; } int front = 0; void popFront () { front = 0; } } This is a valid code if empty _must_ be called, but it will behave differently if passed to f2 in case asserts are compiled out. In case asserts are compiled out empty is never called and front in never populated. Because of this I think that it is necessary to document range behavior.
May 13 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 13 May 2014 12:58:09 -0400, Jonathan M Davis via Digitalmars-d  
<digitalmars-d puremagic.com> wrote:

 On Tue, 13 May 2014 18:38:44 +0200
 Benjamin Thaut via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 I know that there was a recent discussion about how the methods of
 ranges should behave.

 E.g.

 - Does empty always have to be called before calling front or
 popFront?

Certainly, ranges are pretty much always used this way, but there was some debate as to whether empty could have work done in it (and thus _had_ to be called). However, I believe that the consensus was that yes, empty had to be called (certainly, both Walter and Andrei felt that way).

I don't agree there was a consensus. I think empty should not have to be called if it's already logically known that the range is not empty. The current documentation states that, and I don't think there was an agreement that we should change it, despite the arguments from Walter. In any case, I think generic code for an unknown range type in an unknown condition should have to call empty, since it cannot logically prove that it's not. Even if it was required, it would be an unenforceable policy, just like range.save. -Steve
May 13 2014
prev sibling next sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Tue, May 13, 2014 at 09:58:09AM -0700, Jonathan M Davis via Digitalmars-d
wrote:
 On Tue, 13 May 2014 18:38:44 +0200
 Benjamin Thaut via Digitalmars-d <digitalmars-d puremagic.com> wrote:
 
 I know that there was a recent discussion about how the methods of
 ranges should behave.

 E.g.

 - Does empty always have to be called before calling front or
 popFront?

Certainly, ranges are pretty much always used this way, but there was some debate as to whether empty could have work done in it (and thus _had_ to be called). However, I believe that the consensus was that yes, empty had to be called (certainly, both Walter and Andrei felt that way).
 - Is it allowed to call front multiple times between two calls to
 popFront?

Definitely. _Lots_ of range-based code would break otherwise - though there are casese where that can cause problems depending on what you rely on (e.g. map!(a => to!string(a)) will return equal strings, but they aren't the _same_ string).
 Was there a result of that discussion? Is it documented somewhere?

AFAIK, there's just the semi-recent newsgroup discussion on the matter, though maybe someone put something up on the wiki.

I second all of the above. In generic code (all range-based code is generic, since otherwise there's no point in using the range abstraction, you should just use the concrete type directly), you cannot assume anything about what .empty, .front, and .popFront() might do apart from what is specified in the range API. Therefore, since .front and .popFront have unspecified behaviour if .empty is false, the only correct way to write range-based code is to call .empty first to determine whether it's OK to call .front and .popFront. Furthermore, it doesn't make sense to restrict .front to be called only once, since otherwise we should simplify the API by merging .front and .popFront and have the same function both return the current element and advance to the next element. The fact that they were designed to be separate calls implies that .front can be called multiple times. Of course, for efficiency purposes range-based code (esp. Phobos code) should try their best to only call .front once. But it should be perfectly permissible to call .front multiple times. Lastly, since the range API is an *abstraction*, it should not dictate any concrete implementation details such as whether .empty can do non-trivial initialization work. Properly-written range-based code should be able to handle all possible implementations of the range API, including those that do non-trivial work in .empty. Of course, that doesn't mean it's a *good* idea for .empty to do non-trivial work. The code is probably cleaner if that work is done somewhere else (like in the ctor or the function that returns the range). But that's an issue for the implementer of the range, not the consumers. The consumers of the range should not depend on one behaviour or the other, so that they will still work correctly when given a range that, for whatever reason, needs to do non-trivial work in .empty. T -- Prosperity breeds contempt, and poverty breeds consent. -- Suck.com
May 13 2014
prev sibling next sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Tue, May 13, 2014 at 01:29:32PM -0400, Steven Schveighoffer via
Digitalmars-d wrote:
[...]
 I don't agree there was a consensus. I think empty should not have to
 be called if it's already logically known that the range is not empty.

I only partially agree with this, up to the point where .empty has been checked previously, such as: void f1() { void f2(R)(R r) if (isInputRange!R) { doSomething(r.front); } auto r = makeMeARange(); if (!r.empty) f2(r); ... } Even in this case, I'd put an in-contract on f2 that verifies that the range is indeed non-empty: ... void f2(R)(R r) if (isInputRange!R) in { assert(!r.empty); } body { doSomething(r.front); } [...]
 In any case, I think generic code for an unknown range type in an
 unknown condition should have to call empty, since it cannot logically
 prove that it's not.

In my mind, *all* range-based code is generic. If you need to depend on something about your range beyond what the range API guarantees, then you should be using the concrete type rather than a template argument, which means that your code is no longer range-based code -- it's operating on a concrete type. (Of course, if the concrete type implements the range API, then there's nothing wrong with using range API methods, but one shouldn't be under the illusion that one is writing range-based code. It is type-dependent code that just happens to have range-based methods. If the code will break if the range is substituted by a different range that doesn't have the same guarantees (outside of what the range API specifies), then it's not range-based code.) T -- Many open minds should be closed for repairs. -- K5 user
May 13 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Tue, 13 May 2014 13:29:32 -0400
Steven Schveighoffer via Digitalmars-d <digitalmars-d puremagic.com>
wrote:

 On Tue, 13 May 2014 12:58:09 -0400, Jonathan M Davis via
 Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On Tue, 13 May 2014 18:38:44 +0200
 Benjamin Thaut via Digitalmars-d <digitalmars-d puremagic.com>
 wrote:

 I know that there was a recent discussion about how the methods of
 ranges should behave.

 E.g.

 - Does empty always have to be called before calling front or
 popFront?

Certainly, ranges are pretty much always used this way, but there was some debate as to whether empty could have work done in it (and thus _had_ to be called). However, I believe that the consensus was that yes, empty had to be called (certainly, both Walter and Andrei felt that way).

I don't agree there was a consensus. I think empty should not have to be called if it's already logically known that the range is not empty. The current documentation states that, and I don't think there was an agreement that we should change it, despite the arguments from Walter. In any case, I think generic code for an unknown range type in an unknown condition should have to call empty, since it cannot logically prove that it's not. Even if it was required, it would be an unenforceable policy, just like range.save.

Yeah, and they're both cases where the common case will work just fine if you do it wrong but which will break in less common cases, meaning that the odds are much higher that the bug won't be caught. :( - Jonathan M Davis
May 13 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Tue, 13 May 2014 10:30:47 -0700
"H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> wrote:
 Of course, for efficiency purposes range-based code (esp. Phobos code)
 should try their best to only call .front once. But it should be
 perfectly permissible to call .front multiple times.

Oh, but that's part of the fun. If the range's front returns by ref or auto ref - or if it actually made front a public member variable - then it would be _less_ efficient to assign the result of front to a variable in order to avoid calling front multiple times. Much as ranges have a defined API, there's enough flexibility in the API and in how it's implemented for any given range that generalities about what is more or less efficient or which is more or less likely to avoid unintended behaviors isn't a sure thing - which is part of why that particular discussion was instigated in the first place and why discussions about stuff like whether front can be transitive or not keep popping up from time to time. In general, it's probably better to avoid calling front multiple times though - the issue with map being a prime example of where the problem can be worse than simply an issue of efficiency - and in most cases, ranges don't have a front which returns by ref or auto ref. But unfortunately, because that's just _most_ cases, it does make it so that we can't make a blanket statement about what is more or less efficient. - Jonathan M Davis
May 13 2014
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 13 May 2014 13:40:55 -0400, H. S. Teoh via Digitalmars-d  
<digitalmars-d puremagic.com> wrote:

 On Tue, May 13, 2014 at 01:29:32PM -0400, Steven Schveighoffer via  
 Digitalmars-d wrote:
 [...]

 In any case, I think generic code for an unknown range type in an
 unknown condition should have to call empty, since it cannot logically
 prove that it's not.

In my mind, *all* range-based code is generic. If you need to depend on something about your range beyond what the range API guarantees, then you should be using the concrete type rather than a template argument, which means that your code is no longer range-based code -- it's operating on a concrete type.

You can be generic, but still know that empty is not necessary. This is a potential use case (somewhat similar to yours): void foo(R)(R r) { if(!r.empty) { auto r2 = map!(x => x.bar)(r); // or some similar translation range // have to check r2.empty here? The "empty must be called" rules say yes. } } I will note, there are cases in phobos that don't check empty because it's provably not necessary. The issue arose because of the filter range, which someone was trying to make fully lazy. The whole thrust of the argument is that we want to force people to call empty not because we want them to write generically safe code but because we want to *instrument* empty to do something other than check for emptiness. In other words, if we are guaranteed that empty will be called before anything else, we can add extra bits to empty for e.g. lazy initialization. Otherwise, we have to add the bits to all the primitives. It also results in an awkward call when it's not strictly necessary: r2.empty; -Steve
May 13 2014
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Tuesday, 13 May 2014 at 16:38:43 UTC, Benjamin Thaut wrote:
 I know that there was a recent discussion about how the methods 
 of ranges should behave.

 E.g.

 - Does empty always have to be called before calling front or 
 popFront?
 - Is it allowed to call front multiple times between two calls 
 to popFront?

 Was there a result of that discussion? Is it documented 
 somewhere?

 Kind Regards
 Benjamin Thaut

I don't remember any final decision made from that discussion.
May 13 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Tuesday, 13 May 2014 at 17:32:21 UTC, H. S. Teoh via 
Digitalmars-d wrote:
 Lastly, since the range API is an *abstraction*, it should not 
 dictate
 any concrete implementation details such as whether .empty can 
 do
 non-trivial initialization work. Properly-written range-based 
 code
 should be able to handle all possible implementations of the 
 range API,
 including those that do non-trivial work in .empty.

An API is a "user" interface. It should be intuitive. Besides, D ranges will never perform as well as an optimized explicit loop, so you might as well aim for usability over speed. I learned this over 15 years ago when I was fed up with STL begin/end and implemented my own inlined iterators that work like D ranges ( for a scanline renderer ).
May 13 2014
prev sibling next sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Wednesday, 14 May 2014 at 06:00:33 UTC, Ola Fosheim Grøstad 
wrote:
 On Tuesday, 13 May 2014 at 17:32:21 UTC, H. S. Teoh via 
 Digitalmars-d wrote:
 Lastly, since the range API is an *abstraction*, it should not 
 dictate
 any concrete implementation details such as whether .empty can 
 do
 non-trivial initialization work. Properly-written range-based 
 code
 should be able to handle all possible implementations of the 
 range API,
 including those that do non-trivial work in .empty.

An API is a "user" interface. It should be intuitive. Besides, D ranges will never perform as well as an optimized explicit loop, so you might as well aim for usability over speed.

I wouldn't say never, because optimizers have become damn good. I believe the additional overhead of lazy initialization is mostly optimized away where it matters, i.e. inner loops, because the compiler can see that the initialization has already been performed in the first iteration. All it requires is unrolling the first iteration of the loop and treating it specially. But of course, this makes your conclusion even more true, because you
May 14 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Wednesday, 14 May 2014 at 09:47:56 UTC, Marc Schütz wrote:
 I wouldn't say never, because optimizers have become damn good.

Well, "never" without a proof is of course a too strong claim. :-) I agree with that, but I don't think optimizers are that good yet even though some of my troubles have been solved.
 I believe the additional overhead of lazy initialization is 
 mostly optimized away where it matters, i.e. inner loops, 
 because  the compiler can see that the initialization has 
 already been performed in the first iteration. All it requires 
 is unrolling the first iteration of the loop and treating it 
 specially.

You can do this for some generators/iterators, but you have different ways to construct loops and generators and consumers that affect what is most efficient and how many registers you use etc. Abstractions hide what is going on, so the consumer might miss more efficient way of structuring the algorithm. Example: if you know that the end comes after 0, then you only need to test empty() after you read 0. You don't need to test for 0, you just branch up to the start of the loop if the zero-flag is set. Quasi ASM: loop: write(x) start: x = generate_next() branch_if_not_zero loop test( empty() ) branch_if_zero loop write(0) It is easy to construct examples where naive ranges will be suboptimal. For more complex iterators you also need to deal with sparse datastructures, skiplists, run length encoded data, SIMD alignment, guard protected stream ends… Meta information you exploit when you need faster algorithms.
May 14 2014
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Wednesday, 14 May 2014 at 06:00:33 UTC, Ola Fosheim Grøstad 
wrote:
 Besides, D ranges will never perform as well as an optimized 
 explicit loop, so you might as well aim for usability over 
 speed.

There is no single reason why this should be true. Actually ranges of medium complexity are already very close to explicit loops in D when you use something like LDC. Consider sample program like this: 1 void main() 2 { 3 import std.stdio; 4 int max; 5 readf("%d", &max); 6 assert(foo1(max) == foo2(max)); 7 } 8 9 int foo1(int max) 10 { 11 int sum = 0; 12 for (auto i = 0; i < max; ++i) 13 { 14 sum += i*2; 15 } 16 return sum; 17 } 18 19 int foo2(int max) 20 { 21 import std.algorithm : reduce, map; 22 import std.range : iota; 23 return reduce!((a, b) => a + b)(0, iota(0, max).map!(a => a*2)); 24 } Disassembly (ldmd2 -O -release -inline): 765 0000000000402df0 <_D4test4foo1FiZi>: 766 402df0: 31 c0 xor %eax,%eax 767 402df2: 85 ff test %edi,%edi 768 402df4: 7e 10 jle 402e06 <_D4test4foo1FiZi+0x16> 769 402df6: 8d 47 ff lea -0x1(%rdi),%eax 770 402df9: 8d 4f fe lea -0x2(%rdi),%ecx 771 402dfc: 0f af c8 imul %eax,%ecx 772 402dff: 83 e1 fe and $0xfffffffe,%ecx 773 402e02: 8d 44 79 fe lea -0x2(%rcx,%rdi,2),%eax 774 402e06: c3 retq 775 402e07: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1) 776 402e0e: 00 00 777 778 0000000000402e10 <_D4test4foo2FiZi>: 779 402e10: 31 c0 xor %eax,%eax 780 402e12: 85 ff test %edi,%edi 781 402e14: 0f 48 f8 cmovs %eax,%edi 782 402e17: 85 ff test %edi,%edi 783 402e19: 74 10 je 402e2b <_D4test4foo2FiZi+0x1b> 784 402e1b: 8d 47 ff lea -0x1(%rdi),%eax 785 402e1e: 8d 4f fe lea -0x2(%rdi),%ecx 786 402e21: 0f af c8 imul %eax,%ecx 787 402e24: 83 e1 fe and $0xfffffffe,%ecx 788 402e27: 8d 44 79 fe lea -0x2(%rcx,%rdi,2),%eax 789 402e2b: c3 retq 790 402e2c: 0f 1f 40 00 nopl 0x0(%rax) it is almost identical. I fully expect to be 100% identical at certain point of compiler maturity.
May 14 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Wednesday, 14 May 2014 at 13:29:35 UTC, Dicebot wrote:
   9 int foo1(int max)
  10 {
  11     int sum = 0;
  12     for (auto i = 0; i < max; ++i)
  13     {
  14         sum += i*2;
  15     }
  16     return sum;
  17 }

This isn't really a loop. It is an expression: n*(n+1) Try something more realistic such as doing alpha-blending to a buffer or DSP.
May 14 2014
prev sibling next sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Wednesday, 14 May 2014 at 11:23:16 UTC, Ola Fosheim Grøstad 
wrote:
 On Wednesday, 14 May 2014 at 09:47:56 UTC, Marc Schütz wrote:
 I wouldn't say never, because optimizers have become damn good.

Well, "never" without a proof is of course a too strong claim. :-) I agree with that, but I don't think optimizers are that good yet even though some of my troubles have been solved.
 I believe the additional overhead of lazy initialization is 
 mostly optimized away where it matters, i.e. inner loops, 
 because  the compiler can see that the initialization has 
 already been performed in the first iteration. All it requires 
 is unrolling the first iteration of the loop and treating it 
 specially.


As a demonstration of what I mean: /////////////////////////////////// import std.functional; struct Filter(alias predicate, Range) { Range r; private: bool is_initialized; public: void initialize() { alias pred = unaryFun!predicate; if(is_initialized) return; while(!r.empty && !pred(r.front)) r.popFront(); is_initialized = true; } property bool empty() { initialize(); return r.empty; } property auto front() { initialize(); return r.front; } void popFront() { r.popFront(); is_initialized = false; } auto sum() { typeof(r.front) result = 0; foreach(v; this) result += v; return result; } } auto filter(alias predicate, Range)(Range r) { return Filter!(predicate, Range)(r); } extern bool myPredicate(int); struct MyGen { int front; int max; property bool empty() { return front > max; } void popFront() { front++; } } void main() { auto gen = MyGen(1, 6); gen.filter!myPredicate.sum(); gen.filter!"a % 2".sum(); gen.filter!(a => true).sum(); } /////////////////////////////////// Compile this with: ldc2 -O3 -release -output-s demo.d and have a look a the generated assembly code for the Filter.sum() functions. All of them have been inlined as much as possible, and in particular the variable `is_initialized` has disappeared, even in the version that uses an external (unknown to the compiler) predicate. Of course, if you don't access the range in a tight loop, these optimizations usually aren't possible. But arguably, in such cases an extra variable and an extra check for initialization aren't too bad. This means that we can have lazy implementations even without a guaranteed call to `empty`, and still have comparable performance to eagerly initialized ranges where it matters most.
May 14 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Wednesday, 14 May 2014 at 19:32:57 UTC, Marc Schütz wrote:
 Compile this with:

     ldc2 -O3 -release -output-s demo.d

 and have a look a the generated assembly code for the 
 Filter.sum() functions. All of them have been inlined as much 
 as possible, and in particular the variable `is_initialized` 
 has disappeared, even in the version that uses an external 
 (unknown to the compiler) predicate.

I only have DMD installed, but I trust your word for it. However I don't feel confident that compilers will ever catch up, even for simple loops. Take for instance floating point. Floating point math is inaccurate, that means the compiler will have to guess what kind of accuracy you are happy with… It can't, so it can't optimize real well, even when loop unrolling. Why is that? Well, because even if it can create SIMD instructions it cannot decouple the dependencies between consecutive elements without creating drift between the calculations over time. It has to assume the worst case. If you have a simple generator like this: sample[n] = f( sample[n-1] ) you could in theory do sample[n] = f(f(f(f( sample[n-4] )))) sample[n+1] = f(f(f(f( sample[n-3] )))) sample[n+2] = f(f(f(f( sample[n-2] )))) sample[n+3] = f(f(f(f( sample[n-1] )))) But because of floating point inaccuracies you would then risk that the sample[BIGNUMBER] and sample[BIGNUMBER+1] is completely disconnected which could be a disaster. So only hand optimization and analysis of the math and stability is sufficient to get the SIMD speed-up.
 This means that we can have implementations even without a 
 guaranteed call to `empty`, and still have comparable 
 performance to eagerly initialized ranges where it matters most.

Maybe you can. :-) I will have to get my hands on ldc and try to create a counter example… Hm.
May 14 2014
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Wednesday, 14 May 2014 at 14:00:18 UTC, Ola Fosheim Grøstad 
wrote:
 On Wednesday, 14 May 2014 at 13:29:35 UTC, Dicebot wrote:
  9 int foo1(int max)
 10 {
 11     int sum = 0;
 12     for (auto i = 0; i < max; ++i)
 13     {
 14         sum += i*2;
 15     }
 16     return sum;
 17 }

This isn't really a loop. It is an expression: n*(n+1) Try something more realistic such as doing alpha-blending to a buffer or DSP.

I think it is your turn to make a counter-example ;) It does not matter that much what loop actually does. It was effectively an expression here but compiler was able to reduce range version to quite the same expression despite all the intermediate code. Of course there are still many ways to fool existing optimizers but declaring fundamental inability to do so? No way.
May 15 2014
prev sibling next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 12:34:49 UTC, Dicebot wrote:
 I think it is your turn to make a counter-example ;)

I've given 2 examples that no compiler can get at… because they lack contextual knowledge. ;) Basically anything that involves guards at the end is an issue, most things that involve floating point is an issue, but there are others too I think… I'll get back to counter-examples later when I have time to look closer at LDC. (not this week)
May 15 2014
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Thursday, 15 May 2014 at 13:01:34 UTC, Ola Fosheim Grøstad 
wrote:
 On Thursday, 15 May 2014 at 12:34:49 UTC, Dicebot wrote:
 I think it is your turn to make a counter-example ;)

I've given 2 examples that no compiler can get at… because they lack contextual knowledge. ;)

If compiler lacks contextual knowledge, than only means that range is not actually semantically equivalent to a loop. Which is quite possible if you start considering something like SIMD, this is true. What is wrong is assumption that such kinds of loops are anything but tiny minority and this warrants generic "ranges can never be as fast as loops" statement. Btw,
  Floating point math is inaccurate, that means the compiler 
 will have to guess what kind of accuracy you are happy with…

AFAIK it is actually not true. Floating point standard defines basic precision guarantees and compilers are free to make any adjustments outside of those basics. In your example you need to verify generated assembly anyway, loop or range.
May 15 2014
prev sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 15 May 2014 at 13:10:29 UTC, Dicebot wrote:
 If compiler lacks contextual knowledge, than only means that 
 range is not actually semantically equivalent to a loop.

Not really. Here is a simple example, a sawtooth generator that goes from 1 to 0 with a cycle length >=2 (nyquist). import std.algorithm; import std.math; struct gen_sawtooth { enum bool empty = false; float front; float delta; this(immutable float samps_per_cycle){ front = 1.0f; delta = 1.0f/samps_per_cycle; } void popFront() { front -= delta; if(front < 0.0f) front += 1.0f; } } void rangefill_sawtooth(float[] a, immutable float samps_per_cycle){ auto gen = gen_sawtooth(samps_per_cycle); fill(a,gen); } void fill_sawtooth(float[] a,immutable float samps_per_cycle) { if(a.length==0) return; immutable float delta = 1.0f/samps_per_cycle; immutable max_cycle_length = cast(uint)floor(samps_per_cycle*1.0001+1); immutable lastcycle = a.length - max_cycle_length; float v = 1.0f; uint i = 0; do { do{ // main inner loop a[i] = v; ++i; v -= delta; } while(v>=0.0f); v += 1.0f; } while( i < lastcycle ); for(;i<a.length;++i){ // can be optimized further a[i] = v; v -= delta; if (v<0.0f) v += 1.0f; } } The generated code for the range based version does not create a fast innerloop, it lacks enough context and smarts: fill_sawtooth main inner loop: loop: incl %eax leal -2(%rax), %edx movss %xmm1, (%rbx,%rdx,4) subss %xmm0, %xmm1 ucomiss %xmm3, %xmm1 jae loop rangefill_sawtooth inner loop: loop: movss %xmm3, (%rsi) subss %xmm2, %xmm3 decq %rdi ucomiss %xmm3, %xmm0 jbe skip addss %xmm1, %xmm3 skip: addq $4, %rsi testq %rdi, %rdi jne loop
 What is wrong is assumption that such kinds of loops are 
 anything but tiny minority and this warrants generic "ranges 
 can never be as fast as loops" statement.

Not without significant work…
 Floating point math is inaccurate, that means the compiler 
 will have to guess what kind of accuracy you are happy with…

AFAIK it is actually not true. Floating point standard defines basic precision guarantees

Minimum yes. That makes drift unpredictable. Sometimes you care more about deltas than absolute values.
May 16 2014