Make your programs run faster by better using the data cache (2020)
johnnysswlab.com
johnnysswlab.com
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.
class Point:
i: int
def get_x():
return x_array[i]
x_array += 1
- 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'
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.
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.
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.