[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: [ANN] fast LRU cache in Lua
- From: Nagaev Boris <bnagaev@...>
- Date: Tue, 8 Dec 2015 00:43:42 +0300
On Mon, Dec 7, 2015 at 8:15 AM, Shunsuke Shimizu <email@example.com> wrote:
> Hi Vagaev,
> 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.
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)  cache
>> implementation in pure Lua .
>> 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)
>> * 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 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
>> returned value.
>> $ ./benchmark.sh
>> real 0m2.217s
>> user 0m2.204s
>> sys 0m0.008s
>> real 0m5.285s
>> user 0m5.260s
>> sys 0m0.000s
>> real 0m8.737s
>> user 0m8.485s
>> sys 0m0.008s
>> ... 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 .
>>  http://www.cs.uml.edu/~jlu1/doc/codes/lruCache.html
>>  https://github.com/starius/lua-lru
>>  https://github.com/openresty/lua-resty-lrucache
>>  https://github.com/kenshinx/Lua-LRU-Cache
>>  https://github.com/starius/lua-lru/issues/new