On Wed, 10 Feb 2021 00:44:57 GMT, Xue-Lei Andrew Fan <xue...@openjdk.org> wrote:
> I may think it differently. It may be hard to know the future frequency of an > cached item based on the past behaviors. For the above case, I'm not sure > that K=3 is used less frequently than K=1. Maybe, next few seconds, K=1 could > be more frequently. I agree that such prediction might not be 100% accurate. But, quick google search reveals that there are [many](https://www.usenix.org/system/files/hotstorage20_paper_eytan.pdf) [articles](https://link.springer.com/article/10.1007/PL00009255) that claim that LRU caches offer better hit rates than FIFO, especially for in-memory caches. > I would like a solution to following the timeout specification: keep the > newer items if possible. That's a trivial change; all we need to do is change `true` to `false` [here](https://github.com/openjdk/jdk/blob/abe0e238bd25adb1ddd2b655613899bfa063cd85/src/java.base/share/classes/sun/security/util/Cache.java#L268). But, as stated above, LRU is better than FIFO, so I wouldn't want to do that. I could keep LRU and add another linked list that would store items in the order of their expiration dates; then we could quickly scan that list for expired items. Note: the order of expiration dates is not necessarily the order of insertion, because 1) `System.currentTimeMillis()` is not monotonic - it can move back when something changes the system time, 2) the expiration date is calculated at insertion time, so if someone changes the timeout on a non-empty cache, new items may have shorter expiration time than old ones. So, I'd either need to address that first (change `currentTimeMillis` to `nanoTime` and store creation time instead of expiration time), or use insertion sort for adding items (which would get very slow if either of the above mentioned situations happened). Let me know your thoughts. ------------- PR: https://git.openjdk.java.net/jdk/pull/2255
