@nahi JRubyだとlock-freeな方が速いようです。このベンチマークではスレッド使ってないので単純にロックのオーバーヘッドしか効いてませんが

benchmark_parallel_fib.rb

require 'benchmark'
require 'avl_tree'
require 'red_black_tree'
require 'immutable/map'
require 'atomic'


class LockBoundFib
  def initialize(map = RedBlackTree.new)
    @memo = map
    @mutex = Mutex.new
  end

  def [](n)
    @memo[n] ||
      if n < 2
        n
      else
        self[n - 2] + self[n - 1]
      end.tap { |x|
        @mutex.synchronize {
          @memo[n] = x
        }
      }
  end
end

class LockFreeFib
  def initialize(map = Immutable::Map.empty)
    @memo = Atomic.new(map)
  end

  def [](n)
    @memo.value[n] ||
      if n < 2
        n
      else
        self[n - 2] + self[n - 1]
      end.tap { |x|
        @memo.update { |map|
          map.insert(n, x)
        }
      }
  end
end

TIMES = 5
N = 10000

Benchmark.bmbm do |bm|
  bm.report("lock-bound") do
    TIMES.times do
      lock_bound_fib = LockBoundFib.new(RedBlackTree.new)
      lock_bound_fib[N]
    end
  end
  bm.report("lock-free") do
    TIMES.times do
      lock_free_fib = LockFreeFib.new(Immutable::Map.empty)
      lock_free_fib[N]
    end
  end
end