chowells79 / lrucache Goto Github PK

Your LRU cache cannot store more than (maxBound :: Int) - 1 elements, as the corresponding memory requirements would exceed the range of memory that your CPU can address. Hence, you can use a size restriction of maxBound :: Int to simulate an unbounded (i.e., memory-bounded) LRU cache. However, I can see only very few use cases of a memory-bounded LRU cache, as I would normally use a LRU cache to avoid using all memory.

Therfore, I suggest changing the API to always require a size restriction of type Int and tell the user about using maxBound :: Int, if he wants a purely memory-bounded instance of the datastructure.

undefined is used in OrderedStore. If bottom is really necessary here, at least use error so users can find the source of the issue when it leaks out.

Running the following in ghci:

import Data.Cache.LRU
let l0 = newLRU (Just 2) :: LRU Int Int
let (l1, d1) = insertInforming 1 1 l0
let (l2, d2) = insertInforming 2 2 l1
let (l3, d3) = insertInforming 3 3 l2
print [(l1, d1), (l2, d2), (l3, d3)]

Results in:

[(fromList [(1,1)],Nothing),(fromList [(2,2),(1,1)],Nothing),(fromList [(3,3),(2,2)],Just (3,3))]

d3 should be Just (1, 1) rather than Just (3, 3). It seems that insertInforming is returning the input as the dropped element when the cache is full, while it is supposed to return the dropped out element. See https://github.com/chowells79/lrucache/blob/master/src/Data/Cache/LRU/Internal.hs#L146

In the case cache is not full, it is working fine.
Additionally, the IO module, do not expose an insertInforming function. I can create a PR for these changes if you are willing to merge it.

Hi chowells79,

using an LRU cache is an inherently stateful operation. In user code, often a State monad is used to provide the necessary operation ordering information. The canonical way to lift your operations to the State monad would be to use the state operation provided by Control.Monad.State (http://hackage.haskell.org/packages/archive/transformers/latest/doc/html/Control-Monad-Trans-State-Lazy.html#v:state). This requires the returned tuple to be of the form (result, new_state). Hence, I suggest changing your functions to return their results in this form.

best regards,
Simon

I'm using:

ghc-7.6.1
array-0.4.0.1
deepseq-1.3.0.1
containers-0.5.0.0
lrucache-1.1.1.1

When I execute the file:

import qualified Data.Cache.LRU.IO as Lru

main :: IO ()
main = do
    lru <- Lru.newAtomicLRU (Just 10)

    _ <- Lru.lookup "foo" lru
    _ <- Lru.lookup "bar" lru

    Lru.insert "bar" "hi" lru
    Lru.insert "foo" "hi" lru

I get

Prelude.undefined

This is quite serious since it is affecting all hakyll users on GHC 7.6.1.

@A1kmm If you have some time, could you try to reproduce this, since you also appear to be using lrucache on ghc-7.6.1 (#6).

Hi chowells79,

a friend just pointed me to your library, as he was using it as a blueprint for implementing an Adaptive replacement cache. While investigating how your code works, I may have spotted a few possible performance optimizations for the pure version of the LRU cache:

1. It seems that the Maybes for first and last in the datatype definition of LRU are used to handle the case of an empty cache. If you introduce a second constructor Empty, then you could simplify your cache definition and gain performance due to fewer indirections.
2. You might want to consider using a circular doubly linked list. This way you would require only a pointer to first and the Maybes in LinkedValue could also be dropped. The last element of the list is then the one whose next key is equal to the first key of the cache. Again, getting rid of Maybes means getting rid of indirections and, thus, realizing a performance gain.
3. You might want to consider storing the size-bound in just an Int. For an unlimited size, you would store maxBound :: Int. The reason is that you will never be able to store more than maxBound :: Int elements in your LRU cache, as this would exceed the range of memory addressable by your CPU. Again this improves performance, as indirections and code complexity is reduced.
4. You do not require the property of Maps that they keep their keys in an ordered sequence. You could therefore switch to using a persistent hashtable (analogous Johan Tibell's unordered-containers package). I do not see a way to implement it using the public API of unordered-containers. The problem is that the value you store in the underlying IntMap depends on the hash of the key. The performance gain would stem from two sources: first, fewer indirections, because the next and prev "pointers" can then be fully unpacked in the LinkedVal and, second, hashing + IntMap operations are faster than using the comparison operation on a key log-times often. See Johan's post here: http://blog.johantibell.com/2011/11/slides-from-my-guest-lecture-at.html.

Happy haskell hacking,
Simon

Is it just the same as a Data.Map in that case?