Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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)
share|improve this question
    
For the second question you have to use CPU vendor-specific profile tools. Modern CPUs have hidden performance event counters. These counters are usually only accessible from the vendor tools. –  rwong Dec 5 '10 at 8:15
    
Read Agner Fog and Herb Sutter –  rwong Dec 5 '10 at 8:34
add comment

2 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.