Re: [ANN] fast LRU cache in Lua

[Shunsuke Shimizu <grafi@...>]

Hi Vagaev,
Great!

If you absolutely need speed and efficient memory use, I think maybe one
array having 5*N elements (N is max_size) instead of naive chained list
is better.

I mean, the data are packed in the array in following manner.
[VALUE1, PREV1, NEXT1, KEY1, BYTES1, VALUE2, PREV2, NEXT2, KEY2, BYTES2,
..., VALUEN, PREVN, NEXTN, KEYN, BYTESN]

It will be an index of the array, each of PREV, NEXT, and the value of
the hash table. The other linked list for free spaces also need to be
managed within the same array.

Such an implementation is memory efficient and can save GC costs (though
I'm not sure such a nitpick affects the performance in realistic usage).

For better alignments and memory allocation, perhaps it is slightly
better to have two arrays, the main array with 4*N elements [VALUE1,
PREV1, NEXT1, BYTES1, ...], and the other auxiliary array with N
elements [KEY1, ...].

Best, Shunsuke.

On 12/07/2015 12:52 AM, Nagaev Boris wrote:
> Hello, everyone!
> 
> I'm very happy to announce fast Least Recently Used (LRU) [1] cache
> implementation in pure Lua [2].
> 
>     Install: luarocks install lua-lru
>     License: MIT
>     Version: 1.0
>     Lua compatibility: Lua >= 5.1, LuaJIT >= 2.0
>     Homepage: https://github.com/starius/lua-lru
> 
> LRU cache is implemented using a doubly linked list and a hash map.
> Hash Map maps a key to a corresponding tuple. Doubly Linked List is
> used to store list of tuples (value, previous, next, key,
> size_in_bytes). Key is needed in a tuple to be able to remove an
> element from the hash map. Field size_in_bytes is optional and is used
> if sizes in bytes are counted (and constrained) as well as the number
> of elements.
> 
> Create an instance of LRU cache for 100 elements:
> 
>     lru = require 'lru'
>     cache = lru.new(100)
> 
> Create an instance of LRU cache for 100 elements of 1000 bytes totally:
> 
>     lru = require 'lru'
>     cache = lru.new(100, 1000)
> 
> Methods:
> 
>   * cache:set(key, value, [size_in_bytes])
>   * cache:get(key)
>   * cache:delete(key)
>   * cache:pairs() or pairs(cache) for Lua >= 5.2
> 
> Comparison with other implementations
> 
> I have found two other implementations of LRU in Lua.
> 
>   * lua-resty-lrucache[3] by Yichun Zhang uses FFI.
>   * Lua-LRU-Cache[4] by kenshin is written in pure Lua but turned out
> to be rather slow.
> 
> Both lua-resty-lrucache and Lua-LRU-Cache provide ttl for the
> elements, but do not provide size_in_bytes.
> 
> This library (lua-lru) seems to be faster than lua-resty-lrucache and
> Lua-LRU-Cache.
> 
> The benchmark runs cache:set with random keys 1kk times, alternating
> ranges [1;1000] and [1;10000] with period 5. After [1;10000] range it
> calls cache:get(key) with last key from [1;1000] range and checks
> returned value.
> 
> Results:
> 
> 
> $ ./benchmark.sh
> 
>     --------
>     lua-lru
> 
>     real    0m2.217s
>     user    0m2.204s
>     sys     0m0.008s
>     --------
>     LuaRestyLrucacheLibrary.lrucache
> 
>     real    0m5.285s
>     user    0m5.260s
>     sys     0m0.000s
>     --------
>     LuaRestyLrucacheLibrary.pureffi
> 
>     real    0m8.737s
>     user    0m8.485s
>     sys     0m0.008s
>     --------
>     LRUCache.lua
>     ... too slow, waited for 10 hours
> 
> 
> Both lua-lru and resty-lru are compiled by LuaJIT perfectly:
> 
>     $ luajit -jp=v benchmark.lua lru
>     99%  Compiled
> 
>     $ luajit -jp=v benchmark.lua lrucache
>     92%  Compiled
>     8%  Garbage Collector
> 
>     $ luajit -jp=v benchmark.lua pureffi
>     98%  Compiled
> 
> 
> Code: 153 lines
> Tests: 213 lines
> Code coverage by tests: 100% lines of code.
> 
> Disclaimer: this code was written on the way and may contain errors :)
> Please report bugs using GitHub issues [5].
> 
> 
> [1] http://www.cs.uml.edu/~jlu1/doc/codes/lruCache.html
> [2] https://github.com/starius/lua-lru
> [3] https://github.com/openresty/lua-resty-lrucache
> [4] https://github.com/kenshinx/Lua-LRU-Cache
> [5] https://github.com/starius/lua-lru/issues/new
>