ARC (Adaptive Replacement Cache)

[ctcpip]

There is some desire to use (or consider using) ARC. ARC is protected under patent # 6,996,676 granted to IBM, which was assigned to Intel, and is not set to expire until early 2024 (if no further patent term adjustments are made).

IBM and Intel are both members of Ecma, and both have signed the TC39 Royalty Free Technical Committee policy. IANAL, but this may clear the way for using ARC without any issue.

Intel's Standards, Patents, and Intel Business Informational Brief seems to support this as well. Namely:

Consistent with its participation in standard-setting organizations, Intel may voluntarily commit to license its patents that are “essential” for compliance with a standard on fair, reasonable and non-discriminatory (“FRAND” or “RAND”) terms.

Nonetheless, we may consider contacting Intel's standards licensing team.

Alternately, or additionally, a variant of ARC licensed under the CDDL could be considered.

[js-choi]

1. I would be happy to specify this and at least propose it for Stage 2. Though I’d like the opinions of the other champions too, given that any of the engine implementors might balk at the (mild?) legal uncertainty. At the very least, putting it in Stage 2 would raise awareness that we would like it and cause all engine implementers to look at its legal viability.

2. Ideally, we would also collect any prior real-world use cases of ARC caches on the application level, rather than on, say, the CPU level. I remember that Postgres had been using it for paging (before dropping it because of its patent)—but are there use cases that might emerge from needs of large JavaScript applications?

3. Lastly, are there any situations in which LRU is preferable to ARC? Is ARC always better than LRU? (I need to reread the Meggido/Modha paper…) If it is, should we not include LRU if we include ARC?

[kriskowal]

My understanding is that no eviction strategy is optimal for all loads, and that ARC behavior is good for loads that might be better fit for either LRU or LFU if the bias is not known or knowable for a particular load. It is a better default for general purpose caches but will not outperform the best fit algorithm for a known usage pattern.

[falsandtru]

Do you know ARC retains evicted keys? For this reason, ARCSet is incoherent. ARCSet(100) actually retains 200 items like LRU(200). ARCMap will also unacceptable because GC cannot collect the retained keys and their references even after item deletions. The higher performance cache algorithm that resolved the problems is available #12.