Holy crap, that's the reason this algorithm isn't all over the place? That seriously irks me, and this one seems like a great patent to look for either Tesla-esque giveaway or just invalidation (EFF, anybody?).
Smart generic caching could do so much for the global infrastructure with all the data we move around these days.
While the patent may be annoying, in practice there are a number of other cache replacement algorithms and mechanisms that are just as effective as ARC. The tradeoffs inherent in cache replacement algorithms means there are numerous ways of achieving approximately equivalent results. ARC is not a globally optimal design or anything like that.
In that sense, the patent is kind of worthless. Anyone that knows what they are doing can design around it with no loss of functionality or efficiency. A lot of sophisticated systems end up designing custom algorithms tuned for the use case anyway.
Had implemented this for a grad school project long time back. We had compared the complexity and effectives of this algorithm and compared it with lru, by the end the results of both were comparable unless in certain special conditions arc works well, whereas lru fails like a virus scan etc. But the simplicity of lru triumphs. For anyone interested, here's a paper which was an assigned reading for the project - http://www.cs.cmu.edu/~15-440/READINGS/megiddo-computer2004....
(Outperforming LRU with an Adaptive Replacement Cache Algorithm)
5 comments
[ 2.9 ms ] story [ 17.5 ms ] threadhttps://en.wikipedia.org/wiki/Adaptive_replacement_cache
http://patft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=...IBM's patent will take quite a while to expire. It's truly a shame this can't be used by operating system page cache policy because of patents.
Smart generic caching could do so much for the global infrastructure with all the data we move around these days.
In that sense, the patent is kind of worthless. Anyone that knows what they are doing can design around it with no loss of functionality or efficiency. A lot of sophisticated systems end up designing custom algorithms tuned for the use case anyway.
(Outperforming LRU with an Adaptive Replacement Cache Algorithm)