chowells79 / lrucache Goto Github PK
View Code? Open in Web Editor NEWA simple pure LRU cache written in Haskell
License: BSD 3-Clause "New" or "Revised" License
A simple pure LRU cache written in Haskell
License: BSD 3-Clause "New" or "Revised" License
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).
Is it just the same as a Data.Map
in that case?
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.
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
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.
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:
Maybe
s 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.first
and the Maybe
s 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 Maybe
s means getting rid of indirections and, thus, realizing a performance gain.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.Map
s 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
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.