<p>Yes, the two paper do not mention an explicit bound. However, the authors kindly provided me their simulator and it has a <a href="https://github.com/ben-manes/caffeine/blob/master/simulator/src/main/resources/com/github/benmanes/caffeine/cache/simulator/parser/lirs/lirs.h#L8" rel="nofollow noreferrer">bound parameter</a>. Many implementations have had memory leaks (e.g. <a href="https://dev.clojure.org/jira/browse/CCACHE-32" rel="nofollow noreferrer">Clojure's</a>, <a href="https://issues.jboss.org/browse/ISPN-7171?_sscc=t" rel="nofollow noreferrer">Infinispan</a>).</p>

<p>Unfortunately naive pruning is expensive as it requires a long stack walk. Thomas Mueller's <a href="https://github.com/apache/jackrabbit-oak/blob/trunk/oak-core-spi/src/main/java/org/apache/jackrabbit/oak/cache/CacheLIRS.java" rel="nofollow noreferrer">implementation</a> uses a secondary queue for non-resident entries. This adds a little more cost per entry, but significantly improves runtime performance in my benchmarks.</p>

<p>Unfortunately none of the implementations I came across matched the author's simulator. This is because some details are easily missed (like warmup) or not mentioned (don't promote on a correlated references). After debugging traces against their simulator, <a href="https://github.com/ben-manes/caffeine/blob/master/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/irr/LirsPolicy.java" rel="nofollow noreferrer">mine</a> is near perfect and includes Thomas' optimization. It was intended to be accurate and readable in case I adopted it for a cache.</p>

<p>I chose <a href="http://arxiv.org/pdf/1512.00727.pdf" rel="nofollow noreferrer">TinyLFU</a> instead, after introducing an admission window to improve its performance in recency-skewed traces. The authors and I are experimenting with an adaptive window based on simple hill climbing to replace the static configuration. This <a href="http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html" rel="nofollow noreferrer">article</a>, <a href="https://docs.google.com/presentation/d/1NlDxyXsUG1qlVHMl4vsUUBQfAJ2c2NsFPNPr2qymIBs" rel="nofollow noreferrer">slides</a>, and <a href="https://github.com/ben-manes/caffeine/wiki/Efficiency" rel="nofollow noreferrer">simulations</a> should provide a brief introduction to the policy. A reader implemented a minimal <a href="https://github.com/mandreyel/w-tiny-lfu" rel="nofollow noreferrer">C++ port</a>.</p>
Does LIRS store a boundless number of elements?
<p>I'm looking into implementing LIRS caching algorithm (as described in <a href="https://en.wikipedia.org/wiki/LIRS_caching_algorithm" rel="nofollow noreferrer">wikipedia</a> and <a href="http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-02-6.pdf" rel="nofollow noreferrer">this paper</a>), but the sources are rather difficult to follow, leaving out certain cases from their descriptions. Referring to <a href="https://en.wikipedia.org/wiki/LIRS_caching_algorithm#Selecting_the_replacement_victim" rel="nofollow noreferrer">example (e) on wikipedia</a> where a previously unknown element is referenced, it appears the element is added as resident HIR, without any element being deleted from LIRS. This suggests I could keep referencing unique elements, and grow LIRS forever. Is this the case...? This seems bad, as the references could blow up the using application's memory. Am I missing something?</p>

<p>Also, if anyone knows any interesting alternatives to LIRS that are well described, I'd love to know about them - doing some side programming to catch up on my C++, and caching is the topic I've been working on :)</p>