benchmark

"SortedSet" behaves like "Array (sorted after every insert)" and "(insert in place)".

Rehearsal ---------------------------------------------------------------------
Array (unsorted)                    0.120000   0.000000   0.120000 (  0.120734)
Set (unsorted)                      0.000000   0.000000   0.000000 (  0.000302)
Array (sorted once)                 0.130000   0.000000   0.130000 (  0.121996)
Array (sorted after every insert)   0.350000   0.000000   0.350000 (  0.355280)
SortedSet                           0.120000   0.030000   0.150000 (  0.151816)
Array (insert in place)             0.090000   0.000000   0.090000 (  0.093471)
------------------------------------------------------------ total: 0.840000sec

                                        user     system      total        real
Array (unsorted)                    0.120000   0.000000   0.120000 (  0.122492)
Set (unsorted)                      0.000000   0.000000   0.000000 (  0.000327)
Array (sorted once)                 0.120000   0.000000   0.120000 (  0.122906)
Array (sorted after every insert)   0.360000   0.000000   0.360000 (  0.385497)
SortedSet                           0.000000   0.000000   0.000000 (  0.001511)
Array (insert in place)             0.090000   0.000000   0.090000 (  0.093302)

code.rb

require 'benchmark'
require 'set'

seed_data = 2000.times.map { rand(100000) }

Benchmark.bmbm do |x|
  x.report 'Array (unsorted)' do
    list = []
    seed_data.each do |element|
      list << element unless list.include? element
    end
  end

  x.report 'Set (unsorted)' do
    list = []
    seed_data.each do |element|
      list << element
    end
  end

  x.report 'Array (sorted once)' do
    list = []
    seed_data.each do |element|
      list << element unless list.include? element
    end
    list.sort!
  end

  x.report 'Array (sorted after every insert)' do
    list = []
    seed_data.each do |element|
      list << element unless list.include? element
      list.sort!
    end
  end

  x.report 'SortedSet' do
    list = SortedSet.new
    seed_data.each do |element|
      list << element
    end
  end

  x.report 'Array (insert in place)' do
    list = []
    seed_data.each do |element|
      idx = list.index { |x| x > element } || 0
      list.insert(idx, element)
    end
  end
end

Also, SortedSet will automatically use rbtree if available, not sure how big the speed up is, though.

Now that is a pleasant surprise!

The code is slightly disturbing, though, everything is in strings passed to module_eval.

Wow. That is disturbing: https://github.com/ruby/ruby/blob/trunk/lib/set.rb#L514