2

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.

  • If you already know the sequence (and its resource requirements) ahead of time, can't you treat that sequence as if it were a single operation for caching purposes? – Robert Harvey Apr 18 '16 at 20:43
  • @RobertHarvey, Not sure I follow... That single operation would call for the loading of more data than there is RAM? I'll update the question to reflect that. – Lamar Latrell Apr 18 '16 at 20:45
  • I suspect that loading of level assets in a game engine is a similar problem. You can sort of predict what the player might need to see next, but all your assets cannot fit to RAM. You have to have a way to quickly determine and load the assets that are "local" to the player's position. – 9000 Apr 18 '16 at 20:49
  • 1
    Aren't you essentially back to LRU then? – Robert Harvey Apr 18 '16 at 20:58
  • You can cache a computation or aggregate set of data which is itself derived from cached data. – Brandon Apr 18 '16 at 20:59
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.

  • Is it possible this answer would suit as an answer to my linked question? Unless, I'm not reading your answer correctly, the way I see it is that the sequence is the profile (?) – Lamar Latrell Apr 18 '16 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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