current situation, using the example of SortedSet#min (without rbtree):
SortedSet#min calls Enumerable#min
Enumerable#min calls SortedSet#each
SortedSet#each calls SortedSet#to_a
#to_a returns an Array which is guaranteed to be sorted
Enumerable#min wastefully goes through this whole Array anyway
so complexity can be reduced from O(n) to O(1) for #min/#max/#minmax.
other methods may be sped up by delegating to faster implementations on Array.
for instance, SortedSet.new(1..1000).to_a.sum is an order of magnitude faster than SortedSet.new(1..1000).sum.
suggestion:
class SortedSet < Set
# [ ... ]
# non-rbtree case
# [ ... ]
def min
to_a.first
end
def max
to_a.last
end
def minmax
[min, max]
end
def sum
to_a.sum
end
# maybe more?
end
Your recommended implementation greatly improves performance.
I fear this benchmark result "over-idealizes" the performance improvements because SortedSet#to_a is memoized here on the first run, and only cleared when set contents are changed.
Real world performance improvements should end up between 2x (at most) for a fresh or modified set (by virtue of avoiding the extra iteration mentioned in the report), and the results of this benchmark.
Updated by 
Updated by