title: Julia - the way of kings (generator performance)
body: <p>I had some python code which I tried to port to Julia to learn this lovely language. I used generators in python. After porting it seems to me (at this moment) that Julia is really slow in this area! </p>
  
  <p>I made part of my code simplified to this exercise:</p>
  
  <p>Think 4x4 chess board. Find every N-moves long path, chess king could do. In this exercise, the king is not allowed to leap twice at the same position in one path. Don't waste memory -> make a generator of every path. </p>
  
  <p>Algorithm is pretty simple:</p>
  
  <p>if we sign every position with numbers:</p>
  
  <pre><code>0  1  2  3
  4  5  6  7
  8  9  10 11
  12 13 14 16
  </code></pre>
  
  <p>point 0 has 3 neighbors (1, 4, 5). We could find a table for every neighbor for every point:</p>
  
  <pre class="lang-py prettyprint-override"><code>NEIG = [[1, 4, 5], [0, 2, 4, 5, 6], [1, 3, 5, 6, 7], [2, 6, 7], [0, 1, 5, 8, 9], [0, 1, 2, 4, 6, 8, 9, 10], [1, 2, 3, 5, 7, 9, 10, 11], [2, 3, 6, 10, 11], [4, 5, 9, 12, 13], [4, 5, 6, 8, 10, 12, 13, 14], [5, 6, 7, 9, 11, 13, 14, 15], [6, 7, 10, 14, 15], [8, 9, 13], [8, 9, 10, 12, 14], [9, 10, 11, 13, 15], [10, 11, 14]]
  </code></pre>
  
  <p><strong>PYTHON</strong> </p>
  
  <p>A recursive function (generator) which enlarge given path from the list of points or from a generator of (generator of ...) points:</p>
  
  <pre class="lang-py prettyprint-override"><code>def enlarge(path):
      if isinstance(path, list):
          for i in NEIG[path[-1]]:
              if i not in path:
                  yield path[:] + [i]
      else:
          for i in path:
              yield from enlarge(i)
  </code></pre>
  
  <p>Function (generator) which give every path with given length</p>
  
  <pre class="lang-py prettyprint-override"><code>def paths(length):
      steps = ([i] for i in range(16))  # first steps on every point on board
      for _ in range(length-1):
          nsteps = enlarge(steps)
          steps = nsteps
      yield from steps
  </code></pre>
  
  <p>We could see that there are 905776 paths with length 10:</p>
  
  <pre class="lang-py prettyprint-override"><code>sum(1 for i in paths(10))
  Out[89]: 905776
  </code></pre>
  
  <p><strong>JULIA</strong> 
  (<a href="https://gist.github.com/ggggggggg/9ae47879dc131a48b805ce7ec88a10ac" rel="nofollow noreferrer">this code</a> was created by @gggg during our discussion <a href="https://stackoverflow.com/questions/46894052/julian-way-to-do-pythons-yield-and-yield-from">here</a> )</p>
  
  <pre><code>const NEIG_py = [[1, 4, 5], [0, 2, 4, 5, 6], [1, 3, 5, 6, 7], [2, 6, 7], [0, 1, 5, 8, 9], [0, 1, 2, 4, 6, 8, 9, 10], [1, 2, 3, 5, 7, 9, 10, 11], [2, 3, 6, 10, 11], [4, 5, 9, 12, 13], [4, 5, 6, 8, 10, 12, 13, 14], [5, 6, 7, 9, 11, 13, 14, 15], [6, 7, 10, 14, 15], [8, 9, 13], [8, 9, 10, 12, 14], [9, 10, 11, 13, 15], [10, 11, 14]];
  const NEIG = [n.+1 for n in NEIG_py]
  function enlarge(path::Vector{Int})
      (push!(copy(path),loc) for loc in NEIG[path[end]] if !(loc in path))
  end
  collect(enlarge([1]))
  function enlargepaths(paths)
      Iterators.Flatten(enlarge(path) for path in paths)
  end
  collect(enlargepaths([[1],[2]]))
  function paths(targetlen)
      paths = ([i] for i=1:16)
      for newlen in 2:targetlen
          paths = enlargepaths(paths)
      end
      paths
  end
  p = sum(1 for path in paths(10))
  </code></pre>
  
  <p><strong>benchmark</strong></p>
  
  <p>In ipython we could time it:</p>
  
  <p>python 3.6.3:
  </p>
  
  <pre><code>%timeit sum(1 for i in paths(10))
  1.25 s ± 15.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  </code></pre>
  
  <p>julia 0.6.0</p>
  
  <pre><code>julia&gt; @time sum(1 for path in paths(10))
    2.690630 seconds (41.91 M allocations: 1.635 GiB, 11.39% gc time)
  905776
  </code></pre>
  
  <p>Julia 0.7.0-DEV.0</p>
  
  <pre><code>julia&gt; @time sum(1 for path in paths(10))
    4.951745 seconds (35.69 M allocations: 1.504 GiB, 4.31% gc time)
  905776
  </code></pre>
  
  <p><strong>Question(s):</strong></p>
  
  <p>We Julians are <a href="https://julialang.org/benchmarks/" rel="nofollow noreferrer">saying this</a>: <em>It is important to note that the benchmark codes are not written for absolute maximal performance (the fastest code to compute recursion_fibonacci(20) is the constant literal 6765). Instead, the benchmarks are written to test the performance of identical algorithms and code patterns implemented in each language.</em> </p>
  
  <p>In this benchmark, we are using the same idea. Just simple for cycles over arrays enclosed to generators. (Nothing from numpy, numba, pandas or others c-written and compiled python packages)</p>
  
  <p>Is assumption that Julia's generators are terribly slow right? </p>
  
  <p>What could we do to make it really fast? </p>