[ANN] fast LRU cache in Lua

[Nagaev Boris <bnagaev@...>]

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

-- 


Best regards,
Boris Nagaev