Missing LU and LRU is linear complexity - performance
Description
Profiling some code with YourKit showed a hotspot in cache statistics on (miss) for LU and LRU caches.
Basically two issues: (count (keys {....})) is a count of a seq, not efficient. Replaced with a count of the map.
Secondly, (apply f anything) is slow. Profiler showed that the (apply min-key) was really slow. This is mitigated by using a c.d.priority-map instead. On a priority-map, (ffirst {}) or (first (peek {}).
Also inverted the logic for threshold comparison. Since there is a (build-leastness-queue) that populates statistics, should caches should favor codepaths for the state of being full all the time?
Environment
Mac Oracle JDK, Linux OpenJDK
Activity
This was committed in https://github.com/clojure/core.cache/commit/3b48810176c42e0ffd91e9d05b6c7be83b3490f3 but this issue was never closed.
Patch in proper format
I take back the part about (apply) being slow. I think it's more the fact that it's doing a linear scan on keys every single time.
(apply) does show up a lot in a profiler, but I haven't figured out why. (apply + (range big)) seems to even be slightly faster than (reduce +) on the same range.
