Benchmark showing sorted set being slower when rbtree is used. https://github.com/ruby/ruby/blob/trunk/lib/set.rb#L575

bm_sorted_set.rb

require 'set'
require 'benchmark'

begin
  require 'rbtree'
  puts "using rbtree"
  # https://github.com/ruby/ruby/blob/trunk/lib/set.rb#L575
rescue LoadError
  puts "NOT using rbtree"
end

Benchmark.bm do |b|
  s = SortedSet.new
  xs = (0..10000).to_a.shuffle

  b.report("#add") {
    xs.each {|x| s.add(x) }
  }

  xs.shuffle!
 
  b.report("#delete") {
    xs.each {|x| s.delete(x) }
  }

  (1..5).each do |n|
    n = n * 1000
    s = SortedSet.new

    n.times {|x| s << x }

    b.report("#include? #{n} items") {
      10000.times { s.include?(rand(n)) }
    }
  end

  (1..5).each do |n|
    n = n * 1000
    s = SortedSet.new

    n.times {|x| s << x }

    b.report("#to_a #{n} items") {
      10000.times { s.to_a }
    }
  end
end

gistfile1.txt

> ruby sorted_set_benchmark.rb
NOT using rbtree
       user     system      total        real
#add  0.010000   0.000000   0.010000 (  0.007889)
#delete  0.010000   0.000000   0.010000 (  0.004631)
#include? 1000 items  0.000000   0.000000   0.000000 (  0.005060)
#include? 2000 items  0.010000   0.000000   0.010000 (  0.005950)
#include? 3000 items  0.010000   0.000000   0.010000 (  0.005814)
#include? 4000 items  0.010000   0.000000   0.010000 (  0.005993)
#include? 5000 items  0.010000   0.000000   0.010000 (  0.006923)
#to_a 1000 items  0.000000   0.000000   0.000000 (  0.001863)
#to_a 2000 items  0.000000   0.000000   0.000000 (  0.002145)
#to_a 3000 items  0.000000   0.000000   0.000000 (  0.002129)
#to_a 4000 items  0.000000   0.000000   0.000000 (  0.002265)
#to_a 5000 items  0.000000   0.000000   0.000000 (  0.002428)
> ruby sorted_set_benchmark.rb
using rbtree
       user     system      total        real
#add  0.010000   0.000000   0.010000 (  0.016446)
#delete  0.020000   0.000000   0.020000 (  0.013248)
#include? 1000 items  0.010000   0.000000   0.010000 (  0.011822)
#include? 2000 items  0.020000   0.000000   0.020000 (  0.012572)
#include? 3000 items  0.020000   0.000000   0.020000 (  0.013610)
#include? 4000 items  0.020000   0.000000   0.020000 (  0.014295)
#include? 5000 items  0.010000   0.000000   0.010000 (  0.018024)
#to_a 1000 items  0.580000   0.020000   0.600000 (  0.616104)
#to_a 2000 items  1.170000   0.040000   1.210000 (  1.213406)
#to_a 3000 items  1.730000   0.030000   1.760000 (  1.773069)
#to_a 4000 items  2.370000   0.040000   2.410000 (  2.420450)
#to_a 5000 items  2.920000   0.050000   2.970000 (  2.975497)

gistfile2.txt

> ruby sorted_set_benchmark.rb
NOT using rbtree
       user     system      total        real
#add  0.010000   0.000000   0.010000 (  0.016450)
#delete  0.010000   0.000000   0.010000 (  0.010998)
#include? 1000 items  0.010000   0.000000   0.010000 (  0.014637)
#include? 2000 items  0.020000   0.000000   0.020000 (  0.013943)
#include? 3000 items  0.020000   0.000000   0.020000 (  0.017177)
#include? 4000 items  0.020000   0.000000   0.020000 (  0.014222)
#include? 5000 items  0.010000   0.000000   0.010000 (  0.015160)
#to_a 1000 items  0.010000   0.000000   0.010000 (  0.005399)
#to_a 2000 items  0.010000   0.000000   0.010000 (  0.005287)
#to_a 3000 items  0.010000   0.000000   0.010000 (  0.005435)
#to_a 4000 items  0.010000   0.000000   0.010000 (  0.006087)
#to_a 5000 items  0.000000   0.000000   0.000000 (  0.006112)

> ruby sorted_set_benchmark.rb
using rbtree
       user     system      total        real
#add  0.040000   0.000000   0.040000 (  0.041261)
#delete  0.040000   0.000000   0.040000 (  0.031458)
#include? 1000 items  0.030000   0.000000   0.030000 (  0.034940)
#include? 2000 items  0.030000   0.000000   0.030000 (  0.033690)
#include? 3000 items  0.040000   0.000000   0.040000 (  0.033940)
#include? 4000 items  0.030000   0.000000   0.030000 (  0.034908)
#include? 5000 items  0.040000   0.000000   0.040000 (  0.041071)
#to_a 1000 items  1.010000   0.020000   1.030000 (  1.036652)
#to_a 2000 items  1.980000   0.020000   2.000000 (  2.018358)
#to_a 3000 items  2.960000   0.010000   2.970000 (  2.992758)
#to_a 4000 items  3.950000   0.020000   3.970000 (  3.973521)
#to_a 5000 items  4.940000   0.050000   4.990000 (  5.052460)

> ruby -v
ruby 1.9.3p392 (2013-02-22 revision 39386) [x86_64-darwin10.8.0]

FWIW this is on OSX Darwin Kernel Version 12.5.0