Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Recursion detection should use identity map, but it blows up #3887

Closed
headius opened this issue May 12, 2016 · 3 comments
Closed

Recursion detection should use identity map, but it blows up #3887

headius opened this issue May 12, 2016 · 3 comments

Comments

@headius
Copy link
Member

headius commented May 12, 2016

I believe our "execRecursive" logic (mostly ported from MRI) should be using an identity hash. This appears to be what MRI does, and it makes sense since calculating a full hash during a recursive walk could be O(something really big).

However, when I attempted to apply the following patch, recursion detection seemed to break altogether:

diff --git a/core/src/main/java/org/jruby/Ruby.java b/core/src/main/java/org/jruby/Ruby.java
index 10bcba2..d490770 100644
--- a/core/src/main/java/org/jruby/Ruby.java
+++ b/core/src/main/java/org/jruby/Ruby.java
@@ -4310,7 +4310,7 @@ public final class Ruby implements Constantizable {
             list = hash.get(sym);
         }
         if(list == null || list.isNil()) {
-            list = RubyHash.newHash(this);
+            list = RubyHash.newIdentityHash(this);
             hash.put(sym, (RubyHash)list);
         }
         return list;
diff --git a/core/src/main/java/org/jruby/RubyHash.java b/core/src/main/java/org/jruby/RubyHash.java
index 9627915..89ff9b2 100644
--- a/core/src/main/java/org/jruby/RubyHash.java
+++ b/core/src/main/java/org/jruby/RubyHash.java
@@ -223,6 +223,13 @@ public class RubyHash extends RubyObject implements Map {
         return new RubyHash(runtime, valueMap, defaultValue);
     }

+    // MRI: rb_ident_hash_new
+    public static final RubyHash newIdentityHash(Ruby runtime) {
+        RubyHash identityHash = new RubyHash(runtime);
+        identityHash.setComparedByIdentity(true);
+        return identityHash;
+    }
+
     private RubyHashEntry[] table;
     protected int size = 0;
     private int threshold;

We really need to fix this up the right way.

@headius
Copy link
Member Author

headius commented May 12, 2016

Fixed the diff to include the change in Ruby.java.

headius added a commit that referenced this issue May 14, 2016
The old recursion guard (ported from MRI years ago) had a number
of flaws:

* It forced an object ID for every object encountered.
* It created transient objects for every recursive stack.
* It was not using identity hashing (#3887).
* It used a RubyHash internally, which has much more overhead than
  a typical JDK Map.

The new implementation largely follows the pattern of the original
but fixes all the above items. It passes all untagged specs.

See also #3884, which started this whole thing.
headius added a commit that referenced this issue May 14, 2016
The old recursion guard (ported from MRI years ago) had a number
of flaws:

* It forced an object ID for every object encountered.
* It created transient objects for every recursive stack.
* It was not using identity hashing (#3887).
* It used a RubyHash internally, which has much more overhead than
  a typical JDK Map.

The new implementation largely follows the pattern of the original
but fixes all the above items. It passes all untagged specs.

See also #3884, which started this whole thing.
@headius
Copy link
Member Author

headius commented May 16, 2016

This will be done when we merge test-new-recursion to master.

headius added a commit that referenced this issue May 17, 2016
The old recursion guard (ported from MRI years ago) had a number
of flaws:

* It forced an object ID for every object encountered.
* It created transient objects for every recursive stack.
* It was not using identity hashing (#3887).
* It used a RubyHash internally, which has much more overhead than
  a typical JDK Map.

The new implementation largely follows the pattern of the original
but fixes all the above items. It passes all untagged specs.

See also #3884, which started this whole thing.
headius added a commit that referenced this issue May 18, 2016
The old recursion guard (ported from MRI years ago) had a number
of flaws:

* It forced an object ID for every object encountered.
* It created transient objects for every recursive stack.
* It was not using identity hashing (#3887).
* It used a RubyHash internally, which has much more overhead than
  a typical JDK Map.

The new implementation largely follows the pattern of the original
but fixes all the above items. It passes all untagged specs.

See also #3884, which started this whole thing.
@enebo enebo modified the milestones: JRuby 9.1.2.0, JRuby 9.1.3.0 May 23, 2016
@headius
Copy link
Member Author

headius commented Aug 22, 2016

This merged to master a while back. The new Ruby.safeRecurse API works like execRecursive, but without being a direct port from MRI. This means it doesn't use Ruby collections and it has cut out many Rubyisms that were not necessary on JRuby. It also uses an IdentityHashMap.

@headius headius closed this as completed Aug 22, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants