This is a list of microoptimizations. Designing the architecture of your whole program to be cache friendly was not addressed here, but is arguably more important.
Besides SoAs vs AoSs (which is my understanding is the most impactful thing you can do to make many use cases more cache friendly), are there other things you might suggest? Or articles?
For example properly understanding the trade offs with IPC to influence both the architecture of the components of your system and when and how you talk to the other components. Having to switch to the kernel or to other processes can get your data kicked out of caches.
Reduce your working set. Make frequently used data and instructions as small and contiguous as possible. Reuse memory, e.g. store two large objects in a variant if you don't need them at the same time, or instead of calling free() keep the pointer until you need space again. Don't let templates bloat your instruction count. Be open to creating custom data structures when the standard library ones aren't optimal for you.
Recently I worked on a simulation analysis which taught me several things:
- To get the most out of Python, you really need efficient libraries like Numpy. I started off my project in pure Python and some Pandas. But soon I realized it was painfully slow and looked for better solutions.
- Polars looked like a good Pandas alternative, but some googling revealed that it could be slower than Numpy. Although it's easy to work with dataframes (e.g., you can select a column by calling its name), I converted all my code to use Numpy and suddenly saw huge speed boost. But that wasn't the end of it. I was now in a rabbit hole...
- Vectorization helped a lot with speed as well. I learnt that using the right tool (in this case, Numpy) guides you to do better and vectorize operations, whereas Pandas didn't enforce that technique on me. Despite the initial hurdle, I realized that vectorization made my code much more readable and easier to follow.
- I then parallelized my code to utilized all 10 cores of the M1 Pro chip. Seeing that CPU graph get full was just pleasing. For this, I used Python's ProcessPoolExecutor, which is better than ThreadPoolExecutor.
- At this point, my simulations had gone from taking several hours to a couple minutes! Pretty impressive, but then I noticed that increasing the resolution of some variables resulted in RAM issues. I have 32GB of RAM and working with huge matrices was just not feasible. I remembered that the OS community has been using quantization techniques to reduce the memory footprint of LLMs. The way they work often involves going from np.float32 to np.float16. To my surprise, doing this solved my RAM issues without much effect on the accuracy of the results.
- Looking for further improvements, I discovered Dask and used it instead of ProcessPoolExecutor (although, I still used `schedulor="processes"` in Dask). Unlike ProcessPoolExecutor, Dask didn't utilize all my CPU cores all the time, but somehow I found it more capable of handling parallel computation.
- But increasing the resolution of parameters even further would still cause problems. Specifically, I noticed that my Python code would halt. Doing CTRL-Z would stop the program, but the RAM wouldn't get released. In this case, I had to manually `pkill -f python` to throw away all the Python objects that were taking up RAM space.
- This is where I discovered garbage collection. Using `import gc`, I was able to `del <obj>` at key parts of my code and immediately do `gc.collect()` to collect garbage. This was the first time I ever did this and I was pleased to see my program run again w/o RAM issues.
- I then optimized some search algorithms in my code which further sped up the program while also reducing the RAM usage.
- I converted all Numpy arrays to ds.array for further improvements, but some functionalities were not immediately available and I went back to Numpy.
- Looking for further improvements, I thought about running my Python code on GPU. I tried `import cupy as np` but got to problems that I couldn't solve.
- So I tried converting all numpy arrays to Pytorch tensors. Pytorch is available on M1 Mac so I thought why not? Unfor, I got memory limits errors. Reducing the resolution of parameters fixed that, but then I got a mysterious error for which I couldn't find any help:
-[_MTLCommandBuffer addCompletedHandler:]:871: failed assertion `Completed handler provided after commit call'
If you know what this means, please let me know!
This was an educational journey and I learnt much. I think projects like this are the best way to learn new stuff.
This is honest question for those that use python for these compute intensive tasks and is not meant as a critique.
If you ultimately end up having to use c/c++/fortran native libraries and work around pretty much everything python. What is the point of using python instead of c/c++?
Others answered this correctly. Python is more like a glue language that is easy to use. I ended up using type annotations in my code and in the end it looked a lot like a typed language. But the nice thing about Python is that types, manual garbage collection, etc. are not necessary for most applications.
But I can recognize an ad hominem argument when I see it. Merely attempting to illuminate the intelligible with truth.[^1] OP said "If you ultimately end up having to use c/c++/fortran native libraries and work around pretty much everything python. What is the point of using python instead of c/c++?" The answers boiled down to making it easy for people with no formal computer training to leverage C, C++, and Fortran libraries written by professionals. Hopefully that is something we can agree on.
I'm confused by some of this. Specifically, pandas columns are essentially just a thin wrapper around record arrays in numpy right? How could it be that much faster to use numpy over pandas if it's effectively the same thing?
Right, each pandas column is a numpy array (or optionally pyarrow in pandas 2.0), but numpy is going to be faster for things that needs to be vectorized across columns, such as matrix operations.
I used to do this sort of thing in Python. But then I realized that if I wrote my code in something like C++, I had fast code without running through all these hoops. Then I learned Rust which has many of advantages of Python in terms of higher-level niceties. Today, its just way easier to write some Rust code for a simulation then go through all the hoops to make Python code fast enough.
Your entire journey here is battling with Python and not the problem space. Your improvements are solely measured by how your code leaves Python problem solving space, so you end up writing what's probably unpythonic and unmaintainable Python.
Why?
Rewrite in Go, Rust or C++ or whatever.
If you need to go faster than Python, don't use Python. Python is great for everything else. Its overhead and sluggish execution are consequences of its greatest strength.
Exactly my thought. Whenever I see wild optimization goose chases it's Python causing all the issues.
The problem is that a lot is still possible to optimize "in Python" although as you say the code becomes less and less readable to your average Python developer, so that people don't notice they just picked the wrong tool for the job.
You need more speed? Use multiprocessing? Allocate memory appropriately? Rust, or if you like pain, C or C++.
Doesn't Tensorflow has C++ API? I think tensorflow and pytorch under the hood using c++/c. Tensorflow has even official Rust bindings. The same applies to libraries like Open3d and OpenCV - although mostly people consume their python API under the hood is very optimized C++ code parallelized for many CPU and SIMD instructions.
All this reminds me of writing a Go (the board game) engine in Python. There's a lot of looping involved to identify groups and their liberties, and to detect Kos, etc. I profiled my Python code and optimized the algorithm, and it was faster. Then I rewrote my Python "Board" class in Rust and called it from the rest of my Python code, and it was faster again.
Then I wrote the same algorithms in Julia, and it was as fast as the Python / Rust solution. Then I learned that Julia lives up to its claim.
If you're reaching for Numpy / Pandas as an optimization, and not as a convenience, then consider rewriting your code in Julia.
ctrl-z doesnt kill the runnning program, just puts it to the background. The process is still present with all RAM still held by it... you ca use "fg" to bring it back to the foreground.
I think you meant ctrl-c which kills the process.
Using polars and rust might be the best option right now, offering high level operations such as SQL like joins as well as performance. Although im not a rust programmer and i only use tbe python library polars, so please correct me as necessary.
It seems to me there is scope for a language feature of 'managed memory' where you declare the data you need and how it is to be accessed (or access can be determined from the program), and let the language/compiler figure out how to organize it for safety and performance.
For example if you declare an array of structures, the compiler/language should be able to turn that into a structure of arrays under the hood if that is the way the data is accessed.
Not sure how that could work in practice, I guess you'd start with hints, but it seems like something to research. Indeed I'm sure there's already some research in this area.
I could imagine a language /framework where we declare the schema of data, indexes on this schema, and either let a query planner optimise data access or explicitly specify which index to use
Sure at a conceptual level all stored data, even transitory, is a database, but I don't think that's a helpful analysis here, for a start current databases are far too limited.
A database implies a separate runtime system to manage data, whereas this is data storage within a program, part of 'data-structures and algorithms'.
Sure, but you're describing a fully functional database integrated with a fully functional programming language.
Just because you're describing a possibly novel integration of those two systems doesn't mean it's not valuable to consider the prior art for both constituent pieces.
Halide is pretty specialized and only somewhat related to this, but I really like the concept: https://halide-lang.org/
A tldr is: define your logical algorithm and its implementation separately, so you can freely tweak the implementation to optimize it without risking correctness.
I’m working on a masters thesis doing essentially this, for the problem of prefetching. There are a lot of existing papers demonstrating techniques for smarter prefetching for non- sequential data structures like trees and graphs. That can be done with some success purely at the hardware level, but having language- level semantic information helps a lot for dealing with complex data structures. What I’m working on is a cache controller modification to allow the running program or OS to tell the cache controller how best to prefetch specific pieces of data.
"having language- level semantic information helps a lot for dealing with complex data structures."
Yes that's what I'm thinking - much of the current stuff seems to be trying to guess what the code is doing from a low level (eg branch prediction) whereas the language itself could tell.
Definitely possible, it’s a fairly active area. There are a few very similar techniques I’ve seen covered, but I think the details of my/our approach are still unique enough to merit publishing (for now), if I can get reasonable performance results.
And yes, loading semi-arbitrary code into a prefetcher is quite scary. It was the first question I had about this project. I think that maybe picking and choosing one of a multitude of prefetching "recipes" which are trusted would be more plausible as en eventual viable strategy. Like, the compiler inserts some instructions after allocating the nodes of a DAG that says "hey prefetcher, this is a DAG, please choose the graph prefetching algo with x/y/z parameters."
I've previously written about the idea of serialised access patterns. If we could somehow represent all the patterns of the data we're accessing, we could optimise layout.
See SHAPES[1] for a method of selecting data layout without sacrificing the abstraction programmers are typically used to having in OOP.
The idea is that a "layout" is decoupled from the object that stores the data. Layouts are attached to a memory pool which is used to allocate objects. The same object representation can have its data laid out in multiple ways depending on which pool allocates it.
Some things you have no control over, like padding and alignment or explicit stack allocation (not counting non-managed memory / Unsafe). But the rest should apply just the same.
Well it's kind of tough because the JVM does a lot of this for you! The JVM will try to pack "related" memory closer together. It can even do really cool things for tree structures (like a Node class) and linked lists - which is why you see java perform so well on these types of data structure benchmarks.
In Java we have to worry about different things, like the number of fields on an object and object header sizes. A lot of advice in the article is still good to keep in mind when optimizing code on the JVM, though, like keeping frequently accessed fields next to each other.
Cache-friendlier than past versions happens all the time for PHP and Javascript. A fair amount of the gains in PHP7 were optimizations that reduced reallocation of memory, "packed arrays" where if an array is all ints to store it in a more compact structure, etc.
Polymorphic inline caching would be another example of trying to reduce the performance impact of a dynamically typed language...being more cache friendly despite the handicap of not knowing everything until runtime.
In JavaScript you can use Buffers to allocate bytes and manage memory manually to avoid allocations in hot paths. If you're doing that then yes these techniques can be relevant.
And this isn't that obscure, many Node libraries and apps seeking performance do actually do this manual memory management. I just can't find one from a quick search.
62 comments
[ 2.8 ms ] story [ 112 ms ] thread- To get the most out of Python, you really need efficient libraries like Numpy. I started off my project in pure Python and some Pandas. But soon I realized it was painfully slow and looked for better solutions.
- Polars looked like a good Pandas alternative, but some googling revealed that it could be slower than Numpy. Although it's easy to work with dataframes (e.g., you can select a column by calling its name), I converted all my code to use Numpy and suddenly saw huge speed boost. But that wasn't the end of it. I was now in a rabbit hole...
- Vectorization helped a lot with speed as well. I learnt that using the right tool (in this case, Numpy) guides you to do better and vectorize operations, whereas Pandas didn't enforce that technique on me. Despite the initial hurdle, I realized that vectorization made my code much more readable and easier to follow.
- I then parallelized my code to utilized all 10 cores of the M1 Pro chip. Seeing that CPU graph get full was just pleasing. For this, I used Python's ProcessPoolExecutor, which is better than ThreadPoolExecutor.
- At this point, my simulations had gone from taking several hours to a couple minutes! Pretty impressive, but then I noticed that increasing the resolution of some variables resulted in RAM issues. I have 32GB of RAM and working with huge matrices was just not feasible. I remembered that the OS community has been using quantization techniques to reduce the memory footprint of LLMs. The way they work often involves going from np.float32 to np.float16. To my surprise, doing this solved my RAM issues without much effect on the accuracy of the results.
- Looking for further improvements, I discovered Dask and used it instead of ProcessPoolExecutor (although, I still used `schedulor="processes"` in Dask). Unlike ProcessPoolExecutor, Dask didn't utilize all my CPU cores all the time, but somehow I found it more capable of handling parallel computation.
- But increasing the resolution of parameters even further would still cause problems. Specifically, I noticed that my Python code would halt. Doing CTRL-Z would stop the program, but the RAM wouldn't get released. In this case, I had to manually `pkill -f python` to throw away all the Python objects that were taking up RAM space.
- This is where I discovered garbage collection. Using `import gc`, I was able to `del <obj>` at key parts of my code and immediately do `gc.collect()` to collect garbage. This was the first time I ever did this and I was pleased to see my program run again w/o RAM issues.
- I then optimized some search algorithms in my code which further sped up the program while also reducing the RAM usage.
- I converted all Numpy arrays to ds.array for further improvements, but some functionalities were not immediately available and I went back to Numpy.
- Looking for further improvements, I thought about running my Python code on GPU. I tried `import cupy as np` but got to problems that I couldn't solve.
- So I tried converting all numpy arrays to Pytorch tensors. Pytorch is available on M1 Mac so I thought why not? Unfor, I got memory limits errors. Reducing the resolution of parameters fixed that, but then I got a mysterious error for which I couldn't find any help:
If you know what this means, please let me know!This was an educational journey and I learnt much. I think projects like this are the best way to learn new stuff.
If you ultimately end up having to use c/c++/fortran native libraries and work around pretty much everything python. What is the point of using python instead of c/c++?
[^1]: BTW, I am not the sun either.
more you could try:
- span multiple machines, with lambda/ec2-spot and s3
- write c/cpp, call via python subprocess or cffi
- pytorch gpu on ec2-spot
Depending on the resolution of my parameters, I'm dealing with a 32-40GB-ish data.
Use the right tool for the job.
Your entire journey here is battling with Python and not the problem space. Your improvements are solely measured by how your code leaves Python problem solving space, so you end up writing what's probably unpythonic and unmaintainable Python.
Why?
Rewrite in Go, Rust or C++ or whatever.
If you need to go faster than Python, don't use Python. Python is great for everything else. Its overhead and sluggish execution are consequences of its greatest strength.
The problem is that a lot is still possible to optimize "in Python" although as you say the code becomes less and less readable to your average Python developer, so that people don't notice they just picked the wrong tool for the job.
You need more speed? Use multiprocessing? Allocate memory appropriately? Rust, or if you like pain, C or C++.
Then I wrote the same algorithms in Julia, and it was as fast as the Python / Rust solution. Then I learned that Julia lives up to its claim.
If you're reaching for Numpy / Pandas as an optimization, and not as a convenience, then consider rewriting your code in Julia.
For example if you declare an array of structures, the compiler/language should be able to turn that into a structure of arrays under the hood if that is the way the data is accessed.
Not sure how that could work in practice, I guess you'd start with hints, but it seems like something to research. Indeed I'm sure there's already some research in this area.
I could imagine a language /framework where we declare the schema of data, indexes on this schema, and either let a query planner optimise data access or explicitly specify which index to use
A database implies a separate runtime system to manage data, whereas this is data storage within a program, part of 'data-structures and algorithms'.
Just because you're describing a possibly novel integration of those two systems doesn't mean it's not valuable to consider the prior art for both constituent pieces.
A tldr is: define your logical algorithm and its implementation separately, so you can freely tweak the implementation to optimize it without risking correctness.
Yes that's what I'm thinking - much of the current stuff seems to be trying to guess what the code is doing from a low level (eg branch prediction) whereas the language itself could tell.
Sounds like a nightmare post-spectre.
And yes, loading semi-arbitrary code into a prefetcher is quite scary. It was the first question I had about this project. I think that maybe picking and choosing one of a multitude of prefetching "recipes" which are trusted would be more plausible as en eventual viable strategy. Like, the compiler inserts some instructions after allocating the nodes of a DAG that says "hey prefetcher, this is a DAG, please choose the graph prefetching algo with x/y/z parameters."
The idea is that a "layout" is decoupled from the object that stores the data. Layouts are attached to a memory pool which is used to allocate objects. The same object representation can have its data laid out in multiple ways depending on which pool allocates it.
[1]https://www.doc.ic.ac.uk/%7Escd/ShapesOnwards.pdf
class Point:
# shift every pointx_array += 1
In Java we have to worry about different things, like the number of fields on an object and object header sizes. A lot of advice in the article is still good to keep in mind when optimizing code on the JVM, though, like keeping frequently accessed fields next to each other.
Polymorphic inline caching would be another example of trying to reduce the performance impact of a dynamically typed language...being more cache friendly despite the handicap of not knowing everything until runtime.
And this isn't that obscure, many Node libraries and apps seeking performance do actually do this manual memory management. I just can't find one from a quick search.