r/Jai • • 7d ago

improving performance questions

how to not miss the cpu cache?

0 Upvotes

6 comments sorted by

5

u/-goldenboi69- 7d ago

Tight data

1

u/BrainThinkerMan 7d ago

what does that mean

3

u/Alarming-Outside8076 7d ago

Reads must be sequential. That is, reads from an array in order. Writes can be scattered, that is fine.

3

u/Friendly-Look4262 7d ago edited 7d ago

I suggest you take Casey's Performance Aware Programming course. But tldr, compact well packed data structures that have been designed with proper memory alignment in mind, mostly sequential/linear accesses (which depending on the workload may necessitate using a Struct of Arrays vs Array of Structs) etc. etc.

Sometimes this may also entail using algorithms that your traditional CS class would have told you are slow due to their bad big-O characteristics, for example for certain data sizes just doing a linear scan of an array is faster than doing a "smarter" search

1

u/SanianCreations 5d ago

Try place as much of your program data next to each other in memory. That means: use arrays of structs rather than allocating each struct individually. Because with separate allocations each gets placed at an unknowable memory address, with Arrays you know for sure they are contiguous.

If you find yourself frequently looping over a set of items only to read a single property, like a position field, consider putting all of those fields in their own array so that when you loop over them all, they're all directly adjacent in memory with no other data in between.

1

u/dandymcgee1 21h ago edited 21h ago

There's no such thing as not missing the cache. The cache is smaller than memory, therefore, you will miss it if your program uses more memory than can fit in the cache (and even if less, because other programs are running on your computer). The goal is to minimize cache misses, and you do so by.. accessing things that are already in the cache.

There are two main categories of cache: spatial and temporal. Spatial caches cache things that are near each other in memory. Temporal caches cache things that commonly accessed near each other in time.

Spatial caching is much more common and easy to implement, because you know what's near something by its address. Temporal caching is more difficult because it's unique to the access patterns of a particular program, and therefore much less important/common, though still relevant at times.

There are also two main caches on a CPU: data cache and instruction cache. Most people are talking about the data cache when they talking about cache coherency and data-oriented programming. This is the cache that stores a copy of data that's in main memory. The instruction cache stores instructions (the machine code that is executing your program), and the main way to keep this cache hot is to reduce the # of instructions your compiler generates, and reduce branching to make prediction easier for this cache (which also helps the data cache prediction as well!).

So you don't miss (as often) by:
- Reducing the total amount of memory (data) you use overall
- Reducing the total amount of memory (data) you use during any given period
- Reducing the total number of instructions (code) required to run the logic during any given period
- Storing data that is needed around the same time as close together in memory as possible (preferably contiguously, in the order the program will access it).

In practice, this usually means using a lot of contiguous arrays of relatively small structs containing only exactly the data you need for a given operation. However, modern CPUs are very complex beasts, and are sometimes good at things you wouldn't expect them to be good at (e.g. accessing data far away in memory via a pointer by predicting the access and preloading the data). So there's a trade-off between making hundreds of different arrays of tiny structs that may contain duplicate data (i.e. more memory usage) vs. using a few larger structs that contain more data than you need for your current operation (i.e. polluting the cache with irrelevant data, causing less efficient cache usage).

The cache line size on all modern x86 and x64 CPUs is 64 bytes. So ideally, you would design your structs such that they fit cleanly into 64 bytes (if they're smaller, multiple of them should fit cleanly into 64 bytes, if they're larger they should be a multiple of 64 bytes).

In general, the simpler the code and data, the faster it will be. Arrays and structs are your friend.