6 ms·

This was a silly and unnecessary optimization. He’s just using numpy wrong. Instead of: for p in ps: norm(p.center - point) You should do: centers = np.

This was a silly and unnecessary optimization. He’s just using numpy wrong. Instead of: for p in ps: norm(p.center - point) You should do: centers = np.array([p.center for p in ps]) norm(centers - point, axis=1) You’ll get your same speed up in 2 lines without introducing a new dependency

_glass 4y ago
Isn't this the version of refenced on the github repo [0] which speeds up 6x instead of 101x? There's also a "v1.5" version which is 6x faster, and uses "vectorizing" (doing more of the work directly in numpy). This version is much harder to optimize further. [0] https://github.com/ohadravid/poly-match https://github.com/ohadravid/poly-match
- deleted 4y ago
  [deleted]
- brahbrah 4y ago
  No, their v1.5 is still calling norm on every polygon. They’re still using it wrong On Google colab import numpy as np import time vals = np.random.randn(1000000, 2) point = np.array([.2, .3]) s = time.time() for x in vals: np.linalg.norm(x - point) < 3 a = time.time() - s s = time.time() np.linalg.norm(vals - point, axis=1) < 3 b = time.time() - s print(a / b) ~296x faster, significantly faster than the solution in the article.
- akasakahakada 4y ago
  [flagged]
oblio 4y ago
This is nice, how would you go about as a performance noob? I can't imagine there's a line in the docs saying "this is slow!".
- akasakahakada 4y ago
  LineProfiler is the best tool to learn how to write performant Python and do code optimization. https://github.com/pyutils/line_profiler https://github.com/pyutils/line_profiler You can literally see the hot spot of your code, then you can grind different algorithms or change the whole architecture to make it faster. For example replace short for loops to list comprehensions, vectorize all numpy operations (only vectorize partially do not help the issue), using 'not any()' instead or 'all()' for boolean, etc. Doing this for like 2 weeks, basically you can automatically recognize most bad code patterns at a glance.
  - dralley 4y ago
    You should take a look at Scalene - it's even better. https://github.com/plasma-umass/scalene https://github.com/plasma-umass/scalene
    - akasakahakada 4y ago
      Wow this looks sick! Great thanks!
- brahbrah 4y ago
  So in addition to what akasaka said (another thumbs up for line profiler from me, great tool) this isn’t a problem with linalg.norm being slow. It’s plenty fast, but calling it thousands of separate times in a Python loop will be slow. This is more just about learning how to vectorize properly. If you’re working in numpy land and you’re calling a numpy function in a loop that’s iterating over more than a handful of items, chances are you’re not vectorizing properly
  - akasakahakada 4y ago
    I realized that I should say more specifically about numpy usage. If you see a piece of code like this, it rings the bell that the person has no idea what he/she is doing: Bad Pattern: my_list = np.array(xxx) summed = [] for row in my_list: summed.append(np.sum(row)) Worst Pattern: my_list = np.array(xxx) def get_summed(arr): return np.sum(arr) summed = [] for i in range(len(my_list)): summed.append( get_summed(my_list[i]) ) Perfered: # np.array(xxx) is redundant summed = np.sum(xxx, axis=1) Same applies to all numpy operations.
jerf 4y ago
This is the major reason I don't really buy into things like JITs solving all performance problems (as long as you carefully write only and exactly the subset of the language they work well with) or NumPy not being affected by Python being slow. There's more code like this in the world than I think people realize. Having to write in a subset of a language in order for it to perform decently is a big deal. Having no feedback given to the programmer when you deviate from the fast path makes it even harder to learn what the fast path is. The result is not that you get the ease of Python and the speed of C without having to understand much; the result is that you have to be a fairly deep expert in Python and understand the C bindings intimately and learn how to avoid doing what is the natural thing in Python, the Python covered in all the tutorials, or you end up writing your code to run at native Python speeds without even realizing it. It's a feasible amount of knowledge to have, it's not like it's completely insane, but it's still rather a lot. My career just brushed this world and I'm glad I bounced off of it. It would drive me insane to walk through this landmine field every day, and then worse, have to try to guide others through it all the while they are pointing at all the "common practices" that are also written by people utterly oblivious to all this.
- brahbrah 4y ago
  This is a very valid point that I can’t disagree with. I’ve gone through the pain of learning that subset of the language decently well, but also been lucky enough to work at places that compensate very well for that knowledge.

_glass 4y ago

Isn't this the version of refenced on the github repo [0] which speeds up 6x instead of 101x? There's also a "v1.5" version which is 6x faster, and uses "vectorizing" (doing more of the work directly in numpy). This version is much harder to optimize further. [0] https://github.com/ohadravid/poly-match https://github.com/ohadravid/poly-match

deleted 4y ago
[deleted]
brahbrah 4y ago
No, their v1.5 is still calling norm on every polygon. They’re still using it wrong On Google colab import numpy as np import time vals = np.random.randn(1000000, 2) point = np.array([.2, .3]) s = time.time() for x in vals: np.linalg.norm(x - point) < 3 a = time.time() - s s = time.time() np.linalg.norm(vals - point, axis=1) < 3 b = time.time() - s print(a / b) ~296x faster, significantly faster than the solution in the article.
akasakahakada 4y ago
[flagged]

oblio 4y ago

This is nice, how would you go about as a performance noob? I can't imagine there's a line in the docs saying "this is slow!".

akasakahakada 4y ago
LineProfiler is the best tool to learn how to write performant Python and do code optimization. https://github.com/pyutils/line_profiler https://github.com/pyutils/line_profiler You can literally see the hot spot of your code, then you can grind different algorithms or change the whole architecture to make it faster. For example replace short for loops to list comprehensions, vectorize all numpy operations (only vectorize partially do not help the issue), using 'not any()' instead or 'all()' for boolean, etc. Doing this for like 2 weeks, basically you can automatically recognize most bad code patterns at a glance.
- dralley 4y ago
  You should take a look at Scalene - it's even better. https://github.com/plasma-umass/scalene https://github.com/plasma-umass/scalene
  - akasakahakada 4y ago
    Wow this looks sick! Great thanks!
brahbrah 4y ago
So in addition to what akasaka said (another thumbs up for line profiler from me, great tool) this isn’t a problem with linalg.norm being slow. It’s plenty fast, but calling it thousands of separate times in a Python loop will be slow. This is more just about learning how to vectorize properly. If you’re working in numpy land and you’re calling a numpy function in a loop that’s iterating over more than a handful of items, chances are you’re not vectorizing properly
- akasakahakada 4y ago
  I realized that I should say more specifically about numpy usage. If you see a piece of code like this, it rings the bell that the person has no idea what he/she is doing: Bad Pattern: my_list = np.array(xxx) summed = [] for row in my_list: summed.append(np.sum(row)) Worst Pattern: my_list = np.array(xxx) def get_summed(arr): return np.sum(arr) summed = [] for i in range(len(my_list)): summed.append( get_summed(my_list[i]) ) Perfered: # np.array(xxx) is redundant summed = np.sum(xxx, axis=1) Same applies to all numpy operations.

jerf 4y ago

This is the major reason I don't really buy into things like JITs solving all performance problems (as long as you carefully write only and exactly the subset of the language they work well with) or NumPy not being affected by Python being slow. There's more code like this in the world than I think people realize. Having to write in a subset of a language in order for it to perform decently is a big deal. Having no feedback given to the programmer when you deviate from the fast path makes it even harder to learn what the fast path is. The result is not that you get the ease of Python and the speed of C without having to understand much; the result is that you have to be a fairly deep expert in Python and understand the C bindings intimately and learn how to avoid doing what is the natural thing in Python, the Python covered in all the tutorials, or you end up writing your code to run at native Python speeds without even realizing it. It's a feasible amount of knowledge to have, it's not like it's completely insane, but it's still rather a lot. My career just brushed this world and I'm glad I bounced off of it. It would drive me insane to walk through this landmine field every day, and then worse, have to try to guide others through it all the while they are pointing at all the "common practices" that are also written by people utterly oblivious to all this.

brahbrah 4y ago
This is a very valid point that I can’t disagree with. I’ve gone through the pain of learning that subset of the language decently well, but also been lucky enough to work at places that compensate very well for that knowledge.