4 ms·

A vectorized implementation of find_close_polygons wouldn't be very complex or hard to maintain at all, but the authors would also have to ditch their OOP class

by korijn 4y ago

A vectorized implementation of find_close_polygons wouldn't be very complex or hard to maintain at all, but the authors would also have to ditch their OOP class based design, and that's the real issue here. The object model doesn't lend itself to performant, vectorized numpy code.

pbowyer 4y ago
What's a good guide to learn how to make (and see) vectorized code? It's a mindshift and not one I find easy.
- appeldorian 4y ago
  I think a great start is to make arrays of similar data. Instead of an array of (x,y,z) use an array for x, an array for y and another one for z. If you then square these and sum them for example, the compiler might figure out good optimizations for it if you write it as a simple loop. Also read about SIMD instructions like AVX2. They are often used under the hood when possible, but just knowing what they require can help "triggering" them, depending on which language you use. In C++ for example, the compiler really looks for opportunities to use those instructions. You can tell the compiler did it, by looking in the assembly code if any XMM or YMM registers are being used (these are the names of the SIMD registers).
- akasakahakada 4y ago
  A more accruate keyword for googling is "SIMD". Single Instruction Multiple Data. Numpy's tutorial for broadcasting is also a good starting point. https://numpy.org/doc/stable/user/basics.broadcasting.html https://numpy.org/doc/stable/user/basics.broadcasting.html
- korijn 4y ago
  The gist of it is that you give numpy two arrays, and what operation to apply. Then numpy will figure out what the for loop(s) should look like depending on the shape of the arrays. You can look at various tutorials to see how it works. For example: https://jakevdp.github.io/PythonDataScienceHandbook/02.05-computation-on-arrays-broadcasting.html https://jakevdp.github.io/PythonDataScienceHandbook/02.05-co...
rwalle 4y ago
Exactly, that is the real issue, vectorization might be good enough in terms of performance. It doesn't seem to be mentioned in the article at all.
- hn92726819 4y ago
  It might have been added later, but the author mentions vectorization in the beginning: > It’s worth noting that converting parts of / everything to vectorized numpy might be possible for this toy library, but will be nearly impossible for the real library while making the code much less readable and modifiable, and the gains are going to be limited (here’s a partially vertorized version, which is faster but far from the results we are going to achieve).
  - akasakahakada 4y ago
    Semi Vectorized code: https://github.com/ohadravid/poly-match/blob/main/poly_match_v1_5_vectorized.py https://github.com/ohadravid/poly-match/blob/main/poly_match... Expecting Python engineers unable to read defacto standard numpy code but meanwhile expect everyone can read Rust..... Not to mention that the semi-vectorized code is still suboptimal. Too many for loops despite the author clearly know they can all be vectorized. For example instead the author can just write something like: np.argmin( distances[distances<=threshold] ) Also in oneplace there is: np.xxx( np.xxx, np.xxx + np.xxx) You can just slap numexpr on top of it to compile this line on the fly. https://github.com/pydata/numexpr https://github.com/pydata/numexpr
    - Tarq0n 4y ago
      Not super familiar with Python but isn't that append call within a loop going to cause a lot of allocations?
      - akasakahakada 4y ago
        3000 calls to list.append() cost only 2ms. In a computational intense program, no one bothers. Because usually one call to do matrix multiplication is already costing 500ms or so. Of couse you can prelocate memory for size=3000, and append stuff in a loop. But this saves only 10ms. Too insignificant.

by korijn 4y ago

pbowyer 4y ago

What's a good guide to learn how to make (and see) vectorized code? It's a mindshift and not one I find easy.

appeldorian 4y ago
I think a great start is to make arrays of similar data. Instead of an array of (x,y,z) use an array for x, an array for y and another one for z. If you then square these and sum them for example, the compiler might figure out good optimizations for it if you write it as a simple loop. Also read about SIMD instructions like AVX2. They are often used under the hood when possible, but just knowing what they require can help "triggering" them, depending on which language you use. In C++ for example, the compiler really looks for opportunities to use those instructions. You can tell the compiler did it, by looking in the assembly code if any XMM or YMM registers are being used (these are the names of the SIMD registers).
akasakahakada 4y ago
A more accruate keyword for googling is "SIMD". Single Instruction Multiple Data. Numpy's tutorial for broadcasting is also a good starting point. https://numpy.org/doc/stable/user/basics.broadcasting.html https://numpy.org/doc/stable/user/basics.broadcasting.html
korijn 4y ago
The gist of it is that you give numpy two arrays, and what operation to apply. Then numpy will figure out what the for loop(s) should look like depending on the shape of the arrays. You can look at various tutorials to see how it works. For example: https://jakevdp.github.io/PythonDataScienceHandbook/02.05-computation-on-arrays-broadcasting.html https://jakevdp.github.io/PythonDataScienceHandbook/02.05-co...

rwalle 4y ago

Exactly, that is the real issue, vectorization might be good enough in terms of performance. It doesn't seem to be mentioned in the article at all.

hn92726819 4y ago
It might have been added later, but the author mentions vectorization in the beginning: > It’s worth noting that converting parts of / everything to vectorized numpy might be possible for this toy library, but will be nearly impossible for the real library while making the code much less readable and modifiable, and the gains are going to be limited (here’s a partially vertorized version, which is faster but far from the results we are going to achieve).
- akasakahakada 4y ago
  Semi Vectorized code: https://github.com/ohadravid/poly-match/blob/main/poly_match_v1_5_vectorized.py https://github.com/ohadravid/poly-match/blob/main/poly_match... Expecting Python engineers unable to read defacto standard numpy code but meanwhile expect everyone can read Rust..... Not to mention that the semi-vectorized code is still suboptimal. Too many for loops despite the author clearly know they can all be vectorized. For example instead the author can just write something like: np.argmin( distances[distances<=threshold] ) Also in oneplace there is: np.xxx( np.xxx, np.xxx + np.xxx) You can just slap numexpr on top of it to compile this line on the fly. https://github.com/pydata/numexpr https://github.com/pydata/numexpr
  - Tarq0n 4y ago
    Not super familiar with Python but isn't that append call within a loop going to cause a lot of allocations?
    - akasakahakada 4y ago
      3000 calls to list.append() cost only 2ms. In a computational intense program, no one bothers. Because usually one call to do matrix multiplication is already costing 500ms or so. Of couse you can prelocate memory for size=3000, and append stuff in a loop. But this saves only 10ms. Too insignificant.