www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - joiner and map, strange behavior

reply "Stephan Schiffels" <stephan_schiffels mac.com> writes:
Hi,

I am struggling with understanding this behavior. In the code 
below, the function "getVec" is called 8 times, but it should be 
called only 4 times (once for each call inside of map).

Any explanations?

Stephan


import std.stdio;
import std.algorithm;
import std.array;

int[] getVec(size_t i) {
   writeln("getVec is called");
   auto vals = [
     [1, 2, 3, 4],
     [5, 6, 7, 8],
     [9, 10, 11, 12],
     [13, 14, 15, 16]
   ];
   return vals[i];
}


void main() {

   auto result = [0, 1, 2, 3].map!(getVec).joiner.array;
   writeln(result);

}
Mar 12 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Stephan Schiffels:


 I am struggling with understanding this behavior. In the code 
 below, the function "getVec" is called 8 times, but it should 
 be called only 4 times (once for each call inside of map).

 Any explanations?


Maybe it's a matter of calling front() more times, as in filter 
in a recent thread. To be sure take a look inside phobos sources.

By the way, your code is quite inefficient, because it allocates 
a new matrix at each call to getVec.

Bye,
bearophile
Mar 12 2013
parent reply "Stephan Schiffels" <stephan_schiffels mac.com> writes:
On Tuesday, 12 March 2013 at 17:43:43 UTC, bearophile wrote:

 Stephan Schiffels:


 I am struggling with understanding this behavior. In the code 
 below, the function "getVec" is called 8 times, but it should 
 be called only 4 times (once for each call inside of map).

 Any explanations?


 Maybe it's a matter of calling front() more times, as in filter 
 in a recent thread. To be sure take a look inside phobos 
 sources.

 By the way, your code is quite inefficient, because it 
 allocates a new matrix at each call to getVec.

 Bye,
 bearophile


Thanks, I had a brief look at std.algorithm.joiner but couldn't 
find anything obvious, maybe I should look deeper into it.

And yes, the example is quite bad. This version of getVec would 
have been better to illustrate:

import std.range;
auto getVec(size_t i) {
   writeln("getVec is called");
   return iota(i * 4, (i + 1) * 4);
}

Stephan
Mar 12 2013
next sibling parent "lomereiter" <lomereiter gmail.com> writes:
Current implementation of joiner accesses each element two times 
- first, in a loop which skips empty ranges, plus after the loop 
assignment to a variable occurs:

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

On Tuesday, 12 March 2013 at 17:51:57 UTC, Stephan Schiffels 
wrote:

 

 Thanks, I had a brief look at std.algorithm.joiner but couldn't


 find anything obvious, maybe I should look deeper into it.
Mar 12 2013
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 03/12/2013 06:51 PM, Stephan Schiffels wrote:

 ...

 Thanks, I had a brief look at std.algorithm.joiner but couldn't find
 anything obvious, maybe I should look deeper into it.
 ...


I guess it is because of the following:

Eg (similar code occurs two times):
...
     if (_sep.empty)
     {
         // Advance to the next range in the
         // input
         //_items.popFront();
         for (;; _items.popFront())
         {
             if (_items.empty) return;
             if (!_items.front.empty) break; // front called
         }
         _current = _items.front; // front called again
         _items.popFront();
     }
...

The code should only call front once for the first non-empty range.

Presumed example fix (though the implementation seems rather clumsy and 
should probably be replaced completely):

...
     if (_sep.empty)
     {
         // Advance to the next range in the
         // input
         //_items.popFront();
         for (;; _items.popFront())
         {
             if (_items.empty) return;
             _current = _items.front;
             if (!_current.empty) break;
         }
         _items.popFront();
     }
...
Mar 12 2013
parent reply Stephan Schiffels <stephan_schiffels mac.com> writes:
Am 12.03.13 20:22, schrieb Timon Gehr:

 On 03/12/2013 06:51 PM, Stephan Schiffels wrote:

 ...

 Thanks, I had a brief look at std.algorithm.joiner but couldn't find
 anything obvious, maybe I should look deeper into it.
 ...


 I guess it is because of the following:

 Eg (similar code occurs two times):
 ...
      if (_sep.empty)
      {
          // Advance to the next range in the
          // input
          //_items.popFront();
          for (;; _items.popFront())
          {
              if (_items.empty) return;
              if (!_items.front.empty) break; // front called
          }
          _current = _items.front; // front called again
          _items.popFront();
      }
 ...

 The code should only call front once for the first non-empty range.

 Presumed example fix (though the implementation seems rather clumsy and
 should probably be replaced completely):

 ...
      if (_sep.empty)
      {
          // Advance to the next range in the
          // input
          //_items.popFront();
          for (;; _items.popFront())
          {
              if (_items.empty) return;
              _current = _items.front;
              if (!_current.empty) break;
          }
          _items.popFront();
      }
 ...


Thanks, that's very clear now. I stumbled over it because the function I 
call loads a lot of data and a factor 2 makes all the difference in 
runtime. Maybe I should file a bug report or at least a request to 
improve this.

Stephan
Mar 12 2013
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Mar 13, 2013 at 12:22:48AM +0000, Stephan Schiffels wrote:

 Am 12.03.13 20:22, schrieb Timon Gehr:

On 03/12/2013 06:51 PM, Stephan Schiffels wrote:

...

Thanks, I had a brief look at std.algorithm.joiner but couldn't find
anything obvious, maybe I should look deeper into it.
...


I guess it is because of the following:

Eg (similar code occurs two times):
...
     if (_sep.empty)
     {
         // Advance to the next range in the
         // input
         //_items.popFront();
         for (;; _items.popFront())
         {
             if (_items.empty) return;
             if (!_items.front.empty) break; // front called
         }
         _current = _items.front; // front called again
         _items.popFront();
     }
...

The code should only call front once for the first non-empty range.

Presumed example fix (though the implementation seems rather clumsy and
should probably be replaced completely):

...
     if (_sep.empty)
     {
         // Advance to the next range in the
         // input
         //_items.popFront();
         for (;; _items.popFront())
         {
             if (_items.empty) return;
             _current = _items.front;
             if (!_current.empty) break;
         }
         _items.popFront();
     }
...


 
 Thanks, that's very clear now. I stumbled over it because the
 function I call loads a lot of data and a factor 2 makes all the
 difference in runtime. Maybe I should file a bug report or at least
 a request to improve this.


[...]

I was the one responsible for the recent rewrite of joiner; I'll think
over how to fix it so that .front is only evaluated once.


T

-- 
Старый друг лучше новых двух.
Mar 12 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
H. S. Teoh:


 I was the one responsible for the recent rewrite of joiner; 
 I'll think
 over how to fix it so that .front is only evaluated once.


This is a strictly related issue, about filter:
http://d.puremagic.com/issues/show_bug.cgi?id=9674

Bye,
bearophile
Mar 12 2013