8 ms·

Making Python faster with Rust

• isaacfrond 3y ago
  Title is terrible. Better: A Python code is 100x faster by rewriting small part in Rust
  • dang 3y ago
    We've taken the magic numbers out of the title now, as the site guidelines ask - https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
• ssivark 3y ago
  Making Python (near infinitely) faster by using it as a glue language, and running all the computation outside Python :-P
  • baq 3y ago
    This is basically what Python was first designed for and as evidenced by the article still excels at
  • INTPenis 3y ago
    Yeah what's wrong with that? I think this sounds amazing. It gives you all the fast prototyping and simplicity of Python, but once you hit that bottleneck all you have to do is bring in a ringer to replace key components with a faster language. No need to use Golang or Rust from the start, no need for those resources until you absolutely need the speed improvement. Sounds like a dream to a lot of people who find it much easier to develop in Python.
    • okaleniuk 3y ago
      Also, there is a faster Python which is also Python. And the author considered it as well (both PyPy and Numba), it's just in this particular scenario they were not the best way to go.
    • internetter 3y ago
      Right? I mean, it's not like we haven't been doing this already. All the computationally intensive python libraries are just a convenient wrapper for C anyway, the only reason python can be used for ML.
    • alex_sf 3y ago
      Python is a rough language to be productive in. It's a great scratchpad, but dynamic typing, exceptions/poor error handling, and a horrifying deployment and dependency system make me reach for something like Go in any case where I need something to be even vaguely reliable. The more ML I do, the more disappointed I get.
      • xapata 3y ago
        To some degree, it's about familiarity with your tools. And different tools are optimized for different tasks. Besides, aren't you deploying Docker containers, anyway?
        • alex_sf 3y ago
          I do, absolutely. But it seems like an exceptionally rare practice for most Python code, at least in the ML space, which puts me back at the start.
          • xapata 3y ago
            Many ML practitioners aren't software engineers. I don't expect that cohort (non-engineers) would manage a deployment well in any language.
      • ajitid 3y ago
        Ever tried gluing Go with either Python or JavaScript? I'm interested in learning what libraries are there to glue them and how complicated and slow they could be.
        • noam_k 3y ago
          I've used gopy[0] recently to access a go library in Python. It surprisingly Just Worked, but I was disappointed by some performance issues, like converting lists to slices. [0] https://github.com/go-python/gopy https://github.com/go-python/gopy
          • 3y ago
    • josephg 3y ago
      It sounds amazing, but bear in mind there are a lot of code which can’t be sped up like this because: - Some code doesn’t have obvious optimization hotspots, and is instead just generally slow everywhere. - Most FFI boundaries incur their own performance cost. I’m not sure about Python, but I wouldn’t be surprised if FFI to rust in a hot loop is often slower than just writing the same code in Python directly. And it’s not always easy to refactor to avoid this. - A lot of programs in languages like Python are slow because the working set size contains a lot of small objects, and the GC struggles. You can optimize code like this by moving large parts of the object graph into rust. But it can become a mess if the objects rust retains then need references to Python objects, in turn. The optimization described in this blog post is the best case scenario for this sort of thing - the performance hotspot was clear, small, and CPU bound. When you can make optimizations like this you absolutely should. But your mileage may vary when you try this out on your own software.
      • mwcampbell 3y ago
        I wish I had understood this in 2004 when I decided to go all-in with an interpreted language (in this case, Lua) for code that needs to make FFI calls in hot loops. Then again, I suppose my best alternative at the time would have been C++98 as compiled by Visual C++ 6. I'm glad we have much better options now.
      • rpep 3y ago
        > Most FFI boundaries incur their own performance cost. I’m not sure about Python, but I wouldn’t be surprised if FFI to rust in a hot loop is often slower than just writing the same code in Python directly. And it’s not always easy to refactor to avoid this. They definitely do, but I’d usually suggest that if you find this an issue then perhaps the function you’re exposing from the compiled language should be higher level, with more work done in the compiled code to avoid the overhead of returning control back to the interpreted language.
        • josephg 3y ago
          Maybe. But that can also be a self tightening knot. Sometimes there’s no elegant place to cleave a program or library in two, and you really just want to pick a single language for the whole project. Mixing languages can also be a bit of a disaster for maintainability. Refactoring codebases which meaningfully span multiple languages is miserable work.
    • za3faran 3y ago
      Then you give up the benefits of using a managed language, and you now have to maintain two stacks. IMO/IME much better to go with a language where you don't have this dichotomy in the first place - e.g. Java or C#.
  • est 3y ago
    > and running all the computation outside Python You don't have to move all the computation, just `for` loops will help alot.
  • flohofwoe 3y ago
    Well, that's exactly where Python works well. As scripting glue sitting between or above native code which does the heavy-lifting.
• 1MachineElf 3y ago
  Python and Rust. Apple has some job openings in distributed systems for people fluent in both.
  • gjourdvhiokhf 3y ago
    Is Apple still hybrid only, no remote? Any links to some of their careers pages on this? Piqued my curiosity as my background almost lines up, and I'm interested in that kind of role... But I live near one of their offices only hiring for skill sets I don't really have.
• yjftsjthsd-h 3y ago
  > The library was already using numpy for a lot of its calculations, so why should we expect Rust to be better? I literally clicked in to read the article to see if they'd mention this:) But... unless I missed it, there wasn't really an answer? I thought numpy does do the heavy lifting in native code, so why is this faster? Does this version just push more of the logic into native code than numpy did?
  • lmeyerov 3y ago
    People can write slow code in any language ;-) We've had to fire contractors who "wrote" dataframe code but was not vectorized in practice despite repeat request to do so. Same thing for slow code in CUDA. From a maintenance view, I much prefer folks write vectorized data frames vs numpy or low level bindings, but that comes from having lived with the alternative for a lot longer. All of our exceptions are pretty much slotted for deletion. (Our fast path is single or multi-GPU dataframes in python.) Here's to hoping that one day we'll have dependent types in mypy!
    • yjftsjthsd-h 3y ago
      > People can write slow code in any language ;-) That was a lot of my curiosity, because I'm not quite a good enough programmer to know whether the problem is just that the original code is bad or does something super inefficient, and so rewriting it any language will let you make massive improvements.
  • biomcgary 3y ago
    The slowness comes from the interaction of numpy and a Python object "Polygon", which in not numpy. I suspect that a sufficiently clever coder could have optimized the result without resorting to Rust, but at the cost of a substantial increase in complexity of the codebase. The proposed approach keep the Python code simple (and moves the complexity into having another language to deal with).
    • alex_smart 3y ago
      diff --git a/poly_match_v1.py b/poly_match_v1.py index 675c88a..4293a46 100644 --- a/poly_match_v1.py +++ b/poly_match_v1.py @@ -1,4 +1,5 @@ from functools import cached_property +from itertools import compress from typing import List, Tuple import numpy as np from dataclasses import dataclass @@ -56,11 +57,8 @@ def generate_example() -> Tuple[List[Polygon], List[np.array]]: def find_close_polygons( polygon_subset: List[Polygon], point: np.array, max_dist: float ) -> List[Polygon]: - close_polygons = [] - for poly in polygon_subset: - if np.linalg.norm(poly.center - point) < max_dist: - close_polygons.append(poly) - + dist = np.linalg.norm([poly.center for poly in polygon_subset] - point, axis=1) + close_polygons = list(compress(polygon_subset, dist < max_dist)) return close_polygons 10x faster than the original, without resorting to native code, and without substantial increase in complexity of code base.
• brandonpelfrey 3y ago
  Very cool! I can see myself using this soon actually :) On top of the "code speed up" this is a good problem for 2d data structures for performing this type of "find objects within radius" type of query.
• jcolella 3y ago
  This is possibly one of the best written articles end-to-end I have read. Excellent job telling the story
  • brahbrah 3y ago
    Agreed it was well written, but kinda pointless though since they could have “solved” the problem using the existing tools in a couple lines of code without any new deps. All that content annd profiling and they missed the fact that they were using numpy wrong.
    • tecleandor 3y ago
      Totally out of curiosity, could you be a bit more concrete in your posted example? I can't get it to work (I'm inexperienced with numpy and I'm messing something when translating your quick example to python) Thanks!
      • brahbrah 3y ago
        Yea sorry that was just pseudo code. You want it in this form: centers = np.array([ [3, 3], [4, 4] ]) point = np.array([3.5, 3.5]) vals = centers - point np.linalg.norm(vals, axis=1)
• okaleniuk 3y ago
  Good for you! You did everything right: measure always, fix the bottleneck if possible, rewrite if necessary. A little tip, you don't have to compare actual distances, you can compare squared distances just as well. Then in `norm < max_dist`, you don't have to do a `sqrt()` for every `norm`. Saves a few CPU ticks as well. I once rewrote a GDI+ point transformation routine in pure C# and got 200x speedup just because the routine was riddled with needless virtual constructors, copying type conversions, and something called CreateInstanceSlow. Ten years after, I gathered a few of these anecdotes and wrote the Geometry for Programmers book (https://www.manning.com/books/geometry-for-programmers https://www.manning.com/books/geometry-for-programmers) with its main message: when you know geometry behind your tools, you can either use them efficiently, or rewrite them completely.
  • masklinn 3y ago
    The author did talk about it on reddit, but explained that for the purpose of the blog post they wanted to focus on the big stuff and profiling-guided optimisation of the process: https://reddit.com/r/rust/comments/125pbq0/blog_post_making_python_100x_faster_with_less/je6asz4?context=42 https://reddit.com/r/rust/comments/125pbq0/blog_post_making_...
  • ZeroCool2u 3y ago
    The ignore the square root while computing/comparing distances trick is a great one. That's how I got to the top of the performance leaderboard in my first algorithms class.
• firechickenbird 3y ago
  The premise was to not rewrite everything in rust, but you basically ended up rewriting 90% of it in rust
  • smnrchrds 3y ago
    90% of the bottleneck, not 90% of their whole application. The author says that rewriting everything in Rust would have taken months, so the whole application must be huge. "It is big and complex and very business critical and highly algorithmic, so that would take ~months of work, ..."
    • firechickenbird 3y ago
      OP fully rewrote the example program in rust, by also moving the entire data structures there. This would mean that any interaction with these ndarrays could be possible only on the rust side, hence any other code that uses them must be rewritten, unless there’s some porting of rust ndarrays to python numpy ndarrays
      • baq 3y ago
        Yes, what did you expect? That he shares his internal code base with the world just to silence people who can’t generalize?
        • firechickenbird 3y ago
          No? In fact, if you understand what what I wrote, by generalizing this small piece of code it would mean that most of the codebase must be also partially rewritten to rust to be able to interoperate with the new data structures moved in rust. Thus these “less than 100 lines of code” refer to just this simple example program, which was fully rewritten in rust, hence, by generalizing, the premise was pointless
• jacquesm 3y ago
  It's not really Python that was sped up though, it was an application written in python augmented with a bit of optimized rust code. This sort of hybrid is super common, you typically spend 90%+ of your time in computationally intensive problems in a very small subset of your code, typically the innermost loops. Optimizing those will have very good pay-off. Traditionally we'd do this with high level stuff in one language and then assembly for the performance critical parts, these days it is more likely a combination of a scripting language for the high level part and a compiled language for the low level parts (C, rust, whatever). Java and such as less suitable for such optimization purposes, both because they come with a huge runtime and because they are hard to interface to other languages unless they happen to use the same underlying VM, but then there usually isn't much performance gain. Another nice way to optimize computationally intensive code is by finding out if the code is suitable for adaptation to the GPU, which can give you many orders of magnitude speed improvement in some cases.
• b0b10101 3y ago
  This is a great article but there's still a core problem there - why should developers have to choose between accessibility and performance? So much scientific computing code suffers between core packages being split away from their core language - at what point do we stop and abandon python for languages which actually make sense? Obviously julia is the big example here, but its interest, development and ecosystem doesn't seem to be growing at a serious pace. Given that the syntax is moderately similar and the performance benefits are often 10x what's stopping people from switching???
  • ThouYS 3y ago
    everything. why are there still cobol programmers? why is c++ still the defacto native language (also in research)? but also I don't see any problem there, I think the python + c++/rust idiom is actually pretty nice. I have a billion libs to choose from on either side. Great usability on the py side, and unbeatable performance on the c++ side
  • fbdab103 3y ago
    Today, there is a Python package for everything. The ecosystem is possibly best in class for having a library available that will do X. You cannot separate the language from the ecosystem. Being better, faster, and stronger means little if I have to write all of my own supporting libraries. Also, few scientific programmers have any notion of what C or Fortran is under the hood. Most are happy to stand on the shoulders of giants and do work with their specialized datasets. Which for the vast majority of researchers are not big data. If the one-time calculation takes 12 seconds instead of 0.1 seconds is not a problem worth optimizing.
    • koito17 3y ago
      >Today, there is a Python package for everything. The same could be said about CPAN and NPM. Yet Perl is basically dead and JavaScript isn't used for any machine learning tasks as far as I'm aware. WebAssembly did help bring a niche array of audio and video codecs to the ecosystem[1][2], something I'm yet to see from Python. I don't use Python, but with what little exposure I've had to it at work, its overall sluggish performance and need to set up a dozen virtualenvs -- only to dockerize everything in cursed ways when deploying -- makes me wonder how or why people bother with it at all beyond some 5-line script. Then again, Perl used to be THE glue language in the past and mod_perl was as big as FastAPI, and Perl users would also point out how CPAN was unparalleled in breadth and depth. I wonder if Python will follow a similar fate as Perl. One can hope :-) [1] https://github.com/phoboslab/jsmpeg https://github.com/phoboslab/jsmpeg [2] https://github.com/brion/ogv.js/ https://github.com/brion/ogv.js/
• wanderingmind 3y ago
  Why do I need to rewrite in Rust, when I can just use Polars[1] that will cover most usecases [1] https://www.pola.rs/ https://www.pola.rs/
  • wenc 3y ago
    Polars and DuckDB have replaced Pandas for me for the most part.
  • masklinn 3y ago
    What is the relation? Polars replaces pandas, not numpy.
• mattbillenstein 3y ago
  Kudos - this is a very nice blog post - "real" engineering ;)
• FreeHugs 3y ago
  The most important part of the article seems to be that this Python code is taking "an avg of 293.41ms per iteration": def find_close_polygons( polygon_subset: List[Polygon], point: np.array, max_dist: float ) -> List[Polygon]: close_polygons = [] for poly in polygon_subset: if np.linalg.norm(poly.center - point) < max_dist: close_polygons.append(poly) return close_polygons And after replacing it with this Rust code, it is taking "an avg of 23.44ms per iteration": use pyo3::prelude::*; use ndarray_linalg::Norm; use numpy::PyReadonlyArray1; #[pyfunction] fn find_close_polygons( py: Python<'_>, polygons: Vec<PyObject>, point: PyReadonlyArray1<f64>, max_dist: f64, ) -> PyResult<Vec<PyObject>> { let mut close_polygons = vec![]; let point = point.as_array(); for poly in polygons { let center = poly .getattr(py, "center")? .extract::<PyReadonlyArray1<f64>>(py)? .as_array() .to_owned(); if (center - point).norm() < max_dist { close_polygons.push(poly) } } Ok(close_polygons) } Why is the Rust version 13x faster than the Python version?
  • hannofcart 3y ago
    I was surprised that the Rust version is _only_ 13x as fast as the Python version.
    • IshKebab 3y ago
      Probably because it wasn't pure Python to start with.
  • nickstinemates 3y ago
    One carries the entire feature set of the python runtime, the other is compiled.
    • FreeHugs 3y ago
      The time is spent in this 3-line loop: for poly in polygon_subset: if np.linalg.norm(poly.center - point) < max_dist: close_polygons.append(poly) I don't think the entire feature set of the Python runtime is involved in this.
• Heston 3y ago
  It's much easier and more accurate to time your python scripts with `time python script.py`. Cool write up.
  • masklinn 3y ago
    `time` is absolutely awful, with the minor exception of bsd’s time maybe. If you’re going to benchmark scripts or executables, use hyperfine.
    • akasakahakada 3y ago
      Very nice. Thanks for sharing. https://github.com/sharkdp/hyperfine https://github.com/sharkdp/hyperfine
• sandGorgon 3y ago
  >Also, using any JIT-based tricks (PyPy / numba) results in very small gains (as we will measure, just to make sure). i wasnt able to see the numba comparison. anyone know how much worse it was ?
• majoe 3y ago
  I had a similar problem, when I was working as a PhD student a few years ago, where I needed to match the voxel representation of a 3D printer with the tetrahedral mesh of our rendering application. My first attempt in Python was both prohibitively slow and more complicated than necessary, because I tried to use vectorized numpy, where possible. Since this was only a small standalone script, I rewrote it in Julia in a day. The end result was ca. 100x faster and the code a lot cleaner, because I could just implement the core logic for one tetrahedron and then use Julia's broadcast to apply it to the array of tetrahedrons. Anyway, Julia's long startup time often prohibits it from being used inside other languages (even though the Python/Julia interoperability is good). On the contrary the Rust/Python interop presented here seems to be pretty great. Another reason I should finally invest the time to learn Rust.
  • hgomersall 3y ago
    Numba is great if you want to write a naive loop approach in python.
  • xgdgsc 3y ago
    Julia 1.9 is fast. And you can use https://github.com/Suzhou-Tongyuan/jnumpy https://github.com/Suzhou-Tongyuan/jnumpy to write python extension in Julia now. So I think after 1.9 release julia would be much more usable.
  • dunefox 3y ago
    Long startup time is relative. I believe it's much lower now than a couple of versions ago. 0.15s or so? Interop between python and rust will also take time.
• Animats 3y ago
  Using PyPy, which is a real compiler, might help. That's doing spatial data processing by exaustive search, which is inherently slow. There are better algorithms. If the number of items to be searched is large, the spatial indices of MySQL could help.
  • laerus 3y ago
    PyPy is a JIT compiler not a "real compiler", it requires warm up time to start optimizing code on runtime.
    • Alifatisk 3y ago
      In other words, PyPy is not a AOT-compiler.
    • Animats 3y ago
      It does generate machine code, which CPython does not.
  • why_only_15 3y ago
    They tried PyPy at the beginning and it was 2x slower. Plausibly it would be better with additional optimization, but it's not cut and dry.
  • rwalle 3y ago
    Did you read the article?
• moreresearchplz 3y ago
  Like to see comparison to when they use a spatial index like strtree or rtree.
• deleted 3y ago
  [deleted]
• korijn 3y 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 3y 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 3y 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 3y 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 3y 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...
• tus666 3y ago
  > Rust (with the help of pyo3) unlocks true native performance for everyday Python code, with minimal compromises. Hasn't he heard of ctypes? You can wrap C structs add Python objects since forever.
  • UncleEntity 3y ago
    There’s probably a way to get at the numpy objects without having to go through the python runtime and do all the computation in pure C. I assume, haven’t really messed with numpy for anything but I can’t imagine it wouldn’t work that way.
• cornholio 3y ago
  Language design request: Take from Rust Algebraic types, ahead of time compilation and strong types, functional features, a borrow / escape checker that automatically turns shared data into Rc or Arc, as necessary, instead of tormenting me to rewrite performance irrelevant code; Take from Python the simple syntax, default pass by reference of all non-numeric types, simplified string handling, unified slice and array syntax - and any other simplifying feature possible. ... and give me a fast, safe and powerful language that gets out of my way while maximizing the power of the compiler to prevent bugs. Golang was a commendable attempt, but they made '70s design decisions that condemned the language: mandatory garbage collection, nullables, (void*) masquerading as interface{} casts, under-powered compiler etc.
  • machiaweliczny 3y ago
    I think Nim is closest to this wishlist
    • elcritch 3y ago
      Pretty much, ARC is RC without needing to manually write it. It can be as compact as Python and near C++/Rust speeds with some optimization. Then add in macros for real performance tricks like simd. Julias pretty nice as well.
  • mijoharas 3y ago
    Sounds like swift to me
  • za3faran 3y ago
    Modern Java and modern C# should be closer to what you described. On a side note, python is strictly pass by value. For non-primitives, their references are passed by value.
• akasakahakada 3y ago
  The original code already look crap due to making a new list containing object instead of a mask or something else. Also that can be done using list comprehension. Also it totally can be vectorize or parallelize. You need more experienced Python engineer.
• saeranv 3y ago
  I wonder if being able to quickly retrieve a numpy array of the polygon centers would make an equivalent difference. Since then you could at least retrieve the centers from the polygon as an array you could just use numpy operations for the closest polygon operation: ``` centers = get_centers(polgons) # M x 3 array close_idx = np.where( np.linalg.norm(centers - point, axis=1) < max_dist)[0] close_polygons = polygons[close_idx,:] ``` That's one reason I prefer for to use arrays for polygons, rather then abstract it into a Python object. Fundamentally geometries are sequences of points, and with some zero-padding to account for irregular point counts, you can still keep them in a nice, efficient array representation.
  • toxik 3y ago
    Agreed, I speed up Python numpy code with numba quite often and it isn’t at all unreadable to put it in an ndarray subclass. poly = Polygon(vertices) I would bet you can achieve just as much of a speedup with numba or Cython using this form.
• karussell 3y ago
  I wonder why GraalVM is not more often used for these speed critical cases: https://www.graalvm.org/python/ https://www.graalvm.org/python/ (Same for ruby https://www.graalvm.org/ruby/ https://www.graalvm.org/ruby/) Is the problem the Oracle involvement? Or is it not that fast as advertised or problems with the ecosystem (C libraries)?
  • thisgoodlife 3y ago
    My concern is that it’s not ready for prod yet. “At this point, the Python runtime is made available for experimentation and curious end-users. “ https://www.graalvm.org/latest/reference-manual/python/ https://www.graalvm.org/latest/reference-manual/python/
  • dunefox 3y ago
    I would not use anything made by oracle if I have the choice. My team sees it similarly.
    • pjmlp 3y ago
      Better clean up the Linux kernel from Oracle contributions then, in case you are using it. https://lwn.net/Articles/915435/ https://lwn.net/Articles/915435/
      • dunefox 3y ago
        So the Linux kernel is an Oracle licensed product? Better uninstall Ubuntu then.
        • pjmlp 3y ago
          I am not the one having issues with Oracle. In fact, I am thankful that they at least avoided Java being stuck in Java 6, and MaximeVM turned into GraalVM, when no one else cared to save Sun from insolvency. Only IBM made a candidate offer that was quickly withdrawn. So people should stop acting as if there was any magic way to rescue Sun assets. Also the fact they were one of the first GNU/Linux supporters in enterprise context, which allowed us to actually have a couple of GNU/Linux computers among our Aix, HP-UX and Solaris servers, happily running Oracle instances.
• brahbrah 3y ago
  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 3y 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 3y ago
      [deleted]
    • brahbrah 3y 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 3y ago
      [flagged]
  • oblio 3y 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 3y ago
• appeldorian 3y ago
  I think a big mistake in the article, in a context where performance is the main objective, is that the author uses an array of structs (AoS), rather than a struct of arrays (SoA). An SoA makes it so that the data is ordered contiguously, which is easy to read for the CPU, while an AoS structure interleaves different data (namely the x and y in this case), which is very annoying for the CPU. A CPU likes to read chunks of data (for example 128 bits of data/read) and to process these with SIMD instructions, executing a multiple of calculations with one CPU cycle. This is completely broken when using an array of structs. He uses the same data structure in both the Python and Rust code, so I imagine that he can get an extra 4x speedup at least if he rewrites his code with memory layout in mind.
  • tremon 3y ago
    Apache Arrow (https://arrow.apache.org/overview/ https://arrow.apache.org/overview/) is built exactly around this idea: it's a library for managing the in-memory representation of large datasets.
  • prirun 3y ago
    Modern CPU caches are usually loaded in 64-byte units - much larger than 128 bits. I just ran some tests with a C program on an Intel I5 with both AoS and SoA using a list of 1B points with 32-bit X and Y components. Looping through the list of points and totaling all X and Y components was the same speed with either AoS or SoA. It's easy to make intuitive guesses about how things are working that seem completely reasonable. But you have to benchmark because modern CPUs are so complex that reasoning and intuition mostly don't work. Programs used for testing are below. I ran everything twice because my system wasn't always idle, so take the lower of the 2 runs. [jim@mbp ~]$ sh -x x + cat x1.c #include <stdio.h> #define NUM 1000000000 struct { int x; int y; } p[NUM]; int main() { int i,s; for (i=0; i<NUM; i++) { p[i].x = i; p[i].y = i; } s=0; for (i=0; i<NUM; i++) { s += p[i].x + p[i].y; } printf("s=%d\n", s); } + cc -o x1 x1.c + ./x1 s=1808348672 real 0m12.078s user 0m7.319s sys 0m4.363s + ./x1 s=1808348672 real 0m9.415s user 0m6.677s sys 0m2.685s + cat x2.c #include <stdio.h> #define NUM 1000000000 int x[NUM]; int y[NUM]; int main() { int i,s; for (i=0; i<NUM; i++) { x[i] = i; y[i] = i; } s=0; for (i=0; i<NUM; i++) { s += x[i] + y[i]; } printf("s=%d\n", s); } + cc -o x2 x2.c + ./x2 s=1808348672 real 0m9.753s user 0m6.713s sys 0m2.967s + ./x2 s=1808348672 real 0m9.642s user 0m6.674s sys 0m2.902s + cat x3.c #include <stdio.h> #define NUM 1000000000 struct { int x; int y; } p[NUM]; int main() { int i,s; for (i=0; i<NUM; i++) { p[i].x = i; } for (i=0; i<NUM; i++) { p[i].y = i; } s=0; for (i=0; i<NUM; i++) { s += p[i].x; } for (i=0; i<NUM; i++) { s += p[i].y; } printf("s=%d\n", s); } + cc -o x3 x3.c + ./x3 s=1808348672 real 0m13.844s user 0m11.095s sys 0m2.700s + ./x3 s=1808348672 real 0m13.686s user 0m11.038s sys 0m2.611s + cat x4.c #include <stdio.h> #define NUM 1000000000 int x[NUM]; int y[NUM]; int main() { int i,s; for (i=0; i<NUM; i++) x[i] = i; for (i=0; i<NUM; i++) y[i] = i; s=0; for (i=0; i<NUM; i++) s += x[i]; for (i=0; i<NUM; i++) s += y[i]; printf("s=%d\n", s); } + cc -o x4 x4.c + ./x4 s=1808348672 real 0m13.530s user 0m10.851s sys 0m2.633s + ./x4 s=1808348672 real 0m13.489s user 0m10.856s sys 0m2.603s
• wdroz 3y ago
  One of the others understated pros of rewriting some parts in Rust, it's that you can parallelize easily with Rayon[0] [0] -- https://github.com/rayon-rs/rayon https://github.com/rayon-rs/rayon
• xgdgsc 3y ago
  Rust is verbose. I would use https://github.com/Suzhou-Tongyuan/jnumpy https://github.com/Suzhou-Tongyuan/jnumpy to write python extension in Julia and usually get similar performance.
  • shakow 3y ago
    Does it compile AoT or are you stuck with Julia start time?
• poulpy123 3y ago
  I'm wondering how much would be the speedup by rewriting the critical part in cython
• kavalg 3y ago
  For this particular code, vectorization and some acceleration library, such as JAX, may be a better path to optimization. Otherwise an excellent article!
• thanatropism 3y ago
  I feel a lot of the "Python perf" thing is an inferiority complex. cPython is getting faster all the time, and (obviously using libraries like numpy and others that hook into compiled code) I don't think I've ever seen it become a business bottleneck. If it's ever a scaling problem, then you hire lower-level language devs, it's a good problem to have. Python is much, much easier to learn, and Rust is notoriously difficult. This obviously feeds into the inferiority complex. But -- while I do know there's a number of applications where perf is crucial -- I think it's well worth doing an ego check before moving from what's a lower friction path and gives you access to myriad developers, including ones trained in very hard disciplines. Also: does it ever make sense to write something like a CRUD+ backend in Rust? Maybe 100X Rustaceans can do it with one hand tied behind their backs; but imagine what these ubermenschen could be achieving in Python?
  • pjmlp 3y ago
    If writing Tcl extensions in C during the .com wave 23 years ago taught me something, was that glue languages are great, and that I don't want to use any that doesn't come with either AOT or JIT compiler in the box, other than for OS scripting tasks.
  • faitswulff 3y ago
    I think you might be surprised. I would say Rust isn't notoriously difficult per se, it's just harder to please the compiler. But that's still viewing the compiler as an adversary when it's more like an assistant, so the analogy breaks down. You don't have to be a 100x engineer to use Rust. In fact, quite the opposite. Rust gives engineers a lot more guardrails to prevent what would be runtime errors in other languages.
  • JodieBenitez 3y ago
    > Also: does it ever make sense to write something like a CRUD+ backend in Rust? Well... given 2 frameworks equally pleasant to work with, why not using the one with the best performance ? (Whatever performance means... less cpu ? less memory ? better i/o ?). As a Django user, working on problems where Django shines, I have yet to see such a solution in Rust, but that doesn't mean it won't happen one day.
• wcrossbow 3y ago
  Rust is great but isn’t the core problem here using the wrong algorithm? It looks like this is ideally suited for a quad tree instead of a naive for loop. I would expect that to pulverise any current benchmark.
  • flohofwoe 3y ago
    I guess you also need to take the time into account to create the quad tree from an unsorted 'polygon soup' first, and in terms of coding effort, a brute force conversion from python to a compiled tight loop over unsorted arrays provides a lot of bang for the buck (and a speedup of 100x for relatively little effort might be 'good enough' for quite a while until the input data grows big enough to require the next optimization effort). (e.g. it doesn't need to be "as fast as possible", just fast enough to no longer be a workflow bottleneck)
    • wcrossbow 3y ago
      Im assuming the polygons dont change to often so you can amortize the construction of the quadtree. Depending on your world view the implementation is trivial since Shapely, a dependency they already likely have, has an implementation of it.
      • ohr 3y ago
        Author here: actually, in this analogy (as this is just a demo library), the polygons change each time so we couldn't use this type of optimization (at least not in a straightforward way).
• swyx 3y ago
  in the domain of Python tooling made faster with Rust, check out https://github.com/charliermarsh/ruff https://github.com/charliermarsh/ruff which is 10-100x faster than pylint etc
• Dowwie 3y ago
  Elixir is made faster with Rust, too. Rust is a great skillset to have for those measured moments.
• crabbone 3y ago
  > Python is a superb API for researchers, Where does this nonsense come from? No. It isn't. It's just a stupid fashion. Something that should be discouraged, not encouraged by trying to make it work when it's obviously broken. As someone who does work with researchers who do use Python a lot, I see the everyday painful experiences of people who use it. And this pain doesn't need to be there. It's just masochism. And the only real reason is that they don't know any better. The only other thing they know is Matlab, and that's even worse. Python is just a bad language. Popular, but awful. Ironically, while researchers are supposed to be on the forerfront of discovery and technology... well, they aren't. Industry outpaced research. So much so that today there are government programs to onboard researchers into more automated and more automatically verified way to do research. And we aren't talking about making an elite force here. These programs are meant for people in research who copy data from Excel sheets one data point at a time into another spreadsheet. It's that kind of bad. My wife happened to work in such a government center, and that's how I know about what's going on inside these programs. And it's very sad that decisions about the preferred tools for research automation are made by people who, unlike most of their peers, had some exposure to what happens in the industry, but had no deeper understanding of the reasons any particular technology ended up in any particular niche, nor any independent ability to assess the capabilities of any particular tech. It's really sad what's going on there.
  • pahbloo 3y ago
    What are the best alternatives to Python then?
    • crabbone 3y ago
      For research? -- Julia seems to be definitely better. It's purpose-built for doing just that. R would also be there. If you want general statistics, then add J to the fold. But specific fields often have their own, bespoke solutions. I've only ever dealt with math, but it has plenty of its own niche languages that are much better than, say, Sage. My personal choice was Maxyma, but that's because I like Common Lisp. Furthermore, it's just the situation today. It doesn't mean that this is what it has to be tomorrow. Any of the languages I used in this domain have their issues, and could still be improved. We are nowhere near a place where it's hard to imagine something better than what we have. So, I'd say, if you really want a very good language, you might as well start building one now -- you have a very good chance yours will be the best one so far.
• orangepurple 3y ago
  It is an alternative framing of the N+1 problem (mistake) SQL users make https://news.ycombinator.com/item?id=34207974 https://news.ycombinator.com/item?id=34207974
• osmanbaskaya 3y ago
  I am really curious if there is an important reason why not trying this performance improvement with Cython first. Can someone comfortable with Cython explain what are the pros and cons doing this optimization with Cython?