<story><title>Optimizations can have unexpectedly large effects when combined with caches</title><url>https://justinblank.com/notebooks/performanceoptimizationscanhaveunexpectedlylargeeffectswhencombinedwithcaches.html</url></story><parent_chain><item><author>hinkley</author><text>Caching is a weapon of last resort. In most cases it is the last major performance improvement you will see from your code, even if other options were available, and any information architecture problems you have are set in stone or will get worse.&lt;p&gt;Because of the locality aspect, people will assume that it&amp;#x27;s &amp;#x27;free&amp;#x27; to look up a value multiple times instead of passing these data dependencies between the relevant methods. This turns your cache into global shared state, and once that happens you can&amp;#x27;t turn the cache off again. There are other problems with this arrangement as well.&lt;p&gt;The easiest to understand (and yet I&amp;#x27;ve failed on at least one project) is that if the working set for a problem ever becomes proportional to the size of the cache (&amp;gt;1 for single task systems, &amp;gt; 1&amp;#x2F;n for systems with n concurrent tasks), then you can end up evicting data in the middle of a transaction. The obvious consequence is that it causes performance to jump off a cliff. Particularly bad behavior with LRUs but switching to a different statistical model simply reduces the height of the cliff. There is still a cliff. The less obvious consequence is now you have concurrency bugs, because the code assumes that decisions made about the data will go the same way on each call, but due to eviction, two halves of the transaction may make conflicting decisions with undefined behavior.&lt;p&gt;But speaking as the guy who fixes the perf issues other people gave up on: Once you introduce caching you poison the performance well. Flame charts lie when cache is used, and after people rely on the cache it is lying in the other direction when the cache is off, because you&amp;#x27;re calling that path 5 times now and it&amp;#x27;s swamping other bottlenecks. This is what I really mean when I say it&amp;#x27;s a weapon of last resort. Because once you use it, it attempts to take any other options off the table. Caching will be most of the last order of magnitude in scalability that your system ever sees. Every &amp;#x27;win&amp;#x27; from there on will take more time and energy than most people are willing to invest.</text></item><item><author>mjb</author><text>I really love this point.&lt;p&gt;For most applications the optimal size of a (time-based) cache is around the point that keeping an item around in the cache is equal to the cost of accessing it again. This is a point that Jim Gray made in the classic &amp;quot;The 5 Minute Rule for Trading Memory for Disc Accesses&amp;quot; (&lt;a href=&quot;http:&amp;#x2F;&amp;#x2F;www.hpl.hp.com&amp;#x2F;techreports&amp;#x2F;tandem&amp;#x2F;TR-86.1.pdf&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;www.hpl.hp.com&amp;#x2F;techreports&amp;#x2F;tandem&amp;#x2F;TR-86.1.pdf&lt;/a&gt;) back in 1986.&lt;p&gt;A side effect of that is that systems that run faster, and therefore access each cached it more often, get more benefit out of a cache by pushing that set point out further. Whether that happens in any given system depends a lot on the access patterns, and especially temporal locality within those access patterns, but the effect is real in a lot of different kinds of systems.&lt;p&gt;&amp;gt; It&amp;#x27;s common wisdom that systems with caches can fail badly when the caches are cold. When every request misses the cache, the system is overloaded, and never recovers. What I observed was the mirror image.&lt;p&gt;The bottom line is that both locality and memoization are huge contributor to the performance of systems, both positive and negative. When folks (including me) point out the risks of caches, we&amp;#x27;re not implying that caches are always bad. Instead, it&amp;#x27;s pointing out a risk that sometimes they are too &lt;i&gt;good&lt;/i&gt;, leading to a system that can&amp;#x27;t function when the normal level of locality and memoization are not available.</text></item></parent_chain><comment><author>YZF</author><text>I&amp;#x27;m not sure everyone here is talking about the same thing when they talk about caching but if you took caching out of the modern Internet it would collapse immediately.  There&amp;#x27;s caches in your CPU, there&amp;#x27;s caches in your disk drives, there&amp;#x27;s caches in Linux, there&amp;#x27;s caches in every layer of every major cloud service, there&amp;#x27;s caches in your network (CDN).&lt;p&gt;If your CPU had to fetch every instruction and every bit of data from main memory it would run x100 slower.  If your disks didn&amp;#x27;t have caching they&amp;#x27;d generally run slower.  If Linux didn&amp;#x27;t cache your filesystem it&amp;#x27;d need a lot more disk accesses. etc. etc.&lt;p&gt;Ofcourse a properly designed cache has to consider things like what are the access patterns, how to figure out what to keep in the cache and what to toss away, how large is the dataset we&amp;#x27;re caching, invalidation etc.  But there&amp;#x27;s no performance optimization that&amp;#x27;s going to get that NetFlix movie to 100M subscribers directly from the disk it&amp;#x27;s stored on, through the network.&lt;p&gt;Feels like some of the discussion is about something like storing f(x) in a map instead of computing f(x).  I wouldn&amp;#x27;t use this terminology (caching) in this case.  This is more like your standard space to time algorithmic tradeoffs.</text></comment>
<story><title>Optimizations can have unexpectedly large effects when combined with caches</title><url>https://justinblank.com/notebooks/performanceoptimizationscanhaveunexpectedlylargeeffectswhencombinedwithcaches.html</url></story><parent_chain><item><author>hinkley</author><text>Caching is a weapon of last resort. In most cases it is the last major performance improvement you will see from your code, even if other options were available, and any information architecture problems you have are set in stone or will get worse.&lt;p&gt;Because of the locality aspect, people will assume that it&amp;#x27;s &amp;#x27;free&amp;#x27; to look up a value multiple times instead of passing these data dependencies between the relevant methods. This turns your cache into global shared state, and once that happens you can&amp;#x27;t turn the cache off again. There are other problems with this arrangement as well.&lt;p&gt;The easiest to understand (and yet I&amp;#x27;ve failed on at least one project) is that if the working set for a problem ever becomes proportional to the size of the cache (&amp;gt;1 for single task systems, &amp;gt; 1&amp;#x2F;n for systems with n concurrent tasks), then you can end up evicting data in the middle of a transaction. The obvious consequence is that it causes performance to jump off a cliff. Particularly bad behavior with LRUs but switching to a different statistical model simply reduces the height of the cliff. There is still a cliff. The less obvious consequence is now you have concurrency bugs, because the code assumes that decisions made about the data will go the same way on each call, but due to eviction, two halves of the transaction may make conflicting decisions with undefined behavior.&lt;p&gt;But speaking as the guy who fixes the perf issues other people gave up on: Once you introduce caching you poison the performance well. Flame charts lie when cache is used, and after people rely on the cache it is lying in the other direction when the cache is off, because you&amp;#x27;re calling that path 5 times now and it&amp;#x27;s swamping other bottlenecks. This is what I really mean when I say it&amp;#x27;s a weapon of last resort. Because once you use it, it attempts to take any other options off the table. Caching will be most of the last order of magnitude in scalability that your system ever sees. Every &amp;#x27;win&amp;#x27; from there on will take more time and energy than most people are willing to invest.</text></item><item><author>mjb</author><text>I really love this point.&lt;p&gt;For most applications the optimal size of a (time-based) cache is around the point that keeping an item around in the cache is equal to the cost of accessing it again. This is a point that Jim Gray made in the classic &amp;quot;The 5 Minute Rule for Trading Memory for Disc Accesses&amp;quot; (&lt;a href=&quot;http:&amp;#x2F;&amp;#x2F;www.hpl.hp.com&amp;#x2F;techreports&amp;#x2F;tandem&amp;#x2F;TR-86.1.pdf&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;www.hpl.hp.com&amp;#x2F;techreports&amp;#x2F;tandem&amp;#x2F;TR-86.1.pdf&lt;/a&gt;) back in 1986.&lt;p&gt;A side effect of that is that systems that run faster, and therefore access each cached it more often, get more benefit out of a cache by pushing that set point out further. Whether that happens in any given system depends a lot on the access patterns, and especially temporal locality within those access patterns, but the effect is real in a lot of different kinds of systems.&lt;p&gt;&amp;gt; It&amp;#x27;s common wisdom that systems with caches can fail badly when the caches are cold. When every request misses the cache, the system is overloaded, and never recovers. What I observed was the mirror image.&lt;p&gt;The bottom line is that both locality and memoization are huge contributor to the performance of systems, both positive and negative. When folks (including me) point out the risks of caches, we&amp;#x27;re not implying that caches are always bad. Instead, it&amp;#x27;s pointing out a risk that sometimes they are too &lt;i&gt;good&lt;/i&gt;, leading to a system that can&amp;#x27;t function when the normal level of locality and memoization are not available.</text></item></parent_chain><comment><author>zasdffaa</author><text>In my &lt;i&gt;extensive&lt;/i&gt; experience of optimising stuff...&lt;p&gt;&amp;gt; Caching is a weapon of last resort. In most cases it is the last major performance improvement&lt;p&gt;...is wrong. It is one of the very first things I reach for because it is the most effective and simplest, once you&amp;#x27;ve eliminated O(n^2) behaviour etc. It&amp;#x27;s not a magic wand but nothing is.</text></comment>