Memoizing or caching Bash function results

Question

Update: I've implemented several of the features suggested below and packaged the improved code into a dedicated project: bash-cache.

---

I display a number of expensive operations in my Bash prompt (e.g. Git status) that read from disk or even make network requests. Obviously, I want to still have a responsive prompt, and the result of these functions don't change all too often (though I also want to know fairly immediately when they do change, hence why I'm including them in the prompt).

To accomplish this I've created a _cache function that will decorate another function, turning it into a memoized variant that runs no more than once per minute. I've used it successfully for some time now, but it's still far from perfect. The full function is included below, with additional annotations interspersed.

# Given a name and an existing function, create a new function called name that
# executes the same commands as the initial function.
# Used by pgem_decorate.
copy_function() {
  local function="${1:?Missing function}"
  local new_name="${2:?Missing new function name}"
  declare -F "$function" &> /dev/null || {
    echo "No such function $1"; return 1
  }

Re-declare the body of function, but with the function declaration replaced by new_name().

  eval "$(echo "${new_name}()"; declare -f "$function" | tail -n +2)"
}

# Given a function - and optionally a list of environment variables - Decorates
# the function with a short-term caching mechanism, useful for improving the
# responsiveness of functions used in the prompt, at the expense of slightly
# stale data.
#
# Suggested usage:
#   expensive_func() {
#     ...
#   } && _cache expensive_func PWD
#
# This will replace expensive_func with a new fuction that caches the result
# of calling expensive_func with the same arguments and in the same working
# directory too often. The original expensive_func can still be called, if
# necessary, as _orig_expensive_func.
#
# Reading/writing output to files is tricky, for a breakdown of the issues see
# http://stackoverflow.com/a/22607352/113632
#
# It'd be nice to do something like write out,err,exit to a single file (e.g.
# base64 encoded, newline separated), but uuencode isn't always installed.
_cache() {
  func="${1:?"Must provide a function name to cache"}"
  shift

First, copy the function we're decorating from func to _orig_func. For now it still also exists as func, but that will be overwritten with the caching behavior soon.

  copy_function "${func}" "_orig_${func}" || return

Then store the names of the environment variables that can affect the behavior of the function being cached (e.g. the output of git status depends on the current directory so PWD should be included).

  local env="${func}:"
  for v in "$@"; do
    env="$env:\$$v"
  done

Now dynamically construct a _cache_func function which will invoke _orig_func and cache its output.

This function creates a new directory with mktemp, invokes _orig_func writing the stdout, stderr, and return code of the function to out, err, and exit files in the new directory, then finally symlinks the directory to a $cachepath (see below). A symlink is used to ensure that the cache is always consistent - exit will not exist until the function returns, while out and err may be partially-populated before then.

  eval "$(cat <<EOF
    _cache_$func() {
      : "\${cachepath:?"Environment must include cachepath"}"
      mkdir -p "/tmp/._cache"
      local cmddir=\$(mktemp -d -p "/tmp/._cache")
      _orig_$func "\$@" > "\$cmddir/out" 2> "\$cmddir/err"
      echo \$? > "\$cmddir/exit"
      # Add end-of-output marker to preserve trailing newlines
      printf "EOF" >> "\$cmddir/out"
      printf "EOF" >> "\$cmddir/err"
      ln -sfn "\$cmddir" "\$cachepath" # atomic
    }
EOF
  )"

Now func will be redefined to attempt to read the output from _cache_func, rather than by invoking the expensive _orig_func.

  eval "$(cat <<EOF
    $func() {
      # Clean up stale caches in the background
      (find "/tmp/._cache" \
         -not -path "/tmp/._cache" \
         -not -newermt '-1 minute' \
         -delete &)

A hash of any arguments passed into the function, along with the function name and the values of any environment variables passed into _cache, is computed to be used as the cachepath location that the symlink created in _cache_func will point to.

      local arghash=\$(echo "\${*}$env" | md5sum | tr -cd '0-9a-fA-F')
      local cachepath="/tmp/._cache/\$arghash"

If the symlinked files exist their contents will be returned; otherwise the original function will be invoked, cached, and then returned. If the cached files are due to be invalidated soon the original function is instead invoked asynchronously to update the cache behind the scenes.

      # Read from cache - capture output once to avoid races
      # They could be deleted inbetween checking the files exist *then* reading
      local out err exit found
      out=\$(cat "\$cachepath/out" 2>/dev/null)
      err=\$(cat "\$cachepath/err" 2>/dev/null)
      exit=\$(cat "\$cachepath/exit" 2>/dev/null)
      if [[ "\$exit" == "" ]]; then
        # No cache, execute in foreground
        _cache_$func "\$@"
        out=\$(cat "\$cachepath/out")
        err=\$(cat "\$cachepath/err")
        exit=\$(cat "\$cachepath/exit")
      else
        local found=\$(find "/tmp/._cache" \
                   -path "\$cachepath/exit" -newermt '-10 seconds')
        if [[ "\$found" == "" ]]; then 
          # Cache exists but is old, refresh in background
          ( _cache_$func "\$@" & )
        fi
      fi
      # Output cached result, trimming the EOF marker
      printf "%s" "\${out%EOF}"
      printf "%s" "\${err%EOF}" >&2
      return "\${exit:-255}"
    }
EOF
  )"
}

As I said, this works, but there are several things I'd like to improve:

• There's a lot of subshells, command substitutions, and external commands being invoked.
• Worse, there's lots of disk I/O (two find calls and three or six cat calls on reads, and six writes every time the cache is updated).
• Storing the function's results across three files makes reasoning about the caching more complex, as a reader can potentially see the cache in an inconsistent state.

I'd love to be able to use one file (or even zero) rather than three. As noted in a comment above I looked into Base64-encoding the output so I could store the stdout/stderr/exit-code all in one file, but I'm not aware of a cross-platform way to do so.

I also looked into using /dev/shm to avoid actually writing the files to disk, but the contents of this directory would occasionally vanish even when they weren't expected to.

Another option that I haven't experimented with would be to use dynamic variables (e.g. __cache_$arghash_out), but that would require some sort of garbage collection scheme which I don't have to deal with currently thanks to find -delete.

I'd also welcome any general feedback about the idea and implementation, of course.

---

Update: I've implemented several of the features suggested below and packaged the improved code into a dedicated project: bash-cache.

Answer 1

This looks very slick! I've tried it on a few things, and it speeds up very slow commands quite a bit. Less-slow commands, as you've noticed, are still a bit expensive.

A few preliminary thoughts (I'll likely add more to this post as I spend more time looking at this):

• The largest lag time in reading from the cache in a given shell is the time spent reading from the filesystem. Would it be possible to implement a two-teired cache that stores things in memory as a first resort, and the filesystem otherwise? Things could be pushed out of memory if they were too big or too old (memory-as-MRU). This would also make cache use between shells simpler. /dev/shm-type shared memory handles this for you, somewhat, with swap. However, as you've pointed out, that directory can be quite volatile and isn't present on all systems.
• Your backgrounded & commands should be disowned; otherwise, users shells might warn them that there are backgrounded jobs when they exit, if cleanup is still running. You use subshells for these commands, but I suspect there are cases where that won't be enough to fully detach them. I may be wrong though.
• When reading the cache and checking staleness, you can reduce subshell and command count by replacing the cat commands with a native Bash file-read (while...do; ...; done <$file). Relatedly, could you replace the mtime-checking find command with a simple stat? It looks as though the path might be predictable enough that you don't need to search the filesystem.
• I think you could save yourself a subshell and some complexity if you used a predictably-named cache location rather than a mktemp'd one. For a per-user cache shared across multiple shells, you could name it someuniqueconstant-$USER. To prevent shell-sharing, you could provide an option that qualified the name with $$ as well (if you do this, beware of PID-wraparound-caused issues and fail if the PID-named temp dir exists when you first want it).
• Larger ideas: I think you could save yourself time and subshells by abandoning find in favor of one of the following:
  • sqlite: this is almost as ubiquitous as find, and very easy for even non-privileged users to install and use if it's not present. It's likely much faster at deletion, though it would probably impose a slight penalty on cache reads (this is where the two-tiered cache design would probably help a lot). Additionally, because of its memory mapping, SQLite could potentially yield an immense performance benefit in cases where cache values were near-simultaneously accessed from two shells at once. This would also prevent hassles encountered while writing to multiple files to out/err/exit.
  • A Bash implementation of find would likely be faster for very small/shallow directories without too many cached things. Since that sounds like the use case you're targeting, consider trying that out. More info can be seen at these SE questions: 1 2.

Answer 2

The review by Zac B is very nice, I have only minor comments on top of that about the implementation.

Large scripts in here-documents

Escaping $ in large here-documents is troublesome and error prone. Indeed you forgot to escape something here, I let you spot it now ;-)

    local found=\$(find "/tmp/._cache" \
                    -path "\$cachepath/exit" -newermt '-10 seconds')
    if [[ "$found" == "" ]]; then 
      # Cache exists but is old, refresh in background
      ( _cache_$func "\$@" & )
    fi

Sometimes you can simplify by enclosing the here-document's start label in quotes, for example:

  eval "$(echo "_cache_$func() {"; cat << "EOF"
      : "${cachepath:?"Environment must include cachepath"}"
      mkdir -p "/tmp/._cache"
      local cmddir=$(mktemp -d -p "/tmp/._cache")

      # ...
    }
EOF
  )"

But in this example, since you have the $func variable embedded here and there that needs to be expanded, it will be better to use a single-quoted string, and dropping out of it where you need variable interpolation:

  eval '
    _cache_'"$func"'() {
      : "${cachepath:?"Environment must include cachepath"}"
      mkdir -p "/tmp/._cache"
      local cmddir=$(mktemp -d -p "/tmp/._cache")
      _orig_$func "$@" > "$cmddir/out" 2> "$cmddir/err"
      echo $? > "$cmddir/exit"
      # Add end-of-output marker to preserve trailing newlines
      printf "EOF" >> "$cmddir/out"
      printf "EOF" >> "$cmddir/err"
      ln -sfn "$cmddir" "$cachepath" # atomic
    }
  '

This implies you need to be careful with embedded single-quotes in the script, but this might not be a big problem, for example in the longer here-doc you have, all embedded single-quotes can be replaced with double-quotes.

... in "$@" is the default in for loops

Another minor point is that you can omit "$@" in for loops, as that's the default, for example here you can write:

  local env="${func}:"
  for v; do
    env="$env:\$$v"
  done