www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - front evaluated multiple time with joiner depending on where extra

reply Timothee Cour <thelastmammoth gmail.com> writes:
Does that make sense? feature or bug?

void main(){
  import std.algorithm;
  import std.array;
  {
    int counter=0;
    auto b=[1,2,3].map!(a=>{counter++; return [a];}()).joiner([0]).array;
    assert(counter==3);
  }
  {
    int counter=0;
    auto b=[1,2,3].map!(a=>{counter++; return [a];}()).joiner().array;
    assert(counter==6);//why 6 whereas other one was 3?
  }
}
Oct 22 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Timothee Cour:


     auto b=[1,2,3].map!(a=>{counter++; return 
 [a];}()).joiner([0]).array;


Currently there are some problems inside some of the higher order 
functions of Phobos. So as general rule don't put impure code 
inside the functions (usually lambdas) you pass to the higher 
order functions like map, filter, etc.

By the way, a more readable way to put more commands inside a 
lambda should be:

(a){ counter++; return [a]; }

Bye,
bearophile
Oct 22 2013
next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, October 23, 2013 02:21:55 bearophile wrote:

 Timothee Cour:

 auto b=[1,2,3].map!(a=>{counter++; return
 
 [a];}()).joiner([0]).array;


 
 Currently there are some problems inside some of the higher order
 functions of Phobos. So as general rule don't put impure code
 inside the functions (usually lambdas) you pass to the higher
 order functions like map, filter, etc.


Conceptually, front should be pure, but there's no reason that you can't throw 
some impure stuff in there like in this example - particularly if it's just for 
something like tracking the number of calls made. What falls apart is if front 
returns a different result without popFront being called again or front not 
being able to be called multiple times before popFront is called.

As for the multiple calls to front, there is no guarantee as to how many times 
front will be called by a particular function. A function may call front once 
and then reuse the result, or it may call front multiple times. It depends 
entirely on what it's doing. It's also quite possible that different overloads 
end up needing front a different number of times, which could result in a 
differing number of calls. But it could be argued whether it's generally more 
efficient to call front once and reuse the result or to call front multiple 
times as which is more efficient depends on stuff like how expensive it is to 
copy the element type, whether front returns by ref (possibly avoiding a 
copy), and whether front calculates anything or just returns the current 
front. Certainly, I'd argue that it's generally better practice to do the work 
in popFront, because front does frequently gets called multiple times, and you 
almost always end up calling front if you call popFront.

It's possible that map, joiner, and or array could use some efficiency 
improvements, but I wouldn't consider the difference in the number of calls to 
front to be a bug. At most, it might indicate that there are some optimization 
opportunities in one or more of those functions, and it might even be that the 
differing number of calls makes sense when you actually dig into the source 
code. I'd have to go digging to know for sure.

- Jonathan M Davis
Oct 22 2013
prev sibling parent Timothee Cour <thelastmammoth gmail.com> writes:
 Certainly, I'd argue that it's generally better practice to do the work
 in popFront, because front does frequently gets called multiple times, and
 you
 almost always end up calling front if you call popFront.


Actually, the way phobos is designed, often times it's easier to specify
what front does, eg with map and related functions.



 It's possible that map, joiner, and or array could use some efficiency
 improvements, but I wouldn't consider the difference in the number of
 calls to
 front to be a bug. At most, it might indicate that there are some
 optimization
 opportunities in one or more of those functions, and it might even be that
 the
 differing number of calls makes sense when you actually dig into the source
 code. I'd have to go digging to know for sure.



it's not just an issue of optimization opportunities, it's an issue of
correctness and principle of least surprise; the code I shown was simplied
from a larger bug I had where I was doing side effects in the map lambda
that were meant to be called once per element instead of multiple times.

Is there a convenient to achieve the same effect as this:

elements.map ! fun_with_side_effects . joiner . do_something_with_result

but such that fun_with_side_effects is called only once per element ?
(likewise with other functions that operate on ranges).

As it is, joiner and friends is dangerous to use with generic code because
of that. std.array.{array,join} doesn't have this issue.

why not modify joiner (+friends) so that:
if front() is pure, allow calling it multiple times
if not, make sure to call it only once per element
Oct 22 2013
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, October 22, 2013 19:54:18 Timothee Cour wrote:

 Certainly, I'd argue that it's generally better practice to do the work
 in popFront, because front does frequently gets called multiple times, and
 you
 almost always end up calling front if you call popFront.


 
 Actually, the way phobos is designed, often times it's easier to specify
 what front does, eg with map and related functions.


By putting the logic for calculating the element in popFront, you incur 
less of a performance hit. front will frequently get called multiple times per 
element, whereas popFront will only be called once, and it's rare that 
popFront would be called without front being called.


 It's possible that map, joiner, and or array could use some efficiency
 improvements, but I wouldn't consider the difference in the number of
 calls to
 front to be a bug. At most, it might indicate that there are some
 optimization
 opportunities in one or more of those functions, and it might even be that
 the
 differing number of calls makes sense when you actually dig into the
 source
 code. I'd have to go digging to know for sure.


 
 it's not just an issue of optimization opportunities, it's an issue of
 correctness and principle of least surprise; the code I shown was simplied
 from a larger bug I had where I was doing side effects in the map lambda
 that were meant to be called once per element instead of multiple times.


It's just plain wrong for front to have side effects. You _cannot_ rely on 
front being called once per element by any particular range-based function. 
You can add side effects for debugging or whatnot, but if it has any effect on 
the behavior of your program, then it's wrong. Even if front as a getter 
property is not actually const or pure, it needs to be logically const and 
logically pure. If you want to do something once per element, then you need to 
create a wrapper that does that in popFront. popFront is the _only_ function 
that's guaranteed to be only called once per element when iterating over a 
range. And even then, if you're dealing with forward ranges, then the range 
could have been saved and have popFront called on the same element in multiple 
copies of the range, so if you're doing something in state outside of the 
range itself, then you could still be having that something happen more than 
once per element.

In general, if you want to do something once per element which involves side 
effects, I would advise using foreach rather than trying to put it into a 
range. But if you insist on doing so, the side effect should go in popFront, 
not front, or the side effects will often be happening more than once per 
element.

- Jonathan M Davis
Oct 22 2013
prev sibling parent Timothee Cour <thelastmammoth gmail.com> writes:
 In general, if you want to do something once per element which involves
 side
 effects, I would advise using foreach rather than trying to put it into a
 range.



using foreach breaks UFCS chains, and also ElementType != ForeachType



 But if you insist on doing so, the side effect should go in popFront,
 not front, or the side effects will often be happening more than once per
 element.


This won't work if side effect should occur _before_ element is popped. And
this is very awkward to use with map/reduce/filter, as it forces one to
write explicitly a range wrapper, defeating purpose of reusing phobos
components. Having to write a custom range (with pop/front/popBack etc)
just to support lambdas with side effects is a pain.

I'd like to propose a generic solution for that, see the email I just sent:

"std.range.cacheFront proposal&working code: wraps a range to enforce front
is called only once"
Oct 22 2013