Created
May 15, 2019 14:32
-
-
Save jpittis/c4bbf78f3d6f4fe4cfef18345de9d025 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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