SortedSet is much slower than Hash

[Papierkorb]

Hello,

after some discussion over at #jruby, I decided to open an issue here.

A recent benchmark shows that SortedSet is much much slower than using a Hash (Mapping the set value to nil) when deleting items from it.

Full story: https://www.reddit.com/r/ruby/comments/3thkmk/doing_things_quite_fast_or_mixing_languages_or_an/

Benchmark: https://gist.github.com/Papierkorb/ab7bd6c5fdce12e3fc6c

Times from the benchmark (Taken from here)

jruby 2.2.2 java
Array
  1.270000   0.010000   1.280000 (  1.098917)
SortedSet
  1.120000   0.000000   1.120000 (  1.065251)
Hash
  0.100000   0.000000   0.100000 (  0.067120) # Roughly 16x faster

Test machine:

• Intel i5 6600K (Skylake), 4x 3.5GHz
• 16GiB DDR-4 memory @ 2666 MHz

[kares]

MRI also suffers from this problem.
did not run the benchmarks but JRuby is expected will improve considerably in 9.2 with #4690

[kares]

while I did not run the specified benchmarks I have confirmed that using Set/SortedSet (in 9.2) operations are very close to native Java collection Set/SortedSet speed.