6

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.

4

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.

1

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.

  • Well, the immediate thing I want to use it for is a program I have that displays (on a terminal) the duration of each media file in the current directory. I don't want to litter the directory with extra files, so that rules out make (so does the fact that they contain spaces, but I'll take make more generally as a make-like too). The program is a huge pipeline, but most of the time is find … -exec ffprobe «ffprobe-opts» '{}' ';'. If I could cache the ffprobe result (which is to stdout), that'd greatly speed it up. – derobert May 5 '17 at 6:44
  • Of course, I could come up with a dedicated cache to that—but I figured, I'd rather have a generic one. Which obviously can't work with everything, at least not without an incredible amount of work, but could work with enough things. There are a lot of things which are true functions and have no output other than stdout/stderr, and those would all work. Almost any filter, for example. – derobert May 5 '17 at 6:47
  • @derobert There's a Python script name dnuos, that caches bitrate for audio files. It keeps the results in a central database, but IIRC it doesn't automatically re-scan files when they change, you need to explicitly tell it to. That model worked very well for me. – Satō Katsura May 5 '17 at 6:50
  • I'm somewhat confused by the SHA remark—I'm not suggesting actually checksuming the file (that'd be slow). And at least my machine can do SHA-512 faster than a disk read, so comparing one file with an already-known SHA-512 is faster than comparing the two files directly (half as much data to read from disk). But mainly here it's to have fixed-size keys and to help preserve privacy. – derobert May 5 '17 at 6:52
  • Also, thank you for the feedback, I find it helpful at least. And yeah, I could write a quick wrapper around ffprobe that'd cache the results in a SQLite file somewhere... but well, I'm sure I'll find plenty of other uses for the generic one. – derobert May 5 '17 at 6:52
1

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

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.