Optimizations can have unexpectedly large effects when combined with caches
About 15 years ago I was on a team that was having so many problems with caching that I began to see it for the liability that it is. It started with a 2-4 week delay each release cycle while they fixed caching bugs the testers had found, but once I joined the project I saw how deep the problem went.<p>A number of their features invited a full table scan, which is fundamentally incompatible with an LRU cache, and in particular has disastrous stair step functions as the working set grows. Note that this is also a couple of years before anyone had heard of memcached so these were DIY implementations with multiple potential sources of bugs.<p>About the time I found my feet on the project someone wanted to add caching to yet another workflow that was taking 30 seconds to run. It was an admin workflow so there was a little tolerance of slow response times, but not 30 seconds.  I volunteered for the story because I thought we could do better than more caches.<p>Through conversation, step debugging, and profiling I found the spot where they had wanted the caching. What the feature was doing was two relatively expensive lookups of the same data, filtering it on two very different dimensions, and returning the intersection of the two. In typical ORM fashion, both of the concerns were taking it upon themselves to fetch their own data instead of having it handed to them. Since they were both called from the same function, I hoisted the lookup out of the callee into the caller, sending the same list to both. Then I changed the code again to feed the result of call 1 to call 2, to make it work more like consecutive filters.<p>The end result was that the page now loaded in 3 seconds, and I was able to write better unit tests for this code. One might expect that most of that improvement came from running the second filter on a much smaller list, but that&#x27;s where you&#x27;d be wrong. The majority of that improvement came from the hoisting, not the chaining. Due to the amount of work in the filters, the initial lookup shouldn&#x27;t have accounted for more than a third of the page load time, but just sharing the same data dropped the response time to around 6 seconds. Chaining the filters ended up only saving 3 seconds.<p>The problem with large data sets is that CPUs have caches too. And in a garbage collected programming language, there are additional costs to carrying around duplicated data, particularly if it is in tree form like this was. Most likely we were smashing the hell out of CPU caches and introducing extra GC pressure to boot. By passing in the same object tree the second call followed warm and&#x2F;or hot paths through heap memory.<p>I&#x27;d had a similar but less dramatic experiences a few years before that, where I identified that a function, which accounted for 10% of the runtime, was being invoked roughly twice as often as the problem required. By that point 5% looked like low hanging fruit, so I eliminated the duplicate calls and reran the benchmarks. But the results didn&#x27;t make sense so I tweaked and prodded and fiddled. The new time was 20% lower than the old time, for what should have been 5%. This is already way too long so I won&#x27;t go into the reasons here, but in addition to the scenarios I mentioned for the previous issue, there&#x27;s also problems of timing accuracy in profilers, and cyclic use patterns that can misattribute the expense of a call to siblings or the parent. A function that creates many objects may never reach the GC threshold, but a large allocation later in the sequence diagram may. Or collide with cache lines that are needed again later in the call graph.