Re:The only build system that might someday replace make (2010)
by kragen on Saturday November 23, 2019 @08:15PM
(#21617707)
The overall concept of automatically memoizing parts of a batch computation to turn it into an incremental computation is really interesting, because something like 95% of software amounts to different systems for managing caches. The old saying is that there are two hard problems in software: naming, cache invalidation, and off-by-one errors; and cache invalidation is what we're talking about here.
A difficult issue here is that choosing good caches in a computing system is inherently a global optimization problem. Suppose you're spending 95% of your time in function X, so you memoize function X, with a 90% hit rate, but probing and invalidating the cache, and the extra space it takes up, takes 5% of the time that X took. So your system overall does the non-X (100-95)% = 5% of the work it was originally doing, plus 10% of the X work (9% of the total), plus a new 5% of 95% = 4.75% in the cache; so the system is doing 18.75% as much work as before, so (modulo concurrency) it's a bit over 5× faster.
Working on that remaining 9% of the original that is cache misses invoking X, you notice that X is spending 99% of its time in several calls to, indirectly, another function Y, so you memoize Y, and this works out better: you have a 95% hit rate, and managing and probing the Y cache only takes 1% of the work that running Y took. So the 8.91% of the original runtime that was in Y is reduced to 0.0891% of the original in cache management, plus 0.4455% of the original runtime in the cache misses in Y, for a total of 0.5346% of the original runtime, so you've reduced the runtime from 18.75% of the original to 10.3746% of the original; you've almost doubled performance again by adding this other cache.
But you're still spending 4.75% of the original runtime managing the X cache. Now you can improve performance by removing the X cache. Originally you were spending 94.05% of the runtime in Y (although you didn't know it) which you can reduce to 4.7025% in misses on the Y cache, plus 0.9405% in Y-cache management, plus the 5% of the original runtime that wasn't in X, for 9.7025% of the original runtime.
So you quintupled performance by memoizing X, and then later you improved performance by 6.5% by undoing the memoization of X. And this is in a very simple model system which doesn't take into account things like the memory hierarchy (another kind of caching), space budgets, and cache miss rates varying across different parts of the system.
So we have a global optimization problem which we are trying to solve by making local changes to improve things. This is clearly not the right solution, but what is?
Umut Acar described an aproach he calls "self-adjusting computation" which uses a single global caching/memoization system within a program to do fine-grained cache invalidation. His student Matthew Hammer has extended this work. I haven't figured out how their system works yet, but it seems like a promising start.
A difficult issue here is that choosing good caches in a computing system is inherently a global optimization problem. Suppose you're spending 95% of your time in function X, so you memoize function X, with a 90% hit rate, but probing and invalidating the cache, and the extra space it takes up, takes 5% of the time that X took. So your system overall does the non-X (100-95)% = 5% of the work it was originally doing, plus 10% of the X work (9% of the total), plus a new 5% of 95% = 4.75% in the cache; so the system is doing 18.75% as much work as before, so (modulo concurrency) it's a bit over 5× faster.
Working on that remaining 9% of the original that is cache misses invoking X, you notice that X is spending 99% of its time in several calls to, indirectly, another function Y, so you memoize Y, and this works out better: you have a 95% hit rate, and managing and probing the Y cache only takes 1% of the work that running Y took. So the 8.91% of the original runtime that was in Y is reduced to 0.0891% of the original in cache management, plus 0.4455% of the original runtime in the cache misses in Y, for a total of 0.5346% of the original runtime, so you've reduced the runtime from 18.75% of the original to 10.3746% of the original; you've almost doubled performance again by adding this other cache.
But you're still spending 4.75% of the original runtime managing the X cache. Now you can improve performance by removing the X cache. Originally you were spending 94.05% of the runtime in Y (although you didn't know it) which you can reduce to 4.7025% in misses on the Y cache, plus 0.9405% in Y-cache management, plus the 5% of the original runtime that wasn't in X, for 9.7025% of the original runtime.
So you quintupled performance by memoizing X, and then later you improved performance by 6.5% by undoing the memoization of X. And this is in a very simple model system which doesn't take into account things like the memory hierarchy (another kind of caching), space budgets, and cache miss rates varying across different parts of the system.
So we have a global optimization problem which we are trying to solve by making local changes to improve things. This is clearly not the right solution, but what is?
Umut Acar described an aproach he calls "self-adjusting computation" which uses a single global caching/memoization system within a program to do fine-grained cache invalidation. His student Matthew Hammer has extended this work. I haven't figured out how their system works yet, but it seems like a promising start.
The topic topics/caching.html in Dercuano collects a bunch of notes on this topic more generally: http://canonical.org/~kragen/dercuano-20191110.tar.gz.
I really appreciate Raph posting the link to the Mokhov–Mitchell–Peyton-Jones paper in https://news.ycombinator.com/item?id=21617434.