Memoize (cache) for command-line programs?

Question

I sometimes wind up running the same, fairly-expensive command over and over again, to get the same output. E.g., ffprobe to get information about a media file. Given the same input, the same output should be produced always—so caching should be possible.

I've see Memoizing/caching command line output but I'm looking for a more thorough implementation: in particular, that one just seems to compare the command line—if one of the files passed is modified, it won't notice. (It also has a bunch of fixed-length buffers which make me suspicious and is oddly a daemon.)

Before I go off and write my own, I'm curious if one already exists. The key requirements:

• Must re-run the command if any of the input files (on the command line) change
• Must re-run the command if any of the command line options change
• I'm OK (and honestly expect) commands to be run "non-interactive": e.g., with /dev/null as stdin, and a two different files as stdout and stderr.
• If the command errors out, I'm OK with either that being cached along with the exit code or alternatively it just not being cached at all.
• Should return cached content as often as possible, given the above. But correctness comes first.
• Preferable if the cache can be shared between several machines (all under common control) e.g., via NFS.

_{Basically what I'm thinking of doing, if I write my own, is (skipping some locking and error checking for briefness): take command line + stat results of each item on the command line (error or dev, inode, size, mtime) and pass that whole mess through SHA-512 or SHA-256. That'll give a key that is a fixed size but will change if the command or the files change (unless someone makes a size- and mtime-preserving change, in which case they deserve what they get). Check if that key is in the cache directory. If it already exists, copy their contents to stdout & stderr. Otherwise, run the command in a subprocesses with stdin /dev/null and two files as stdout and stderr. If successful, put the files in to the cache directory. Then copy their contents to stdout and stderr. If it turns out I wind up writing my own, design feedback welcome. And the result will be free software.}

Answer 1

There are so many cases where what you want won't work that you won't find a generic tool that gives really good results:

• Commands that access files that aren't on the command line. (locate myfile)
• Commands that access the network. (wget http://news.example.com/headlines)
• Commands that depend on the time. (date)
• Commands that have random output. (pwgen)
• …

If you handle the task of deciding which commands to apply the tool on, then what you want is a build tool: a tool that runs commands if their output is not up to date. The venerable make won't be very nice: you have to define the dependencies manually, in particular you need to carefully separate caches for different commands and manually revoke caches if you change the command, and you need to store each cache in a separate file, which is inconvenient. One of the many alternatives may be more up to the task, perhaps SCons which supports both checksum- and timestamp-based dependency analysis, has a caching mechanism on top of that, and can be tweaked by writing Python code.

Answer 2

This is more of a brain dump than a real answer, but it's too long for a comment. If that's inappropriate I'll delete it. Just let me know. shrug

First, I think the main problem is that you're thinking it in terms of "command --> result". If it were "file(s) --> result" you could just use make. If there are only a small, fixed number of commands that leads from file(s) to results you could still use make: write a make target for each command.

If you insist it should be "arbitrary command --> result", the first thing that comes to mind is some kind of REPL, or a shell-in-language-X. There's no shortage of these things these days, a new one seems to pop up every two weeks or so. The point being, these would allow you to work with structured data, rather than just a string (the command) and a number of files.

Taking checksum of dev + inode + size + mtime seems sane. You can always do a full compare if you worry about false positives (on a side note: a full compare is always faster than taking SHA-* for each file and comparing the results). For the backend you could use SQLite, but you'd need some mechanism to expire old records.

Things might be easier if you'd be able to point out more restrictions on what the commands and / or the files might be. Aiming for a completely general caching of "command --> result" but still keeping track of changes in the input files seems a little too ambitious.

Answer 3

I found this question while writing my own script for roughly the same purpose and your idea about caching files with their dev+inode+size+mtime looked very useful, so I added it. Your idea and my implementation differ, since I stumbled on this page late and decided not to rewrite everything:

1. The script stores cache entries in a single YAML file for simplicity. You could still share this file across several machines, but there's a risk of an RCE, plus you'll need to write a locking wrapper because of TOCTOU on the YAML file.

2. It will probably only work on Linux and, with luck, on other Unixes.

3. Use at your own risk. Your cache contents will not be protected.

Run gem install chronic_duration first.

#!/usr/bin/env ruby
# Usage: memoize [-D DATABASE] [-T TIMEOUT] [-F] [--] COMMAND [ARG]...
#     or memoize [-D DATABASE] --cleanup
#
# OPTIONS
#   -D DATABASE      Store entries in YAML format in DATABASE file.
#   -T TIMEOUT       Invalidate memoized entries older than TIMEOUT.
#   -F               Track file changes (dev+inode+size+mtime).
#   --cleanup        Remove all stale entries.

require 'date'
require 'optparse'
require 'digest'
require 'yaml'
require 'chronic_duration'
require 'open3'

MYSELF          = File.basename(__FILE__)
DEFAULT_DBFILE  = "#{Dir.home}/.config/memoize.yml"
DEFAULT_TIMEOUT = '1 week'

def fc(fpath) # File characteristic
  return [:dev, :ino, :size, :mtime].map do |s|
    Digest::SHA1.digest(Integer(File.stat(fpath).send(s)).to_s.b)
  end.join
end

def cmdline_checksum(cmdline, fchanges)
  pre_cksum_bytes = "".b

  cmdline.each do |c|
    characteristic   = (File.exists?(c) and fchanges) ? fc(c) : c
    pre_cksum_bytes += Digest::SHA1.digest(characteristic)
  end

  return Digest::SHA1.digest(pre_cksum_bytes)
end

def timed_out?(entry)
  return (entry[:timestamp] + Integer(entry[:timeout])) < Time.now
end

def pluralize(n, singular, plural)
  return (n % 100 == 11 || n % 10 != 1) ? plural : singular
end

fail "memoize: FATAL: this is a script, not a library" unless __FILE__ == $0

$dbfile   = DEFAULT_DBFILE
$timeout  = DEFAULT_TIMEOUT
$fchanges = false
$cleanup  = false
$retcode  = 0
$replay   = false

ARGV.options do |o|
  o.version = '2018.06.23'
  o.banner  = "Usage: memoize [OPTION]... [--] COMMAND [ARG]...\n"+
              "Cache results of COMMAND and replay its output"

  o.separator ""
  o.separator "OPTIONS"

  o.summary_indent = "  "
  o.summary_width  = 17

  o.on('-D=DATABASE', "Default: #{DEFAULT_DBFILE}")       { |d| $dbfile   = d    }
  o.on('-T=TIMEOUT',  "Default: #{DEFAULT_TIMEOUT}")      { |t| $timeout  = t    }
  o.on('-F', "Track file changes (dev+inode+size+mtime)") {     $fchanges = true }
  o.on('--cleanup', "Remove all stale entries")           {     $cleanup  = true }
end.parse!

begin
  File.open($dbfile, 'a') {}
  File.chmod(0600, $dbfile)
end unless File.exists?($dbfile)

db      = (YAML.load(File.read($dbfile)) or {})
cmdline = ARGV
cksum   = cmdline_checksum(cmdline, $fchanges)
entry   = {
  cmdline:   cmdline,
  timestamp: Time.now,
  timeout:   '1 week',
  stdout:    "",
  stderr:    "",
  retcode:   0,
}

if $cleanup
  entries = db.keys.select{|k| timed_out?(db[k]) }
  c = entries.count

  entries.each do |k|
    db.delete(k)
  end

  STDERR.puts "memoize: NOTE: #{c} stale #{pluralize(c, "entry", "entries")} removed"

  File.open($dbfile, 'w') { |f| f << YAML.dump(db) }

  exit
end

$replay = db.key?(cksum) && (not timed_out?(db[cksum]))

if $replay
  entry = db[cksum]
else
  Open3.popen3(*cmdline) do |i, o, e, t|
    i.close
    entry[:stdout]    = o.read
    entry[:stderr]    = e.read
    entry[:retcode]   = t.value.exitstatus
  end

  entry[:timestamp] = Time.now
  entry[:timeout]   = Integer(ChronicDuration.parse($timeout))
  db[cksum] = entry
end

$retcode = entry[:retcode]
STDOUT.write(entry[:stdout]) # NOTE: we don't record or replay stream timing
STDERR.write(entry[:stderr])
STDOUT.flush
STDERR.flush

File.open($dbfile, 'w') { |f| f << YAML.dump(db) }

exit! $retcode