On 12/01/2017 07:21 AM, Steven Schveighoffer wrote:
> On 12/1/17 4:29 AM, Johan Engelen wrote:

>> (Also, I would expect "popFront" to return the element popped, but it
>> doesn't, OK...
>
> pop removes the front element, but if getting the front element is
> expensive (say if it's a map with a complex lambda function), you don't
> want to execute that just so you can return it to someone who doesn't
> care. This is why front and popFront are separate.

Yet, we're told that compilers are pretty good at eliminating that unused copy especially for function templates where all code is visible.

[I have second thoughts about what I write below. Bear with me...]

I think the actual reason is one that I learned in C++ circles which I will never forget as I was lurking on comp.lang.c++.moderated as the whole exception safety was discussed, finally solved, and popularized by Herb Sutter.

So, even thoug exception safety is not a common topic of D community, the real reason for why popFront() does not return the element is for strong exception safety guarantee. Otherwise, it's not possible to recover from a post-blit that may throw. The reason is, popFront() must change the structure of the container *before* the returned object must be copied. When the copying throws, then the element is already lost from the container.

However, there are two potential solutions that I think of:

- D could move the element out; so no post-blit would be necessary. However, as we see in moveFront()'s source code, it might have to call a provided moveFront() and that might throw:

    static if (is(typeof(&r.moveFront)))
    {
        return r.moveFront();
    }

- D has scope(failure) which could revert the container's state but I don't think it's possible for all containers. (And I should have said "ranges".)

Regardless, separating front() from popFront() is preferable due to cohesion: fewer responsibilities per function, especially such low level ones.

Ali

On 12/1/17 1:33 PM, Ali Çehreli wrote:
> On 12/01/2017 07:21 AM, Steven Schveighoffer wrote:
>  > On 12/1/17 4:29 AM, Johan Engelen wrote:
> 
>  >> (Also, I would expect "popFront" to return the element popped, but it
>  >> doesn't, OK...
>  >
>  > pop removes the front element, but if getting the front element is
>  > expensive (say if it's a map with a complex lambda function), you don't
>  > want to execute that just so you can return it to someone who doesn't
>  > care. This is why front and popFront are separate.
> 
> Yet, we're told that compilers are pretty good at eliminating that unused copy especially for function templates where all code is visible.

yes, true. But this is not something to rely on, and it's not always possible.

> [I have second thoughts about what I write below. Bear with me...]
> 
> I think the actual reason is one that I learned in C++ circles which I will never forget as I was lurking on comp.lang.c++.moderated as the whole exception safety was discussed, finally solved, and popularized by Herb Sutter.
> 
> So, even thoug exception safety is not a common topic of D community, the real reason for why popFront() does not return the element is for strong exception safety guarantee. Otherwise, it's not possible to recover from a post-blit that may throw. The reason is, popFront() must change the structure of the container *before* the returned object must be copied. When the copying throws, then the element is already lost from the container.

Hm... yes this is a more pressing problem. But I don't know if it has to do with exception safety vs. purely implementation concerns. I remember discussions about such a wrapper, and a case where it breaks down is byLine.

Once you popFront a byLine range, the element that was at front is now possibly invalid (the buffer may be reused). So in order to return the line from popFront, you have to store it somewhere. This means allocating another buffer to hold the line you just returned. So the costs of doing this aren't just that you might do work and just throw it away, it's that you have this extra caching problem you didn't have before.

> However, there are two potential solutions that I think of:
> 
> - D could move the element out; so no post-blit would be necessary. However, as we see in moveFront()'s source code, it might have to call a provided moveFront() and that might throw:
> 
>      static if (is(typeof(&r.moveFront)))
>      {
>          return r.moveFront();
>      }

For byLine, this is a non-starter. You can't move the whole thing into the return value, as it's referenced data. You'd have to allocate.

> - D has scope(failure) which could revert the container's state but I don't think it's possible for all containers. (And I should have said "ranges".)

Most definitely, ranges never expand.

-Steve

On Friday, 1 December 2017 at 18:33:09 UTC, Ali Çehreli wrote:
> On 12/01/2017 07:21 AM, Steven Schveighoffer wrote:
> > On 12/1/17 4:29 AM, Johan Engelen wrote:
>
> >> (Also, I would expect "popFront" to return the element
> popped, but it
> >> doesn't, OK...
> >
> > pop removes the front element, but if getting the front
> element is
> > expensive (say if it's a map with a complex lambda function),
> you don't
> > want to execute that just so you can return it to someone who
> doesn't
> > care. This is why front and popFront are separate.
>
> Yet, we're told that compilers are pretty good at eliminating that unused copy especially for function templates where all code is visible.

I assume that Steven means "copying the front element" when he wrote "getting the front element"? There is no need for a copy, because the element will be removed from the range, so we can move (whose cost only depends on the size of the element, internal pointers being disallowed by the language).
If it is expensive to actually get _to_ the front/back element (i.e. find its memory location), then having to do the operation twice is a disadvantage.

Ali: the compiler can only elide copying/moving of an unused return value when inlining the function. (the duty of making the return value move/copy is on the callee, not the caller)

Note that because front/back() and popFront/Back() are separate, a copy *is* needed when one wants to "pop an element off". Thus moveFront/Back() and popFront/Back() should be used. OK.
The fact that "pop" does something different from other programming languages is something important to remember when teaching people about D. And I think should be made clear in the documentation; let's add an example of how one is supposed to use all this in an efficient manner?

Back on topic: let's change the documentation of moveFront such that it is clear that it does _not_ reduce the number of elements in the range?

> So, even though exception safety is not a common topic of D community, the real reason for why popFront() does not return the element is for strong exception safety guarantee.

Interesting point. Argh why do we allow the user to throw in move?

> Regardless, separating front() from popFront() is preferable due to cohesion: fewer responsibilities per function, especially such low level ones.

This doesn't make much sense ;-)
popFrontN has more responsibility, and one gains better performance than simply calling popFront N times. It's similar here.

-Johan

On Friday, 1 December 2017 at 18:55:53 UTC, Steven Schveighoffer wrote:
>
> Once you popFront a byLine range, the element that was at front is now possibly invalid (the buffer may be reused). So in order to return the line from popFront, you have to store it somewhere. This means allocating another buffer to hold the line you just returned. So the costs of doing this aren't just that you might do work and just throw it away, it's that you have this extra caching problem you didn't have before.

Cool, thanks.
Can we add points like this to the documentation?
(if not, user frustration and forum threads will keep coming about these things... ;-)

-Johan

On 12/3/17 12:42 AM, Johan Engelen wrote:
> On Friday, 1 December 2017 at 18:33:09 UTC, Ali Çehreli wrote:
>> On 12/01/2017 07:21 AM, Steven Schveighoffer wrote:
>> > On 12/1/17 4:29 AM, Johan Engelen wrote:
>>
>> >> (Also, I would expect "popFront" to return the element
>> popped, but it
>> >> doesn't, OK...
>> >
>> > pop removes the front element, but if getting the front
>> element is
>> > expensive (say if it's a map with a complex lambda function),
>> you don't
>> > want to execute that just so you can return it to someone who
>> doesn't
>> > care. This is why front and popFront are separate.
>>
>> Yet, we're told that compilers are pretty good at eliminating that unused copy especially for function templates where all code is visible.
> 
> I assume that Steven means "copying the front element" when he wrote "getting the front element"?

No I mean generating the front element. For example:

auto m = [1, 2, 3].map!(a => reallyExpensiveFunction(a));

Each time you call front, it's going to be really expensive. If you aren't going to use it, then generating it is wasted cycles.

(BTW, I said "pop" when I meant "popFront", sorry for *that* confusion too!)

> There is no need for a copy, because the element will be removed from the range, so we can move (whose cost only depends on the size of the element, internal pointers being disallowed by the language).

Yeah, this wasn't my concern, sorry for being ambiguous.

-Steve

On 12/03/2017 12:42 AM, Johan Engelen wrote:
> On Friday, 1 December 2017 at 18:33:09 UTC, Ali Çehreli wrote:
>> On 12/01/2017 07:21 AM, Steven Schveighoffer wrote:
>> > On 12/1/17 4:29 AM, Johan Engelen wrote:
>>
>> >> (Also, I would expect "popFront" to return the element
>> popped, but it
>> >> doesn't, OK...
>> >
>> > pop removes the front element, but if getting the front
>> element is
>> > expensive (say if it's a map with a complex lambda function),
>> you don't
>> > want to execute that just so you can return it to someone who
>> doesn't
>> > care. This is why front and popFront are separate.
>>
>> Yet, we're told that compilers are pretty good at eliminating that unused copy especially for function templates where all code is visible.
> 
> I assume that Steven means "copying the front element" when he wrote "getting the front element"? There is no need for a copy, because the element will be removed from the range, so we can move (whose cost only depends on the size of the element, internal pointers being disallowed by the language).
> If it is expensive to actually get _to_ the front/back element (i.e. find its memory location), then having to do the operation twice is a disadvantage.
> 
> Ali: the compiler can only elide copying/moving of an unused return value when inlining the function. (the duty of making the return value move/copy is on the callee, not the caller)
> 
> Note that because front/back() and popFront/Back() are separate, a copy *is* needed when one wants to "pop an element off". Thus moveFront/Back() and popFront/Back() should be used. OK.
> The fact that "pop" does something different from other programming languages is something important to remember when teaching people about D. And I think should be made clear in the documentation; let's add an example of how one is supposed to use all this in an efficient manner?
> 
> Back on topic: let's change the documentation of moveFront such that it is clear that it does _not_ reduce the number of elements in the range?
> 
>> So, even though exception safety is not a common topic of D community, the real reason for why popFront() does not return the element is for strong exception safety guarantee.
> 
> Interesting point. Argh why do we allow the user to throw in move?
> 
>> Regardless, separating front() from popFront() is preferable due to cohesion: fewer responsibilities per function, especially such low level ones.
> 
> This doesn't make much sense ;-)
> popFrontN has more responsibility, and one gains better performance than simply calling popFront N times. It's similar here.

Thanks Ali for asking me to comment in this thread. The matter of fact is moveFront was needed for different purposes.

First off, moving in D cannot throw; all objects are moveable by means of bitwise move.

The main reason for moveFront's existence is supporting ranges that have front() return an rvalue. For those, there would otherwise be no efficient means to move data out of the range to its user.

Now, why does popFront return void instead of the popped element? We need front() anyway as a non-destructive way to look at the current element of the range, so having popFront return that element is redundant. Plus, it's difficult to optimize away particularly in separately compiled code.


Andrei