It appears that TTL cache exhibits quadratic performance (+ its evict is buggy)

Description

The library looks useful, thanks!

I looked at the code, and unless I'm mistaken, every cache miss seems to result in a full pass over the entire cache to evict old entries. The performance implications of this would be unacceptable for my target application. Replacing the TTL data structure with a persistent analog of a LinkedHashMap and using a take-while instead could fix this problem.

Also, evict seems to pass the cache in twice, rather than the cache and the TTL...

Environment

None

Activity

Show:
Sean Corfield
March 2, 2018, 7:35 AM

Release 0.7.0

Sean Corfield
March 2, 2018, 7:26 AM

Added a persistent queue and a generation number to ensure miss is a minimal walk of outdated cache items and evict is O(1).

Kevin Downey
March 1, 2018, 6:33 PM

sounds good to me.

you could store some kind of generation number (a number incremented on every add to the cache) with the value and the entry in the evict queue and only remove items when those things match, so then you don't need to walk the queue when manually evicting.

Sean Corfield
March 1, 2018, 6:30 AM

I'm looking at this and considering adding a PersistentQueue of key/time pairs so each miss would only need to walk that far enough to find all aged out keys, but also keeping the ttl hash map for fast access there (to keep lookup and has? O(1)). miss would only walk as far as it needed to find all expired keys each time, rather than filtering the entire collection. evict would become O as it would need to reduce the queue to remove the matching key.

Since changing the fields in the TTLCache would break any code that uses it directly, I'd introduce a new TTLCacheQ for this time (and possible a new factory function? How much code uses the factory and then assumes the layout of the underlying type?). And, of course, clearly document the two performance options.

Thoughts?

Ivan Kryvoruchko
March 7, 2017, 5:11 PM

Is it an intended behavior? http://dev.clojure.org/jira/browse/CCACHE-15?focusedCommentId=34738&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-34738 Spent some time debugging this problem today, looks like bug to me. In case this is really a bug should a separate issue be created for it?

Simplest way to reproduce (`has?` returns true, but item itself is no longer in cache):

Completed

Assignee

Sean Corfield

Reporter

Jason Wolfe

Labels

None

Approval

None

Patch

None

Priority

Critical