Persistent memoization

[matthew-piziak]

Is there a way to have Emacs persist the cache between sessions, by saving and restoring the cache to the filesystem?

[skeeto]

Emacs Lisp hash tables are readable, so, in theory, the table could be printed to a file then read back in a different Emacs session. In order for this to work, every key and value in the hash table must also be readable:

Emacs Lisp Readable Closures https://nullprogram.com/blog/2013/12/30/

You may also want to enable print-circle in order to correctly restore any references without making extra copies.

As it's currently written, the hash table is hidden inside a closure so you can't access it directly. The library would need to be modified to expose it. I'd probably do this by adding the hash table to the symbol plist along with the other metadata.

The other half is that you'd need to restore the hash table, so you'd need an interface that lets you supply the hash table rather than let the memoize package create a fresh hash table.

Ultimately, though, in the seven years since I first wrote this library, I've come to believe it's nearly always inappropriate to use a general memoization library like this. Or, at the very least, this should be a macro that expands into a static implementation rather than dynamically wrap the function with a variadic closure as the memoize package does.

Why? Because it's very easy to build this functionality yourself, and a custom solution will be far more efficient, more precise, and more flexible. The last item is what you're stuck on.

When I say "far more efficient," I really do mean it. Check out this benchmark. @alphapapa, you'll probably find this interesting:

https://gist.github.com/skeeto/424992df03a6cfa9997354bd1ccc1ae7

I have two implementations. The first is dumb and straightforward, relying on the memoize package. The second has manual memoization, making it a little more complicated, but not much more so. The difference in performance is striking:

count-sums-1 (1.558840815 298 1.0068730169999998) count-sums-2 (0.000993427 0 0.0)

The manual version is more than 1000x faster and (in the benchmark) creates no garbage. Going through the memoize wrapper closure, which uses "apply" on a list of arguments to call the underlying function, is quite expensive. It also wouldn't be difficult to modify the second version to persist across Emacs sessions: Store the table in a global variable, then print/read it at the appropriate times.

[matthew-piziak]

What excellent advice and comprehensive explanation! I'll keep it in mind and build my systems ad-hoc as you suggest. The code example you linked is a useful template. Thank you!

[alphapapa]

That's very interesting, Chris, thanks. I confirm the same results with your script.

It is very surprising what a difference it makes. I wonder if that points to a bottleneck in Emacs that could be fixed. Should apply be that slow?

By the way, while doing some experimenting trying to learn more about what makes a difference, something I noticed is that, even though a certain function may not cause GC on its own, calling them sequentially can cause GC anyway, throwing off one function's results.

For example, in this file, containing several variations of your original one, I get these results:

count-sums-1     (3.352717385 298 2.3611887889999985)
count-sums-2     (0.001646163 0 0.0)
count-sums-5     (0.010839308 1 0.009193710999999993)
count-sums-6     (0.001892828 0 0.0)
count-sums-7     (0.010837876 1 0.00877702299999994)
count-sums-8     (0.001640857 0 0.0)
count-sums-9     (0.001900644 0 0.0)
count-sums-10    (0.011724034 1 0.009902230999999873)
count-sums-11    (0.001812701 0 0.0)
count-sums-12    (0.012136934 1 0.010128074999999903)
count-sums-13    (0.001652392 0 0.0)

Looking at 12 and 13, 12 seems to cause a bit of GC, and 13 doesn't. But if I comment out 11, I get these results:

count-sums-1     (3.333522484 298 2.3430062730000003)
count-sums-2     (0.001688782 0 0.0)
count-sums-5     (0.013246934 1 0.009019619000000034)
count-sums-6     (0.001942769 0 0.0)
count-sums-7     (0.013237231 1 0.011166784999999901)
count-sums-8     (0.002077549 0 0.0)
count-sums-9     (0.00193919 0 0.0)
count-sums-10    (0.012695605 1 0.010841668999999943)
count-sums-12    (0.001850387 0 0.0)
count-sums-13    (0.025108149 1 0.02304767399999985)

Now 12 seems to cause no GC, and 13 does. Of course, they still don't compare to the memoized version, but it does throw off results a little.

[skeeto]

@alphapapa, I added a third benchmark of a "simple" memoize wrapper and it's significantly faster. It's only about 5x slower than the custom solution and has one garbage collection. That's closer to what I was expecting.

I dug more into the memoize package, and it turns out the performance killer is run-at-time. Internally it's a linear O(n) algorithm on the number of timers (see timer--activate), and memoize creates lots of timers. The package should instead use a single, global timer in a smarter way: essentially maintaining its own timer queue using something better than O(n) (e.g. a heap). Or maybe not use timers at all when they're not requested.

[FelipeLema]

what about using persist-defvar? I use for my frecentf.el package and it saves / restores the persisted hash table per Emacs session without any extra customizations.