5 ms·

> a cache can be added in 10 LOCs Yes, and then 10 months debugging edge cases where communicating parts are looking at different versions of the "same" data.

> a cache can be added in 10 LOCs Yes, and then 10 months debugging edge cases where communicating parts are looking at different versions of the "same" data. Caching is really important, but caching (and cache-invalidation) is really difficult, adding caching to an application that doesn't use caching is not "10 LOC and done".

huhtenberg 10y ago
> caching (and cache-invalidation) is really difficult That's an urban legend. Needlessly complicated or over-abstracted general-purpose caching frameworks are difficult, but your dumbest imaginable linear LRU fast lookup is both exceptionally useful and can indeed be done in 10 LoC in a lot of cases.
- throwawayReply 10y ago
  It's not the algorithm that's difficult, it's the effect of adding caching to a system that wasn't built with caching in place at the start that is difficult. This isn't an "urban legend" it's first hand experience working with companies trying to add caching. No, those companies aren't even trying to write caching algorithms, they're just bundling in a caching layer and hoping that the system behaves in the same way. It only takes somewhere which writes data (perhaps in a way that bypasses the caching layer so the cache doesn't know it has changed) and re-reads it back quickly for software which used to work suddenly breaks. Now you might look at that and go "omg refactor it! That's horrible code, that should never ship" etc, but not everywhere is the s.v. bubble with endless amounts of the best developers to throw at problems. Code which worked and solved a business problem ended up shipping, possibly without testers and probably without code reviews. So adding a caching layer suddenly "breaks" those reports, now who's going to have to fix it, not the person who wrote those reports even if the very behavior of side-effected data changes and db re-reads is precisely a cause of data layer slowness that led to wanting to implement caching...
  - sqeaky 10y ago
    > It only takes somewhere which writes data (perhaps in a way that bypasses the caching layer so the cache doesn't know it has changed) and re-reads it back quickly for software which used to work suddenly breaks. So those 10 lines need to be in the wrong place? Why expose the uncached API? Web or single system implement caching in a defined is easy if you don't have a defined API you probably don't have a good system. If you don't have a good system, why are you trying to implement caching? The not being good part is probably why its slow.
  - xixi77 10y ago
    I am not sure you and the OP are talking about the same thing. Bundling a caching layer without even trying to write caching algorithms -- particularly if such a layer is serving multiple purposes -- sounds to me like what the parent is calling a "general-purpose caching framework", probably overly abstracted too as these things are wont to be. I would be super cautious incorporating this kind of black-box stuff. Even if the docs have 10 LOC examples, there can be all kinds of unexpected quirks that you would need to be aware of before doing anything. I read the OP as talking about specific, single-purpose caching techniques -- e.g. when you need to repeatedly compute a function of arbitrary parameters, it can help a lot to simply store values for the more common parameter combinations.
    - striking 10y ago
      It all depends on the purity of the underlying computation. If you're multiplying XXL numbers together, that's different than accessing a database with dynamic or variable data. Math is totally pure. But you'll have to evaluate the constraints on the purity of that database access.
  - huhtenberg 10y ago
    Nobody's saying that one can just throw in a caching layer, touching nothing else and it will just magically work. There's obviously some thought and due consideration required, but it is NOT "really difficult". And in a lot of cases it is in fact as simple as adding a handful lines of code. PS. It is an urban legend, because "cache invalidation is hard" gets repeated a lot, initially as a joke, but it doesn't preclude people who aren't familiar with the subject from taking it as a fact and then repeating it as such. Voice recognition from scratch is hard. Some lock-free data structures are hard. Caching is not hard. It's knowing what the heck you are actually doing and doing it well is what's hard. By the same measure, C macros would be hard, because some idiot can do #define true false and everyone else will spend the same 10 months trying to understand why the hell things break now and then. Caching is hard is when someone starts messing with other people' code without fully understanding it. But then anything is "hard" under these circumstances.
- xixi77 10y ago
  Precisely -- it's the "general-purpose" part that is extremely complicated, which is what everyone here seems to be talking about when bringing up invalidation, but having simple, specific and localized caching in a performance-critical region is not that hard, and can be very effective.
- falcolas 10y ago
  I have to agree with the parent - cache invalidation is tough. When do you do it? What triggers an invalidation? When is it OK to use known-stale data? How long should a cache be valid for? If multiple copies of a program are brought up, what effect will it have on the caches? How do updates from one instance get populated to others? What are the impacts on up- and down-stream services? I'm going to borrow from someone much more eloquent than I: How simple it is to declare a static hashtable, and yet how perilous! http://thecodelesscode.com/case/148?topic=caching http://thecodelesscode.com/case/148?topic=caching
- rantanplan 10y ago
  >That's an urban legend. ROFL. What are you talking about? You're talking as if it's a solved problem for all cases. Hint: it's not. If it was an urban legend people wouldn't write dissertations on it.
creshal 10y ago
It really depends on what you're trying to cache. Caching expensive calculations e.g. is trivial to get right (use all arguments as cache key) and often you don't even need invalidation (unless your algorithm changes at runtime).
- Klathmon 10y ago
  Memoization works amazingly and can be very easy to implement, but it's not always that applicable. In my experience, I just don't hit that many pure functions that don't do things like touch the database (which can change out from under the function), or are called enough with the same arguments that memoization is actually worth it. But when it does work, it's like magic. I do a lot of work in javascript now, and it's great being able to wrap a function in a single line `memoize` function and instantly improve performance.
vinceguidry 10y ago
Caching is just another layer of complexity on top of your app. Sort of like HTML templates. If you're expecting it to be a no-maintenance drop-in solution, you're going to get burned. If you're willing to think carefully about how it fits into your domain, then you might be able to get away with a 10 LOC method on your base controller class.
- jakub_h 10y ago
  It's a pervasive element, though. Which to me means two things. First, I wonder if there isn't a way of adding it (really) transparently into a language. Basically, whenever there's a possibility that a value is a function of old values, chances are that a previously used result is still available. Second, strategies can have massive time and space implications, but that's exactly why being explicit about them in the application's code in any way should be avoided at all costs: they shouldn't change the semantics, only pragmatics. Given that compilers already do this with simpler things (are my local variables actually on stack or are they kept in registers?), one has to wonder if this isn't one of those things that computers could perhaps figure out on their own in the future, just like we don't allocate registers by hand anymore either. In a similar way that, say, ATLAS finds out by trial and error the best way to perform FP linear algebra within a system of parametric code solutions. I think the "here's what I mean, give me a piece of code that does this" approach could have massive impact in the future. Transparent caching, glue code/plumbing, automatic algorithm selection based on result constraints etc. all seem like possible applications.
jsingleton 10y ago
Seconded that cache-invalidation is hard. This may be a cliché, but it really is hard. Implementing a cache may be easy but debugging a cache, or particularly the interactions of multiple caches (some outside of your control) certainly isn't. I've encountered these problems on many projects and also written about them in detail for my recent book.
- jakub_h 10y ago
  In fact, it is well known that the two hardest things in programming are cache invalidation, naming things, and off-by-one errors.
slowmovintarget 10y ago
This is another one of those PLace-Oriented Programming (PLOP) problems. Rather than a fictional "now" read at a place, perceive a factual "then" which may be cached to your heart's content. Granted, if you aren't taking advantage of immutable data in the first place, it can hurt to get there.
flukus 10y ago
In the real I world see caching mess things up more than they help with stupid implementations like caching entire database tables, n+1 problems being moved from the database to the cache, etc. Where I am now we have this absolutely retarded in memory cache that we write to (it will write to the DB several minutes later). At other places I've seen the cache stored in session variables. Caching has it's place, but more often than not I see it used as a bandaid on a terrible design.
MrDosu 10y ago
> can be added in 10 LOCs to me is kinda like you can easily make heavier elements by just adding a few electrons, protons and neutrons...

huhtenberg 10y ago

> caching (and cache-invalidation) is really difficult That's an urban legend. Needlessly complicated or over-abstracted general-purpose caching frameworks are difficult, but your dumbest imaginable linear LRU fast lookup is both exceptionally useful and can indeed be done in 10 LoC in a lot of cases.

throwawayReply 10y ago
It's not the algorithm that's difficult, it's the effect of adding caching to a system that wasn't built with caching in place at the start that is difficult. This isn't an "urban legend" it's first hand experience working with companies trying to add caching. No, those companies aren't even trying to write caching algorithms, they're just bundling in a caching layer and hoping that the system behaves in the same way. It only takes somewhere which writes data (perhaps in a way that bypasses the caching layer so the cache doesn't know it has changed) and re-reads it back quickly for software which used to work suddenly breaks. Now you might look at that and go "omg refactor it! That's horrible code, that should never ship" etc, but not everywhere is the s.v. bubble with endless amounts of the best developers to throw at problems. Code which worked and solved a business problem ended up shipping, possibly without testers and probably without code reviews. So adding a caching layer suddenly "breaks" those reports, now who's going to have to fix it, not the person who wrote those reports even if the very behavior of side-effected data changes and db re-reads is precisely a cause of data layer slowness that led to wanting to implement caching...
- sqeaky 10y ago
  > It only takes somewhere which writes data (perhaps in a way that bypasses the caching layer so the cache doesn't know it has changed) and re-reads it back quickly for software which used to work suddenly breaks. So those 10 lines need to be in the wrong place? Why expose the uncached API? Web or single system implement caching in a defined is easy if you don't have a defined API you probably don't have a good system. If you don't have a good system, why are you trying to implement caching? The not being good part is probably why its slow.
- xixi77 10y ago
  I am not sure you and the OP are talking about the same thing. Bundling a caching layer without even trying to write caching algorithms -- particularly if such a layer is serving multiple purposes -- sounds to me like what the parent is calling a "general-purpose caching framework", probably overly abstracted too as these things are wont to be. I would be super cautious incorporating this kind of black-box stuff. Even if the docs have 10 LOC examples, there can be all kinds of unexpected quirks that you would need to be aware of before doing anything. I read the OP as talking about specific, single-purpose caching techniques -- e.g. when you need to repeatedly compute a function of arbitrary parameters, it can help a lot to simply store values for the more common parameter combinations.
  - striking 10y ago
    It all depends on the purity of the underlying computation. If you're multiplying XXL numbers together, that's different than accessing a database with dynamic or variable data. Math is totally pure. But you'll have to evaluate the constraints on the purity of that database access.
- huhtenberg 10y ago
  Nobody's saying that one can just throw in a caching layer, touching nothing else and it will just magically work. There's obviously some thought and due consideration required, but it is NOT "really difficult". And in a lot of cases it is in fact as simple as adding a handful lines of code. PS. It is an urban legend, because "cache invalidation is hard" gets repeated a lot, initially as a joke, but it doesn't preclude people who aren't familiar with the subject from taking it as a fact and then repeating it as such. Voice recognition from scratch is hard. Some lock-free data structures are hard. Caching is not hard. It's knowing what the heck you are actually doing and doing it well is what's hard. By the same measure, C macros would be hard, because some idiot can do #define true false and everyone else will spend the same 10 months trying to understand why the hell things break now and then. Caching is hard is when someone starts messing with other people' code without fully understanding it. But then anything is "hard" under these circumstances.
xixi77 10y ago
Precisely -- it's the "general-purpose" part that is extremely complicated, which is what everyone here seems to be talking about when bringing up invalidation, but having simple, specific and localized caching in a performance-critical region is not that hard, and can be very effective.
falcolas 10y ago
I have to agree with the parent - cache invalidation is tough. When do you do it? What triggers an invalidation? When is it OK to use known-stale data? How long should a cache be valid for? If multiple copies of a program are brought up, what effect will it have on the caches? How do updates from one instance get populated to others? What are the impacts on up- and down-stream services? I'm going to borrow from someone much more eloquent than I: How simple it is to declare a static hashtable, and yet how perilous! http://thecodelesscode.com/case/148?topic=caching http://thecodelesscode.com/case/148?topic=caching
rantanplan 10y ago
>That's an urban legend. ROFL. What are you talking about? You're talking as if it's a solved problem for all cases. Hint: it's not. If it was an urban legend people wouldn't write dissertations on it.

creshal 10y ago

It really depends on what you're trying to cache. Caching expensive calculations e.g. is trivial to get right (use all arguments as cache key) and often you don't even need invalidation (unless your algorithm changes at runtime).

Klathmon 10y ago
Memoization works amazingly and can be very easy to implement, but it's not always that applicable. In my experience, I just don't hit that many pure functions that don't do things like touch the database (which can change out from under the function), or are called enough with the same arguments that memoization is actually worth it. But when it does work, it's like magic. I do a lot of work in javascript now, and it's great being able to wrap a function in a single line `memoize` function and instantly improve performance.

vinceguidry 10y ago

Caching is just another layer of complexity on top of your app. Sort of like HTML templates. If you're expecting it to be a no-maintenance drop-in solution, you're going to get burned. If you're willing to think carefully about how it fits into your domain, then you might be able to get away with a 10 LOC method on your base controller class.

jakub_h 10y ago
It's a pervasive element, though. Which to me means two things. First, I wonder if there isn't a way of adding it (really) transparently into a language. Basically, whenever there's a possibility that a value is a function of old values, chances are that a previously used result is still available. Second, strategies can have massive time and space implications, but that's exactly why being explicit about them in the application's code in any way should be avoided at all costs: they shouldn't change the semantics, only pragmatics. Given that compilers already do this with simpler things (are my local variables actually on stack or are they kept in registers?), one has to wonder if this isn't one of those things that computers could perhaps figure out on their own in the future, just like we don't allocate registers by hand anymore either. In a similar way that, say, ATLAS finds out by trial and error the best way to perform FP linear algebra within a system of parametric code solutions. I think the "here's what I mean, give me a piece of code that does this" approach could have massive impact in the future. Transparent caching, glue code/plumbing, automatic algorithm selection based on result constraints etc. all seem like possible applications.

jsingleton 10y ago

Seconded that cache-invalidation is hard. This may be a cliché, but it really is hard. Implementing a cache may be easy but debugging a cache, or particularly the interactions of multiple caches (some outside of your control) certainly isn't. I've encountered these problems on many projects and also written about them in detail for my recent book.

jakub_h 10y ago
In fact, it is well known that the two hardest things in programming are cache invalidation, naming things, and off-by-one errors.

slowmovintarget 10y ago

This is another one of those PLace-Oriented Programming (PLOP) problems. Rather than a fictional "now" read at a place, perceive a factual "then" which may be cached to your heart's content. Granted, if you aren't taking advantage of immutable data in the first place, it can hurt to get there.

flukus 10y ago

In the real I world see caching mess things up more than they help with stupid implementations like caching entire database tables, n+1 problems being moved from the database to the cache, etc. Where I am now we have this absolutely retarded in memory cache that we write to (it will write to the DB several minutes later). At other places I've seen the cache stored in session variables. Caching has it's place, but more often than not I see it used as a bandaid on a terrible design.

MrDosu 10y ago

> can be added in 10 LOCs to me is kinda like you can easily make heavier elements by just adding a few electrons, protons and neutrons...