[brahbrah]

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]

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

[brahbrah]

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.

[jerf]

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]

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.

[oblio]

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]

LineProfiler is the best tool to learn how to write performant Python and do code optimization.

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]

You should take a look at Scalene - it's even better.

https://github.com/plasma-umass/scalene

[akasakahakada]

Wow this looks sick! Great thanks!

[brahbrah]

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]

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.