Recent adventures in performance optimization with Rust
willcrichton.net
willcrichton.net
Step 1:. A slow but easy implementation. It allows to make sure the algorithm is correct, and later allows validating the faster variants.
Step 2: Algorithm and datastructure optimization, guided by profiling.
Step 3: Micro optimization, again guided by profiling. A standard bag of tricks is applied. I didn't see cache friendlyness/tiling in here, which surprised me.
Step 4: Parallelism, first by SIMD then by threads.
I am very much not downing the author: This is a great teaching of the process, it's a lot of hard brainy work, and we didn't see everything he tried but which failed. So thank you, author.
My point is: it is not magic. It is engineering. It is a skill that can be aquired, thought, even planned and measured.
Unfortunately in this day and age, the art of optimization is lost. Companies are willing to ship shitty code to production and increase performance by throwing more hardware at it.
But I'd have thought there must be heuristics to help narrow the search.
For example you could calculate how each question correlates to all the other questions[1]. If you picked the set of k questions with the best correlation, then you have a good sense of which will be in the actual "k-corr set".
You could widen your search a little bit, but by chopping out any questions which correlate poorly to the overall score, you narrow your search greatly, going from 200 choose 5 to 10 choose 5 is a speedup factor of a million, and you've probably considered all the sets that are likely to be in the final bucket.
It's been a while since I've worked in the domain, but OP might also want to check out https://en.wikipedia.org/wiki/Item_response_theory and https://en.wikipedia.org/wiki/Classical_test_theory.
[1] https://en.wikipedia.org/wiki/Point-biserial_correlation_coe...
I would not be surprised if we do rewrites of all the past 20 year code in to Rust or Go or any other performant language.
Lets agree on this, you are smart and the author is right.
I am sorry people who are complaining are not seeing where the ball is going.
But to get back to what you’re talking about here, we recently spoke with Lunar about their transition from a Node backend to a Java backend and then finally to a Go backend and how they can’t imagine building anything without Go going forward. Very interesting considering that the JVM is quite performant itself. I’m not sure we’re going to follow them down the Go rabbit hole, I think we’ll remain on a Node backend for non-performant stuff since it lets us use one language for most things. But I do think your predictions are right.
I guess the title gets clicks, but I'm curious how good python gets. I'm under the impression pandas is pretty fast despite it being python
I feel though the killer is that inner loop where dataframe operations are being performed across a large number of iterations, and there's significant overhead there.
For-loops are usually not the most performant solution in Python.
I could be wrong, I feel that there's a SQL way to answer that question, in which case DuckDB might be able to exploit vectorization, parallelization, indexing and query optimization across the dataset in one fell swoop.
code in pandas can be very slow (standard pure-python speed) or "fast-for-python" depending on if you are going with or against the grain. a pandas dataframe is basically a bunch of numpy arrays, one array per column. if you do columnar calculations that can be reduced to numpy operations, like summing over a column, then numpy will execute the operation in native code, and it will be fast-for-python, but there will still be some overhead due to wrapping things in python, as well as perhaps temporary array allocation etc.
if you do something against the grain, such as expressing all your pandas calculations as on row-wise operations instead of column-wise operations, or using "apply(lambda x: pure_python_expression_of(x))", then pandas cannot execute it efficiently, as the operations are going against the grain of how things are stored in memory, and the operations cannot be reduced to native code primitives on the column arrays that are implemented in numpy.
another alternative to switching to rust is using cython to define a native python module. by starting with python code and using many of the same optimization rules of thumb in this post (static typing! avoid frequent tiny allocation, preallocate stuff! avoid hashing complex things, prefer arrays with indexes!), you can translate idiomatic (and very slow) pure python code into simple code that looks closer to array-oriented fortran-in-C, that runs very fast and compiles to a native python module that is easy to integrate.
I think it's more like 50-200x in my experience. Which is still crazy slow, but not 1000x slow.
> for qs in combinations(all_qs, K):
> > ...
> > corrs.append({'qs': qs, 'r': r})
>
> corrs.sort_values(...)
with a python style list comprehension:
> def build_q(combination):
> > ...
> > return {'qs': qs, 'r': r}
>
> max(build_q(c) for c in combinations(all_qs, K), key = lambda v: v['r'])
But my thing is, I think the problem could be solved in a different way in Python where we can use performant libraries to get an answer in a reasonable time.
The author says the naive Python implementation with a for-loop takes 36 milliseconds per iteration, and the problem requires 2.5 billion iterations (= 2.9 years, which is unreasonable) while optimized Rust takes 8 mins (corrected).
I believe we can solve the problem in Python in a reasonable amount of time (not 2.9 years) by expressing it differently. And I believe we can do it in Python without trying to optimize Python operations like the author is doing with Rust.
Imagine your boss came up to you and said I need the answer by this week and that you could only use Python, you would need to come up with a way to solve it. I wouldn't start by trying to optimizing Python's for-loop -- I would break out of the loop paradigm altogether and use arrays, database indices, optimized dataframe libraries (probably written in C++ or Rust) to get there. Because Python is not fast -- everyone knows this -- Python programmers will often think of other ways (generally reaching for libraries) to solve the problem.
“Setup some infra, and get someone who knows how to operate it, and then write new code in python, and babysit it as it ossifies into a core piece of infrastructure”
_or_ optimise it in a language you’re already using, or is semi-common in your stack already, and then move on with things.
The author wrote in a strongly typed, ahead of time compiled language, ran a profiler to help wipe out hotspots for optimization, and the program is now dramatically faster than unoptimized Python.
Yay? I guess?
It does feel a little unfair a comparison. Everyone knows that for loops are slow in python.. as is much of the core library. But pushing analysis to c using pythonic APIs (numpy/numba/pytorch) is fairly trivial
The post deals a lot both with strings and maps with strings as keys. One idea is to intern these strings using an interer like [1] which returns string keys as monotonically increasing integers starting at 0. Then instead of a map you can just have a regular vector with the interned key as the index into the vector. This gives you the map functionality with very good performance.
This is after many years of corporate java/c#/python/ruby shops. The number of "developers" and "architects" that don't understand low level concepts is draining and disappointing. Worked with too many corporate "code monkeys" that masquerade themselves as "engineers" or "architects". It has got me jaded sometimes.
The author of this post has given me hope that there are people out there willing to push the boundaries of their code with their years of experience and understanding of low level computer concepts.
Definitely bookmarked and will use as reference!
Also, I wonder if there is some way to use branch-and-bound to look at fewer combinations.
It's just another LLVM frontend.
Also I'm slightly annoyed by the fact that they kept talking about great GPU performance in their marketing material and all you can find in the docs is: "it's coming. probably. only to Nvidia hardware btw."
The problem is you're advertising performance and static typing to Python programmers, but pretty much anyone who is voluntarily choosing to use Python has already decided they don't care a jot about performance or static typing.
Everyone else who is forced to use Python doesn't have the option of introducing another language anyway.
It's like showing how much faster you can get your handcrafted assembly code to run vs a bash script.
I don't think the point of the article is a rust-v-python comparison. Sure, unoptimized-python2rust2optimized rust was a part of the clickbait 180,000x title but... - the author explicitly says the python2rust bit is only a factor of 8. - the Python bit is just one section of a pretty long article - the author says they typically start implementing something in Python so... why wouldn't they include their initial implementation?
I don't think this article should be dismissed just for including a simple python implementation- that isn't the point.
This format is likely very useful for anyone working on such large sets using Jupyter/Python and waiting days for scripts to complete -- there is nothing wrong with those final tricky optimisations when applied to single-use scripts
I found it a useful reminder that there is often more to be squeezed out on inner loops with a few mins more thought
But in a real scenario there are often so many other constraints that “optimized code” is far from the top. Salaries are also expensive, so if you factor in the lifetime cost of writing and maintaining a bit of exotic Rust for an exotic problem, it might actually be cheaper to buy a bigger machine and brute force the problem.
Sure, we could all benefit from learning a bit of Rust then, but if you’re in the Python data space you know that it’s almost as crowded as frontend frameworks, and learning Rust comes across as a yet-another-framework problem, that few of us really feel like we have time for.
Personally I’m stuck maintaining a wizard’s (who has now left the company) solo project which initially seemed like a great solution, but has caused more grief in maintenance and bugs than any existing not-as-custom-tailored community solution out there. So if I were to tell my manager “I’ve spent a week to rewrite this job that spends 40 minutes at 2 AM to spend 1 millisecond at 2 AM, from a language that everyone uses to a language that only I use” I’m not sure he’d appreciate it.
good engineering should figure out what the main constraints are, and solve for those, while doing a "good enough" job for everything else and no more -- like you allude to, the main bottlenecks to solve for are usually things like reducing engineering effort, reducing schedule, reducing long term maintenance cost of the overall system (not just this isolated component) - especially how easy it is to hire someone who can understand and fix the thing.
but, this article isn't a "how to make good whole-system engineering tradeoffs for the long-term benefit or your employer / client" article, it's an article showing how to write fast rust code.
As you can probably tell from my sentiment above, it doesn’t help the author’s cause by basing the premise on a strawman. If the intention was to push Rust for Python users, this article shoots far, really far, but completely misses the mark. Nobody was telling themselves that Python was the fastest language out there.
I guess you could make a point out of how the author didn’t need to bring Python into the article, but on the flip side, they clearly state that they typically prototype in Python. So it would also be an incomplete article if they left out the initial implementation for the problem they are solving.
Fairly complex code like what the author showed turns out to use a bunch of different random things nobody expected.
Are you really saying this about C++? For real?
I quite like C++ but the idea that it doesn't hide complexity is hilarious. Something as simple as `a = b` can call constructors, copy constructors, assignment constructors, move constructors (depending on a lot of details), do implicit type conversion, throw exceptions, etc. etc.
In Rust it's just memcpy.
Maybe you're thinking of proc macros which can do a lot more than in C++, but they're just a more convenient way of doing codegen which you can equally do in C++ (e.g. to generate Protobuf code).
Instead, Rust opted to do as much syntactic sugar as possible.
Of all the criticisms of Rust, this is really the weirdest. What syntactic sugar do you find objectionable in Rust? It has almost none.
Are you talking about macros?
the problem is that in a lot of applications nobody cares about safety or security. it is just that devs operate in evironments where that matters and they think therefore it matters everywhere all the time.
when a language does something for you you then typically don’t learn what it actually does under the hood which will come back to bite you later. i have some of that problem with the latest C++ features as well, btw, which is why my C++ tends to look like C with classes and here and there use of a modern feature.
Rust safety on the small scale is an enabler for stability in the large scale, giving the possibility to take more risky optimizations. This is exactly where C and C++ fall flat. You can write small scale stable software with them, but multy decade multi team 1000k+ lines of software turns in a CVE fest. A lot more effort in documenting interface details and validation need to be done,because the compiler can't do it for you
It's well known that Rust's default HashMap hashing function is slow because it's designed to be safe against DoS [1]. If you want your HashMap to be faster, just use a faster hashing function like ahash[2], which can be up to 40% faster.
[1] https://doc.rust-lang.org/book/ch08-03-hash-maps.html#hashin...
> Note that everywhere we refer to HashMap is actually an alias for fxhash::FxHashMap, which is just std::collections::HashMap with a more efficient hashing algorithm