Clairvoyance in caching - optimal strategies?

Question

This question relates to the question here, but I'll generalise it so that you can answer effectively without reading all of that.

---

Context:

Imagine you had a large set of data greater than your available RAM that was partitioned in to chunks.

_{(Sized such that access was efficiently processed by virtual memory managers etc.)}.

An application with a GUI prompts a user to record a sequential process that will require access to sections of this data over time.

In realtime this would be managed by a kind of LRU cache for the user so they get feedback (perhaps at a lower resolution to account for latency). Data required, but not in RAM would be loaded by replacing older data that is tagged 'least recently used'...

But now instead, imagine that I know the sequence in advance - i.e. I effectively have look-ahead/clairvoyance of future memory access requirements.

It is assumed that the size (in GB/whatever) of unique data required integrated over the full sequence, is higher than the amount of RAM available (at least double).

Questions:

What optimal algorithms/strategies are there to manage this in the case of:

1. Needing to 'play' back the sequence in a kind of psuedo-realtime (sequential) manner for a user.
2. Needing to just process it as fast as possible in a non-sequential 'offline' fashion.

Imagine a worst case where data was required 'on and off', but often throughout the sequence - i.e. its requirement period is just over the period that an LRU, LFU strategy would dictate it 'not-required'. But, by most definitions of optimal we'd rather just keep it in RAM, right?

---

Update: should note, I'm caching input data - the outputs of the actual application function have no (helpful) relation between iterations.

Answer 1

All you can really do is profile—any general advice is going to be very, well, general. You should try to keep your working set small so that it fits in the first levels of cache, and avoid redundant memory accesses. If it’s expensive to compute an intermediate value, precompute it and store the result. If you know you will need data, prefetch it from RAM.

For cache control, you can use compiler intrinsics such as GCC’s __builtin_prefetch:

void __builtin_prefetch (const void *addr, ...)

This function is used to minimize cache-miss latency by moving data into a cache before it is accessed. You can insert calls to __builtin_prefetch into code for which you know addresses of data in memory that is likely to be accessed soon. If the target supports them, data prefetch instructions will be generated. If the prefetch is done early enough before the access then the data will be in the cache by the time it is accessed.

It allows you to specify whether you expect to read or write, and what degree of temporal locality you expect the accesses to have.

For virtual memory control, you can load data using mmap and tell the virtual memory manager how you expect to access the mapped pages using madvise, e.g.:

MADV_SEQUENTIAL

Expect page references in sequential order. (Hence, pages in the given range can be aggressively read ahead, and may be freed soon after they are accessed.)

MADV_WILLNEED

Expect access in the near future. (Hence, it might be a good idea to read some pages ahead.)

You’ll need to benchmark and profile to determine where to actually use such strategies. Intel VTune can give you useful stats on how your application is making use of the cache and pipeline.