Re: [ANN] fast LRU cache in Lua

[Nagaev Boris <bnagaev@...>]

On Mon, Dec 7, 2015 at 8:15 AM, Shunsuke Shimizu <grafi@grafi.jp> wrote:
> 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.

Hi Shunsuke,

thank you for the idea of preallocating large array and using an index
instead of a pointer to implement a linked list. I'll try it.

> 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).

My current implementation saves GC overhead by reusing last removed
tuple instead of creating new one, when an element of a cache is
replaced. This optimization increased the speed drastically.

> 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, ...].

I'm not sure about this. All 5 elements of a tuple are likely to be
used within a short period of time. Moving one of them to another
array requires two cache lines (instead of one) to be fetched from
RAM. Although I'll try this method as well.


> 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
>>
>



-- 


Best regards,
Boris Nagaev