Skip to content

Instantly share code, notes, and snippets.

@jpittis
Created May 15, 2019 14:32
Show Gist options
  • Save jpittis/c4bbf78f3d6f4fe4cfef18345de9d025 to your computer and use it in GitHub Desktop.
Save jpittis/c4bbf78f3d6f4fe4cfef18345de9d025 to your computer and use it in GitHub Desktop.
require 'forwardable'
class LRUHash
# This LRU (Least Recently Used) hash will allow
# the cleaning of resources as time goes on.
# The goal is to remove the least recently used resources
# everytime we set a new resource. A default window of
# 5 minutes will allow empty item to stay in the hash
# for a maximum of 5 minutes
extend Forwardable
def_delegators :@table, :size, :count, :empty?, :values
attr_reader :table
MINIMUM_TIME_IN_LRU = 300
[:keys, :clear].each do |attribute|
define_method :"#{attribute}" do
@lock.synchronize { @table.public_send(attribute) }
end
end
def initialize
@table = {}
@lock = Mutex.new
end
def set(key, resource)
@lock.synchronize do
@table.delete(key)
@table[key] = resource
resource.updated_at = Time.now
end
clear_unused_resources
end
def get(key)
@lock.synchronize do
found = @table.delete(key)
if found
@table[key] = found
end
found
end
end
def delete(key)
@lock.synchronize do
@table.delete(key)
end
end
def []=(key, resource)
set(key, resource)
end
def [](key)
get(key)
end
def clear_unused_resources
return unless @lock.try_lock
# Clears resources that have not been used in the last 5 minutes.
begin
@table.each do |_, resource|
break if resource.updated_at + MINIMUM_TIME_IN_LRU > Time.now
next if resource.in_use?
resource = @table.delete(resource.name)
if resource
resource.destroy
end
end
ensure
@lock.unlock
end
end
end
require_relative 'lru'
class Resource
attr_accessor :name, :updated_at, :in_use
def initialize(name, in_use: true, updated_at: Time.now)
@name = name
@in_use = in_use
@updated_at = updated_at
end
def in_use?
@in_use
end
def destroy; end
end
# The number of measurements to perform. (Higher means lower error.)
SAMPLES = 10000
def run(n)
lru = LRUHash.new
# Load the LRU with a baseline of resources.
n.times do |i|
lru.set("#{i}", Resource.new("#{i}"))
end
# Let the updated_at time to be older than the MINIMUM_TIME_IN_LRU. This means that the
# algorithm will be forced to scan over these resources rather than quit early.
lru.table.each do |_, resource|
resource.updated_at = Time.now - (LRUHash::MINIMUM_TIME_IN_LRU * 2)
end
start = Time.now
SAMPLES.times do |i|
lru.clear_unused_resources
end
puts "clear_unused_resources: #{((Time.now - start).to_i * (10 ** 3)) / SAMPLES.to_f} ms"
end
#run(1)
#run(10)
#run(100)
#run(1000)
run(500)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment