search

tc39 / proposal-policy-map-set

A TC39 proposal for Maps and Sets with cache replacement policies like LRU and LFU.
BSD 3-Clause "New" or "Revised" License
15 stars 2 forks source link

Which cache-replacement policies to include #2

Open js-choi opened 2 years ago

js-choi commented 2 years ago

Currently the policy contains classes for FIFO (first in, first out), LIFO (last in, first out), LRU (least recently used out), and LFU (least frequently used out). Are these adequate? Are they too much? Are there other policies that should be built in? Should we start with a minimal collection of policies? There are many sophisticated policies used in CPU paging (some of which are still patented); should we consider those?

js-choi commented 2 years ago

From Matrix conversations today:

[@rbuckton] Are we only considering a very basic cache approach, or is the possibility of more complex caching strategies (i.e., cache key dependencies, user-defined change monitors, absolute or sliding expiration, etc.) on the table?

Everything is on the table for discussion in Stage 1, although we probably want to start simple and add more complicated policies after we standardize the simple cases.

What’s most important is that we gather concrete JavaScript use cases for those algorithms, like sliding expiration etc.

[@kriskowal] If we wait, IBM’s patent on ARC will expire and we will only need one.

[@ctcpip] ARC patent was assigned to Intel so it's out of my hands ☹️ expires in Feb 2024 if there are no further adjustments could write a letter to Intel asking nicely for RF license Intel is an ECMA member

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. 🤔

I would love to support ARC as a policy, but, although it outperforms LRU and that’s important for CPU caches, it might not be a big enough difference to overcome the patent problems. If we standardized ARCMap, then each of the engine vendors would have to take their own legal counsel regarding Intel’s license. But maybe it’s worth seriously considering…

littledan commented 2 years ago

We don't need to worry too much about TC39 participants' patents: (if they decide not to opt out, which has never happened) our standards process establishes an open license to their patents, for use in the relevant standard. The relevant policy is Ecma's Royalty-free Patent Policy, which TC39 has adopted.

ctcpip commented 2 years ago

I opened #9 to discuss the ARC licensing concerns.

falsandtru commented 1 year ago

We have to understand and consider that ARC and some algorithms retain evicted keys as histories or ghost caches https://github.com/tc39/proposal-policy-map-set/issues/9#issuecomment-1302897567. DWC #12 is appropriate for resolving the problems.

TomokiMiyauci commented 1 year ago

Do we need LIFO as a cache policy? I don't know of any situation where it is an appropriate option.