Benchmarks comparing ruby's SortedSet implemented with and without the rbtree extension.

sorted-set-bench.out

Rehearsal ----------------------------------------------------------------------------
SortedSetRBTree#add and #first             0.040000   0.000000   0.040000 (  0.039830)
SortedSetNoRBTree#add and #first          17.180000   0.360000  17.540000 ( 17.567993)
------------------------------------------------------------------ total: 17.580000sec

                                               user     system      total        real
SortedSetRBTree#add and #first             0.050000   0.000000   0.050000 (  0.042851)
SortedSetNoRBTree#add and #first          36.200000   0.670000  36.870000 ( 36.914300)

sorted-set-bench.rb

require 'set'
require 'rbtree'

# This is stdlib SortedSet if the `require 'rbtree'` succeeds.
class SortedSetRBTree < Set
  class << self
    def [](*ary)        # :nodoc:
      new(ary)
    end
  end

  def initialize(*args)
    @hash = RBTree.new
    super
  end

  def add(o)
    o.respond_to?(:<=>) or raise ArgumentError, "value must respond to <=>"
    super
  end
  alias << add
end

# This is stdlib SortedSet if the `require 'rbtree'` fails with LoadError.
class SortedSetNoRBTree < Set
  class << self
    def [](*ary)        # :nodoc:
      new(ary)
    end
  end

  def initialize(*args)
    @keys = nil
    super
  end

  def clear
    @keys = nil
    super
  end

  def replace(enum)
    @keys = nil
    super
  end

  def add(o)
    o.respond_to?(:<=>) or raise ArgumentError, "value must respond to <=>"
    @keys = nil
    super
  end
  alias << add

  def delete(o)
    @keys = nil
    @hash.delete(o)
    self
  end

  def delete_if
    block_given? or return enum_for(__method__)
    n = @hash.size
    super
    @keys = nil if @hash.size != n
    self
  end

  def keep_if
    block_given? or return enum_for(__method__)
    n = @hash.size
    super
    @keys = nil if @hash.size != n
    self
  end

  def merge(enum)
    @keys = nil
    super
  end

  def each(&block)
    block or return enum_for(__method__)
    to_a.each(&block)
    self
  end

  def to_a
    (@keys = @hash.keys).sort! unless @keys
    @keys
  end
end

if __FILE__ == $0
  require 'benchmark'

  Benchmark.bmbm(40) do |b|
    [SortedSetRBTree, SortedSetNoRBTree].each do |set_class|
      srand 7654321
      
      s = set_class.new
      xs = (0..10000).to_a.shuffle

      b.report("#{set_class}#add and #first") {
        xs.each {|x| s.add(x); s.first }
      }
    end
  end
end