5 ms·
Make your programs run faster by better using the data cache (2020)
- charcircuit 3y agoThis 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.
- hoten 3y agoBesides 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?
- charcircuit 3y agoFor 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.
- jzwinck 3y agoReduce 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.
- behnamoh 3y agoRecently 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.
- wudangmonk 3y agoThis 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++?
- jameson71 3y agoThe code outside the critical path is easier and quicker
- nathants 3y agothink of python wrapping other tools the same way bash does.
- behnamoh 3y agoOthers 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.
- keithalewis 3y agoTricycle riders will never become Formula 1 drivers.
- wiseowise 3y agoYou’re not Plato either, didn’t stop you from trying to come up with sound analogy.
- keithalewis 3y agoBut 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. [^1]: BTW, I am not the sun either.
- Nocturium 3y ago[flagged]
- Nocturium 3y ago[flagged]
- deleted 3y ago[deleted]
- jacknews 3y agoIt 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.
- klysm 3y agoI frequently having a hard time deciding which transpose to use when there are multiple consumers that each want a different shape
- ttymck 3y agoSounds like a database
- williamdclt 3y agoYeah it gave me this hunch too. 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
- ttymck 3y agoYou've described SQL :)
- jacknews 3y agoSure 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'.
- etoulas 3y agoThis might be a silly question but are there similar optimizations that apply to Java?
- MrBuddyCasino 3y agoSome 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.
- winrid 3y agoWell 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.
- karelpeeters 3y agoThat sounds interesting, what does the JVM do for tree structures and linked lists? Is that just about compacting memory?
- mklepaczewski 3y agoIs it feasible to construct CPU cache friendly programs in interpreted languages like PHP and JavaScript?
- tyingq 3y agoCache-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.
- eatonphil 3y agoIn 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.
- __s 3y agoYes. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Typed_arrays https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guid...
- kosolam 3y agoYes! Very simple and easy to understand explanation. The best I read on this subject so far.
- barbariangrunge 3y agoI don’t understand why compilers can’t automatically do some of this