On 6/25/13 4:47 AM, Timon Gehr wrote:
>
> Good point, but takeExactly currently is not a better choice due to its
> poor quality of implementation.
>
> https://github.com/D-Programming-Language/phobos/blob/master/std/range.d#L2904

What's wrong with it?

Andrei

On 06/25/2013 07:16 PM, Andrei Alexandrescu wrote:
> On 6/25/13 4:47 AM, Timon Gehr wrote:
>>
>> Good point, but takeExactly currently is not a better choice due to its
>> poor quality of implementation.
>>
>> https://github.com/D-Programming-Language/phobos/blob/master/std/range.d#L2904
>>
>
> What's wrong with it?
>
> Andrei
>

It either has all the overhead of take or does not properly propagate the underlying range's capabilities.

On Tuesday, June 25, 2013 19:33:32 Timon Gehr wrote:
> On 06/25/2013 07:16 PM, Andrei Alexandrescu wrote:
> > On 6/25/13 4:47 AM, Timon Gehr wrote:
> >> Good point, but takeExactly currently is not a better choice due to its poor quality of implementation.
> >> 
> >> https://github.com/D-Programming-Language/phobos/blob/master/std/range.d# L2904>
> > What's wrong with it?
> > 
> > Andrei
> 
> It either has all the overhead of take or does not properly propagate the underlying range's capabilities.

I don't think you're taking into account what take does. The primary case when takeExactly doesn't use take is when the range doesn't define length, in which case, the best that you can get out of it is a forward range, and that's exactly what it does.

On the other hand, when take is used, it _does_ propagate the original range's capabilites appropriately. take was specifically engineered to avoid wrapping ranges when it doesn't need to, so it shouldn't result in any any extra overhead if it isn't necessary. In particular, if the range has slicing, then Take is aliased away to the original type, and a slice is returned. The one case that I can think of where you really lose out on a range's capabilties with take is with bidirectional ranges which don't have slicing as they end up as forward ranges rather than bidirectional ranges, but without slicing, you can't do better than that.

I suppose that takeExactly's Result type (in the case where it actually creates its own type) could (and should) forward the primitives associated with hasMobileElements and hasAssignableElements (which it currently doesn't), but that's all I can see that's missing.

- Jonathan M Davis

On 06/25/2013 09:21 PM, Jonathan M Davis wrote:
> On Tuesday, June 25, 2013 19:33:32 Timon Gehr wrote:
>> On 06/25/2013 07:16 PM, Andrei Alexandrescu wrote:
>>> On 6/25/13 4:47 AM, Timon Gehr wrote:
>>>> Good point, but takeExactly currently is not a better choice due to its
>>>> poor quality of implementation.
>>>>
>>>> https://github.com/D-Programming-Language/phobos/blob/master/std/range.d#
>>>> L2904>
>>> What's wrong with it?
>>>
>>> Andrei
>>
>> It either has all the overhead of take or does not properly propagate
>> the underlying range's capabilities.
>
> I don't think you're taking into account what take does.

I think I do.

> The primary case when
> takeExactly doesn't use take is when the range doesn't define length, in which
> case, the best that you can get out of it is a forward range, and that's
> exactly what it does.
>
> On the other hand, when take is used, it _does_ propagate the original range's
> capabilites appropriately. take was specifically engineered to avoid wrapping
> ranges when it doesn't need to, so it shouldn't result in any any extra
> overhead if it isn't necessary.

Take will check the wrapped range's 'empty' repeatedly. takeExactly does not need to do that at all.

(overhead)

> In particular, if the range has slicing, then
> Take is aliased away to the original type, and a slice is returned. The one
> case that I can think of where you really lose out on a range's capabilties
> with take is with bidirectional ranges which don't have slicing as they end up
> as forward ranges rather than bidirectional ranges, but without slicing, you
> can't do better than that.
>

I'm fine with that.

> I suppose that takeExactly's Result type (in the case where it actually
> creates its own type) could (and should) forward the primitives associated
> with hasMobileElements and hasAssignableElements (which it currently doesn't),
> but that's all I can see that's missing.
> ...

(not properly propagating the underlying range's capabilities.)

On Tuesday, June 25, 2013 21:42:17 Timon Gehr wrote:
> On 06/25/2013 09:21 PM, Jonathan M Davis wrote:
> > On Tuesday, June 25, 2013 19:33:32 Timon Gehr wrote:
> >> On 06/25/2013 07:16 PM, Andrei Alexandrescu wrote:
> >>> On 6/25/13 4:47 AM, Timon Gehr wrote:
> >>>> Good point, but takeExactly currently is not a better choice due to its poor quality of implementation.
> >>>> 
> >>>> https://github.com/D-Programming-Language/phobos/blob/master/std/range.
> >>>> d#
> >>>> L2904>
> >>> 
> >>> What's wrong with it?
> >>> 
> >>> Andrei
> >> 
> >> It either has all the overhead of take or does not properly propagate the underlying range's capabilities.
> > 
> > I don't think you're taking into account what take does.
> 
> I think I do.
> 
> > The primary case when
> > takeExactly doesn't use take is when the range doesn't define length, in
> > which case, the best that you can get out of it is a forward range, and
> > that's exactly what it does.
> > 
> > On the other hand, when take is used, it _does_ propagate the original range's capabilites appropriately. take was specifically engineered to avoid wrapping ranges when it doesn't need to, so it shouldn't result in any any extra overhead if it isn't necessary.
> 
> Take will check the wrapped range's 'empty' repeatedly. takeExactly does not need to do that at all.

It only does that with assertions. takeExactly could do exactly the same, or the assertion in Take could be removed. The overhead is gone with -release regardless. The only overhead that's required is the decrementing of the length, and that's required by Take's semantics. takeExactly avoids that because it's able to assume that the underlying range is large enough. Regardless, the overhead for take is minor, but it _is_ better to use takeExactly when you can.

> > I suppose that takeExactly's Result type (in the case where it actually
> > creates its own type) could (and should) forward the primitives associated
> > with hasMobileElements and hasAssignableElements (which it currently
> > doesn't), but that's all I can see that's missing.
> > ...
> 
> (not properly propagating the underlying range's capabilities.)

With regards to a couple of attributes that aren't even used much. Yes, they should be propagated, but you seemed to be saying that there were big problems with takeExactly, whereas the only issue is very minor, and it would be very quick to fix it.

- Jonathan M Davis

On Tuesday, June 25, 2013 16:37:06 Jonathan M Davis wrote:
> On Tuesday, June 25, 2013 21:42:17 Timon Gehr wrote:
> > On 06/25/2013 09:21 PM, Jonathan M Davis wrote:
> > > I suppose that takeExactly's Result type (in the case where it actually
> > > creates its own type) could (and should) forward the primitives
> > > associated
> > > with hasMobileElements and hasAssignableElements (which it currently
> > > doesn't), but that's all I can see that's missing.
> > > ...
> > 
> > (not properly propagating the underlying range's capabilities.)
> 
> With regards to a couple of attributes that aren't even used much. Yes, they should be propagated, but you seemed to be saying that there were big problems with takeExactly, whereas the only issue is very minor, and it would be very quick to fix it.

I would like to thank you for pointing out the missing propagation though. I suspect that those attributes are frequently forgotten. They're less critical than the main ones, but they should still be propagated appropriately.

http://d.puremagic.com/issues/show_bug.cgi?id=10474

- Jonathan M Davis

On 06/25/2013 10:37 PM, Jonathan M Davis wrote:
> On Tuesday, June 25, 2013 21:42:17 Timon Gehr wrote:
>> On 06/25/2013 09:21 PM, Jonathan M Davis wrote:
>>> On Tuesday, June 25, 2013 19:33:32 Timon Gehr wrote:
>>>> On 06/25/2013 07:16 PM, Andrei Alexandrescu wrote:
>>>>> On 6/25/13 4:47 AM, Timon Gehr wrote:
>>>>>> Good point, but takeExactly currently is not a better choice due to its
>>>>>> poor quality of implementation.
>>>>>>
>>>>>> https://github.com/D-Programming-Language/phobos/blob/master/std/range.
>>>>>> d#
>>>>>> L2904>
>>>>>
>>>>> What's wrong with it?
>>>>>
>>>>> Andrei
>>>>
>>>> It either has all the overhead of take or does not properly propagate
>>>> the underlying range's capabilities.
>>>
>>> I don't think you're taking into account what take does.
>>
>> I think I do.
>>
>>> The primary case when
>>> takeExactly doesn't use take is when the range doesn't define length, in
>>> which case, the best that you can get out of it is a forward range, and
>>> that's exactly what it does.
>>>
>>> On the other hand, when take is used, it _does_ propagate the original
>>> range's capabilites appropriately. take was specifically engineered to
>>> avoid wrapping ranges when it doesn't need to, so it shouldn't result in
>>> any any extra overhead if it isn't necessary.
>>
>> Take will check the wrapped range's 'empty' repeatedly. takeExactly does
>> not need to do that at all.
>
> It only does that with assertions. ...

https://github.com/D-Programming-Language/phobos/blob/master/std/range.d#L2648

On Wednesday, June 26, 2013 00:11:29 Timon Gehr wrote:
> On 06/25/2013 10:37 PM, Jonathan M Davis wrote:
> > On Tuesday, June 25, 2013 21:42:17 Timon Gehr wrote:
> >> Take will check the wrapped range's 'empty' repeatedly. takeExactly does not need to do that at all.
> > 
> > It only does that with assertions. ...
> 
> https://github.com/D-Programming-Language/phobos/blob/master/std/range.d#L26 48

Clearly, I missed that. Well, it is true that takeExactly avoids calling empty on the range that it's wrapping in its own empty function, but it's pretty rare that a wrapper range doesn't call the wrapped empty in its own empty function. So, I'd tend to view that as on optimization on takeExactly's part rather than a deficiency on take's part.

Regardless, it's definitely more efficient to use takeExactly when you can. The _only_ benefit to take over takeExactly (assuming that the propagation issue is fixed) is that you don't have to guarantee that the range you're passing it has enough elements. If you know that it does, then takeExactly is better.

- Jonathan M Davis

On Sunday, June 23, 2013 07:47:16 Andrei Alexandrescu wrote:
> On 6/23/13 7:39 AM, Andrei Alexandrescu wrote:
> > Again, we can make things work by introducing a primitive for bidirectional ranges:
> > 
> > R before(R r1, R r2);
> > 
> > Assuming r2 is reachable from r1, returns the portion of r1 that lies before r2. (Definition: a range r2 is reachable from another range r1 if calling r1.popFront() repeatedly will at some point make r1.front and r2.front refer to the same value.)
> 
> The question is, should we add this primitive? There's discussion on adding ranges to C++, and discussion inevitably reaches an impasse when it gets to this particular matter.
> 
> I personally think we should and am amazed that we made it so far
> without that primitive. However, unlike others, I don't think it's an
> essential matter. Some C++ people tend to be apprehensive when they
> figure they can do something with iterators that's not doable with ranges.

I think that we should be very leery of any case where iterators can do more than ranges. That doesn't necessarily mean that when we find something that iterators can do that ranges can't that we should add something new to ranges, but I think that when we find such cases, we should look at them very closely and figure out the best way to work around the problem and how critical a problem it is. There's also a definite cost to adding new range primitives, so I don't think that we want to jump the gun in favor of either adding or not adding new range primitives in order to overcome deficiencies in comparison to iterators.

Unfortunately, I never got around to reading the rfind discussion, so I don't know the details on that (I really should go back and read it), but not being able to do rfind is a major negative IMHO. Bidirectional ranges in general suffer when it comes to doing stuff with their back end, and I think that that becomes particularly clear when doing stuff with containers. So, we may really want to look at what we can do to improve support for stuff on the back end of ranges without having to add a whole lot of new stuff to do it. However, I'll have to study up on the suggested before primitive before I can really comment on whether that particular primitive is something that we should add or not.

Regardless, I think that we would do well to play around more with ranges and std.container in order to determine where the std.container API is weak with regards to ranges. In some cases, that probably means improving the API. In others, it may entail looking closer at whether we need to make any adjustments to the range primitives. Hopefully, we can make everything work well with little to no adjustments to the range API itself, but thus far, containers appear to be one area where iterators are actually considerably better than ranges (at least when it comes to using the iterator or range with the container's functions rather than simply iterating over the elements or passing the iterators or ranges to functions unrelated to the container).

- Jonathan M Davis

On Tuesday, 25 June 2013 at 22:39:07 UTC, Jonathan M Davis wrote:
> On Wednesday, June 26, 2013 00:11:29 Timon Gehr wrote:
>> On 06/25/2013 10:37 PM, Jonathan M Davis wrote:
>> > On Tuesday, June 25, 2013 21:42:17 Timon Gehr wrote:
>> >> Take will check the wrapped range's 'empty' repeatedly. takeExactly does
>> >> not need to do that at all.
>> > 
>> > It only does that with assertions. ...
>> 
>> https://github.com/D-Programming-Language/phobos/blob/master/std/range.d#L26
>> 48
>
> Clearly, I missed that. Well, it is true that takeExactly avoids calling empty
> on the range that it's wrapping in its own empty function, but it's pretty
> rare that a wrapper range doesn't call the wrapped empty in its own empty
> function. So, I'd tend to view that as on optimization on takeExactly's part
> rather than a deficiency on take's part.
>
> Regardless, it's definitely more efficient to use takeExactly when you can. The
> _only_ benefit to take over takeExactly (assuming that the propagation issue is
> fixed) is that you don't have to guarantee that the range you're passing it has
> enough elements. If you know that it does, then takeExactly is better.
>
> - Jonathan M Davis

In regards to Take/TakeExactly, it might be best to implement both as a common struct? eg:

private struct TakeImplementation(bool Exactly = false)
{...}
alias Take = TakeImplementation!false;
private alias TakeExactly = TakeImplementation!true; //TakeExactly is obscure

I mean, at the end of the day, except for "pop", they are basically the same functions... I think it would be better to have a few static ifs in select locations, rather than duplicating everything with subtle differences...