fifo_hash.rb

require "pp"
require "benchmark"

# Yea. Extremely slow and prolly Linux only
def mem_sampler
  stat = GC.stat
  stat.map do |k,v|
    "#{k}\t#{v}"
  end.join("\n")
end

def gc
  GC.start(full_mark: true, immediate_sweep: true)
end

# TODO: investigate if rbtree http://www.geocities.co.jp/SiliconValley-PaloAlto/3388/rbtree/README.html
# which uses linux kernel red-black tree balancing is even faster than
# what we attempt in Ruby here.

# Since Ruby 1.9 Hashes are ordered. Based on insert actions. So since
# Ruby maintains ordering, we can implement a FiFo Hash that maintains
# a fixed number of items in its table. And when we assign a new item
# the oldest one gets deleted.
# More on Ruby (MRI) implementation of its' hashes and ordering here:
# https://www.igvita.com/2009/02/04/ruby-19-internals-ordered-hash/
class FifoHash < Hash
  MAX_ITEM_NUM = 100
  def []=(k,v)
    # Assign the new item
    ret = super(k,v)
    # Check we are now longer than the MAX_ITEM_NUM
    if keys.count > MAX_ITEM_NUM
      # Remove an item
      #
      # We use keys.first, which is probably heavy during read-intensive
      # runs. Maybe there are better ways to get the oldest item, but if so
      # I am not aware of them in the Hash API docs nor the C source.
      delete(keys.first)
    end
    ret
  end
end

n = 2_000_000
fifo_hash = FifoHash.new
ruby_hash = Hash.new

filled_fifo_hash = FifoHash.new
n.times {|i| filled_fifo_hash[i] = i }
filled_ruby_hash = Hash.new
n.times  {|i| filled_ruby_hash[i] = i }

# After assigning, trigger the GC to assert that we have no more garbage
GC.start

Benchmark.bm do |bm|
  bm.report("fifo_w") { n.times {|i| fifo_hash[i] = i } }
  bm.report("ruby_w") { n.times {|i| ruby_hash[i] = i } }
  bm.report("ffif_r") { n.times {|i| filled_fifo_hash[i] } }
  bm.report("ffrb_r") { n.times {|i| filled_ruby_hash[i] } }
end

fifo_hash = nil
ruby_hash = nil
filled_fifo_hash = nil
filled_ruby_hash = nil

# TODO: check if new.sampler returns an object that can sample
# multiple times in a single thread like we do here,
# or if it needs to be reinstated every sample.
puts "Mem prof"
puts "start: #{mem_sampler}"

# To measure as balanced as possible, define h, but set it to nil every run.
# Also call the GC before every run.
h = nil
gc
h = FifoHash.new
n.times {|i| h[i] = i }
puts "assigned fifo no GC"
puts mem_sampler

h = nil
gc
h = FifoHash.new
n.times {|i| h[i] = i }
gc
puts "assigned fifo w  GC"
puts mem_sampler

h = nil
gc
h = Hash.new
n.times {|i| h[i] = i }
puts "assigned RB   no GC"
puts mem_sampler

h = nil
gc
h = Hash.new
n.times {|i| h[i] = i }
gc
puts "assigned RB   w  GC"
puts mem_sampler

output.txt

ber@emilia:tmp ☙ ruby ./fifo_hash.rb 
       user     system      total        real
fifo_w  2.880000   0.010000   2.890000 (  2.889292)
ruby_w  0.880000   0.020000   0.900000 (  0.901890)
ffif_r  0.200000   0.000000   0.200000 (  0.200345)
ffrb_r  0.700000   0.000000   0.700000 (  0.698157)
Mem prof
start: count	472
heap_allocated_pages	74
heap_sorted_length	75
heap_allocatable_pages	0
heap_available_slots	30160
heap_live_slots	12461
heap_free_slots	17699
heap_final_slots	0
heap_marked_slots	44
heap_swept_slots	17930
heap_eden_pages	74
heap_tomb_pages	0
total_allocated_pages	74
total_freed_pages	0
total_allocated_objects	8067034
total_freed_objects	8054573
malloc_increase_bytes	29184312
malloc_increase_bytes_limit	33554432
minor_gc_count	466
major_gc_count	6
remembered_wb_unprotected_objects	0
remembered_wb_unprotected_objects_limit	370
old_objects	36
old_objects_limit	23980
oldmalloc_increase_bytes	102090072
oldmalloc_increase_bytes_limit	33438322
assigned fifo no GC
count	696
heap_allocated_pages	74
heap_sorted_length	75
heap_allocatable_pages	0
heap_available_slots	30160
heap_live_slots	29862
heap_free_slots	298
heap_final_slots	0
heap_marked_slots	12261
heap_swept_slots	8947
heap_eden_pages	74
heap_tomb_pages	0
total_allocated_pages	74
total_freed_pages	0
total_allocated_objects	12067053
total_freed_objects	12037191
malloc_increase_bytes	81040
malloc_increase_bytes_limit	16777216
minor_gc_count	689
major_gc_count	7
remembered_wb_unprotected_objects	186
remembered_wb_unprotected_objects_limit	372
old_objects	12045
old_objects_limit	24064
oldmalloc_increase_bytes	122032
oldmalloc_increase_bytes_limit	32782668
assigned fifo w  GC
count	921
heap_allocated_pages	74
heap_sorted_length	75
heap_allocatable_pages	0
heap_available_slots	30160
heap_live_slots	12261
heap_free_slots	17899
heap_final_slots	0
heap_marked_slots	12257
heap_swept_slots	17902
heap_eden_pages	74
heap_tomb_pages	0
total_allocated_pages	74
total_freed_pages	0
total_allocated_objects	16067070
total_freed_objects	16054809
malloc_increase_bytes	1104
malloc_increase_bytes_limit	16777216
minor_gc_count	912
major_gc_count	9
remembered_wb_unprotected_objects	186
remembered_wb_unprotected_objects_limit	372
old_objects	12039
old_objects_limit	24078
oldmalloc_increase_bytes	1552
oldmalloc_increase_bytes_limit	32139870
assigned RB   no GC
count	926
heap_allocated_pages	74
heap_sorted_length	75
heap_allocatable_pages	0
heap_available_slots	30160
heap_live_slots	12260
heap_free_slots	17900
heap_final_slots	0
heap_marked_slots	41
heap_swept_slots	17903
heap_eden_pages	74
heap_tomb_pages	0
total_allocated_pages	74
total_freed_pages	0
total_allocated_objects	16067185
total_freed_objects	16054925
malloc_increase_bytes	9498592
malloc_increase_bytes_limit	33554432
minor_gc_count	915
major_gc_count	11
remembered_wb_unprotected_objects	0
remembered_wb_unprotected_objects_limit	372
old_objects	31
old_objects_limit	24076
oldmalloc_increase_bytes	99425152
oldmalloc_increase_bytes_limit	44484247
assigned RB   w  GC
count	931
heap_allocated_pages	74
heap_sorted_length	75
heap_allocatable_pages	0
heap_available_slots	30160
heap_live_slots	12261
heap_free_slots	17899
heap_final_slots	0
heap_marked_slots	12257
heap_swept_slots	17902
heap_eden_pages	74
heap_tomb_pages	0
total_allocated_pages	74
total_freed_pages	0
total_allocated_objects	16067302
total_freed_objects	16055041
malloc_increase_bytes	1104
malloc_increase_bytes_limit	32883343
minor_gc_count	918
major_gc_count	13
remembered_wb_unprotected_objects	186
remembered_wb_unprotected_objects_limit	372
old_objects	12039
old_objects_limit	24078
oldmalloc_increase_bytes	83319296
oldmalloc_increase_bytes_limit	6280128