Using Rust to corrode insane Python run-times (2021) | Hacker News Reader

Using Rust to corrode insane Python run-times (2021)

vortexa.com

50 pointsfanf236 comments

Difficult to draw conclusions with no code here.

An interesting thing they didn't mention is that Matplotlib's point-in-path code is actually already in C. So this isn't really a case of Rust being X times faster than Python, it's X times faster than some other C algorithm. That's probably why X is only ~4 (they don't actually give a single-thread comparison), instead of ~50.

https://github.com/matplotlib/matplotlib/blob/cb487f3c077c93...

I expect the Rust code is faster because that code is waaaaay more complicated than what they probably need (https://stackoverflow.com/q/11716268/265521) - e.g. it handles stroke widths.

IMO this result is not very interesting.

Here is a much better blog post on the topic of optimizing geometrical operations with Rust. If I remember correctly some of the commenters of the HN thread even delivered better "pure" Python versions than the optimized Rust proposed by really leveraging Numpy.

- https://ohadravid.github.io/posts/2023-03-rusty-python/

- https://news.ycombinator.com/item?id=35367520

My background is very different so this post made me sad. Doing tons of point-in-polygon tests is a common problem and should use spatial index. If we're testing N points against P polygons, the problem should scale O(N * log(P)) not O(N * P). The author was on the right track with bounding box tests, but that's more of a micro optimization. You want something like nested bounding boxes where each level contains 2 or more smaller ones, this is how you go from P to log(P) time - by never testing most of the polygons at all. I have my own preferred spatial index, but all of them tend toward this complexity improvement.

Would "quadtree" be the keyword here? That's always the first thing I think of when handling distributed points and doing some (local) measure on them.

You want a spatial indexing scheme. Quadtree is one approach, but depending on the distribution of your data (both size + location), an RTree would be better.

Related: - Quatree - RTree - BVH - Grid

>> Would "quadtree" be the keyword here?

Quadtree is one option, and would be my choice for 2D. Most people seem to prefer other structures for various reasons. You may also look at BSP trees, BVH or nested Bounding Boxes. There are others as well.

Rust approach may be great, strikes me as potentially a natural fit for a spatial index though - curious if spatial index would be practical and how it compares. Geopandas from memory has at least some support for spatial indexes. I believe geopandas if used naively will also do spatial operations quite naively (slowly)

I would even go further: this sounds like a database problem.

Is the set of ship positions and watched polygons entirely different from run to run? If not, it should be possible to go much faster than even the new rust based approach that takes 6 hours.

I would have used a postgres database with a PostGIS spatial index.

Absolutely. It’s kind of amusing to read a post that’s kind of dragging the wrong tool for the job, and then recommends another wrong tool for the job. The whole time I’m just yelling, “This is a geodatabase problem!”

There’s the right way, the wrong way, and the Max Power way. Wrong but faster!

This. While reading the post, I wondered when he'd mention something about spatial databases or spatial indexes.

Agreed. As someone who often advocates for the use of Rust to speed up perf-sensitive Python functions (and in particular, in the GIS domain), this sounds like they haven't fully understood the problem or thought about how to solve it more efficiently with a spatial index (which is easily done in Geopandas, let alone PostGIS). However, the post is a bit vague on details so who really knows.

I'd just throw it into a quadtree (or similar) and go get a coffee. I know there are some pretty fast bounding box algorithms from when I used to mess with such things but can't remember them off the top of my head.

Not an expert here, but something I didn't grasp from the article was, how much of the improvement came from running multiple cores, and how much from Rust being faster than Python? Granted, those two things may be intertwined.

Same question here. From one to eight threads typically doesn't account for 8x reduction directly. So if it's ten times faster, then I'd assume a single threaded Rust version made it at least twice as fast. Though I'd wager that a rewrite in Python, now starting out with full knowledge of the problem domain, would have likely also improved performance.

Python is slower than most things.

I have this thing I do where I'm using a json file basically as a database. Doing it with pure python was annoyingly slow so I wrote a simple(ish) wrapper around the boost::property-tree library (which does xml and json as both are needed for the project) and have been happily chugging along for years now.

I do wonder how much easier it would be to do the same thing in rust as I've found half the battle is tracking object/class lifetimes across the C-API barrier. As a side note, I'm also really good at hunting down segfaults...

https://pypi.org/project/orjson/

Try this from pypi. Its a big boost when dealing with json in python.

I was taken by surprise too by the false dichotomy presented:

> 1. Try breaking the data into chunks, and then using multi-processing (ugly in Python) to leverage a more powerful cloud virtual machine, sticking with matplotlib

> 2. Write a very small native custom library to do the math we want, using threads

There are a many more ways you could try to go about this, off the top of my head: numba, pypy (or other alternative python), jax/torch/tensorflow, multiprocessing, joblib.

so a 5x speedup from using 8x threads? I am not convinced this couldn't be achieved with numpy+multiprocessing ( or even maybe threading sinc numpy releases the GIL I think)

Wouldn't it be easier to port the code to Julia? Had the chance to use it for some control theory problems and it feels much more modern and sane than Python - especially under the hood.

On the other hand multiple dispatch and the way imports are handled left me quite confused as a beginner.

But it's powerful and also very fast, especially for plots.

Well let’s see the author used Rust because they had used it in another context recently. And you seem to raise your hand because you’ve used Julia recently.

There are at least a dozen languages that this would be easier in… depending on your background.

Oh I see. Didn't intended to be condescending here I was just really impressed by the Julia ecosystem for typical Python "data science" tasks and I don't know of any alternative with that much of newly designed and powerful scientific libraries.

I really want to know what the optimizations might have looked like had they used a profiler like scalene [0] to find where the unnecessary copying was happening.

[0] https://github.com/plasma-umass/scalene

I would have tried Numpy and GEOS before jumping to Rust.

Is there a code link I’m missing?

My immediate reaction was to try just annotating ctypes and see what performance delta exists

Have you tried pypy? Might be interesting comparison.

OT I heard recently that rust isn't actually used in Firefox which of the original use case? What's the story there?

It's used in Firefox. See e.g. the infobox of https://en.wikipedia.org/w/index.php?title=Firefox&oldid=123....

Idk where you got that info from because it is definitely. The CSS stack in Firefox was written in Rust in the context of Servo and then ported to Firefox.

There's plenty of Rust in Firefox, see https://wiki.mozilla.org/Oxidation

You might be thinking of Servo, which is a (purely?) Rust rendering engine that Mozilla abandoned, though it's not completely dead.

If you look at the actual LOC stats (https://docs.google.com/spreadsheets/d/1flUGg6Ut4bjtyWdyH_9e...), the rate at which the percentage of Rust code increases is pretty glacial: at the beginning of 2019 it was around 8%, mid 2020 (when the table ends) it got to ~ 12%. And today it's apparently at 11.4% (https://4e6.github.io/firefox-lang-stats/) - although I'm not sure if this is an apples-to-apples comparison, as the table compared Rust vs. C/C++, while the pie chart includes all code - incl. HTML, JS etc. If I take just the Rust and C/C++ from the pie chart, Rust would be at ~ 22%.

Firefox is something like 22 million lines of code, there's no way to make a dent in that at a pace that doesn't seem relatively glacial

Not an insider, but I can try:

1. I don't know if Rust is being used in Firefox today (edit: turns out it is, see my sibling comment), but I can imagine why they wouldn't: Mixing C++ and Rust is probably non-trivial with the kind of portability they're aiming for. A lot of the UI and "business" logic in Firefox is, and has pretty much always been, implemented in JS and XUL (which was also available to extensions before WebExtensions, which is why Firefox extensions could back then change almost anything about the browser). So with JS available for a lot of the logic, Rust is probably mainly interesting for replacing the lower level C++ parts.

2.Back when Rust was created, it was used in a project called Servo - a new browser engine. To my knowledge there were never concrete plans to switch Firefox over to that engine, but Firefox adopted a lot of the techniques they pioneered. Mozilla was a different organisation back then, happy to experiment with no clear path to revenue. I didn't find any of those developments too surprising. I'm definitely not surprised they don't undertake a major incremental rewrite these days where it's more about fast profitability.

Rust is definitely used in Firefox, but Servo[0], which was going to be the replacement browser engine (or at least the testbed for that), was abandoned by Mozilla, in a limbo for some time and now under new stewardship.

On a meta-level, I think the story that people like to tell is that Mozilla chose increasing executive compensation rather than using the same money to keep the Servo (and people working on Rust itself) employed.

[0]: https://servo.org

Firefox is currently 11.4% Rust, according to https://4e6.github.io/firefox-lang-stats/

> OT I heard recently that rust isn't actually used in Firefox which of the original use case?

Narrator: It wasn’t the original use case.

The amount of compute cycles and development time that could have been saved for every single time, teams have to deal with scraping scripting code for something that actually performs.

Several options are available with JIT and AOT toolchains, alongside REPL programming environments.

Reply on news.ycombinator.com