Programming language constructs for cache optimization?

Question

Clearly optimizing cache usages is bound to improve my program efficiency. Surprisingly, I don't see too many programming languages actually having this sort of a feature. So here's my question:

1. What kind of language constructs have you seen that help improving cache usage?
2. How to innovate on cache usage since most systems won't easily reveal stuff like their L1 cache size easily? (Windows does have API or maybe /proc/cpuinfo on Linux, but I am looking for something simpler for the intermediate developer)

Answer 1

This is just an off-the-head list.

Concepts

• Spatial locality
• Temporal locality.
• Easily-predictable memory access patterns.
  • For example, reading/writing megabytes of data sequentially is not at all inefficient, because the CPU can predict the next address and automatically read ahead.

Programming language constructs.

• Data alignment directives.
• Switching between array of structure and structure of array.
• Vectorized data containers provided by high-performance libraries.

The compiler has already done some of the work for you. For example, groups of functions that are closely related (for example, likely to be called in successive sequence) will be compiled into binary instructions and then stored close to each other, so that they reside within the same 4KB page block. There is simply no way for a developer to cater to such details manually.

For native compiled languages, local variables are stored on the stack, and the area closest to the current stack position is likely to be cached. If a large variable (several KBs or more) is allocated from the stack, the CPU may have to evict something else from the cache to make room. On the other hand, if the large variable is used very frequently, then allocating from stack can be justified.

Answer 2

there's no trivial answer here. in a multiprocessing system (i.e. any modern OS), you can't make many assumptions about the state of virtual memory. you can make some general observations regarding data structures though. hashing techniques may allow you to develop a more reliable affinity between data and storage, whereas data structures like trees will tend to employ offsets that degrade the effectiveness of caching...BUT take this all with a huge caveat...profiling the benefits of one technique over another is going to be extremely difficult and specific to your own architecture and memory hierarchy.

the shortest answer here is for the "intermediate developer", you are far better off using well-tested libraries that have clearly stated performance bounds and well-understood memory consumption patterns. trying to optimize for caching on a specific hardware platform would seem to be a painful last resort for the most difficult problems.