hat-cache-miss.md

To test out the cache miss behavior of read operations, run a program building the index (30k entries) then another program building then reading the index (30k queries), and find their diff.

Here's how to generate the test script cmd.sh

3.times do |i|
  %w[triez hash da].each do |ty|
    puts "valgrind --tool=cachegrind --cachegrind-out-file=tmp/#{ty} ruby t.rb #{ty}"
    puts "valgrind --tool=cachegrind --cachegrind-out-file=tmp/#{ty}.read ruby t.rb #{ty} read"
    puts "cg_diff tmp/#{ty} tmp/#{ty}.read > tmp/#{ty}#{i}.diff"
  end
end

Here's the script (calculate-result.rb) to extract the summary from output file:

res = {}
%w[hash da triez].each do |x|
  res[x] = []
  3.times do |i|
    data = File.readlines("tmp/#{x}#{i}.diff").last.sub(/summary:/, '').strip
    data.split.each_with_index do |datum, j|
      res[x][j] ||= 0
      res[x][j] += datum.to_i
    end
  end
end

# cost of L1 cache miss is not very important, so we ignore them and calculate LL cache misses
puts "total LL cache misses"
res.each do |k, data|
  ir, i1mr, ilmr, dr, d1mr, dlmr, dw, d1mw, dlmw = data
  puts "#{k}:\t#{ilmr + dlmr + dlmw}"
end

Result (LL cache: 6291456 B, 64 B, 12-way associative):

$ zsh < cmd.sh
$ ruby calculate-result.rb
total cache misses
hash:	53458
da:	82985
triez:	29170

---

To test the cache-oblivion feature, we need to config the program with similar algorithms and different cache sizes... There are more benchmark results in the article, comparing HAT-tries with burst-tries.