<< Back to previous view

[CCACHE-21] LRU and LU caches never evict entries that came in as a seed and are never accessed Created: 14/Mar/12  Updated: 14/Mar/12  Resolved: 14/Mar/12

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Completed Votes: 0
Labels: bug, cache, lru, lu


 Description   

If one initializes an LRU or LU cache with seed data and those datum are never touched, then they are never evicted.

  (def C (lru-cache-factory {:a 1, :b 2} :limit 2))
  
  (-> C (assoc :c 3) (assoc :d 4) (assoc :e 5))

You would expect that the cache should contain only :d and :e, but it instead includes :a, :b, :d and :e! The problem is that seeds are never added to the eviction queue.



 Comments   
Comment by Fogus [ 14/Mar/12 8:15 AM ]

Fixed in 5751b7e8d8d2f10c87b8a79c8ed9b0324368514d





[CCACHE-1] Storing falsey value in underlying struct causes failure in get with not-found arg Created: 28/Nov/11  Updated: 30/Nov/11  Resolved: 30/Nov/11

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Completed Votes: 0
Labels: associative, bug


 Description   

Cache c seeded with {:a nil} and accessed via (get c :a 42) returns 42 instead of nil. The reason for this is that the map vatAt delegates directly to the lookup protocol function without a has? guard.



 Comments   
Comment by Fogus [ 30/Nov/11 10:57 AM ]

Fixed in https://github.com/clojure/core.cache/commit/7f77aee164d59441caa56979821bae8f64affba7





[CCACHE-3] Add LIRS support. Created: 04/Dec/11  Updated: 06/Dec/11  Resolved: 06/Dec/11

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Completed Votes: 0
Labels: cache, lirs


 Description   

Clache had an implementation of the LIRS http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.2184 strategy. This capability should be merged into core.cache also.



 Comments   
Comment by Fogus [ 06/Dec/11 8:40 AM ]

Added LIRS stock from Clache in f71d276695adc5c3af77799201140ea840cd5f79.





[CCACHE-4] Added LIRS factory fn Created: 06/Dec/11  Updated: 08/Dec/11  Resolved: 08/Dec/11

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Completed Votes: 0
Labels: cache, enhancement


 Description   

LIRS is implemented as a type only ATM. There should also be a corresponding factory fn.



 Comments   
Comment by Fogus [ 08/Dec/11 12:11 PM ]

Completed in f4d1bf9f1069ba875a7a6a8a65646b35c6fbfd8f





[CCACHE-2] FIFOCache seed does not properly seed the FIFO queue Created: 30/Nov/11  Updated: 09/Dec/11  Resolved: 09/Dec/11

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Completed Votes: 0
Labels: None


 Description   
(def c (clojure.core.cache/seed (FIFOCache. {} nil 1) {:a 1 :b 2}))

(defmethod print-method clojure.lang.PersistentQueue [q, w]
  (print-method '<- w)
  (print-method (seq q) w)
  (print-method '-< w))

(str c )
;=> "{:a 1, :b 2}, <-(:clojure.core.cache/free)-<"

(str (assoc c :c 3))
;=> "{:a 1, :c 3, :b 2}, <-(:c)-<"

The queue never gets the seed keys :a and :b and so they will never get expelled.



 Comments   
Comment by Fogus [ 09/Dec/11 6:46 AM ]

Fixed in 7be1589095b48b7158584897a6b08c93322c3607





[CCACHE-7] Add eviction implementation to FIFOCache Created: 08/Dec/11  Updated: 09/Dec/11  Resolved: 09/Dec/11

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Completed Votes: 0
Labels: associative, cache, evict, fifo


 Description   

The evict method in the ProtocolCache needs implementation for FIFOCache. I will start initially with a single key eviction method to start. The evict method would form the basis for the associative dissoc which in turn forms the basis for proper limited seeding. Currently only the BasicCache impl has evict.



 Comments   
Comment by Fogus [ 09/Dec/11 8:52 AM ]

Added in 094363f48dbd5d4399d5e7df2b3fe995cdaf1737.





[CCACHE-12] LRUCache miss explodes if given an empty lru table Created: 09/Dec/11  Updated: 09/Dec/11  Resolved: 09/Dec/11

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Completed Votes: 0
Labels: None


 Description   

The min-key method used to determine least tick explodes with:

clojure.lang.ArityException: Wrong number of args (1) passed to: core$min-key

This is a corner case that should be handled.



 Comments   
Comment by Fogus [ 09/Dec/11 9:42 AM ]

Fixed in beaa62d02c964b1c0114ab088c6a835ca4391f80.





[CCACHE-8] Add eviction implementation to LRUCache Created: 08/Dec/11  Updated: 09/Dec/11  Resolved: 09/Dec/11

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Completed Votes: 0
Labels: associative, cache, evict, lru


 Description   

The evict method in the ProtocolCache needs implementation for LRUCache. I will start initially with a single key eviction method to start. The evict method would form the basis for the associative dissoc which in turn forms the basis for proper limited seeding. Currently only the BasicCache impl has evict.



 Comments   
Comment by Fogus [ 09/Dec/11 9:11 PM ]

Added in 77174780ac030ca3e72d51cae4dfb3eb2ac286ee.





[CCACHE-9] Add eviction implementation to TTLCache Created: 08/Dec/11  Updated: 10/Dec/11  Resolved: 10/Dec/11

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Completed Votes: 0
Labels: associative, ccahe, evict, ttl


 Description   

The evict method in the ProtocolCache needs implementation for TTLCache. I will start initially with a single key eviction method to start. The evict method would form the basis for the associative dissoc. Currently only the BasicCache impl has evict.



 Comments   
Comment by Fogus [ 10/Dec/11 7:35 AM ]

Added in c25022137d55be6aab9e34b5c0f91bc933a05926.





[CCACHE-10] Add eviction implementation to LUCache Created: 08/Dec/11  Updated: 12/Dec/11  Resolved: 12/Dec/11

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Completed Votes: 0
Labels: associative, cache, evict, lu


 Description   

The evict method in the ProtocolCache needs implementation for LUCache. I will start initially with a single key eviction method to start. The evict method would form the basis for the associative dissoc which in turn forms the basis for proper limited seeding. Currently only the BasicCache impl has evict.



 Comments   
Comment by Fogus [ 12/Dec/11 7:54 AM ]

Implemented in ca4587bdbdca2728b191bf98472a778231250e61.





[CCACHE-6] Cut 0.5.0 release jar Created: 06/Dec/11  Updated: 13/Dec/11  Resolved: 13/Dec/11

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Completed Votes: 0
Labels: release


 Description   

The core.cache functionality, with LIRS will be inline with Clache. A release should be cut and pushed to Maven central pending CCACHE-4.



 Comments   
Comment by Fogus [ 13/Dec/11 7:44 AM ]

v0.5.0 jar deployed to Maven central. Release notes outstanding.

Comment by Fogus [ 13/Dec/11 12:02 PM ]

Announced at: http://groups.google.com/group/clojure/browse_frm/thread/69d08572ab265dc7

Release notes at: https://github.com/clojure/core.cache/blob/master/docs/release-notes/release-0.5.0.markdown

README at: https://github.com/clojure/core.cache/blob/master/README.md

Post at: http://blog.fogus.me/2011/12/13/announcing-core-cache-v0-5-0/





[CCACHE-19] Create 3-arg version of lookup Created: 04/Jan/12  Updated: 05/Jan/12  Resolved: 05/Jan/12

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Completed Votes: 0
Labels: cache, lookup

Approval: Ok

 Description   

Currently, lookup comes in only the 2-arg flavor (i.e. gimme a key and I'll give you a value or nil). The issue with this is that nil is potentially a legal value. Therefore, the 3-arg version logic is the same as the 3-arg `assoc` (.lookup this key not-found).

This change should propagate to all of the existing cache impls.



 Comments   
Comment by Fogus [ 05/Jan/12 7:36 AM ]

Added in f4450a039ef703ce62c61dd497aafed73194f1c2





[CCACHE-5] Implement SoftCache Created: 06/Dec/11  Updated: 13/Jul/12  Resolved: 19/Jun/12

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: Fogus Assignee: Unassigned
Resolution: Completed Votes: 0
Labels: None

Attachments: File mutable-soft-cache.diff    

 Description   

Clache had a buggy implementation of a cache backed by soft references. This capability should be explored further and implemented properly for core.cache.



 Comments   
Comment by Paul Stadig [ 04/Jun/12 10:20 AM ]

I'd be interested in taking a crack at this, but would find it useful to have more infos about what bugs existed in the Clache implementation.

Comment by Paul Stadig [ 16/Jun/12 8:14 AM ]

I've implemented a mutable SoftCache. I felt as though the tradeoffs made it worth using a ConcurrentHashMap as the base for SoftCache.

SoftReference objects are mutable (and tied to a specific instance of ReferenceQueue). ReferenceQueue is mutable. Using an immutable map as the base for SoftCache would cost {O(n)} when removing cleared SoftReference objects from the cache.

If immutability is desirable, I also have an implementation of an immutable SoftCache, but it suffers from the above {O(n)} cost.

Comment by Fogus [ 19/Jun/12 6:53 AM ]

I have no problem with internal mutability in the cache impls, so that immutable code might not be needed. I've pushed the 0.7.0-SNAPSHOT version with your additions and will run it through the paces post-haste. Thank you for tackling this Paul, it's a huge help.

Comment by Fogus [ 19/Jun/12 6:54 AM ]

Planned for v0.7.0

Comment by Fogus [ 13/Jul/12 10:47 AM ]

Actually released in version 0.6.1.





[CCACHE-23] Overwriting entries in LRU-cache deletes LRU key-values unnecessarily Created: 22/Jun/12  Updated: 22/Aug/12  Resolved: 13/Jul/12

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Arthur Edelstein Assignee: Fogus
Resolution: Completed Votes: 0
Labels: None


 Description   

To "overwrite" the value in an LRUCache, one uses assoc. Surprisingly, another k,v entry is evicted, even though the total number of items in the cache should not be increased by overwriting.

Demo:

(def C0 (lru-cache-factory {} :threshold 3))
; --> #<Var@7ec74910: {}>

(def C1 (-> C0 (assoc :a 1) (assoc :b 2) (assoc :c 3)))
; --> #<Var@315863e4: {:c 3, :b 2, :a 1}>

(-> C1 (assoc :a 4) (assoc :a 5) (assoc :a 6))
; --> {:a 6}



 Comments   
Comment by Fogus [ 12/Jul/12 6:40 AM ]

I've pushed a commit to master that I believe fixes this problem. I'll look at it a bit more and will release a v0.6.1 version ASAP.
Thank you

Comment by Fogus [ 12/Jul/12 3:24 PM ]

version 0.6.1 has been pushed out to Maven central.

Comment by Fogus [ 13/Jul/12 10:46 AM ]

v0.6.1 pushed to Maven Central.

Comment by Si Yu [ 16/Jul/12 1:30 PM ]

It appears v0.6.1 still has not fixed the issue

(-> (cache/lru-cache-factory {} :threshold 2)
(assoc :a 1)
(assoc :b 2)
(assoc :b 3))
{:b 3}

Comment by Arthur Edelstein [ 22/Aug/12 7:28 PM ]

Works for me in 0.6.2. Thanks, Fogus!

(-> (cache/lru-cache-factory {} :threshold 2)
(assoc :a 1)
(assoc :b 2)
(assoc :b 3))

; {:b 3, :a 1}





[CCACHE-25] TTLCache appears to have inconsistent behavior with respect to the TTL parameter Created: 02/Aug/12  Updated: 14/Aug/12  Resolved: 14/Aug/12

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: David Santiago Assignee: Fogus
Resolution: Completed Votes: 0
Labels: None


 Description   

There appears to be some inconsistency in the implementation of TTLCache. Specifically, it appears that if you lookup a value whose TTL has expired, but no new items have been added to the cache, it will still be present. But if you ask if the cache has? the value, it will report that it does not. For example:

```
user> (defn sleepy [e t] (Thread/sleep t) e)
#'user/sleepy
user> (-> (ttl-cache-factory {} :ttl 1000) (assoc :a 1)
(assoc :b 2)
(sleepy 2200)
(has? :a))
false
user> (-> (ttl-cache-factory {} :ttl 1000) (assoc :a 1)
(assoc :b 2)
(sleepy 2200)
(get :a))
1
```

So here we see, has? reports the value is no longer in the cache, but get will still give you the value. Unless I am misunderstanding the purpose or contract of these two functions, it seems that they should agree in whether or not a value is in the cache.

This also brings up the question of whether a value in a TTL cache that has passed the TTL should remain in the cache until the cache is updated. My expectation was that an item is not in the cache after the TTL has passed (ie, has? is currently correct). I can also see the argument that the TTL parameter is merely a lower bound on the amount of time it is cached; if it can be accommodated for longer, it will be (and thus lookup is currently correct).

As I said, my expectation was that things are no longer in the cache after the TTL, and I would still vote for this behavior as the correct one for a TTL cache, as it seems like a reasonable cache to use for things that can change out from under you, but a short period where it is out of date is acceptable (which is how I was trying to use it).



 Comments   
Comment by David Santiago [ 14/Aug/12 6:39 PM ]

core.cache 0.6.2 fixes this issue for me; the call to get in the code above now returns 'nil' to match the false return from has?. I'd close the issue if I could.

Thanks Fogus.

Comment by Fogus [ 14/Aug/12 8:33 PM ]

Fixed in v0.6.2





[CCACHE-24] Numerous Reflective Calls in core.cache Created: 19/Jul/12  Updated: 14/Aug/12  Resolved: 14/Aug/12

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: David Santiago Assignee: Fogus
Resolution: Completed Votes: 0
Labels: None
Environment:

core.cache 0.6.1, Clojure 1.3



 Description   

When I run lein check on my code, core.cache is a source of many reflective calls. Fortunately they don't seem to account for much time in my own profiling. But given that the purpose of a cache is to provide access to time-critical things, and the library can't easily anticipate the usage patterns of its users, it would be nice if we could remove these reflective calls, particularly where there does not appear to be any restriction to the use of the cache by doing so (that is, most of these appear to be from Java interop calls that are entirely inside the implementation of the caches).

Here's the output from lein check listing the reflective call sites:

Reflection warning, clojure/core/cache.clj:87 - reference to field iterator can't be resolved.
Reflection warning, clojure/core/cache.clj:87 - call to equiv can't be resolved.
Reflection warning, clojure/core/cache.clj:107 - reference to field iterator can't be resolved.
Reflection warning, clojure/core/cache.clj:107 - call to equiv can't be resolved.
Reflection warning, clojure/core/cache.clj:149 - reference to field iterator can't be resolved.
Reflection warning, clojure/core/cache.clj:149 - call to equiv can't be resolved.
Reflection warning, clojure/core/cache.clj:187 - reference to field iterator can't be resolved.
Reflection warning, clojure/core/cache.clj:187 - call to equiv can't be resolved.
Reflection warning, clojure/core/cache.clj:241 - reference to field iterator can't be resolved.
Reflection warning, clojure/core/cache.clj:241 - call to equiv can't be resolved.
Reflection warning, clojure/core/cache.clj:273 - reference to field iterator can't be resolved.
Reflection warning, clojure/core/cache.clj:273 - call to equiv can't be resolved.
Reflection warning, clojure/core/cache.clj:398 - reference to field iterator can't be resolved.
Reflection warning, clojure/core/cache.clj:398 - call to equiv can't be resolved.
Reflection warning, clojure/core/cache.clj:471 - reference to field poll can't be resolved.
Reflection warning, clojure/core/cache.clj:473 - call to remove can't be resolved.
Reflection warning, clojure/core/cache.clj:474 - call to remove can't be resolved.
Reflection warning, clojure/core/cache.clj:475 - reference to field poll can't be resolved.
Reflection warning, clojure/core/cache.clj:482 - reference to field iterator can't be resolved.
Reflection warning, clojure/core/cache.clj:482 - call to equiv can't be resolved.
Reflection warning, clojure/core/cache.clj:486 - reference to field get can't be resolved.
Reflection warning, clojure/core/cache.clj:488 - reference to field get can't be resolved.
Reflection warning, clojure/core/cache.clj:491 - reference to field get can't be resolved.
Reflection warning, clojure/core/cache.clj:500 - reference to field get can't be resolved.
Reflection warning, clojure/core/cache.clj:507 - call to put can't be resolved.
Reflection warning, clojure/core/cache.clj:508 - call to put can't be resolved.
Reflection warning, clojure/core/cache.clj:515 - call to remove can't be resolved.
Reflection warning, clojure/core/cache.clj:516 - call to remove can't be resolved.
Reflection warning, clojure/core/cache.clj:528 - reference to field get can't be resolved.
Reflection warning, clojure/core/cache.clj:528 - reference to field get can't be resolved.
Reflection warning, clojure/core/cache.clj:562 - reference to field q can't be resolved.



 Comments   
Comment by David Santiago [ 14/Aug/12 6:35 PM ]

core.cache 0.6.2 fixes this issue for me. I'd close the issue if I could.

Comment by Fogus [ 14/Aug/12 8:33 PM ]

fixed in v0.6.2





[CCACHE-13] Deprecate Clache Created: 13/Dec/11  Updated: 14/Aug/12  Resolved: 14/Aug/12

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Minor
Reporter: Fogus Assignee: Fogus
Resolution: Completed Votes: 0
Labels: clache, documentation


 Description   

core.cache was originally Clache , but its inclusion into contrib means the latter is redundant. The Clache repo should indicate the move and change to a place for docs and examples. Likewise, a formal announcement should be made.






[CCACHE-33] Some tests have ordering dependent upon Clojure hash function Created: 31/Jan/14  Updated: 14/Feb/14  Resolved: 14/Feb/14

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: Andy Fingerhut Assignee: Fogus
Resolution: Completed Votes: 0
Labels: None

Attachments: File ccache-33-v1.diff    
Patch: Code and Test

 Description   

The ones modified in the proposed patch are the ones failing with Clojure 1.6.0-master-SNAPSHOT as of Jan 30 2014, after some hash function changes had been made. There may be others that are dependent upon the hash ordering, but they are not failing. I haven't tried to determine if others might be sensitive to the hash function, too, other than the ones currently failing.



 Comments   
Comment by Fogus [ 14/Feb/14 1:55 PM ]

I've applied the test changes and will check over the remaining tests to ensure compatibility. Thank you.





[CCACHE-22] Change limit parameter name in TTLCache Created: 30/Mar/12  Updated: 15/Jun/12  Resolved: 15/Jun/12

Status: Resolved
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Trivial
Reporter: Sebastián Bernardo Galkin Assignee: Fogus
Resolution: Completed Votes: 0
Labels: enhancement, patch,, ttl

Attachments: Text File Changed-limit-parameter-name-in-TTLCache.patch    
Patch: Code

 Description   

"limit" is used in other caches to represent quantity, for TTL it represents time. Using the same name is confusing



 Comments   
Comment by Fogus [ 15/Jun/12 1:48 PM ]

Changed to :ttl-ms





[CCACHE-26] hit function in LRU cache can give funny results Created: 22/Aug/12  Updated: 22/Aug/12

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Arthur Edelstein Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: None


 Description   

A common-sense usage in caches is hit/get. But if I naively do this to an LRUCache, without checking first for the presence of the key, I can break the limit.

(-> (cache/lru-cache-factory {} :threshold 2)
(cache/hit :x)
(cache/hit :y)
(cache/hit :z)
(assoc :a 1)
(assoc :b 2)
(assoc :c 3)
(assoc :d 4)
(assoc :e 5))

; {:e 5, :d 4, :c 3, :b 2, :a 1}






[CCACHE-11] Add eviction implementation to LIRSCache Created: 08/Dec/11  Updated: 08/Dec/11

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: associative, cache, evict, lirs


 Description   

The evict method in the ProtocolCache needs implementation for LIRSCache. I will start initially with a single key eviction method to start. The evict method would form the basis for the associative dissoc which in turn forms the basis for proper limited seeding. LIRS poses an additional complication due to its dual limit lists. Currently only the BasicCache impl has evict.






[CCACHE-16] Benchmark v0.5.x against Google Guava Created: 16/Dec/11  Updated: 16/Dec/11

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: Fogus Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: benchmark, cache, guava


 Description   

Perform some tests and benchmarks of core.cache and Google Guava's com.google.common.cache library.






[CCACHE-17] Create function backed cache Created: 16/Dec/11  Updated: 19/Dec/11

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: cache, fn-cache, new-feature


 Description   

A cache implementation that is backed by a function that performs some action on a cache miss could serve as a front for any of the existing cache impls.



 Comments   
Comment by Rich Hickey [ 16/Dec/11 9:45 AM ]

It doesn't perform an action per se, it gets a passed key and returns a value, which the cache then caches (associates with the key) and returns. The tricky bit is when the function can't get a value. There needs to be some protocol for communicating that (could be like 3 arg get), and, should the cache be asked again later for the same key, calling the fn again.

Comment by Fogus [ 19/Dec/11 7:29 AM ]

Thanks for the feedback Rich. I believe I understand the subtleties now.





[CCACHE-27] Missing LU and LRU is linear complexity - performance Created: 04/Sep/12  Updated: 12/Sep/12

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Ghadi Shayban Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: enhancement, performance
Environment:

Mac Oracle JDK, Linux OpenJDK


Attachments: Text File priority-map-fixed.patch     Text File priority-map.patch    
Patch: Code

 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?



 Comments   
Comment by Ghadi Shayban [ 06/Sep/12 10:49 PM ]

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.

Comment by Ghadi Shayban [ 12/Sep/12 9:27 AM ]

Patch in proper format





[CCACHE-30] make-reference need not be dynamic Created: 09/Feb/13  Updated: 09/Feb/13

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Major
Reporter: Paul Stadig Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: None


 Description   

It looks like make-reference was made dynamic to support multiple clojure versions. Rebinding make-reference is really only needed for tests, and it would be a shame if making it dynamic causes performance issues.

Perhaps it is not enough of a performance issue to worry about. Otherwise, it might be possible to work around it. Perhaps directly pasting in and using the with-redefs macro, or something similar?






[CCACHE-28] SoftCache NullPointerException in has? with many threads Created: 24/Oct/12  Updated: 09/Feb/13

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: James Aley Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: None
Environment:

Linux, Oracle JRE 1.6


Attachments: Text File 0001-CCACHE-28-fixes-concurrency-bug-in-has.patch    
Patch: Code

 Description   

"cell" can be null on this call to SoftReference.get():
https://github.com/clojure/core.cache/blob/master/src/main/clojure/clojure/core/cache.clj#L501

If the cache did not contain "item" in the call to (get cache item) in the let binding, but another thread pre-empts and adds it before the subsequent call to contains?, we'll attempt to call .get() on nil.

Would it perhaps be sufficient to just check whether cell is nil instead of calling contains? in the check on the previous line?



 Comments   
Comment by Paul Stadig [ 09/Feb/13 6:13 AM ]

Good catch!

This is rather simple to reproduce:

(use 'clojure.core.cache)
(def cache (soft-reference-cache {}))
(def mutator (Thread. #(loop [] (assoc cache :foo :bar) (dissoc cache :foo) (recur))))
(.start mutator)
(loop [] (has? cache :foo) (recur))

The attached patch fixes the issue, by not referring back to the cache after attempting to pull out a SoftReference.





[CCACHE-31] SoftCaches update in-place, other cache types don't Created: 25/Jul/13  Updated: 25/Jul/13

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Tassilo Horn Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: None


 Description   

I've successfully used SoftCaches in my project, and now I had the need for another simple cache, so I've created a BasicCache. Thereby, I fell into the trap that while SoftCaches update in-place, BasicCaches don't (and looking at the code, all other cache types except for aforementioned SoftCache don't, too).

user> (def C (cache/soft-cache-factory {}))
#'user/C
user> (cache/miss C :a 1)
{:a #<SoftReference java.lang.ref.SoftReference@2bf31c53>}
user> C
{:a #<SoftReference java.lang.ref.SoftReference@2bf31c53>} ;; updated in-place
user> (def C (cache/basic-cache-factory {}))
#'user/C
user> (cache/miss C :a 1)
{:a 1}
user> C                                                    ;; nope, no update, still initial value
{}

So with every cache type except for SoftCaches, you have to use the return value of `miss` (and `evict`). But the documentation doesn't mention that at all. The typical has?/miss/hit snippets explaining the usage pattern also discard the value of `miss`.

IMHO, a cache is something mutable and should of course update in place. I mean, when you `(def C (some-cache...))`, are you really supposed to use `alter-var-root` or make the cache Var dynamic and use `set!`?






[CCACHE-29] Is IPersistentCollection definition of cons correct? Created: 18/Nov/12  Updated: 18/Nov/12

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Brian Marick Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: None


 Description   

Here's the definition of `cons` for caches:

clojure.lang.IPersistentCollection
(cons _# elem#
(clojure.core/cons ~base-field elem#))

This seems wrong to me. Note first that the arguments to `clojure.core/cons` are in the wrong order. As a result, the result of (for example) conj is incorrect. Consider this:

user=> (def starts-with-a (cache/fifo-cache-factory {:a 1} :threshold 3))

#'user/starts-with-a
user=> starts-with-a
{:a 1}
user=> (conj starts-with-a [:c 3])
({:a 1} :c 3)

Even if the argument order was correct, the result would still be a sequence rather than the type of the base field. I think you want something more like

clojure.lang.IPersistentCollection
(cons this# elem#
(apply assoc this# elem#))

After all, this particular collection is an IPersistentMap, so its `conj` and `into` behavior should be the same as other objects for which `map?` is true.






[CCACHE-20] Add some examples to github page Created: 08/Feb/12  Updated: 19/Feb/12

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: Juha Syrjälä Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: None


 Description   

Could you add some examples on how to use core.cache to github readme?



 Comments   
Comment by Fogus [ 19/Feb/12 6:24 PM ]

Can do. In the meantime checkout how core.memoize uses it at https://github.com/clojure/core.memoize/blob/master/src/main/clojure/clojure/core/memoize.clj#L50

I think I might bring this through fn into core.cache in a more generic way.





[CCACHE-32] LIRSCache defect allows it's memory use to grow without bound Created: 10/Oct/13  Updated: 10/Oct/13

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Jonathan Coveney Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: None


 Description   

Hello! I was messing around with the LIRSCache and ran into what I think is a bug.

https://github.com/clojure/core.cache/blob/master/src/main/clojure/clojure/core/cache.clj#L371

In the case of a bunch of misses on unique keys, then the stack S will grow without bound and violate the limit that you give it.

(def C (cache/lirs-cache-factory {} :s-history-limit 2 :q-history-limit 1))
(defn populate [n] (let [pairs (map (fn [x] [x x]) (range n))] (reduce (fn [cache [k v]] (cache/miss cache k v)) C pairs)))
(.toString (populate 10))
"{9 9, 1 1, 0 0}, {0 1, 1 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 8, 8 9, 9 10}, {9 10}, 10, 2, 1"

You can see that the S stack is growing without bound, and if you do (populate 1000), then it is 1000 pieces large.

I'm not sure what the desired outcome is, but any time we add something to one of the queues, we need to make sure that we're doing the right thing with what is kicked out, unless I'm misinterpreting things.

Thanks for making Clojure awesome!






[CCACHE-15] It appears that TTL cache exhibits quadratic performance (+ its evict is buggy) Created: 14/Dec/11  Updated: 27/May/14

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Jason Wolfe Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: None

Attachments: Text File Avoid-scanning-all-ttl-entries.patch    

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



 Comments   
Comment by Fogus [ 15/Dec/11 12:21 PM ]

TTLCache eviction fixed. Patches welcomed for the other change, but we might be able to get away with a sorted map ttl map.

Comment by Kimmo Koskinen [ 22/May/14 12:09 AM ]

Could we use a priority map (https://github.com/clojure/data.priority-map) for the ttl map and iterate it with

 (for [... :while]) 
so that we break out early?

Comment by Kimmo Koskinen [ 25/May/14 5:16 AM ]

I tried using priority-map for the ttl data and take-while instead of filter in key-killer. This would seem to help in the case where the entries in the cache are mostly fresh, since in that case we avoid iterating over all entries in ttl. We'r still in the original complexity class, but this should be an improvement still.

The change is here https://github.com/viesti/core.cache/commit/ca76508ae89ea22ce6551017403d76879805c26c, what do you think about it? I'm planning on getting to test it in our environment (~30000 cache entries, 100-200 queries per second).

Comment by Kimmo Koskinen [ 25/May/14 5:28 AM ]

Here's the change as a patch file too. Replaces filter with take-while in key-killer and uses priority-map to keep ttl data sorted.

Comment by Kimmo Koskinen [ 27/May/14 4:38 AM ]

Hmm, I made another observation. I have a scenario where I combine TTLCache with LUCache so that I keep a bounded number of items in cache and have an expiration time limit too.

The ttl structure in TTLCache isn't aware of this behaviour, so it just accumulates entries that have been evicted from the backing cache.





[CCACHE-14] Asynchronous Cache Support Created: 13/Dec/11  Updated: 13/Dec/11

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Pierre-Yves Ritschard Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: None


 Description   

If people start implementing the cache protocol on top of external caches: Memcache, Redis, or others, an async version could make sense.

I started toying with an AsyncCacheProtocol which for all functions returning values would take two arities, a standard one which would return an instance of IRef, a second one which would take an extra callback argument to be called with the results. This doesn't solve everything though and async versions of LRU and friends would have to be implemented.

The alternative would be to have additional calls in CacheProtocol, such as async-has? async-lookup which would implement the 2 arity semantics and then rely on the fact that the underlying cache respects some sort of async semantics, since we cannot do that with Associative, maybe another middleman protocol CacheStorage could be used, this way, all external cache providers would have to do is implement a CacheProvider with optional asynchronous support.

I hope at least part of this makes sense.






[CCACHE-18] Explore JSR 107- Java Temporary Caching API Created: 19/Dec/11  Updated: 19/Dec/11

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Trivial
Reporter: Fogus Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: jsr-107, research


 Description   

Is this relevant to core.cache? And many other questions answered.

<http://jcp.org/en/jsr/detail?id=107>






[CCACHE-34] Update data.priority-map dependency Created: 27/Feb/14  Updated: 20/Mar/14

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Trivial
Reporter: Ambrose Bonnaire-Sergeant Assignee: Fogus
Resolution: Unresolved Votes: 1
Labels: None

Attachments: Text File ccache-34-v1.patch    

 Description   

The current data.priority-map dependency has some unresolved reflection.

Depending on 0.0.4 fixes this.



 Comments   
Comment by Andy Fingerhut [ 20/Mar/14 6:39 PM ]

Attached patch ccache-34-v1.patch which updates the data.priority-map dependency to the latest released version 0.0.4, in both pom.xml and project.clj files.





Generated at Fri Jul 25 11:07:22 CDT 2014 using JIRA 4.4#649-r158309.