[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: [ANN] fast LRU cache in Lua
- From: Nagaev Boris <bnagaev@...>
- Date: Sun, 6 Dec 2015 18:52:52 +0300
I'm very happy to announce fast Least Recently Used (LRU)  cache
implementation in pure Lua .
Install: luarocks install lua-lru
Lua compatibility: Lua >= 5.1, LuaJIT >= 2.0
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
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)
* cache:set(key, value, [size_in_bytes])
* 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 by Yichun Zhang uses FFI.
* Lua-LRU-Cache 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
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
... too slow, waited for 10 hours
Both lua-lru and resty-lru are compiled by LuaJIT perfectly:
$ luajit -jp=v benchmark.lua lru
$ luajit -jp=v benchmark.lua lrucache
8% Garbage Collector
$ luajit -jp=v benchmark.lua pureffi
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 .