native implementation of set.rb #4690

kares · 2017-06-27T10:34:42Z

work towards having Set/SortedSet natively instead of set.rb

had these changes lying around for a long-time (mostly waiting to target 9.2)
primarily this has been motivated for premium Java Integration features :
Set implements java.util.Set and SortedSet implements java.util.SortedSet

but there's also a significant gain in performance.
set.rb is rather loosely written with some ugly-ness such as patching/features-detection on SortedSet.new

for maximum compatibility sets are backed by a Hash like before (and serializes the same as before), this is important for some older versions of Sprockets when under Rails switching between MRI and JRuby.

SortedSet uses Java's TreeSet implementation for ordering as it was available and performs better than the pieces in set.rb

some (naive) performance numbers, also showcasing Set is now at Java's HashSet speed :

Ruby Set#include? hit   0.530000   0.000000   0.530000 (  0.473302)
Ruby Set#include? miss  0.450000   0.000000   0.450000 (  0.452750)
HashSet#include? hit    0.390000   0.000000   0.390000 (  0.388358)
HashSet#include? miss   0.370000   0.000000   0.370000 (  0.364610)
     Set.new([1,2,3])    1.860000   0.010000   1.870000 (  1.847379)
SortedSet.new([1,2,3])   3.560000   0.010000   3.570000 (  3.538512)
     Set#inspect         4.180000   0.000000   4.180000 (  4.157021)
SortedSet#inspect        4.160000   0.010000   4.170000 (  4.145266)
     Set#flatten         1.510000   0.000000   1.510000 (  1.504799)
     Set#each {|e| e}    1.310000   0.000000   1.310000 (  1.306374)

JRuby 9.1.9

Ruby Set#include? hit   0.660000   0.000000   0.660000 (  0.657267)
Ruby Set#include? miss  0.810000   0.000000   0.810000 (  0.811419)
HashSet#include? hit    0.430000   0.000000   0.430000 (  0.421336)
HashSet#include? miss   0.370000   0.000000   0.370000 (  0.367006)
     Set.new([1,2,3])    8.600000   0.010000   8.610000 (  8.455883)
SortedSet.new([1,2,3])  15.920000   0.020000  15.940000 ( 15.828404)
     Set#inspect         6.710000   0.000000   6.710000 (  6.633052)
SortedSet#inspect        5.730000   0.010000   5.740000 (  5.663528)
     Set#flatten         8.960000   0.000000   8.960000 (  8.879096)
     Set#each {|e| e}    1.680000   0.000000   1.680000 (  1.663696)

MRI 2.3.3

Ruby Set#include? hit   0.960000   0.000000   0.960000 (  0.957069)
Ruby Set#include? miss  1.040000   0.000000   1.040000 (  1.043396)
     Set.new([1,2,3])   20.590000   0.010000  20.600000 ( 20.606219)
SortedSet.new([1,2,3])  30.410000   0.000000  30.410000 ( 30.411511)
     Set#inspect        10.890000   0.000000  10.890000 ( 10.889514)
SortedSet#inspect       11.010000   0.000000  11.010000 ( 11.007346)
     Set#flatten        20.050000   0.000000  20.050000 ( 20.054732)
     Set#each {|e| e}    2.680000   0.000000   2.680000 (  2.686750)

kares · 2017-06-27T11:57:03Z

also to be noted that due use of Sets in Rails this has a noticeable impact on a decently sized Rails app.
... e.g. I am seeing a 15% rake test on master compared to 9.1.9.0 (probably not all due this but some).

UPDATE: compared to 9.1.12 its still seems to be a consistent 5% improvement using this branch ...

…et.rb)

... with auto (magic) toJava conversions (like RubyArray does)

... wouldn't care really but this is spec-ed by RubySpecs

(and raises an ArgumentError with a more useful message)

... relaxed the respond_to?(:<=>) expectation as it seems less important

... necessary since we use some Java internal structures its been implemented in Java, could have been done with _load/_dump although would require exposing some of the Set/SortedSet internals

... and thus MRI's (pure Ruby) set.rb implementation as well important with Rails using Sprockets at its marshalling Set instances

kares added enhancement performance stdlib labels Jun 27, 2017

kares mentioned this pull request Jun 27, 2017

SortedSet is much slower than Hash #3476

Closed

kares added this to the JRuby 9.2.0.0 milestone Jun 28, 2017

kares force-pushed the test-set-native branch from 09a504d to c69e177 Compare September 17, 2017 06:16

kares added 16 commits September 17, 2017 08:29

a well working (first) draft of rewritten native Set impl (based on s…

e12fa3c

…et.rb)

extract out Array's Comparator impls into classes (for reusability)

3bb3ae7

get native SortedSet working (using Java's TreeSet as an order backend)

7c602d9

fix Set#divide un-wrapping Array when yielded from TSort's

e0d6b6f

jruby specific .rb bits from stdlib's set.rb (pretty print only)

c40e4c4

Ruby's Set/SortedSet implements java.util.Set/java.util.SortedSet

40db09d

... with auto (magic) toJava conversions (like RubyArray does)

re-def SortedSet#sort directly - work around to_a re-def issues

9eddbb7

re-def SortedSet[] over Set's to produce RubySortedSet instances

bdcfbf0

[spec] improve SortedSet#to_a spec -> we expect sorted contents

8c5a031

SortedSet is (always) expected to process its elements ordered

007e8f3

... wouldn't care really but this is spec-ed by RubySpecs

comparator already preforms a cmp compatibility check

a6bba18

(and raises an ArgumentError with a more useful message)

[spec] SortedSet argument error on adding 'incompatible' elements

7d65e94

... relaxed the respond_to?(:<=>) expectation as it seems less important

internal refactoring in RubySet - for a clearer intent

716b781

final frontier for MRI compat - make sure marshal-ing works

325a60d

... necessary since we use some Java internal structures its been implemented in Java, could have been done with _load/_dump although would require exposing some of the Set/SortedSet internals

assure Set marshal-ing is compatible at the binary level with previous

bec2eca

... and thus MRI's (pure Ruby) set.rb implementation as well important with Rails using Sprockets at its marshalling Set instances

delegate Set#hash directly, for equals/hashCode rely on super dispatch

f9d0d0f

kares force-pushed the test-set-native branch from c69e177 to f9d0d0f Compare September 17, 2017 06:29

kares merged commit 7a6eb69 into master Sep 17, 2017

kares deleted the test-set-native branch September 17, 2017 08:09

headius mentioned this pull request Mar 28, 2018

JRuby 9.2 Projects #5119

Closed

15 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

GitHub Sponsors

native implementation of set.rb #4690

native implementation of set.rb #4690

kares commented Jun 27, 2017

kares commented Jun 27, 2017 •

edited

Loading

native implementation of set.rb #4690

native implementation of set.rb #4690

Conversation

kares commented Jun 27, 2017

kares commented Jun 27, 2017 • edited Loading

kares commented Jun 27, 2017 •

edited

Loading