4 ms·

> 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

by jnbiche 10y ago

> 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.

dagw 10y ago
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
- ced 10y ago
  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-tips/ http://docs.julialang.org/en/release-0.4/manual/performance-...
  - dagw 10y ago
    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
    - Tarrosion 10y ago
      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.
    - ced 10y ago
      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.
      - dagw 10y ago
        Thanks. To both you and Tarrosion. Guess I need to take some time at some point to sit down and actually learn 'proper' Julia.
- shakna 10y ago
  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?
- Tarrosion 10y ago
  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))
reinhardt 10y ago
Show me an example that uses `reduce` with a function other than sum/product that makes it clearer than the equivalent loop.
- ramblenode 10y ago
  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)
  - dalke 10y ago
    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.
    - reinhardt 10y ago
      > I don't think that does what you think it does: Heh, just proved my point. Reduce won't be missed.
    - ramblenode 10y ago
      Ouch, good catch! I can't think of a nice way to salvage reduce but these are some clever alternatives. Point anti-reduce.
      - 10y ago
probably_wrong 10y ago
> 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-slow-for-a-simple-for-loop#8097669 http://stackoverflow.com/questions/8097408/why-python-is-so-...
- jnbiche 10y ago
  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.

by jnbiche 10y ago

dagw 10y ago

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

ced 10y ago
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-tips/ http://docs.julialang.org/en/release-0.4/manual/performance-...
- dagw 10y ago
  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
  - Tarrosion 10y ago
    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.
  - ced 10y ago
    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.
    - dagw 10y ago
      Thanks. To both you and Tarrosion. Guess I need to take some time at some point to sit down and actually learn 'proper' Julia.
shakna 10y ago
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?
Tarrosion 10y ago
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))

reinhardt 10y ago

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

ramblenode 10y ago
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)
- dalke 10y ago
  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.
  - reinhardt 10y ago
    > I don't think that does what you think it does: Heh, just proved my point. Reduce won't be missed.
  - ramblenode 10y ago
    Ouch, good catch! I can't think of a nice way to salvage reduce but these are some clever alternatives. Point anti-reduce.
    - 10y ago

probably_wrong 10y ago

> 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-slow-for-a-simple-for-loop#8097669 http://stackoverflow.com/questions/8097408/why-python-is-so-...

jnbiche 10y ago
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.