On Tue, 16 Feb 2021 19:38:50 GMT, djelinski <github.com+30433125+djelin...@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. > > Well, if removing all expired items before evicting live ones is a > non-negotiable, implementing all operations in constant time is much easier > with FIFO, where we only need to keep one item order. > The new commits contain the following changes: > - use `nanoTime` instead of `currentTimeMillis` to make sure that time never > goes back > - store insertion time instead of expiration time, so that older items always > expire before newer ones, even when timeout is changed > - change internal hash map to store (and evict) items in insertion (FIFO) > order > - always stop scanning entries after finding the first non-expired item, > because subsequent items are now guaranteed to have later expiration dates, > and collected soft references are handled by reference queue. > > tier1 and jdk_security tests passed; benchmark results show only minimal > changes. I verified that none of the classes using `Cache` mentions LRU, > looks like this was an implementation detail. Actually there's a much easier solution to reduce the number of slow `put()`s without making any behavioral changes. The cache object could store the earliest expire time, and then exit `expungeExpiredEntries()` early when current time is earlier than the earliest expire time - when it is, we know that there are no expired items in the queue and we can skip the scan entirely. @XueleiFan do you think the above is worth exploring? ------------- PR: https://git.openjdk.java.net/jdk/pull/2255
