7
$\begingroup$

I've been having problems designing an effective caching mechanism. The mechanism is to be used as part of a project developing scientific software.

The goal is to save computation time by loading results of identical computations done in the past.

The problem I've been encountering is how to know if a computation is identical to a previous one. Checking the input parameters can be sufficient in most cases, but sometimes the code changes, and then even though the input parameters can be identical, the results may differ.

The problem is that modifying the code now needs to be coupled with clearing the cache, in case that code creates cached results. This is a manual step which is error-prone. Failure can cause the results to stay the same, even after code changes have been made, leading to bugs or erroneous conclusions.

I was wondering if there is any mechanism for caching which can solve, or somehow help avoid this pitfall.

Thanks, Ofer

$\endgroup$
  • $\begingroup$ Hashing the current source code - is a great idea, but how do you implement it? Discovering which files are used by a function seems difficult for most languages I can think of (I use Matlab). $\endgroup$ – Ofer Apr 28 '13 at 8:25
  • $\begingroup$ Ofer, you can ask it at Stack Overflow... This needs some reflection capabilities in the language. $\endgroup$ – Deer Hunter Apr 28 '13 at 16:19
  • $\begingroup$ @DeerHunter, I've actually found such a function in MATLAB called depfun $\endgroup$ – Ofer May 1 '13 at 20:32
  • $\begingroup$ Is the time you would save by caching significantly more than the time you will spend implementing this? This seems like a hard problem to solve and you can have a CPU compute a lot of redundant results while you're not working... $\endgroup$ – Jeff May 18 '13 at 1:58
5
$\begingroup$

The answer depends, in part, both on how robust of a solution you're looking for and on what kind of development workflow you use.

One particularly simple option is to tag each cache entry with the version number of the software. As long as every change to the code is accompanied by a change in version number, this will give you an easy way to check whether a cache file is still valid. However, version numbering is probably only appropriate if changes to the project are committed all at once.

A less robust option that is nonetheless more suited for continuous development would be to simply compare the last-modified dates for your [oldest] cache files and your source files. If the source files were last modified before all of the cache files, the latter should still be usable.


@DeerHunter pointed out a technique that is more robust than either of the above options and should work regardless of your development methodology.

When creating a cache file, include a hash of the current source code. At the start of program execution, hash the current source code and compare the result to the hash contained in each cache file. If they don't match, the file was produced by a different version of the software and should be removed.

A similar procedure can expedite comparisons between input parameters. Store a hash of the input parameters in each cache file, and then compare that hash to a hash of the current input parameters to check for a match. The only downside here is that you can no longer look for cache files with input parameters that are close to those of the current simulation.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ John Delong, you can consider editing your answer to include hashing the source code and the inputs and then comparing the two hashes with their previous versions. Much better in terms of conflict resolution, avoiding false alarms etc. $\endgroup$ – Deer Hunter Apr 27 '13 at 18:07
  • $\begingroup$ @DeerHunter, you make a great point. I had considered mentioning hashing the source code, but I naively dismissed the idea as too computationally intensive. Of course, provided that one does not use something inappropriate like a cryptographic hash, this is an excellent idea. $\endgroup$ – Ben Apr 27 '13 at 18:18
  • 1
    $\begingroup$ Compared to the time necessary to re-run a calculation, hashing is quite OK. Weak formerly-cryptographic hashes like MD5 are fast enough to compute and sport low probability of collisions. My impression is that 32 bit or 64 bit hashes are too small for many memoizing applications. $\endgroup$ – Deer Hunter Apr 27 '13 at 18:27
  • 4
    $\begingroup$ There are several projects in research reproducibility that are considering this question and broader issues. The list is quite long, so I'll point you to one, sumatra. It's Python-based, but hopefully it can help you find similar packages in the MATLAB space. $\endgroup$ – Aron Ahmadia Apr 28 '13 at 21:51
  • $\begingroup$ I have an implementation of the second suggestion that you should checkout. I originally wanted to serialize all the params into a store of some variety, but I realized that would require keeping a whole metaData cache on the side which has its own headaches. I opted for md5 pureley because the output hex was small enough to fit cleanly as a file name. :P $\endgroup$ – meawoppl Apr 29 '13 at 17:23
2
$\begingroup$

I have a Python implementation that satisfies the interest you specify. Take a look at it to see a simple way to do this in languages capable of introspection.

Any function that you decorate with it will be run once, and the results cached locally. Subsequent invocations with:

  1. the same arguments
  2. the same function code

will be loaded from disk.

It uses a different storage mechanism if the result is an array for faster saves and loads.

This would be a bunch harder to write in c/c++ and similar. Though a simple trick might be salting the hash with a pre-processor directive such as TIME or DATE or some such if you want to err on the side of tossing your cached results after a recompile.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This is pretty fragile: it compares equality using str() (rendering functions as arguments useless, for example), names can collide, you can't return functions and other non-pickleable objects, and transitive dependencies are not versioned, to name a few issues. $\endgroup$ – Jed Brown Apr 30 '13 at 1:21
  • $\begingroup$ That's pretty neat. I like the decorator idea. I might implement a Matlab one (if no one here happens to have a Matlab implementation by any chance?). $\endgroup$ – Ofer May 1 '13 at 20:05
  • $\begingroup$ A fair critique @JedBrown. I will add the passed function hashing bit later today, but dealing with non-pickleable datatypes seems out of scope. If thats important, you can write a pickling routing for it etc. Functional returns would be really hard with this approach. I wrote this for a function that needed to generate something like 100 floats worth of data from each several GB datasets it was run on, not as a catch-all solution really... It works great for that sort of thing :) $\endgroup$ – meawoppl May 2 '13 at 20:58
  • $\begingroup$ Also notably, it is posix specific in its temp file path, so it will probably not run correctly on windows. $\endgroup$ – meawoppl May 2 '13 at 20:59

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.