[Borges-users] performance/memory

[Слепнев Владимир]

I started reading the source to Borges. I think LRUCache has an error.

   def [](key)
     val = @table[key]
     @age_table[key] = 0
     return val
   end

What if we add 20 elements to the cache, then access all of them 
(setting their age to 0), then add another 20 elements? Also, if we 
try to access a value that isn't in the cache, this will make 
@age_table grow.

Here's what I would try in this case (haven't tested):

   def [](key)
     val = @table[key]
     if(val) do
       age = @age_table(key)
       @age_table.each do |k, a|
         @age_table[k] = a + 1 if a < age
       end
       @age_table[key] = 0  
     end
     return val
   end

Though, a LRUCache with two hashes is overkill. Actually we need a 
hash to hold the key=>value pairs, and an array to remember the access 
order. Something like:

def []=(key,val)
  @table[key] = val
  @age_array << key
  @age_array.delete_at(0) if @age_array.length>= capacity
end

def [](key)
  val = @table[key]
  @age_array.delete(key)
  @age_array << key if val
end

Vladimir Slepnev