Hacker News Reader

Comment by jnbiche | Hacker News Reader

> Try running a nested loop on a non-trivial example, and you can end up spending minutes in what would take milliseconds in any other language.

Huh? Can you provide an example? There's nothing about writing nested loops in Python that is qualitatively different from other languages.

> If you want to program in Python, you must get used to the functional paradigm. Not "should", "must".

This is incorrect, much to my chagrin. Python's trend over the past few years has been not only not to encourage functional programming, but to explicitly discourage functional programming. For example, starting in Python 3, `reduce` has been banished from the language proper to the standard library.

View on HN

Huh? Can you provide an example?

Well he did mention numpy and obviously doing something that can be done in numpy with nested loops will be much much slower. However that is as much a case of numpy being really fast as python being slow.

For example, just tested elementwise multiplication of two 10kX10k matrices and with numpy and numpy arrays it took ~350 ms vs ~15 seconds with a nested for loops and python lists. Still minutes vs. milliseconds seems like extreme hyperbole.

edit: Figured I'd test how long the naive nested loop approach would take in a 'fast' language like Julia, and much to my surprise it took over 50 seconds.

edit2: cleaned up all my code to try to make it as similar as possible across both languages:

Nested for loops python 2.7: ~30 seconds

Nested for loops Julia 4.6; ~50 seconds

Nested for loops PyPy 5.3.1 ~0.9 seconds

Make of these numbers what you will

Could you post the Julia code? Unfortunately, you do have to make sure that the types are correctly inferred by the compiler in high-performance loops. Or maybe you used a global.

http://docs.julialang.org/en/release-0.4/manual/performance-...

I'll admit I don't really know that much Julia and basically wrote naive MATLAB code (and I wanted to make it as close as possible to my python code):

  s=10000;
  a=ones(s,s);
  b=ones(s,s);
  c=zeros(s,s);

  tic();
  for i in 1:s
    for j in 1:s
      c[i,j]=a[i,j]*b[i,j]
    end
  end
  toc();

Obviously in real code I'd simple write

  c=a.*b

and get basically the same performance as numpy

It looks like this was done at global scope. It's important to wrap things in a function for maximum performance - AFAIK, because method dispatch and precompilation happen at the function level, functions are much much faster than not functions.

Julia also stores its arrays column major, so put the outer loop over columns for another order of magnitude performance increase. (I'm not sure I love this feature, but presumably there's a reason...maybe for better performance on matrix operations?) My reply to your grandparent comment has a simple implementation that runs in 0.4 seconds on an aging machine.

Tarrosion is right, on my machine, putting the code inside a function is 10X faster, and then swapping the order of the loops gives another 10X improvement:

    function f(s)
      a=ones(s,s);
      b=ones(s,s);
      c=zeros(s,s);

      tic();
      for j in 1:s
         for i in 1:s
          c[i,j]=a[i,j]*b[i,j]
         end
      end
      toc();
      return c
    end

Note that you also might have to run the function twice, because the first time JIT-compilation kicks in.

Julia 0.5 also now automatically devectorizes some code (eg. x = a .* b .+ c) so that you don't have to write explicit loops to get performance benefits.

Thanks. To both you and Tarrosion.

Guess I need to take some time at some point to sit down and actually learn 'proper' Julia.

Based purely on my experience with native CPython, I have usually found for loops to be a bottleneck - and nested list comprehensions to be the saviour.

I wonder what the difference would look like then?

I've been using Julia a lot lately so these results really surprised me, and I wrote my own test. Punchline: it takes about 0.4 seconds on Julia 0.4.6, on my machine which is several years old. Check it out:

julia> include("elmult.jl")

eachindex

0.42587028

outer loop over rows

8.923323015

outer loop over cols

0.516270241

Code:

    function elmult(m1, m2)
       result = zeros(m1)
       for i in eachindex(m1)
           result[i] = m1[i] * m2[i]
       end
       return result
    end

    function elmult_rowmajor(m1, m2)
        result = zeros(m1)
        nr = size(m1, 1)
        nc = size(m1, 2)
        for i in 1:nr, j in 1:nc
            result[i,j] = m1[i,j] * m2[i,j]
        end
        return result
    end

    function elmult_colmajor(m1, m2)
        result = zeros(m1)
        nr = size(m1, 1)
        nc = size(m1, 2)
        for j in 1:nc, i in 1:nr
            result[i,j] = m1[i,j] * m2[i,j]
        end
        return result
    end

    elmult(rand(3,3), rand(3,3))
    elmult_colmajor(rand(3,3), rand(3,3))
    elmult_rowmajor(rand(3,3), rand(3,3))

    m1, m2 = rand(10000,10000), rand(10000, 10000);

    println("eachindex")
    println(@elapsed elmult(m1, m2))
    println("outer loop over rows")
    println(@elapsed elmult_rowmajor(m1, m2))
    println("outer loop over cols")
    println(@elapsed elmult_colmajor(m1, m2))

> Can you provide an example?

Gladly. Check the nested loop in [1]. That's exactly what I fought against (although that's not me asking that question). No other language AFAIK suffers from that issue.

[1] http://stackoverflow.com/questions/8097408/why-python-is-so-...

1) That particular example is 10 or 20 seconds on CPython, depending on CPython version, machine, etc.

2) With the exception of Luajit and JS, any dynamic interpreted language will take in the range of 5-20 secs to run equivalent code. I'm pretty sure Ruby and PHP are in the same range, no time to benchmark it now. Besides, if you use the Pythonic version of this loop (using list comprehensions), it will take more like 5 or 10 seconds and not 20. Run the same code on Pypy, and it takes under a second.

3) In any case, if performance is really an issue, the correct answer (as the parent discovered) is to use Numpy or Cython or C extensions for that part of the code. This is not uncommon knowledge.

4) I've been using Python in production for a decade and have never thought of this (~0.2 vs ~10 secs) as a problem because I never used pure Python for critical numeric code (or Ruby, or even JS). I did that in C or Cython, or Numpy (or OCaml, on one occasion). If I had to do something like that now, I'd probably use Rust and call it from Python (assuming I was writing the app in Python).

5) Any language has edge cases like this that can surprise you if you're not familiar with the ecosystem. The higher the level of abstraction, the more edge cases. Look at even the Julia thread directly below this one. It's a massive difference between the naive, Julia beginner version (no offense, I would have written it the same way, probably) and the experienced Julia programmer version. Even a language like Go has performance gotchas.

Python certainly has it's problems (like building large, robust programs, although that's being actively addressed with MyPy types), but I honestly don't agree that this is one of them.

Show me an example that uses `reduce` with a function other than sum/product that makes it clearer than the equivalent loop.

Reduce doesn't have side effects, handles an empty collection, doesn't need to reference the index of the iterable, and self-documents the code as a fold. I find the last part nice because a loop or a Python comprehension would need to add a comment to explain what would otherwise be clear from the syntax.

Here's an alternative example where I think it makes sense (checking if the size of all elements in a collection are equal):

  reduce(lambda a, b: len(a) == len(b), ls)

I don't think that does what you think it does:

  >>> reduce(lambda a, b: len(a) == len(b), ["a", "b", "c"])
  Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    File "<stdin>", line 1, in <lambda>
  TypeError: object of type 'bool' has no len()

It's trying to do len(len("a") == len("b")) == len("c"), which becomes len(True) == len("c"), and len(True) doesn't work.

Some variations which do work are:

  len(set(map(len, ls))) == 1
  len(set(len(x) for x in ls)) == 1
  all(len(ls[0]) == len(x) for x in ls)
  len(min(ls, key=len)) == len(max(ls, key=len))

Append "if ls else True" to handle the empty list.

> I don't think that does what you think it does:

Heh, just proved my point. Reduce won't be missed.

Ouch, good catch! I can't think of a nice way to salvage reduce but these are some clever alternatives. Point anti-reduce.

This doesn't salvage it in any meaningful sense, but it does work:

  class EqualLengths:
    def __init__(self, size):
      self.size = size
    def __nonzero__(self):
      return True
    def __repr__(self):
      return "True"
  
  def equal_lengths(a, b):
    if isinstance(a, EqualLengths):
      if a.size == len(b):
        return a
      return False
    if a is False:
      return a
    n = len(a)
    if n == len(b):
      return EqualLengths(n)
    return False

  >>> reduce(equal_lengths, ["a", "b", "cc", "d"])
  False
  >>> reduce(equal_lengths, ["a", "b", "c", "d"])
  True

However, I could do something similar with sum():

  class SumEqual:
    def __init__(self):
      self.size = None
      self.is_equal = True
        
    def __add__(self, other):
      if self.is_equal:
        if self.size is None:
          self.size = len(other)
        else:
          self.is_equal = (self.size == len(other))
      return self
      
    def __nonzero__(self):
      return self.is_equal
      
    def __repr__(self):
      return repr(self.is_equal)


  >>> sum(["a", "b", "cc", "d"], SumEqual())
  False
  >>> sum(["a", "b", "c", "d"], SumEqual())
  True

and unlike the first case, this sum() solution will work when there are fewer than two items in the list.

Reply on news.ycombinator.com