chowells79/lrucache — Issue #2: Possible performance optimizations
Author: meiersi
Created: 2011-12-11 09:09:26+00:00
State: open

Hi chowells79,

a friend just pointed me to your library, as he was using it as a blueprint for implementing an [Adaptive replacement cache](http://en.wikipedia.org/wiki/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 `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.

2. You might want to consider using a circular doubly linked list. This way you would require only a pointer to `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.

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 `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](http://hackage.haskell.org/package/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